CS6375 Homework VII solution

Description

1. A graph with no links is a trivial D-Map. True/False [5 Points]
2. Consider the Bayesian network given below [5 Points]
a. Is A conditionally independent of D give {B,C}.
b. Is E marginally independent of F
c. Which edge would you delete to make A independent of C.
3. Evaluate the distribution p(a), p(b|c) and p(c|a) corresponding to the joint distribution given in
the Table. Hence show by direct evaluation that p(a,b,c) = p(a) p(c|a) p(b|c). Draw the
corresponding directed graph. [10 Points]
a b c p(a, b, c)
0 0 0 0.192
0 0 1 0.144
0 1 0 0.048
0 1 1 0.216
1 0 0 0.192
1 0 1 0.064
1 1 0 0.048
1 1 1 0.096
4. Consider the directed graphical model in following figure with 4 binary variables.
[10 Points]
a. Write down the expression for P(S=1|V=1) in terms of α, β, ϒ, 𝝏𝝏.
b. Write down the expression for P(S=1|V=0) . Is it the same or different to P(S=1|V=1? Explain why.
c. Find the maximum likelihood estimate of α, β, ϒ using the following dataset, where each row is a
training case.
V G R S
1 1 1 1
1 1 0 1
1 0 0 0
5. Hidden variables in DGMs: [10 Points]
a. Consider the following graphical model, where we number nodes left to right, top to bottom.
The graph defines the joint as
𝑃𝑃(𝑋𝑋1,𝑋𝑋2, 𝑋𝑋3,𝑋𝑋4, 𝑋𝑋5, 𝑋𝑋6)
= �𝑃𝑃(𝑋𝑋1)𝑃𝑃(𝑋𝑋2)𝑃𝑃(𝑋𝑋3)𝑝𝑝(𝐻𝐻 = ℎ|𝑋𝑋1𝑋𝑋2𝑋𝑋3)𝑃𝑃(𝑋𝑋4|𝐻𝐻 = ℎ)𝑃𝑃(𝑋𝑋5|𝐻𝐻 = ℎ)𝑃𝑃(𝑋𝑋6|𝐻𝐻 = ℎ)
ℎ
where we have marginalized over the hidden variable H.
Assuming all nodes are binary, how many parameters does this model have?
b. Consider the following graph and its joint distribution ( again we number nodes from left to right
and from top to bottom)
𝑃𝑃(𝑋𝑋1,𝑋𝑋2, 𝑋𝑋3,𝑋𝑋4, 𝑋𝑋5,𝑋𝑋6)
= 𝑃𝑃(𝑋𝑋1)𝑃𝑃(𝑋𝑋2)𝑃𝑃(𝑋𝑋3) 𝑃𝑃(𝑋𝑋4|𝑋𝑋1, 𝑋𝑋2,𝑋𝑋3)𝑃𝑃(𝑋𝑋5|𝑋𝑋1, 𝑋𝑋2,𝑋𝑋3, 𝑋𝑋4)𝑃𝑃(𝑋𝑋6|𝑋𝑋1,𝑋𝑋2, 𝑋𝑋3, 𝑋𝑋4,𝑋𝑋5)
Assuming all nodes are binary, how many parameters does this model have?
6. What is the complexity of computing 𝑃𝑃(𝐸𝐸 = 𝑒𝑒) using variable elimination in the following
Bayesian network along the ordering (𝐴𝐴, 𝐵𝐵, 𝐶𝐶,𝐷𝐷) The edges in the Bayesian network are 𝐴𝐴 →
𝐵𝐵, 𝐴𝐴 → 𝐶𝐶, 𝐵𝐵 → 𝐶𝐶, 𝐶𝐶 → 𝐷𝐷 𝑎𝑎𝑎𝑎𝑎𝑎 𝐷𝐷 → 𝐸𝐸. [5 Points]
7. What is the complexity of computing 𝑃𝑃(𝐸𝐸 = 𝑒𝑒) using variable elimination in the following
Bayesian network along the ordering (𝐵𝐵, 𝐶𝐶,𝐷𝐷, 𝐴𝐴). The edges in the Bayesian network are 𝐴𝐴 →
𝐵𝐵, 𝐵𝐵 → 𝐶𝐶, 𝐶𝐶 → 𝐷𝐷 𝑎𝑎𝑎𝑎𝑎𝑎 𝐷𝐷 → 𝐸𝐸. [5 Points]