はじめに
PRML解答例まとめを参照
演習 8.1
変数を1つずつ周辺化することによって，有向グラフの同時分布の表現
p(\mathbf{x})=\prod_{k=1}^{K} p\left(x_{k} \mid \mathrm{pa}_{k}\right) \tag{8.5}
が正しく規格化されていることを示せ．ただし個々の条件付き分布は正しく規格化されていると仮定する．
\int p(\mathbf{x}) d\mathbf{x} = 1であることを示せばよい。
\begin{aligned} \int p(\mathbf{x}) d \mathbf{x} &=\int \prod_{k=1}^{K} p\left(x_{k} \mid \mathbf{p a}_{k}\right) d \mathbf{x} \\ &=\int \cdots \int p\left(x_{K} \mid \mathbf{p a}_{K}\right) \prod_{k=1}^{K-1} p\left(x_{k} \mid \mathbf{p} \mathbf{a}_{k}\right) d x_{1} x_{2} \cdots x_{K} \\ &=\int \cdots \int\left[\prod_{k=1}^{K-1} p\left(x_{k} \mid \mathbf{p} \mathbf{a}_{k}\right) \int p\left(x_{K} \mid \mathbf{p a}_{K}\right) d x_{K}\right] d x_{1} x_{2} \cdots x_{K-1} \\ &=\int \cdots \int \prod_{k=1}^{K-1} p\left(x_{k} \mid \mathbf{p} \mathbf{a}_{k}\right) d x_{1} x_{2} \cdots x_{K-1} \\ &=\cdots \\ &=1 \end{aligned}
演習 8.2
有向グラフにおいて，すべてのノードについて，自分より小さい番号を持つノードに向かうリンクが存在しないようにノードを順序付けることができるなら，有向閉路は存在しないことを示せ．
N個の変数x_1, x_2, \cdots x_Nを仮定する。題意より
\begin{aligned}
x_1 \rightarrow \cdots \rightarrow x_N
\end{aligned}
となる経路は存在しうるが、
\begin{aligned}
x_N \rightarrow \cdots \rightarrow x_1
\end{aligned}
となる経路は存在しないため、有向閉路は存在しない。
演習 8.3
表8.2で与えられる同時分布を持つ3つの2値変数a,b,c \in \{0, 1\}を考える．この分布が以下の特性を持つことを直接計算によって示せ．aおよびbは周辺依存である．すなわちp(a, b) \neq p(a)p(b)．しかしcで条件付けられると独立である．すなわちc=0およびc=1のいずれの場合でもp(a, b \mid c) = p(a\mid c)p(b\mid c)である．
各確率を周辺化することで地道に求めていく。
\begin{aligned}
p(a)&=\sum_{b \in\{0,1\}} \sum_{c \in\{0,1\}} p(a, b, c) \\
p(b)&=\sum_{a \in\{0,1\}} \sum_{c \in\{0,1\}} p(a, b, c) \\
p(a,b)&=\sum_{c \in\{0,1\}} p(a,b,c)
\end{aligned}
これをa=0, b=0について求めると
\begin{aligned}
p(a=0) &= \frac{192+144+48+216}{1000}=\frac{600}{1000},\ p(b=0) = \frac{192+144+192+64}{1000} =\frac{592}{1000} \\
p(a=0, b=0) &= \frac{192+144}{1000} = \frac{336}{1000}
\end{aligned}
これよりp(a=0, b=0) \neq p(a=0)p(b=0)であることが示された。同様にして、いずれのa,bの組み合わせでもp(a, b) \neq p(a)p(b)となる。
次にcで条件付けられた場合、ベイズの定理から
p(a, b \mid c)= \frac{p(a,b,c)}{p(c)} =\frac{p(a, b, c)}{\sum_{a \in\{0,1\}} \sum_{b \in\{0,1\}} p(a, b, c)}
同様に
\begin{aligned}
p(a \mid c)&=\frac{\sum_{b \in\{0,1\}} p(a, b, c)}{\sum_{a \in\{0,1\}} \sum_{b \in\{0,1\}} p(a, b, c)} \\
p(b \mid c)&=\frac{\sum_{a \in\{0,1\}} p(a, b, c)}{\sum_{a \in\{0,1\}} \sum_{b \in\{0,1\}} p(a, b, c)}
\end{aligned}
である。それぞれ計算していくと
\begin{aligned}
p(c=0) &= \frac{192+48+192+48}{1000} = \frac{480}{1000} \\
p(a=0, b=0 \mid c=0) &= \frac{p(a=0, b=0, c=0)}{p(c=0)} = \frac{192}{480} = \frac{2}{5} \\
p(a=0 \mid c=0) &= \frac{p(a=0, c=0)}{p(c=0)} = \frac{240}{480} = \frac{1}{2} \\
p(b=0 \mid c=0) &= \frac{p(b=0, c=0)}{p(c=0)} = \frac{384}{480} = \frac{4}{5} \\
\end{aligned}
これより、p(a=0, b=0 \mid c=0) = p(a=0 \mid c=0)p(b=0 \mid c=0)が成立していることがわかる。同様にしてすべて計算していくと結果は以下の表の通りになる。
\begin{array}{|c|c|c|c|}\hline a & b & \mathrm{c} & p(a, b \mid c) \\ \hline \hline 0 & 0 & 0 & 0.400 \\ \hline 0 & 1 & 0 & 0.100 \\ \hline 1 & 0 & 0 & 0.400 \\ \hline 1 & 1 & 0 & 0.100 \\ \hline \hline 0 & 0 & 1 & 0.277 \\ \hline 0 & 1 & 1 & 0.415 \\ \hline 1 & 0 & 1 & 0.123 \\ \hline 1 & 1 & 1 & 0.185 \\ \hline\end{array} \hspace{2em} \begin{array}{|c|c|c|c|}\hline a & b & c & p(a \mid c) p(b \mid c) \\ \hline \hline 0 & 0 & 0 & 0.400 \\ \hline 0 & 1 & 0 & 0.100 \\ \hline 1 & 0 & 0 & 0.400 \\ \hline 1 & 1 & 0 & 0.100 \\ \hline \hline 0 & 0 & 1 & 0.277 \\ \hline 0 & 1 & 1 & 0.415 \\ \hline 1 & 0 & 1 & 0.123 \\ \hline 1 & 1 & 1 & 0.185 \\ \hline\end{array}
これよりp(a,b\mid c) = p(a\mid c)p(b\mid c)が成立していることが示された。つまりcで条件付けられた場合にa,bは独立である。
演習 8.4
表8.2で与えられる同時分布に対して分布p(a), p(b\mid c)およびp(c\mid a)を計算せよ．その結果からp(a, b, c) = p(a)p(c\mid a)p(b\mid c)を直接計算して示し，対応する有向グラフを描け．
演習8.3と同様にp(c|a)を計算する。
\begin{aligned}
p(c=0|a=0) &= \frac{192+48}{600} = 0.4\\
p(c=0|a=1) &= \frac{192+48}{400} = 0.6\\
p(c=1|a=0) &= \frac{144+216}{600} = 0.6\\
p(c=1|a=1) &= \frac{64+96}{400} = 0.4\\
\end{aligned}
これを用いてp(a)p(c|a)p(b|c)を計算すると、以下の通り表8.2のp(a,b,c)に一致する。
\begin{array}{|c|c|c|c|}\hline a & b & \mathrm{c} & p(a)p(c|a)p(b|c) \\ \hline \hline 0 & 0 & 0 & 0.6\times 0.4\times 0.8=0.192 \\ \hline 0 & 0 & 1 & 0.6\times 0.6\times 0.4=0.144 \\ \hline 0 & 1 & 0 & 0.6\times 0.4\times 0.2=0.048 \\ \hline 0 & 1 & 1 & 0.6\times 0.6\times 0.6=0.216 \\ \hline \hline 1 & 0 & 0 & 0.4\times 0.6\times 0.8=0.192 \\ \hline 1 & 0 & 1 & 0.4\times 0.4\times 0.4=0.064 \\ \hline 1 & 1 & 0 & 0.4\times 0.6\times 0.2=0.048 \\ \hline 1 & 1 & 1 & 0.4\times 0.4\times 0.6=0.096 \\ \hline\end{array}
従って、有向グラフは「a→c→b」となる。
演習 8.5
p(\mathbf{t} \mid \mathbf{X}, \mathbf{w}, \beta)=\prod_{n=1}^{N} p\left(t_{n} \mid \mathbf{x}_{n}, \mathbf{w}, \beta\right) \tag{7.79}
および
p(\mathbf{w} \mid \boldsymbol{\alpha})=\prod_{i=1}^{M} \mathcal{N} \left( w_i \mid 0, \alpha_i^{-1} \right) \tag{7.80}
によって記述される．RVMに対応する有向確率的グラフィカルモデルを描け．
教科書P.57から
RVMでは1つの超パラメータの代わりに個々の重みパラメータw_iごとに異なった超パラメータ\alpha_iを用いる
ので(7.80)となっている。そこでこの式をまず有向グラフにすると
のようになる。ノードはM個存在する。
同様に(7.79)を有向グラフにすると
ノードはN個存在する。t_nは\mathbf{x}_n,\mathbf{w}_i, \betaより生成される。なお、t_nは観測変数なのでノードに影をつけておく。
(7.80)で得た重み\mathbf{w}が(7.79)のt_nへの親ノードになっているので、これらを繋いで
という図を得る。
演習 8.6
図8.13に示されるモデルにおいて，条件付き分布p(y\mid x_1, \ldots, x_M)（ただしx_i \in \{0,1\}）を規定するのに必要なパラメータ数は，ロジスティックシグモイド関数表現
p\left(y=1 \mid x_{1}, \ldots, x_{M}\right)=\sigma\left(w_{0}+\sum_{i=1}^{M} w_{i} x_{i}\right)=\sigma\left(\mathbf{w}^{\mathrm{T}} \mathbf{x}\right) \tag{8.10}
を用いれば2^MからM + 1に減らせることを示した．別の表現(Pearl, 1988) として，
p\left(y=1 \mid x_{1}, \ldots, x_{M}\right)=1-\left(1-\mu_{0}\right) \prod_{i=1}^{M}\left(1-\mu_{i}\right)^{x_{i}} \tag{8.104}
で与えられるものもある．ただし，0 \leqslant \mu_i \leqslant 1 (i = 0,\ldots, M)であり，条件付き分布(8. 104)はnoisy ORとして知られる．この表現が論理的OR関数（すなわち，少なくとも1つのiに対してx_i = 1であれば常にy=1を与える関数）を「ソフト」 （確率的） にしたものであると解釈できることを示せ．また，\mu_iの解釈について論ぜよ．
まず、\mu_0 = 0、\mu_i = 1 for i = 1, \ldotsの場合を考える。この時、8.104式は、
p\left(y=1 \mid x_{1}, \ldots, x_{M}\right)=1- \prod_{i=1}^{M}0^{x_{i}} =
\begin{cases}
0 &\text{if every } x_i = 0\\
1 &\text{else}
\end{cases}
と表される。これは、論理的OR関数（すなわち，少なくとも1つのiに対してx_i = 1であれば常にy=1を与える関数）に等しい。そして、\mu_0 \approx 0, \mu_1 \approx 1の時は、OR関数に近似できる。
次に、\mu_0,\mu_iについて考える。\mathbf{x} = \mathbf{0}の時、
\begin{aligned}
p(y = 1|\mathbf{x} = \mathbf{0}) = 1 - (1-\mu_0)\prod_i (1-\mu_i)^0 = 1 - (1-\mu_0) = \mu_0
\end{aligned}
すなわち、\mu_0は、\mathbf{x} = \mathbf{0}の時のy = 1の確率と見ることができる。
次に、x_i = 1, \mathbf{x}_{-i} = \mathbf{0}を考えると、
\begin{aligned}
p(y = 1|x_i =1, \mathbf{x}_{-i} = \mathbf{0}) = 1 - (1-\mu_0)(1-\mu_i) = \mu_0 + \mu_i -\mu_0 \mu_i
\end{aligned}
今、\mu_0 \approx 0とすると、
\begin{aligned}
p(y = 1|x_i =1, \mathbf{x}_{-i}) \approx \mu_i
\end{aligned}
である。すなわち、\mu_iとは、\mu_0 = 0である時に、x_i = 1、\mathbf{x}_{-i} = \mathbf{0}である確率に等しい。以上から、8.104式は、論理的OR関数をソフトに(確率的に)したものであると言える。
演習 8.7
再帰的関係
\mathbb{E}\left[x_{i}\right]=\sum_{j \in \mathrm{pa}_{i}} w_{i j} \mathbb{E}\left[x_{j}\right]+b_{i} \tag{8.15}
および
\begin{aligned} \operatorname{cov}\left[x_{i}, x_{j}\right] &=\mathbb{E}\left[\left(x_{i}-\mathbb{E}\left[x_{i}\right]\right)\left(x_{j}-\mathbb{E}\left[x_{j}\right]\right)\right] \\ &=\mathbb{E}\left[\left(x_{i}-\mathbb{E}\left[x_{i}\right]\right)\left\{\sum_{k \in \mathrm{pa}_{j}} w_{j k}\left(x_{k}-\mathbb{E}\left[x_{k}\right]\right)+\sqrt{v_{j}} \epsilon_{j}\right\}\right] \\ &=\sum_{k \in \mathrm{pa}_{j}} w_{j k} \operatorname{cov}\left[x_{i}, x_{k}\right]+I_{i j} v_{j} . \end{aligned} \tag{8.16}
を用いて，図8.14に示されるグラフの同時分布の平均および共分散が，それぞれ
\mu=\left(b_{1}, b_{2}+w_{21} b_{1}, b_{3}+w_{32} b_{2}+w_{32} w_{21} b_{1}\right)^{\mathrm{T}} \tag{8.17}
および
\Sigma=\left(\begin{array}{ccc}v_{1} & w_{21} v_{1} & w_{32} w_{21} v_{1} \\ w_{21} v_{1} & v_{2}+w_{21}^{2} v_{1} & w_{32}\left(v_{2}+w_{21}^{2} v_{1}\right) \\ w_{32} w_{21} v_{1} & w_{32}\left(v_{2}+w_{21}^{2} v_{1}\right) & v_{3}+w_{32}^{2}\left(v_{2}+w_{21}^{2} v_{1}\right)\end{array}\right) \tag{8.18}
で与えられることを示せ．
図8.14のグラフに示された変数間の依存関係 (x_1 \rightarrow x_2 \rightarrow x_3) より、
\begin{aligned}
\mathbb{E}\left[x_1\right] &= b_1 \\
\mathbb{E}\left[x_2\right] &= w_{21} \mathbb{E}\left[x_1\right] + b_2 \\
&= w_{21} b_1 + b_2 \\
\mathbb{E}\left[x_3\right] &= w_{32} \mathbb{E}\left[x_2\right] + b_3 \\
&= w_{32} w_{21} b_1 + w_{32} b_2 + b_3 \\
\mathrm{var}\left[x_1\right] &= v_1 \\
\mathrm{cov}\left[x_1, x_2\right] &= w_{21} \mathrm{cov}\left[x_1, x_1\right] \\
&= w_{21} v_1 = \mathrm{cov}\left[x_2, x_1\right] \\
\mathrm{var}\left[x_2\right] &= w_{21} \mathrm{cov}\left[x_2, x_1\right] + v_2 \\
&= w^2_{21} v_1 + v_2 \\
\mathrm{cov}\left[x_1, x_3\right] &= w_{32} \mathrm{cov}\left[x_1, x_2\right] \\
&= w_{32}w_{21} v_1 = \mathrm{cov}\left[x_3, x_1\right] \\
\mathrm{cov}\left[x_2, x_3\right] &= w_{32} \mathrm{cov}\left[x_2, x_2\right] \\
&= w_{32}w^2_{21} v_1 + w_{32} v_2 = w_{32}(w^2_{21} v_1 + v_2) = \mathrm{cov}\left[x_3, x_2\right] \\
\mathrm{var}\left[x_3\right] &= w_{32} \mathrm{cov}\left[x_3, x_2\right] + v_3 \\
&= w^2_{32}(w^2_{21} v_1 + v_2) + v_3
\end{aligned}
演習 8.8
a \perp \!\!\! \perp b, c \mid dならばa \perp \!\!\! \perp b \mid dであることを示せ．
a \perp \!\!\! \perp b, c \mid d より条件付き独立の定義から
p(a, b, c \mid d)=p(a \mid d)p(b, c \mid d)
である．両辺をcについて周辺化することで
p(a,b \mid d) =p(a \mid d)p(b \mid d)
が得られ，条件付き独立の定義から
a \perp \!\!\! \perp b \mid d
である．以上により示された．
演習 8.9
有向グラフにおいて，マルコフブランケット内のすべてのノードに条件付けられたノード\mathbf{x}の条件付き分布が，グラフの残りの変数に対して独立であることを有向分離規準を用いて示せ．
マルコフブランケット内のすべてのノードとは\mathbf{x}の親、子、共同親の全てのノードである。これらが全て条件付けられている時、\mathbf{x}が条件付けられていないノードに対して独立であることを示す。まず、条件付けられていないノードは、
(1) \mathbf{x}の親ノードの親
(2) \mathbf{x}の親ノードの子
(3) \mathbf{x}の子ノードの子
(4) \mathbf{x}の共同親ノードの親
(5) \mathbf{x}の共同親ノードの子
のいずれかが\mathbf{x}との経路に存在する。よって(1)~(5)のいずれも\mathbf{x}と独立であることを示せば良い。
p.91の2条件を改めて示すと、
ノード\mathbf{y}で経路が遮断されている条件は
(a)\mathbf{y}が条件づけられていて、経路に含まれる矢印が\mathbf{y}でhead-to-tailもしくはtail-to-tail
(b)\mathbf{y}がその子孫とともに条件づけられておらず、経路に含まれる矢印が\mathbf{y}でhead-to-head
(1)について、(1)から\mathbf{x}への経路は、\mathbf{x}の親ノードが(a)に当てはまり(head-to-tail)、遮断されている。
(2)について、(2)から\mathbf{x}への経路は、\mathbf{x}の親ノードが(a)に当てはまり(tail-to-tail)、遮断されている。
(3)について、\mathbf{x}から(3)への経路は、\mathbf{x}の子ノードが(a)に当てはまり(tail-to-tail)、遮断されている。
(4)について、(4)から\mathbf{x}への経路は、\mathbf{x}の共同親ノードが(a)に当てはまり(head-to-tail)、遮断されている。
(5)について、(5)から\mathbf{x}への経路は、\mathbf{x}の共同親ノードが(a)に当てはまり(tail-to-tail)、遮断されている。
以上により示された。
演習 8.10
すべての変数が観測されていない図8.54に示される有向グラフを考える．a \perp \!\!\! \perp b \mid \emptysetを示せ．今，dを観測したとする．一般にa \not\perp \!\!\! \perp b \mid dであることを示せ．
まず、図8.54のグラフより、
\begin{aligned}
p(a, b, c, d) = p(a)p(b)p(c|a, b)p(d|c).
\end{aligned}
上式をcとdに関して周辺化することで、
\begin{aligned}
p(a, b) &= p(a)p(b)\sum_{c}\sum_{d}p(c|a, b)p(d|c) \\
&= p(a)p(b)\sum_{c}p(c|a, b)\sum_{d}p(d|c) \\
&= p(a)p(b) \times 1 \times 1 \\
&= p(a)p(b)
\end{aligned}
となるので、a \perp \!\!\! \perp b \mid \emptyset。次に、
\begin{aligned}
p(a, b|d) &= \frac{\sum_{c} p(a, b, c, d)}{\sum_{a}\sum_{b}\sum_{c} p(a, b, c, d)} \\
&= \frac{p(d|a, b)p(a)p(b)}{p(d)} \\
&= \frac{p(d|a, b)p(d)}{p(d)} \frac{p(a)p(b)}{p(d)}.
\end{aligned}
しかし、
\begin{aligned}
p(a|d)(b|d) &= \frac{p(a, d)}{p(d)} \frac{p(b, d)}{p(d)} \\
&= \frac{p(d|a)p(a)}{p(d)} \frac{p(d|b)p(b)}{p(d)} \\
&= \frac{p(d|a)p(d|b)}{p(d)} \frac{p(a)p(b)}{p(d)} \\
&\neq p(a, b|d)
\end{aligned}
なので、a \not\perp \!\!\! \perp b \mid d。
演習 8.11
図8.21 に示される車の燃料装置の例を考える．燃料計Gの状態を直接観測する代わりに，燃料計が運転手Dによって観測され，彼が燃料計の読みを我々に報告すると仮定する．この報告は 燃料計が満タンを指しているD = 1かあるいは空を指しているD = 0かのいずれかである．この運転手はいささか信頼性に欠け，以下の確率に従うとする．
p(D=1 \mid G=1)=0.9 \tag{8.105}
p(D=0 \mid G=0)=0.9 \tag{8.106}
今運転手が燃料計が空を指していることを報告したとする．すなわち我々はD=0を観測した．この観測値だけが与えられたときの，タンクが空である確率を求めよ．同様に，バッテリが切れているという観測も得られたときのタンクが空である確率を求め，後者の確率の方が低いことを確認せよ．この結果の直感的解釈について議論し，図8.54との関係を説明せよ．
教科書P.89の問題設定から
\begin{array}{l}p(G=1 \mid B=1, F=1)=0.8 \\ p(G=1 \mid B=1, F=0)=0.2 \\ p(G=1 \mid B=0, F=1)=0.2 \\ p(G=1 \mid B=0, F=0)=0.1 .\end{array} \hspace{1em}
\begin{array}{l}p(G=0 \mid B=1, F=1)=0.2 \\ p(G=0 \mid B=1, F=0)=0.8 \\ p(G=0 \mid B=0, F=1)=0.8 \\ p(G=0 \mid B=0, F=0)=0.9 .\end{array}
である。またp(D=0\mid G=1) = 0.1, p(D=0 \mid G=0) = 0.9である。
求めたいのはp(F=0 \mid D=0)なので、式変形をすると
p(F=0 \mid D=0)=\frac{p(D=0 \mid F=0) p(F=0)}{p(D=0)}=\frac{\sum_{G \in \{0,1\}} p(D=0, G \mid F=0) p(F=0)}{p(D=0)} \tag{*}
である。まずp(G=0)を計算する。これは(8.30)にも出ているが
\begin{aligned} p(G=0) &=\sum_{B \in\{0,1\}}\sum_{F \in\{0.1\}} p(G=0 \mid B, F) p(B) p(F) \\
&=p(G=0 \mid B=0, F=0)p(B=0)p(F=0) + p(G=0 \mid B=0, F=1)p(B=0)p(F=1) \\
&+ p(G=0 \mid B=1, F=0)p(B=1)p(F=0) + p(G=0 \mid B=1, F=1)p(B=1)p(F=1) \\
&=0.9 \times 0.1 \times 0.1+0.8 \times 0.1 \times 0.9+0.8 \times 0.9 \times 0.1+0.2 \times 0.9 \times 0.9 \\ &=0.315 \end{aligned}
であり、p(G=1) = 1-0.315 = 0.685が求まる。
(*)式の分母を計算すると
\begin{aligned}
p(D=0) &=\sum_{G \in\{0,1\}} p(D=0 \mid G) p(G) \\ &=0.9 \times 0.315+0.1 \times 0.685=0.352
\end{aligned}
となる。次に\sum_{G \in \{0,1\}} p(D=0, G \mid F=0)を計算する。
\begin{aligned}
\sum_{G \in[0,1]} p(D=0, G \mid F=0) &=\sum_{G \in\{0,1\}} p(D=0 \mid G, F=0) p(G \mid F=0) \\
&=\sum_{G \in\{0,1\}} p(D=0 \mid G) p(G \mid F=0) \\
&=0.9 \times 0.81+0.1 \times 0.19=0.748
\end{aligned}
ここで問題設定からDはGのみに依存しているのでp(D=0\mid G, F=0) = p(D=0 \mid G)であることを用いた。よってこれらの値を用いることで、(*)式は
p(F=0\mid D=0) =\frac{0.748 \times 0.1}{0.352} = 0.2125
次に、B=0が観測されたときの求める確率は
\begin{aligned}
p(F=0 \mid D=0, B=0) &=\frac{p(D=0, B=0, F=0)}{p(D=0, B=0)} \\ &=\frac{\sum_{G} p(D=0, B=0, F=0, G)}{\sum_{G} p(D=0, B=0, G)} \\ &=\frac{\sum_{G} p(B=0, F=0, G) p(D=0 \mid B=0, F=0, G)}{\sum_{G} p(B=0, G) p(D=0 \mid B=0, G)} \\ &=\frac{\sum_{G} p(B=0, F=0, G) p(D=0 \mid G)}{\sum_{G} p(B=0, G) p(D=0 \mid G)}
\end{aligned}\tag{**}
これを計算する。分子のp(B=0, F=0, G)について
\begin{aligned} p(F=0, B=0, G=0) &=p(G=0 \mid B=0, F=0) p(B=0, F=0) \\ &=0.9 \times p(B=0) \times p(F=0) \\ &=0.9 \times 0.1 \times 0.1=0.009 \\
p(F=0, B=0, G=1) &=0.1 \times p(B=0) \times p(F=0) \\ &=0.001 \end{aligned}
分母のp(B=0, G)について
\begin{aligned} p(B=0, G=0) &=\sum_{F} p(B=0, G=0, F) \\
&=p(F=0, B=0, G=0)+p(F=1, B=0, G=0) \\
&=0.009+p(G=0 \mid B=0, F=1) p(B=0) p(F=1) \\
&=0.009+0.8 \times 0.1 \times 0.9 \\ &=0.081 \\
p(B=0, G=1) &=p(F=0, B=0, G=1)+p(F=1, B=0, G=1) \\ &=0.1 \times 0.1 \times 0.1+0.2 \times 0.1 \times 0.9 \\ &=0.001+0.018=0.019
\end{aligned}
以上の計算から
\begin{aligned} p(F=0 \mid D=0, B=0) &=\frac{\sum_{G} p(D=0 \mid G) p(F=0, B=0, G)}{\sum_{G} p(D=0 \mid G) p(B=0, G)} \\ &=\frac{0.9 \times 0.009+0.1 \times 0.001}{0.9 \times 0.081+0.1 \times 0.019} \\ &=\frac{9 \times 9+1 \times 1}{9 \times 81+1 \times 19}=\frac{41}{374}=0.1096 \cdots \end{aligned}
これらの計算から、p(F=0 \mid D=0) \gt p(F=0 \mid D=0, B=0)となっている。すなわちバッテリの状態を確認したことでタンクが空の確率は減少した。この減少はバッテリの状態B=0がG=0を弁明してしまうため、F=0の可能性が低くなる直感と一致する。
また、図8.54と結びつけると、ノードcはG，ノードdはDに対応する。
演習 8.12
M個の異なる確率変数集合に対して2^{M(M-1)/2}個の異なる無向グラフが存在することを示せ．M=3の場合における8個の可能なグラフをすべて描け．
演習 8.13
反復条件付きモード(ICM) を使って
E(\mathbf{x}, \mathbf{y})=h \sum_{i} x_{i}-\beta \sum_{\{i, j\}} x_{i} x_{j}-\eta \sum_{i} x_{i} y_{i} \tag{8.42}
で与えられるエネルギー関数を最小化することを考える．すべての他の変数を固定して，ある1つの変数x_jに関する2状態のエネルギー値の差を書き下せ．またその表現が，グラフにおけるx_jの近傍の局所的な量だけに依存することを示せ．
※PRML下巻pp.102~103を参照。教科書中の問題設定から、すべての\mathbf{x}, \mathbf{y}は\{+1, -1\}の2値である。
ある変数x_kがエネルギー関数E(\mathbf{x, y})に与える影響を考えるために、(8.42)式を変形すると
E(\mathbf{x}, \mathbf{y})=h\left(\sum_{i \neq k} x_{i}+x_{k}\right)-\beta\left(\sum_{i\neq k} x_{i} x_{j}+x_{k} \sum_{l} x_{l}\right) - \eta \left( \sum_{i\neq k} x_i y_i + x_k y_k \right)
となる。ここで問題設定からx_lはx_kに隣接する変数である。
\mathbf{x,y}のうち、x_jのみ1, -1の2状態を考え、残りの変数は固定されているのならば、そのときのエネルギー差は
\begin{aligned}
E(\mathbf{x,y})|_{x_j=1} - E(\mathbf{x,y})|_{x_j=-1}
&=\left(h-\beta \sum_{l} x_{l}-\eta y_{j}\right)-\left(-h+\beta \sum_{l} x_{l}+\eta y_{j}\right) \\
&=2h -2\beta \sum_{l}x_l -2\eta y_j
\end{aligned}
となる。このエネルギー差は確かにグラフにおけるx_jの近傍の局所的な量だけに依存している。
演習 8.14
エネルギー関数が
E(\mathbf{x}, \mathbf{y})=h \sum_{i} x_{i}-\beta \sum_{\{i, j\}} x_{i} x_{j}-\eta \sum_{i} x_{i} y_{i} \tag{8.42}
で与えられ，その係数が\beta = h = 0である場合を考える．最も確からしい潜在変数の値はすべてのiに対してx_i = y_iであることを示せ．
エネルギー関数は
E(\mathbf{x}, \mathbf{y}) = -\eta \sum_{i} x_{i} y_{i}
となる。これはx_i = y_iであればE=-\eta, x_i \neq y_iであればE=\etaとなる。
潜在変数x_iと観測値y_iに対し、エネルギー関数Eが負になれば\mathbf{x},\mathbf{y}の同時分布
p(\mathbf{x}, \mathbf{y})=\frac{1}{Z} \exp \{-E(\mathbf{x}, \mathbf{y})\} \tag{8.43}
が大きくなり、\mathbf{y}が観測されているのでp(\mathbf{x}\mid \mathbf{y}) = p(\mathbf{x}, \mathbf{y})/p(\mathbf{y})も大きくなる。
すなわち最も確からしいx_iの値はすべてのiに対してx_i = y_iであり、これはノイズ付加画像そのものである。
演習 8.15
図8.38に示されるグラフにおいて，2 つの隣接ノード上の同時分布p(x_{n-1}, x_n)が
p\left(x_{n-1}, x_{n}\right)=\frac{1}{Z} \mu_{\alpha}\left(x_{n-1}\right) \psi_{n-1, n}\left(x_{n-1}, x_{n}\right) \mu_{\beta}\left(x_{n}\right) \tag{8.58}
の形で表現されることを示せ．
8.4.1節の議論と同様に考えれば良い。求める周辺分布は
p(x_{n-1},x_n) = \sum_{x_1}\sum_{x_1}\cdots\sum_{x_{n-2}}\sum_{x_{n+1}}\cdots\sum_{x_N}p(\mathbf{x})
である。(8.52)式と同様にポテンシャル関数を用いると、図8.38に書かれてある2つのメッセージ\mu_{\alpha}(x_n)と\mu_{\beta}(x_n)を用いて
\begin{aligned}
p\left(x_{n-1}, x_{n}\right) &=\frac{1}{Z}\left[\sum_{x_{n-2}} \psi_{n-2, n-1}\left(x_{n-2}, x_{n-1}\right) \ldots\left[\sum_{x_{2}} \psi_{2,3}\left(x_{2}, x_{3}\right)\left[\sum_{x_{1}} \psi_{1,2}\left(x_{1}, x_{2}\right)\right]\right] \ldots\right] \\
& \times \psi_{n-1, n}\left(x_{n-1}, x_{n}\right) \\ & \times\left[\sum_{x_{n+1}} \psi_{n, n+1}\left(x_{n}, x_{n+1}\right) \ldots\left[\sum_{x_{N}} \psi_{N-1, N}\left(x_{N-1}, x_{N}\right)\right] \ldots\right] \\
&=\frac{1}{Z} \mu_{\alpha}\left(x_{n-1}\right) \psi_{n-1, n}\left(x_{n-1}, x_{n}\right) \mu_{\beta}\left(x_{n}\right)
\end{aligned}
と書ける。
演習 8.16
図8.38に示されるグラフにおいて，すべてのノードn\in \{1, \ldots ,N-1\}に対してp(x_n \mid x_N)を計算する推論問題を考える．この問題を効率的に解くために8.4.1 節で議論したメッセージパッシングアルゴリズムが利用できることを示し，どのメッセージがどのように修正されるかについて議論せよ．
教科書p.112の上段に記載のとおり、ポテンシャル関数にI(x_N,\hat{x}_N)を掛けるだけで良い（\hat{x}_Nは変数x_Nの観測値）。
\mu_\alpha (x_n)の再帰式は教科書の議論と同じ。
\mu_\beta (x_n)の再帰式は、初期条件を通常の
\begin{aligned}
\mu_\beta (x_{N-1}) &= \sum _{x_N} \psi_{N-1,N}(x_{N-1},x_N)
\end{aligned}
に代えて、
\begin{aligned}
\mu_\beta (x_{N-1}) &= \sum _{x_N} I(x_N,\hat
x_N)\psi_{N-1,N}(x_{N-1},x_N)\\
&= \psi_{N-1,N}(x_{N-1},\hat{x}_N)
\end{aligned}
とすれば良い。
演習 8.17
図8.38に示される形のN=5ノードのグラフを考える．ただしx_3およびx_5は観測されているとする．有向分離性を使ってx_2 \perp \!\!\! \perp x_5 \mid x_3を示せ．8.4.1 節のメッセージパッシングアルゴリズムをp(x_2 \mid x_3, x_5)の計算に用いたとき，結果がx_5の値に依存しないことを示せ．
（前半部分）
x_2とx_5を結ぶ経路はx_3が観測された時遮断されるためx_2 \perp \!\!\! \perp x_5 \mid x_3である．
（後半部分）
ベイズの定理により
\begin{aligned}
p(x_2 \mid x_3, x_5)&=\frac{p(x_2 , x_3, x_5)}{p(x_3, x_5)}\\
&=\frac{\sum_{x_1, x_4}\psi_{1, 2}\psi_{2, 3}\psi_{3, 4}\psi_{4, 5}}{\sum_{x_1,x_2,x_4}\psi_{1, 2}\psi_{2, 3}\psi_{3, 4}\psi_{4, 5}}\\
&=\frac{\sum_{x_1}\psi_{1, 2}\psi_{2, 3}\sum_{x_4}\psi_{3, 4}\psi_{4, 5}}{\sum_{x_1,x_2}\psi_{1, 2}\psi_{2, 3}\sum_{x_4}\psi_{3, 4}\psi_{4, 5}}\\
&=\frac{\sum_{x_1}\psi_{1, 2}\psi_{2, 3}}{\sum_{x_1,x_2}\psi_{1, 2}\psi_{2, 3}}
\end{aligned}
演習 8.18
有向木によって表現される分布が，対応する無向木上の等価な分布によって（自明に）表現されることを示せ．無向木で表現される分布が，クリークポテンシャルを適切に規格化することにより，有向木で表現可能であることも示せ．ある与えられた無向木から構築できる異なる有向木の数を計算せよ．
x_1を親に持ち、x_2を子に持つような木の一部分を抜き出して考える。ポテンシャル関数
\psi_{2,1} = p(x_2 \mid x_1)
とすることで自明に無向木に変換できる(木では親が一つのためモラル化の必要はない)
また、無向木から有向木への変換は、
p(x_2 \mid x_1) = \frac{\psi_{2,1}}{\sum _{x_2} \psi_{2,1}}
として規格化すればよい。その際、有向木の作り方は根の選び方に対応するN通り(要素数の数)である。
演習 8.19
8.4.4 節において導出した積和アルゴリズムを，8.4.1 節において議論したノードの連鎖モデルに適用し，結果
p\left(x_{n}\right)=\frac{1}{Z} \mu_{\alpha}\left(x_{n}\right) \mu_{\beta}\left(x_{n}\right) \tag{8.54}
\begin{aligned} \mu_{\alpha}\left(x_{n}\right) &=\sum_{x_{n-1}} \psi_{n-1, n}\left(x_{n-1}, x_{n}\right)\left[\sum_{x_{n-2}} \cdots\right] \\ &=\sum_{x_{n-1}} \psi_{n-1, n}\left(x_{n-1}, x_{n}\right) \mu_{\alpha}\left(x_{n-1}\right) \end{aligned} \tag{8.55}
および
\begin{aligned} \mu_{\beta}\left(x_{n}\right) &=\sum_{x_{n+1}} \psi_{n, n+1}\left(x_{n}, x_{n+1}\right)\left[\sum_{x_{n+2}} \cdots\right] \\ &=\sum_{x_{n+1}} \psi_{n, n+1}\left(x_{n}, x_{n+1}\right) \mu_{\beta}\left(x_{n+1}\right) \end{aligned} \tag{8.57}
が特別な場合として得られることを示せ．
規格化項Zを因子fなどに包含させて、\psiをfに対応させれば、それぞれ
\begin{aligned} \mu_{x_{m} \rightarrow f_{s}}\left(x_{m}\right) &=\prod_{l \in \operatorname{ne}\left(x_{m}\right) \backslash f_{s}}\left[\sum_{X_{l m}} F_{l}\left(x_{m}, X_{l m}\right)\right] \\ &=\prod_{l \in \operatorname{ne}\left(x_{m}\right) \backslash f_{s}} \mu_{f_{l} \rightarrow x_{m}}\left(x_{m}\right) \end{aligned} \tag{8.69}
p\left(\mathbf{x}_{s}\right)=f_{s}\left(\mathbf{x}_{s}\right) \prod_{i \in \operatorname{ne}\left(f_{s}\right)} \mu_{x_{i} \rightarrow f_{s}}\left(x_{i}\right) \tag{8.72}
の特殊な場合(直鎖状に限定したもの)とみなせる。
演習 8.20
木構造因子グラフにおける積和アルゴリズムのメッセージパッシングの手続きについて考える．メッセージはまずすべての葉ノードから任意に選ばれた根ノードに向かって伝播され，その後根ノードから葉ノードヘと伝播される各ステップにおいて，メッセージを送るべきノードが，そのメッセージを計算するために必要なすべてのメッセージをすでに受け取っているようにメッセージパッシングのスケジュールを組むことが可能であることを，帰納法を用いて示せ．
ノードが1個の時はあきらかに成り立つ．
ノードがN個のとき題意を満たすスケジュールを組むことができると仮定する．題意を満たすスケジュールを考えたときN個のノードには根が存在するため増やすノードは葉ノードとなる．葉ノードを増やすときすべてのメッセージが伝播されるようにスケジュールを組むことができる木構造因子グラフのノードに付け加えるのでN+1個の時も題意を満たすようなスケジュールを組むことが可能である．
以上により帰納法から任意のNについて題意を満たすスケジュールを組むことができる．
演習 8.21
因子グラフにおいて，積和メッセージパッシングアルゴリズムを実行した後，
p\left(\mathbf{x}_{s}\right)=f_{s}\left(\mathbf{x}_{s}\right) \prod_{i \in \operatorname{ne}\left(f_{s}\right)} \mu_{x_{i} \rightarrow f_{s}}\left(x_{i}\right) \tag{8.72}
を適用することにより，各因子f_s(\mathbf{x}_s)に関連する変数\mathbf{x}_s全体上の周辺分布p(\mathbf{x}_s)が計算できることを示せ．
因子f_sと繋がっている変数の組\mathbf{x}_s上の周辺分布を計算する。
（教科書の議論では\mathbf{x}_sの構成要素のうち、根ノード側の変数\{ x \}と葉ノード側の変数\{ x_1, \cdots x_M \}を区別したが、今回は\mathbf{x}_sのすべての要素について横並びの議論をするので、その必要はない。）
(8.61)式に変えて、周辺分布は、
\begin{aligned}
p(\mathbf{x}_s)
=\sum_{\mathbf{x}\backslash{\mathbf{x}_s}}
p(\mathbf{x})
\end{aligned}
となる。
上図にて、x_iに隣接する因子（f_sを除く）の積は、
\begin{aligned}
\prod_{j \in \mathrm{ne} (x_i) \backslash f_s}
F_{ij} (x_i, X_{ij})
\end{aligned}
なので、同時分布p(\mathbf{x})は、
\begin{aligned}
p(\mathbf{x} ) = f_s(\mathbf{x} _s)
\prod_{i \in \mathrm{ne} (f_s) }
\prod_{j \in \mathrm{ne} (x_i) \backslash f_s}
F_{ij} (x_i, X_{ij})
\end{aligned}
と書ける。従って、
\begin{aligned}
p(\mathbf{x}_s)
&=\sum_{\mathbf{x}\backslash{\mathbf{x}_s}}
f_s(\mathbf{x} _s)
\prod_{i \in \mathrm{ne} (f_s) }
\prod_{j \in \mathrm{ne} (x_i) \backslash f_s}
F_{ij} (x_i, X_{ij}) \\
&=f_s(\mathbf{x} _s)
\prod_{i \in \mathrm{ne} (f_s) }
\sum_{\mathbf{x}\backslash{\mathbf{x}_s}}
\prod_{j \in \mathrm{ne} (x_i) \backslash f_s}
F_{ij} (x_i, X_{ij}) \\
&=f_s(\mathbf{x} _s)
\prod_{i \in \mathrm{ne} (f_s) }
\mu _{x_i \rightarrow f_s} (x_i)
\end{aligned}
と題意の周辺分布が計算された。
なお、１行目から２行目への式変形で、変数x_iでの和がi番目以外のツリー内の因子に影響を与えないこと、すなわち
\begin{aligned}
&\sum_{x_1}\sum_{x_2}\cdots \left( F_{11}F_{12}F_{13}F_{21}F_{22}\cdots \right)\\
=& \left( \sum_{x_1} F_{11} F_{12} F_{13} \right)
\left( \sum_{x_2} F_{21} F_{22} \right) \cdots
\end{aligned}
を用いた。また、2行目から3行目の式変形で、教科書と同様に
\begin{aligned}
\mu _{x_i \rightarrow f_s} (x_i)
=\sum_{\mathbf{x}\backslash{\mathbf{x}_s}}
\prod_{j \in \mathrm{ne} (x_i) \backslash f_s}
F_{ij} (x_i, X_{ij})
\end{aligned}
と定義した。
演習 8.22
木構造因子グラフを考える．連結部分グラフであるような変数ノードの部分集合が与えられたとする．（すなわち，その部分集合の任意の変数ノードが，少なくとも他の1つの変数ノードに1つの因子ノードを通して連結されているとする．）積和アルゴリズムを利用して，その部分集合上の周辺分布を計算する方法を示せ．
与えられた連結部分グラフであるような変数ノードの部分集合を\mathbf{x}_aとする。残りの変数ノードを\mathbf{x}_bとする。
定義(8.61)から、\mathbf{x}_aについての周辺分布は\mathbf{x}_aを除くすべての変数、すなわち\mathbf{x}_bについての同時分布の和を取れば良い。
p(\mathbf{x}_a) = \sum_{\mathbf{x}_b}p(\mathbf{x})
また、因子グラフを使った同時分布p(\mathbf{x})は(8.59)や(8.60)のように、連結されている変数ノードと因子の積で表現される。
p(\mathbf{x}) =\prod_{s}f_s(\mathbf{x}_s)
この2式から
p(\mathbf{x}_a) = \sum_{\mathbf{x}_b}\prod_{s}f_s(\mathbf{x}_s)
となる。ここで、このf_s(\mathbf{x}_s)は2つのパターンで構成される。すなわち、
-
\mathbf{x}_bに属する変数ノードとリンクせず、\mathbf{x}_aに属する変数ノード間でのみリンクしている因子ノードf_s^{'}
-
\mathbf{x}_aに含まれる変数ノードと\mathbf{x}_bに含まれる変数ノード間のリンクを1つ以上持つ因子ノードf_s^{''}
である。注意すべき点として、1の方は\sum_{\mathbf{x}_b}と入れ替えることができないのでメッセージ\muの形で書くことはできず、純粋にf^{'}_sの積が残ることになる。2のうち\mathbf{x}_bが関わる場合は積と和を交換することでメッセージとして表現可能である。
f_sを\mathbf{x}_aと\mathbf{x}_b間に存在する因子ノード、x_sをf_sと接続している変数ノード（x_s \in \mathbf{x}_a）、f_{s_a}を\mathbf{x}_aに属する変数ノード間にのみ存在する因子ノード、\mathbf{x}_{s_a}をf_{s_a}と接続している変数ノードの部分集合であるとする。この記法を用いて、1と2の場合の積で表現して
\begin{aligned}
p\left(\mathbf{x}_{a}\right) &=\prod_{s_{a}} f_{s_{a}}\left(\mathbf{x}_{s_{a}}\right) \prod_{s \in \operatorname{ne} \mathbf{x}_{a}} \mu_{f_{s} \rightarrow x_{s}}\left(x_{s}\right)
\end{aligned}
と書ける。
この図を例にすると、\mathbf{x}_a=\{x_2, x_8, x_9\}としたとき、f_{s_a} = f_6, \mathbf{x}_{s_a}=\{x_8, x_9\}となる。
p(\mathbf{x}) = f_1(x_1, x_2)f_2(x_2, x_3, x_6)f_3(x_2,x_5,x_8)f_4(x_4, x_5)f_5(x_5,x_7)f_6(x_8,x_9)f_7(x_9, x_{10})であるから、
\begin{aligned}
p(\mathbf{x}_a) &= p(x_2, x_8, x_9) \\
&= \sum_{x_1,x_3,x_6,x_4,x_5,x_7,x_{10}}p(\mathbf{x}) \\
&=f_6(x_8,x_9)\mu_{f_1 \rightarrow x_2}(x_2)\mu_{f_2 \rightarrow x_3}(x_3)\mu_{x_5 \rightarrow f_3}(x_5)\mu_{f_7 \rightarrow x_9}(x_9) \\
&=f_6(x_8,x_9)\mu_{f_1 \rightarrow x_2}(x_2)\mu_{f_2 \rightarrow x_3}(x_3)\left[ \mu_{f_4 \rightarrow x_5}(x_5)\mu_{f_5 \rightarrow x_5}(x_5) \right]\mu_{f_7 \rightarrow x_9}(x_9) \\
&= f_6(x_8,x_9)\prod_{s \in \operatorname{ne} \mathbf{x}_{a}} \mu_{f_{s} \rightarrow x_{s}}\left(x_{s}\right)
\end{aligned}
のように書ける。
演習 8.23
8.4.4 節において，因子グラフの変数ノードx_i上の周辺分布p(x_i)が，隣接因子ノードからこのノードに伝わるメッセージの積として
\begin{aligned} p(x) &=\prod_{s \in \operatorname{ne}(x)}\left[\sum_{X_{s}} F_{s}\left(x, X_{s}\right)\right] \\ &=\prod_{s \in \operatorname{ne}(x)} \mu_{f_{s} \rightarrow x}(x) \end{aligned} \tag{8.63}
の形で与えられることを示した．x_iに接続されるリンクを1つ選んだとする．周辺分布p(x_i)はこの1つのリンクに沿って入ってくるメッセージと同じリンクに沿って出ていくメッセージとの積として書くこともできることを示せ．
\begin{aligned}
p(x_i) &= \prod_{s \in \operatorname{ne}(x_i)} \mu_{f_{s} \rightarrow x_i}(x_i) \ \ (\because \mathrm{Eq.} 8.63) \\
&= \mu_{f_{s} \rightarrow x_i}(x_i) \prod_{t \in \operatorname{ne}(x_i)\setminus f_s} \mu_{f_{t} \rightarrow x_i}(x_i) \\
&= \mu_{f_{s} \rightarrow x_i}(x_i) \mu_{x_i \rightarrow f_s}(x_i). \ \ (\because \mathrm{Eq.} 8.69)
\end{aligned}
演習 8.24
木構造因子グラフにおいて，積和メッセージパッシングアルゴリズムを実行したとする．因子f_s(\mathbf{x}_s)の変数\mathbf{x}_s上の周辺分布が
p\left(\mathbf{x}_{s}\right)=f_{s}\left(\mathbf{x}_{s}\right) \prod_{i \in \operatorname{ne}\left(f_{s}\right)} \mu_{x_{i} \rightarrow f_{s}}\left(x_{i}\right) \tag{8.72}
の形に書けることを示せ．これは，この因子ノードに接続されるすべてのリンクに沿って入ってきたメッセージの積に，局所的な因子f_{s}(\mathbf{x}_s)を掛けたものである．
演習8.21と同様
演習 8.25
図8.51 のグラフにおいて，ノードx_3を根ノードとして積和アルゴリズムを実行するとx_2上の正しい周辺分布が得られる．このことは
\begin{aligned} \widetilde{p}\left(x_{2}\right) &=\mu_{f_{a} \rightarrow x_{2}}\left(x_{2}\right) \mu_{f_{b} \rightarrow x_{2}}\left(x_{2}\right) \mu_{f_{c} \rightarrow x_{2}}\left(x_{2}\right) \\ &=\left[\sum_{x_{1}} f_{a}\left(x_{1}, x_{2}\right)\right]\left[\sum_{x_{3}} f_{b}\left(x_{2}, x_{3}\right)\right]\left[\sum_{x_{4}} f_{c}\left(x_{2}, x_{4}\right)\right] \\ &=\sum_{x_{1}} \sum_{x_{3}} \sum_{x_{4}} f_{a}\left(x_{1}, x_{2}\right) f_{b}\left(x_{2}, x_{3}\right) f_{c}\left(x_{2}, x_{4}\right) \\ &=\sum_{x_{1}} \sum_{x_{3}} \sum_{x_{4}} \widetilde{p}(\mathrm{x}) \end{aligned} \tag{8.86}
において確かめられた．では，x_1およびx_3についても正しい周辺分布が得られることを示せ．同様に，このグラフにおいて積和アルゴリズムを実行した後，
p\left(\mathbf{x}_{s}\right)=f_{s}\left(\mathbf{x}_{s}\right) \prod_{i \in \operatorname{ne}\left(f_{s}\right)} \mu_{x_{i} \rightarrow f_{s}}\left(x_{i}\right) \tag{8.72}
の結果を適用すれば，x_1およびx_2上の正しい同時分布が得られることを示せ．
p. 124と同様に進める。x_1について新たに必要なメッセージシークエンスを求めると、
\begin{aligned}
&\mu_{f_a \rightarrow x_1}(x_1) = \sum_{x_2} f_a(x_1, x_2) \mu_{x_2 \rightarrow f_a} (x_2) \\
&\mu_{x_2 \rightarrow f_a} (x_2) = \mu_{f_b \rightarrow x_2}(x_2) \mu_{f_c \rightarrow x_2}(x_2) \\
&\mu_{f_b \rightarrow x_2}(x_2) = \sum_{x_3} f_b(x_2, x_3)
\end{aligned}
になる。これを代入して、
\begin{aligned}
\tilde{p}(x_1) &= \mu_{f_a \rightarrow x_1}(x_1) \\
&= \sum_{x_2} f_a(x_1, x_2) \mu_{x_2 \rightarrow f_a} (x_2)\\
&= \sum_{x_2} f_a(x_1, x_2) \mu_{f_b \rightarrow x_2}(x_2) \mu_{f_c \rightarrow x_2}(x_2) \\
&=\sum_{x_2} f_a(x_1, x_2) \sum_{x_3} f_b(x_2, x_3) \sum_{x_4} f_b(x_2, x_4)\\
&= \sum_{x_2}\sum_{x_3}\sum_{x_4} f_a(x_1, x_2) f_b(x_2, x_3) f_b(x_2, x_4)\\
&= \sum_{x_2}\sum_{x_3}\sum_{x_4} \tilde{p}(\mathbf{x})&(\because (8.73))
\end{aligned}
また、x_3について、同様に新たに必要なメッセージシークエンスを求めて代入すると、
\begin{aligned}
\tilde{p}(x_3) &= \mu_{f_b \rightarrow x_3}(x_3) \\
&= \sum_{x_2} f_b(x_3, x_2) \mu_{x_2 \rightarrow f_b} (x_2)\\
&= \sum_{x_2} f_b(x_3, x_2) \mu_{f_a \rightarrow x_2}(x_2) \mu_{f_c \rightarrow x_2}(x_2) \\
&=\sum_{x_2} f_b(x_3, x_2) \sum_{x_1} f_a(x_1, x_2) \sum_{x_4} f_c(x_2, x_4)\\
&= \sum_{x_1}\sum_{x_2}\sum_{x_4} f_a(x_1, x_2) f_b(x_2, x_3) f_c(x_2, x_4)\\
&= \sum_{x_1}\sum_{x_2}\sum_{x_4} \tilde{p}(\mathbf{x})
\end{aligned}
になる。
次にx_1とx_2の同時分布を求める。(8.72)と\tilde{p}(x_1)導出過程から、
\begin{aligned}
p(x_1, x_2) &= f_a(x_1, x_2)\mu_{x_2 \rightarrow f_a}(x_2) \\
&= f_a(x_1, x_2)\mu_{x_2 \rightarrow f_a} (x_2)\\
&= f_a(x_1, x_2) \sum_{x_3} f_b(x_2, x_3) \sum_{x_4} f_b(x_2, x_4) \\
&= \sum_{x_3} \sum_{x_4}\tilde{p}(\mathbf{x})
\end{aligned}
演習 8.26
離散変数上の木構造因子グラフを考える．共通の因子に属さない2つの変数x_aおよびx_b上の同時分布p(x_a,x_b)を計算したいとする．積和アルゴリズムを使ってこの同時分布を計算する手順を示せ．ただしその手順では，それらの変数のうちの1つが，取り得る値のうちのそれぞれに各ステップで固定される．
(8.72)を繰り返し用いて、x_a,x_bが共通する因子を持つようにすれば良い。
参考： https://tips-memo.com/prml-8-26
演習 8.27
2つの3状態離散変数xおよびyを考える．例えばx,y \in \{0, 1, 2\}である．これらの変数上の同時分布p(x,y)であって，周辺分布p(x)を最大にする値\hat{x}と周辺分布p(y)を最大にする値\hat{y}とを組み合わせると，同時分布の確率が0となる（すなわちp(\hat{x}, \hat{y})= 0となる）ようなものを作れ．
演習 8.28
8.4.7 節で，因子グラフに対する積和アルゴリズムにおける保留メッセージの概念が定義された．グラフが1つ以上の閉路を持つ場合，アルゴリズムをどんなに長く実行しても少なくとも1つの保留メッセージが常に存在することを示せ．
閉路上のノード又は因子を1つ選びnとする。閉路に沿ってnの隣のノード又は因子をn+1とする。
閉路に沿ってn+1の隣りでnと反対側のノード又は因子をn+2とする。
閉路上のノード又は因子が閉路上のリンクに保留メッセージを持つとする。
何回か保留メッセージを送信した時、閉路上から保留メッセージが消えたとする。
これはノードの因子の上では起こり得ない。
なぜならnがn+1とのリンク上の保留メッセージを送信するとn+1が保留メッセージを持つため
保留メッセージが消えないからである。
閉路上どこのノード又は因子をnとしても良いので
結局、閉路上どのノード又は因子においても閉路上の保留メッセージを送信した後
保留メッセージが消えることはない。
演習 8.29
積和アルゴリズムを（ループのない）木構造因子グラフに対して実行した場合，ある有限個のメッセージが送られた後，保留メッセージが存在しなくなることを示せ．
あるツリーがN個のメッセージを送ったあと保留メッセージがなくなったとする。
このときのメッセージ列をM_{1}, M_{2}, \cdots, M_{N}とする。
このツリーの任意のノードpに葉ノードoを追加する。新しくできたツリーのメッセージ列は
(1) メッセージ列の先頭にノードo → ノードpのメッセージM_{o}を追加する。
(2) メッセージ列の末尾にノードp → ノードoのメッセージM_{n+1}を追加する。
(3) メッセージ列のうちノードpからo以外の隣接ノードへの送信メッセージM_{p1} \cdotsを、M_{o}が含まれるように変える。
という手順で得ることができる、得られたメッセージは
M_{0}, M_{1}, M_{2}, \cdots, M_{p 1}, \cdots, M_{N}, M_{N+1}となり、これを送信したあと保留メッセージは残らない。
よって、有限個のメッセージ送信で保留メッセージがなくなるツリーに葉ノードを1つ付け加えたものは有限個のメッセージで保留メッセージがなくなると言える。
次に、ノード1つからなるツリーは保留メッセージを持たない。
また、全てのツリーはノード1つから初めて1つづつ葉ノードを追加していくことで作ることができる。
以上より全てのツリーは有限個のメッセージを送信したあと保留メッセージが無くなるといえる。
Discussion
演習8.4の解答部分の４行目、5行目についてですが、P(c=1 | a=0)=0.4、P(c=1 | a=1)=0.6のところは、
P(c=1 | a=0)=0.6、P(c=1 | a=1)=0.4であると思います。ご確認くださいませ。
ありがとうございます。修正いたしました。
演習8.13の解答の下から５行目以降の部分ですが、解答の流れからはxjをxkとした方がよろしいかと思います。
演習8.23の解答の下から1行目ですが、ftではなくfsであるように思います。
修正しました。
演習8.29の解答上から6行目ですが、”Mp1,...Moを含むように変える。”は、”Mp1,...を、Moが含まれるように変える”の方が良いように思います。