# PRML第8章演習問題解答
<head>
<style>
div.panel-primary {
border: 1px solid #000;
margin: 10px 5px;
padding: 16px 10px 0px;
}
</style>
</head>
## 演習 8.1
<div class="panel-primary">
変数を1つずつ周辺化することによって，有向グラフの同時分布の表現
$$
p(\mathbf{x})=\prod_{k=1}^{K} p\left(x_{k} \mid \mathrm{pa}_{k}\right) \tag{8.5}
$$
が正しく規格化されていることを示せ．ただし個々の条件付き分布は正しく規格化されていると仮定する．
</div>
$\int p(\mathbf{x}) d\mathbf{x} = 1$であることを示せばよい。
\begin{align}
\int p(\mathbf{x}) d\mathbf{x} &= \int \prod^K_{k = 1} p(x_k|\mathrm{pa}_k) d\mathbf{x} \\
&= \idotsint p(x_K|\mathrm{pa}_K) \prod^{K - 1}_{k = 1} p(x_k|\mathbf{pa}_k) dx_1x_2\cdots x_K \\
&= \idotsint \Big[\prod^{K - 1}_{k = 1} p(x_k|\mathbf{pa}_k) \int p(x_K|\mathrm{pa}_K) dx_K\Big] dx_1x_2\cdots x_{K - 1} \\
&= \idotsint \prod^{K - 1}_{k = 1} p(x_k|\mathbf{pa}_k) dx_1x_2\cdots x_{K - 1} \\
&= \cdots \\
&= 1.
\end{align}
## 演習 8.2
<div class="panel-primary">
有向グラフにおいて，すべてのノードについて，自分より小さい番号を持つノードに向かうリンクが存在しないようにノードを順序付けることができるなら，有向閉路は存在しないことを示せ．
</div>
$N$個の変数$x_1, x_2, \cdots x_N$を仮定する。題意より
\begin{align}
x_1 \rightarrow \cdots \rightarrow x_N
\end{align}
となる経路は存在しうるが、
\begin{align}
x_N \rightarrow \cdots \rightarrow x_1
\end{align}
となる経路は存在しないため、有向閉路は存在しない。
## 演習 8.3
<div class="panel-primary">
表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)$である．
</div>
各確率を周辺化することで地道に求めていく。
$$
\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
<div class="panel-primary">
表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)$を直接計算して示し，対応する有向グラフを描け．
</div>
演習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.4\\
p(c=1|a=1) &= \frac{64+96}{400} = 0.6\\
\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
<div class="panel-primary">
$$
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に対応する有向確率的グラフィカルモデルを描け．
</div>
教科書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
<div class="panel-primary">
図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$の解釈について論ぜよ．
</div>
まず、$\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{align}
p(y = 1|\mathbf{x} = \mathbf{0}) = 1 - (1-\mu_0)\prod_i (1-\mu_i)^0 = 1 - (1-\mu_0) = \mu_0
\end{align}
すなわち、$\mu_0$は、$\mathbf{x} = \mathbf{0}$の時の$y = 1$の確率と見ることができる。
次に、$x_i = 1$、$\mathbf{x}_{-i} = \mathbf{0}$を考えると、
\begin{align}
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{align}
今、$\mu_0 \approx 0$とすると、
\begin{align}
p(y = 1|x_i =1, \mathbf{x}_{-i}) \approx \mu_i
\end{align}
である。すなわち、$\mu_i$とは、$\mu_0 = 0$である時に、$x_i = 1$、$\mathbf{x}_{-i} = \mathbf{0}$である確率に等しい。以上から、8.104式は、論理的OR関数をソフトに(確率的に)したものであると言える。
## 演習 8.7
<div class="panel-primary">
再帰的関係
$$
\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}
$$
で与えられることを示せ．
</div>
図8.14のグラフに示された変数間の依存関係 ($x_1 \rightarrow x_2 \rightarrow x_3$) より、
\begin{align}
\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{align}
## 演習 8.8
<div class="panel-primary">
$a \perp \!\!\! \perp b, c \mid d$ならば$a \perp \!\!\! \perp b \mid d$であることを示せ．
</div>
$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
<div class="panel-primary">
有向グラフにおいて，マルコフブランケット内のすべてのノードに条件付けられたノード$\mathbf{x}$の条件付き分布が，グラフの残りの変数に対して独立であることを有向分離規準を用いて示せ．
</div>
マルコフブランケット内のすべてのノードとは$\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
<div class="panel-primary">
すべての変数が観測されていない図8.54に示される有向グラフを考える．$a \perp \!\!\! \perp b \mid \emptyset$を示せ．今，$d$を観測したとする．一般に$a \not\perp \!\!\! \perp b \mid d$であることを示せ．
</div>
まず、図8.54のグラフより、
\begin{align}
p(a, b, c, d) = p(a)p(b)p(c|a, b)p(d|c).
\end{align}
上式を$c$と$d$に関して周辺化することで、
\begin{align}
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{align}
となるので、$a \perp \!\!\! \perp b \mid \emptyset$。
次に、
\begin{align}
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{align}
しかし、
\begin{align}
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{align}
なので、$a \not\perp \!\!\! \perp b \mid d$。
## 演習 8.11
<div class="panel-primary">
図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との関係を説明せよ．
</div>
教科書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
<div class="panel-primary">
$M$個の異なる確率変数集合に対して$2^{M(M-1)/2}$個の異なる無向グラフが存在することを示せ．$M=3$の場合における8個の可能なグラフをすべて描け．
</div>
※
## 演習 8.13
<div class="panel-primary">
反復条件付きモード(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$の近傍の局所的な量だけに依存することを示せ．
</div>
※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
<div class="panel-primary">
エネルギー関数が
$$
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$であることを示せ．
</div>
エネルギー関数は
$$
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
<div class="panel-primary">
図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}
$$
の形で表現されることを示せ．
</div>
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
<div class="panel-primary">
図8.38に示されるグラフにおいて，すべてのノード$n\in \{1, \ldots ,N-1\}$に対して$p(x_n \mid x_N)$を計算する推論問題を考える．この問題を効率的に解くために8.4.1 節で議論したメッセージパッシングアルゴリズムが利用できることを示し，どのメッセージがどのように修正されるかについて議論せよ．
</div>
教科書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
<div class="panel-primary">
図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$の値に依存しないことを示せ．
</div>
（前半部分）
$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
<div class="panel-primary">
有向木によって表現される分布が，対応する無向木上の等価な分布によって（自明に）表現されることを示せ．無向木で表現される分布が，クリークポテンシャルを適切に規格化することにより，有向木で表現可能であることも示せ．ある与えられた無向木から構築できる異なる有向木の数を計算せよ．
</div>
$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
<div class="panel-primary">
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}
$$
が特別な場合として得られることを示せ．
</div>
規格化項$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
<div class="panel-primary">
木構造因子グラフにおける積和アルゴリズムのメッセージパッシングの手続きについて考える．メッセージはまずすべての葉ノードから任意に選ばれた根ノードに向かって伝播され，その後根ノードから葉ノードヘと伝播される各ステップにおいて，メッセージを送るべきノードが，そのメッセージを計算するために必要なすべてのメッセージをすでに受け取っているようにメッセージパッシングのスケジュールを組むことが可能であることを，帰納法を用いて示せ．
</div>
ノードが1個の時はあきらかに成り立つ．
ノードが$N$個のとき題意を満たすスケジュールを組むことができると仮定する．題意を満たすスケジュールを考えたとき$N$個のノードには根が存在するため増やすノードは葉ノードとなる．葉ノードを増やすときすべてのメッセージが伝播されるようにスケジュールを組むことができる木構造因子グラフのノードに付け加えるので$N+1$個の時も題意を満たすようなスケジュールを組むことが可能である．
以上により帰納法から任意のNについて題意を満たすスケジュールを組むことができる．
## 演習 8.21
<div class="panel-primary">
因子グラフにおいて，積和メッセージパッシングアルゴリズムを実行した後，
$$
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)$が計算できることを示せ．
</div>
因子$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
<div class="panel-primary">
木構造因子グラフを考える．連結部分グラフであるような変数ノードの部分集合が与えられたとする．（すなわち，その部分集合の任意の変数ノードが，少なくとも他の1つの変数ノードに1つの因子ノードを通して連結されているとする．）積和アルゴリズムを利用して，その部分集合上の周辺分布を計算する方法を示せ．
</div>
与えられた連結部分グラフであるような変数ノードの部分集合を$\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つのパターンで構成される。すなわち、
1. $\mathbf{x}_b$に属する変数ノードとリンクせず、$\mathbf{x}_a$に属する変数ノード間でのみリンクしている因子ノード$f_s^{'}$
2. $\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}
$$
と書ける。
<hr>
<img src="https://i.imgur.com/Sor4lG6.png" width="100%">
この図を例にすると、$\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
<div class="panel-primary">
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つのリンクに沿って入ってくるメッセージと同じリンクに沿って出ていくメッセージとの積として書くこともできることを示せ．
</div>
$$
\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_t}(x_i). \ \ (\because \mathrm{Eq.} 8.69)
\end{aligned}
$$
## 演習 8.24
<div class="panel-primary">
木構造因子グラフにおいて，積和メッセージパッシングアルゴリズムを実行したとする．因子$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)$を掛けたものである．
</div>
演習8.21と同様
## 演習 8.25
<div class="panel-primary">
図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$上の正しい同時分布が得られることを示せ．
</div>
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
<div class="panel-primary">
離散変数上の木構造因子グラフを考える．共通の因子に属さない2つの変数$x_a$および$x_b$上の同時分布$p(x_a,x_b)$を計算したいとする．積和アルゴリズムを使ってこの同時分布を計算する手順を示せ．ただしその手順では，それらの変数のうちの1つが，取り得る値のうちのそれぞれに各ステップで固定される．
</div>
(8.72)を繰り返し用いて、$x_a,x_b$が共通する因子を持つようにすれば良い。
参考：https://tips-memo.com/prml-8-26
## 演習 8.27
<div class="panel-primary">
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$となる）ようなものを作れ．
</div>
## 演習 8.28
<div class="panel-primary">
8.4.7 節で，因子グラフに対する積和アルゴリズムにおける**保留**メッセージの概念が定義された．グラフが1つ以上の閉路を持つ場合，アルゴリズムをどんなに長く実行しても少なくとも1つの保留メッセージが常に存在することを示せ．
</div>
閉路上のノード又は因子を1つ選びnとする。閉路に沿ってnの隣のノード又は因子をn+1とする。
閉路に沿ってn+1の隣りでnと反対側のノード又は因子をn+2とする。
閉路上のノード又は因子が閉路上のリンクに保留メッセージを持つとする。
何回か保留メッセージを送信した時、閉路上から保留メッセージが消えたとする。
これはノードの因子の上では起こり得ない。
なぜならnがn+1とのリンク上の保留メッセージを送信するとn+1が保留メッセージを持つため
保留メッセージが消えないからである。
閉路上どこのノード又は因子をnとしても良いので
結局、閉路上どのノード又は因子においても閉路上の保留メッセージを送信した後
保留メッセージが消えることはない。
## 演習 8.29
<div class="panel-primary">
積和アルゴリズムを（ループのない）木構造因子グラフに対して実行した場合，ある有限個のメッセージが送られた後，保留メッセージが存在しなくなることを示せ．
</div>
あるツリーがN個のメッセージを送ったあと保留メッセージがなくなったとする。
このときのメッセージ列を$M_{1}, M_{2}, \cdots, M_{N}$とする。
このツリーの任意のノードpに葉ノードoを追加する。新しくできたツリーのメッセージ列は
(1) メッセージ列の先頭にノードo → ノードpのメッセージMoを追加する。
(2) メッセージ列の末尾にノードp → ノードoのメッセージMn+1を追加する。
(3) メッセージ列のうちノードpからo以外の隣接ノードへの送信メッセージMp1・・・Moを含むように変える。
という手順で得ることができる、得られたメッセージは
$M_{0}, M_{1}, M_{2}, \cdots, M_{p 1}, \cdots, M_{N}, M_{N+1}$となり、これを送信したあと保留メッセージは残らない。
よって、有限個のメッセージ送信で保留メッセージがなくなるツリーに葉ノードを1つ付け加えたものは有限個のメッセージで保留メッセージがなくなると言える。
次に、ノード1つからなるツリーは保留メッセージを持たない。
また、全てのツリーはノード1つから初めて1つづつ葉ノードを追加していくことで作ることができる。
以上より全てのツリーは有限個のメッセージを送信したあと保留メッセージが無くなるといえる。
Sign in with Wallet
Connect another wallet