Machine Learning Chapter 15 Solutions Problems Show That The Product Xii The Number Cross Product

1

Solutions To Problems of Chapter 15

15.1. Show that in the product n

Y

i=1

(1 −xi)

the number of cross product terms, x1x2· · · xk,1≤k≤n, for all possible

15.2. Prove that if a probability distribution psatisfies the Markov condition,

as implied by a BN, then pis given as the product of the conditional dis-

tributions given the values of the parents.

P(x1|Pa1) = P(x1)

(b) Assume that it is true up to the value l−1, i.e.,

P(xl−1,· · · , x1) =

l−1

Y

P(xi|Pai)

15.3. Show that if a probability distribution factorizes according to a Bayesian

15.4. Consider a DAG and associate each node with a random variable. Define

for each node the conditional probability of the respective variable given

the values of its parents. Show that the product of the conditional prob-

abilities yield a valid joint probability and that the Markov condition is

satisfied.

x1

xl−2

xl−1

= 1

since the most right hand side summation always results in 1, due to the

ancestral ordering. Also

P(xl|Pal)P(xl−1|Pal−1)· · · P(x1|Pa1)≥0

=Pxk+1 · · · PlQl

i=1 P(xi|Pai)

Pxk· · · PlQl

i=1 P(xi|Pai):= A

B

The numerator Abecomes

15.5. Consider the graph in Figure 1. The r.v. x has two possible outcomes,

with probabilities P(x1) = 0.3 and P(x2) = 0.7. Variable y has three

possible outcomes with conditional probabilities,

P(y1|x1) = 0.3, P (y2|x1) = 0.2, P (y3|x1) = 0.5,

P(y1|x2) = 0.1, P (y2|x2) = 0.4, P (y3|x2) = 0.5.

Finally, the conditional probabilities for z are

Figure 1: Graphical Model for Problem 15.5

P(z1|y1) = 0.2, P (z2|y1) = 0.8,

P(z1|y2) = 0.2, P (z2|y2) = 0.8,

P(z1|y3) = 0.4, P (z2|y3) = 0.6.

4

Show that this probability distribution, which factorizes over the graph,

has x and z independent. However, x and z in the graph are not d–

separated, since y is not instantiated.

Solution: It must be shown that P(z|x) = P(z) for all combinations of

the values z1, z2, x1, x2. We will sketch the derivation. Let

P(x1)

=P(z1, y1, x1) + P(z1, y2, x1) + P(z1, y3, x1)

P(x1)

P(z1) = X

xX

y

P(x, y, z1) = X

xX

y

P(z1|y)P(y|x)P(x).

15.6. Consider the DAG in Figure 2. Detect the d–separations and d–connections

in the graph.

x2). Then it passes via x5to x7(converging node but the descendant of x5

is instantiated). Then to x8and x9(serial unblocked connection). Recall

15.7. Consider the DAG of Figure 3. Detect the blanket of node x5and verify

that if all the nodes in the blanket are instantiated, then the node becomes

d–separated from the rest of the nodes in the graph.

Solution: The blanket of x5comprises the nodes x1,x2, x8,x9(children)

and x4,x6(share children with x5). Check that any chain that connects x5

with any node outside the blanket, once nodes in the blanket have been

instantiated, is blocked.

15.8. In a linear Gaussian Bayesian network model, derive the mean values and

the respective covariance matrices for each one of the variables in a recur-

sive manner

Solution: Since

P(xi|Pai) = N xiX

θik xk+θi0, σ2

i!,

k:xk∈pai

where niis a white (zero-mean) noise Gaussian source. Having adopted

ancestral ordering and considering, say, xi, we are certain that xiis not

involved in any one of the parent sets, Pa1,Pa2,· · · ,Pai−1. We will derive

the covariances inductively.

k:xk∈Pai

E“(xj−E[xj])( X

k:xk∈Pai

θik(xk−E[xk]) + σini)#=

X

k:xk∈Pai

θikE [(xj−E[xj])(xk−E[xk])] + 0, i 6=j,

and finally

15.9. Assuming the variables associated with the nodes of the Bayesian structure

of Figure 4 to be Gaussian, find the respective mean values and covari-

ances.

7

Solution: Following the recursive manner of computation, as suggested

1θ2

21σ2

1+σ2

2θ32 $θ2

21σ2

1+σ2

2

θ32θ21σ2

1θ32 $θ2

21σ2

1+σ2

2θ2

32 $θ2

21σ2

1+σ2

2+σ2

3

15.10. Prove that if pis a Gibbs distribution that factorizes over a MRF H, then

His an I-map for p.

Solution: Let X,Y,Zbe any three disjoint sets such as Zseparates X

and Y. Then we will show that for any x ∈Xand y ∈Y, x ⊥y|Z.

Let us start by assuming that X∪Y∪Z=X, where Xis the set of all

points. Thus, any clique in Hwill be contained either in X∪Zor Y∪Z,

15.11. Show that if His the moral graph that results from moralization of a BN

structure then

I(H)⊆I(G)

15.12. Consider a Bayesian network structure and a probability distribution p.

Then show that if I(G)⊆I(p), then pfactorizes over G.

G.

15.13. Show that in a undirected chain graphical model, the marginal probability

P(xj) of a node, xj, is given by

P(xj) = 1

Zµf(xj)µb(xj),

15.14. Show that the joint distribution of two neighboring nodes in a undirected

chain graphical model is given by

P(xj, xj+1) = 1

Zµf(xj)ψj,j+1 (xj, xj+1)µb(xj+1).

Solution: Following the same steps as for the problem 15.13, we have

P(xj, xj+1) = 1

ZX

x1

· · · X

xj−1X

xj+2

· · · X

xl

l−1

Y

i=1

ψi,i+1(xi, xi+1)

j−1

15.15. Using Figure 15.26, prove that if there is a second message passing, start-

ing from x, towards the leaves, then any node will have the available

information for the computation of the respective marginals.

Solution: Let us consider node x4. The proof is similar for all the other

nodes. In order to compute P(x4), we need µfd→x4(x4), µfe→x4(x4)

15.16. Consider the tree graph of Figure 15.26. Compute the marginal probabil-

ity P(x1, x2, x3, x4).

Solution: Let VA′be all the nodes of VAexcluding x2,x3and x4. Then

following similar reasoning as for (15.46)

P(x1, x2, x3, x4) = 1

ZX

ΨA(x1, x2, x3, x4,xA′)·

15.17. Repeat the message procedure to find the optimal combination of vari-

ables for Example 15.4 using the logarithmic version and the max–sum

algorithm