1. The adjacency matrix representation of a graph G is

╱! 1  、|

!(!) 2  1   0   0   1   0   0   0   0   

!(!) 3  1   0   0   1   1   1   0   0   

A =  !(!) 4  0   1   1   0   0   0   0   0    .                                 (1)

!(!) 5  0   0   1   0   0   0   0   0   

!(!) 6  0   0   1   0   0   0   1   1   

! 7   0   0   0   0   0   1   0   1   |

(a) Plot the graph G using its adjacency matrix A shown in Equation 1. Write down

the edge list representation of G.                                                       [4 MARKS]

(b) What is the order and size of G given by Equation 1?  Is G connected?  Is G a

directed graph?                                                                                   [4 MARKS]

(c) Provide the geodesic distance and the shortest path of node 6 from every other node in G, justifying your answer.                                                      [3 MARKS]

(d) Derive the normalized betweenness centrality of node 6 and node 5 of graph G.

[6 MARKS]

(e) Derive the density of graph G. Interpret the computed density by comparing G to

its corresponding null or complete graph.  Which aspect of the adjacency matrix A of G, given by Equation 1, provide a first indication of the magnitude of the

density of G before computing this density?                                      [3 MARKS]

2. Let y e R50  be a binary response variable such that yi  e {0, 1} for i e {1, 2, ..., 50}, X an 50 × 2 design matrix, 9 e R2  a vector of parameters and ∈ e R50  noise. 50 and 2 are the number of data points and number of parameters, respectively.  Moreover, to ease notation, let 北i(T)  e R2  be the i-th row of the design matrix X .

It is assumed that yi   e  {0, 1}, i e  {1, 2, ..., 50}, are independently and identically distributed. Each observed output yi  is drawn from a Bernoulli distribution

yi  ~ Bernoulli(πi ) := πi(y)i (1 _ πi )1_yi ,

where the probability πi  that the i-th observation is equal to 1 is given by the logistic

function

πi  = P (yi  = 1I北i , 9) =             1           

(a) Write down the likelihood function c(yIX, 9), which is the conditional probability distribution function of observing the n dimensional output yT  = (y1 , y2 , ..., y50 ) given the design matrix X and the parameters 9T  = (θ1 , θ2 ).  The expression of

the likelihood should be left in terms of the πi .                                 [2 MARKS]

(b) Derive the cost function  J(9)  :=  _ ln c(yIX, 9) for logistic regression,  which

is defined as the negative log-likelihood, using the expression for the likelihood

c(yIX, 9) found by answering Question 2(a).                                    [3 MARKS]

(c) Derive the partial derivative ∂J (9)/∂πi  of the cost function J(9) with respect to

πi , where i e {1, 2, ..., 50}.

(d) Derive the partial derivative ∂πi /∂θj , where j e {1, 2}.

[4 MARKS]

[4 MARKS]

(e) Derive the partial derivative ∂J (9)/∂θj  of the cost function J(9) with respect to

parameter θj , where j e {1, 2}.                                                          [4 MARKS]

(f) Use the partial derivative ∂J (9)/∂θj   to state the sequential updating step for

gradient descent applied on the cost function J(9) for logistic regression; express the approximation θ1(k)+1  and θ2(k)+1  at step k + 1 of gradient descent, given θ1(k)  and θ2(k)  at step k .  What are the impacts of the learning rate on the gradient descent algorithm?                                                                                           [6 MARKS]

3. Figure 1 shows a Bayesian network for three potential diseases, pneumonia (N), tuber- culosis (T) and calcification pulmonum(C). Either of pneumonia (N) and tuberculosis (T) may cause a patient to have lung infiltrates (I). The lung infiltrates may show up on an x-ray (X). Calcification pulmonum(C) can also be detected by x-ray (X). There is a separate sputum smear test (S) for tuberculosis. All of the random variables are binary taking values in 0, 1.  A value of 1 indicates presence of disease in the case of N, T and C, presence of symptom in the case of I, and a positive diagnosis in the case of X and S. A value of 0 indicates absence of disease, absence of symptom or negative diagnosis. 

Figure 1:  Bayesian network for pneumonia (N), tuberculosis (T) and calcification pul- monum(C)

(a) What are Par(I), CoPar(I) and Ch(I), where Par, CoPar and Ch denote the par-

ents, co-parents and children of I?

[3 MARKS]

(b) Which are the local Markov assumptions induced by the Bayesian network of

Figure 1?

[3 MARKS]

(c) What is the factorization of the joint distribution P(X,S,I,N,T,C) of the Bayesian network described by Figure 1?                                                          [3 MARKS]

(d) What is the Markov Blanket of I? Show that the full conditional distribution fraction of I is proportional to

p(IIV/{I}) x p(IIPar(I))   ù   p(νII, CoPar(I)).

νeCh(I)