Artificial Intelligence and Machine Learning Mock Examination

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

School of Computer Science

Artificial Intelligence and Machine Learning

Mock Examination

Note

Answer ALL questions.  Each question will be marked out of 20.  The paper will be marked out of 60, which will be rescaled to a mark out of 100 .

Question 1

Figure 1:  Directed acyclic graph (DAG) for Q1 .

This question relates to the combinatorial (optimization) problem of finding all topological orderings of a given directed acyclic graph (DAG) with N vertices.

(a) What  is the worst-case size of the  configuration space  X  for this  combinatorial problem, in terms of N? Justify your answer. [2 marks]

(b)  A DAG with no edges is said to be disconnected. Assume the DAG in Figure 1 is disconnected.  How many possible topological orderings of the nodes are there? Justify your solution. [3 marks]

(c) You  must  solve the  problem  of devising an  efficient algorithm for computing all topological orderings of the DAG in Figure 1 .

(i)  Give the steps in an exhaustive SDP algorithm for solving this problem. [5 marks]

(ii)  Use this SDP algorithm to compute the set of all possible topological orderings of this DAG. [6 marks]

(d)  Now, assume the DAG in Figure 1 represents a probabilistic graphical model (PGM) over the random variables X,Y,Z,U and V .

(i)  Using the topological ordering [X,U,Y,V, Z] give the corresponding chain fac- torization of the joint distribution P (X,Y,Z,U, V) . [2 marks]

(ii)  Using your chain factorization in (d)(i) above, remove all redundant dependen- cies from the conditional distributions, to give the Markov factorization of the joint distribution. [2 marks]

Question 2

Figure 2: Task schedule chart for Q2 .

(a)  This question relates to dynamic programming as a method for combinatorial opti- mization.

(i)  Explain the principle of optimality. [2 marks]

(ii)  Explain  how the principle of optimality reduces the computational complexity of an exact algorithm for solving an optimization problem. [3 marks]

(iii)  Explain the concept of memoization. [3 marks]

(b)  Consider the planning problem of automatically selecting the best subset of a set of tasks to complete.  Each of the N = 6 tasks is associated with a value, from the list v = [20 , 7, 4, 3, 10, 8]. The optimal subset has the largest sum of values.  Each task begins and ends at the times given in the schedule chart above (Figure 3) .  Tasks can only be selected together if they do not overlap.  The list p = [0 , 0, 0, 1, 3, 1] gives the largest task index n′ < n such that task n′ does not overlap with task n.

(i)  Use the following Bellman recursion to compute the total value of the optimal subset of tasks, : [8 marks]

(ii) What is the time complexity of this recursion?  Justify your answer. [2 marks]

(iii) What is the worst case time complexity of the exhaustive solution to this prob- lem in general (that is, independent of the specific task values and start/end times)? Justify your answer. [2 marks]

Question 3

Figure 3:  Deep neural networks for Q3 .

(a)  For the deep neural network of Figure 2(a) (autoencoder) above with softplus acti- vation nonlinearities, write down the formulae for the hidden nodes z1 , z2  and the output nodes y1 , y2 , y3 . [6 marks]

(b)  The formulae for the deep network of Figure 2(b) are given in matrix form as,

z = max（0,WTx), a = max（0,VTz), y = max（0, UTa)

with weights

(i)  For  inputs with value x =  [ 3   2 ]T ,  compute the values of the first  hidden  layer z. [4 marks]

(ii)  Given that the values of the second hidden layer are a =  [ 0.75   0  ]T , compute the value of the output y. [4 marks]

(c)  Using dual numbers for automatic differentiation, derive two dual number formulae: one for y paired with yu1     (its derivative with  respect to the weight  u1 )  and  the other for y paired with yu2    (derivative with respect to weight u2 ) .  Both expressions should be in terms of the hidden outputs a and parameters U.  Show your working. [6 marks]