Graphical Models¶
Figure 10.13 is a nice illustration of contrastive divergence.
Exercise 10.1¶
\[\begin{split}\DeclareMathOperator{\MarkovBlanket}{MB}
(x_1)\\
(x_3)\\
(x_7)\\
(x_1) \rightarrow (x_2)\\
(x_3) \rightarrow (x_2)\\
(x_7) \rightarrow (x_5)\\
(x_2) \rightarrow (x_5)\\
(x_2) \rightarrow (x_4)\\
(x_5) \rightarrow (x_6)\\
(x_4) \rightarrow (x_6)\end{split}\]
The Markov blanket for \(x_2\) is \(\MarkovBlanket(x_2) = \{ x_1, x_3, x_5, x_4, x_7 \}\).
Exercise 10.2¶
\[\begin{split}\begin{multline}
Pr(x_1, \ldots, x_{15}) =
Pr(x_1) Pr(x_2) Pr(x_3) Pr(x_4 \mid x_1, x_2) Pr(x_5 \mid x_2, x_3)
Pr(x_6) Pr(x_7) Pr(x_8 \mid x_4, x_5) Pr(x_9 \mid x_3, x_5, x_6)\\
Pr(x_{10} \mid x_7) Pr(x_{11} \mid x_8, x_{10}) Pr(x_{12} \mid x_8, x_9)
Pr(x_{13} \mid x_9) Pr(x_{14} \mid x_{11}) Pr(x_{15} \mid x_{12})
\end{multline}\end{split}\]
Exercise 10.3¶
\[\begin{split}(x_1) \leftrightarrow (x_2) \leftrightarrow (x_5)\\
(x_2) \leftrightarrow (x_3) \leftrightarrow (x_4)\\
(x_1) \leftrightarrow (x_5)\\
(x_5) \leftrightarrow (x_6)\end{split}\]
Exercise 10.4¶
\[\begin{split}\mathcal{S}_1 &= \{ x_1, x_4 \}\\
\mathcal{S}_2 &= \{ x_2, x_4, x_8 \}\\
\mathcal{S}_3 &= \{ x_2, x_5, x_8 \}\\
\mathcal{S}_4 &= \{ x_3 \}\\
\mathcal{S}_5 &= \{ x_6, x_9 \}\\
\mathcal{S}_6 &= \{ x_7, x_{10} \}\\
\mathcal{S}_7 &= \{ x_7, x_{11} \}\\
\mathcal{S}_8 &= \{ x_8, x_{11} \}\\
\mathcal{S}_9 &= \{ x_8, x_{12} \}\\
\mathcal{S}_{10} &= \{ x_9, x_{12}, x_{13}, x_{15} \}\\
\mathcal{S}_{11} &= \{ x_{11}, x_{14} \}\end{split}\]
Exercise 10.5¶
[1]:
from itertools import product
def phi(i, j):
_ = {};
_[(0, 0)] = 1.0
_[(0, 1)] = 0.1
_[(1, 0)] = 0.1
_[(1, 1)] = 2.0
return _[(i, j)]
Z = 0.0
P = {}
for x_1, x_2, x_3, x_4 in product([0, 1], [0, 1], [0, 1], [0, 1]):
PI = phi(x_1, x_2) * phi(x_2, x_3) * phi(x_3, x_4) * phi(x_4, x_1)
P[(x_1, x_2, x_3, x_4)] = PI
Z += PI
_ = 'Pr(x_1 = {}, x_2 = {}, x_3 = {}, x_4 = {}) = {:.5f}'
for k, v in P.items():
print(_.format(*k, v / Z))
Pr(x_1 = 0, x_2 = 0, x_3 = 0, x_4 = 0) = 0.05787
Pr(x_1 = 0, x_2 = 0, x_3 = 0, x_4 = 1) = 0.00058
Pr(x_1 = 0, x_2 = 0, x_3 = 1, x_4 = 0) = 0.00058
Pr(x_1 = 0, x_2 = 0, x_3 = 1, x_4 = 1) = 0.00116
Pr(x_1 = 0, x_2 = 1, x_3 = 0, x_4 = 0) = 0.00058
Pr(x_1 = 0, x_2 = 1, x_3 = 0, x_4 = 1) = 0.00001
Pr(x_1 = 0, x_2 = 1, x_3 = 1, x_4 = 0) = 0.00116
Pr(x_1 = 0, x_2 = 1, x_3 = 1, x_4 = 1) = 0.00231
Pr(x_1 = 1, x_2 = 0, x_3 = 0, x_4 = 0) = 0.00058
Pr(x_1 = 1, x_2 = 0, x_3 = 0, x_4 = 1) = 0.00116
Pr(x_1 = 1, x_2 = 0, x_3 = 1, x_4 = 0) = 0.00001
Pr(x_1 = 1, x_2 = 0, x_3 = 1, x_4 = 1) = 0.00231
Pr(x_1 = 1, x_2 = 1, x_3 = 0, x_4 = 0) = 0.00116
Pr(x_1 = 1, x_2 = 1, x_3 = 0, x_4 = 1) = 0.00231
Pr(x_1 = 1, x_2 = 1, x_3 = 1, x_4 = 0) = 0.00231
Pr(x_1 = 1, x_2 = 1, x_3 = 1, x_4 = 1) = 0.92592
Exercise 10.6¶
Figure 10.7a¶
\[\begin{split}\MarkovBlanket(x_1) &= \{ x_3 \}\\
\MarkovBlanket(x_2) &= \{ x_3 \}\\
\MarkovBlanket(x_3) &= \{ x_1, x_2 \}\end{split}\]
Figure 10.7b¶
\[\begin{split}\MarkovBlanket(x_1) &= \{ x_3 \}\\
\MarkovBlanket(x_2) &= \{ x_3 \}\\
\MarkovBlanket(x_3) &= \{ x_1, x_2 \}\end{split}\]
Figure 10.7c¶
\[\begin{split}\MarkovBlanket(x_1) &= \{ x_3, x_2 \}\\
\MarkovBlanket(x_2) &= \{ x_3, x_1 \}\\
\MarkovBlanket(x_3) &= \{ x_1, x_2 \}\end{split}\]
Figure 10.8a¶
\[\begin{split}\MarkovBlanket(x_1) &= \{ x_2, x_3 \}\\
\MarkovBlanket(x_2) &= \{ x_1, x_4 \}\\
\MarkovBlanket(x_3) &= \{ x_1, x_4 \}\\
\MarkovBlanket(x_4) &= \{ x_2, x_3 \}\end{split}\]
Figure 10.8b¶
\[\begin{split}\MarkovBlanket(x_1) &= \{ x_2, x_3 \}\\
\MarkovBlanket(x_2) &= \{ x_1, x_4, x_3 \}\\
\MarkovBlanket(x_3) &= \{ x_1, x_4, x_2 \}\\
\MarkovBlanket(x_4) &= \{ x_2, x_3 \}\end{split}\]
Exercise 10.7¶
Figure 10.7a¶
\[\begin{split}Pr(x_2 \mid x_1, x_3)
&= \frac{Pr(x_1, x_2, x_3)}{\int Pr(x_2, x_1, x_3) dx_2}
& \quad & \text{Bayes' rule}\\
&= \frac{
Pr(x_1) Pr(x_3 \mid x_1) Pr(x_2 \mid x_3)
}{
\int Pr(x_1) Pr(x_3 \mid x_1) Pr(x_2 \mid x_3) dx_2
}
& \quad & \text{factorization of graphical model}\\
&= Pr(x_2 \mid x_3)\end{split}\]
Figure 10.7b¶
\[\begin{split}Pr(x_2 \mid x_1, x_3)
&= \frac{Pr(x_1, x_2, x_3)}{\int Pr(x_2, x_1, x_3) dx_2}
& \quad & \text{Bayes' rule}\\
&= \frac{
Z^{-1} \phi_1[x_1, x_3] \phi_2[x_2, x_3]
}{
\int Z^{-1} \phi_1[x_1, x_3] \phi_2[x_2, x_3] dx_2
}
& \quad & \text{factorization of graphical model}\\
&= \frac{\phi_2[x_2, x_3]}{\int \phi_2[x_2, x_3] dx_2}\end{split}\]
Figure 10.7c¶
\[\begin{split}Pr(x_2 \mid x_1)
&= \frac{Pr(x_1, x_2)}{\int Pr(x_2, x_1) dx_2}
& \quad & \text{Bayes' rule}\\
&= \frac{
Pr(x_1) Pr(x_2)
}{
\int Pr(x_1) Pr(x_2) dx_2
}
& \quad & \text{factorization of graphical model}\\
&= Pr(x_2)\end{split}\]
Figure 10.8a¶
The factorization of this undirected graphical model is
\[Pr(x_1, x_2, x_3, x_4) =
\frac{1}{Z} \phi_1[x_1, x_2] \phi_2[x_1, x_3]
\phi_3[x_2, x_4] \phi_4[x_3, x_4]\]
where
\[\begin{split}Pr(x_1 \mid x_2, x_3, x_4)
&= \frac{Pr(x_1, x_2, x_3, x_4)}{\int Pr(x_1, x_2, x_3, x_4) dx_1}
& \quad & \text{Bayes' rule}\\
&= \frac{
\phi_1[x_1, x_2] \phi_2[x_1, x_3]
}{
\int \phi_1[x_1, x_2] \phi_2[x_1, x_3] dx_1
}\end{split}\]
and
\[\begin{split}Pr(x_2 \mid x_1, x_3, x_4)
&= \frac{Pr(x_1, x_2, x_3, x_4)}{\int Pr(x_2, x_1, x_3, x_4) dx_2}
& \quad & \text{Bayes' rule}\\
&= \frac{
\phi_1[x_1, x_2] \phi_3[x_2, x_4]
}{
\int \phi_1[x_1, x_2] \phi_3[x_2, x_4] dx_2
}.\end{split}\]
Figure 10.8b¶
The factorization of this directed graphical model is
\[Pr(x_1, x_2, x_3, x_4) =
Pr(x_1) Pr(x_2 \mid x_1) Pr(x_3 \mid x_1) Pr(x_4 \mid x_2, x_3)\]
where
\[\begin{split}Pr(x_1, x_2, x_3)
&= \int Pr(x_1, x_2, x_3, x_4) dx_4\\
&= \int Pr(x_1) Pr(x_2 \mid x_1)
Pr(x_3 \mid x_1) Pr(x_4 \mid x_2, x_3) dx_4\\
&= Pr(x_1) Pr(x_2 \mid x_1) Pr(x_3 \mid x_1),\end{split}\]
\[\begin{split}Pr(x_1 \mid x_2, x_3, x_4)
&= \frac{Pr(x_1, x_2, x_3, x_4)}{\int Pr(x_1, x_2, x_3, x_4) dx_1}
& \quad & \text{Bayes' rule}\\
&= \frac{
Pr(x_1) Pr(x_2 \mid x_1) Pr(x_3 \mid x_1)
}{
\int Pr(x_1) Pr(x_2 \mid x_1) Pr(x_3 \mid x_1) dx_1
}\\
&= \frac{
Pr(x_1, x_2, x_3)
}{
Pr(x_2, x_3)
}\\
&= Pr(x_1 \mid x_2, x_3),\end{split}\]
and
\[\begin{split}Pr(x_2 \mid x_1, x_3)
&= \frac{Pr(x_1, x_2, x_3)}{\int Pr(x_2, x_1, x_3) dx_2}
& \quad & \text{Bayes' rule}\\
&= \frac{Pr(x_2 \mid x_1)}{\int Pr(x_2 \mid x_1) dx_2}\\
&= Pr(x_2 \mid x_1).\end{split}\]
Exercise 10.8¶
Figure 10.7a¶
\[\begin{split}(x_1) -[A]- (x_3)\\
(x_2) -[B]- (x_3)\end{split}\]
Figure 10.7b¶
\[\begin{split}(x_1) -[A]- (x_3)\\
(x_2) -[B]- (x_3)\end{split}\]
Figure 10.7c¶
\[\begin{split}(x_1) -[A]-\\
(x_2) -[A]-\\
(x_3) -[A]-\end{split}\]
Figure 10.8a¶
\[\begin{split}(x_1) -[A]- (x_2)\\
(x_1) -[B]- (x_3)\\
(x_2) -[C]- (x_4)\\
(x_3) -[D]- (x_4)\end{split}\]
Figure 10.8b¶
\[\begin{split}(x_1) -[A]- (x_2)\\
(x_1) -[B]- (x_3)\\
(x_2) -[C]-\\
(x_3) -[C]-\\
(x_4) -[C]-\end{split}\]
Exercise 10.9¶
\[\MarkovBlanket(w_2) = \{ w_1, w_5, w_4 \}\]
Exercise 10.10¶
\[\MarkovBlanket(w_8) = \{ w_5, w_7, w_9, w_{11} \}\]