Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
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 xiX
θ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
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
