PRML演習問題 8.25(標準) - 機械学習基礎理論独習

問題

図 $8.51$ のグラフにおいて、ノード $x_3$ を根ノードとして積和アルゴリスムを実行すると
$x_2$ 上の正しい周辺分布が得られる。
このことは $(8.86)$ において確かめられた。
では、 $x_1$ および $x_3$ についても正しい周辺分布が得られることを示せ。
同様に、このグラフにおいて秘和アルゴリズムを実行した後、
$(8.72)$ の結果を適用すれば $x_1$ および $x_2$ 上の正しい同時分布が得られることを示せ。

参照

図 $8.51$
f:id:olj611:20211205142224p:plain:w350

$\begin{eqnarray} p({\bf x})=\prod_sf_s({\bf x}_s)\tag{8.59} \end{eqnarray}$

$\begin{eqnarray} p(x)&=&\prod_{s\in{\rm ne}(x)}\left(\sum_{X_s}F_s(x,X_s)\right)\\ &=&\prod_{s\in{\rm ne}(x)}\mu_{f_s\rightarrow x}(x)\tag{8.63} \end{eqnarray}$

$\begin{eqnarray} \mu_{f_s\rightarrow x}(x)&=&\sum_{x_1}\cdots\sum_{x_M}f_s(x,x_1,\ldots,x_M)\prod_{m\in{\rm ne}(f_s)\backslash x}\left(\sum_{X_{sm}G_m(x_m,X_{sm})}\right)\\ &=&\sum_{x_1}\cdots\sum_{x_M}f_s(x,x_1,\ldots,x_M)\prod_{m\in{\rm ne}(f_s)\backslash x}\mu_{x_m\rightarrow f_s}(x_m)\tag{8.66} \end{eqnarray}$

$\begin{eqnarray} \mu_{x_m\rightarrow f_s}(x_m)&=&\prod_{l\in{\rm ne}(x_m)\backslash f_s}\left(\sum_{X_{lm}}F_l(x_m,X_{lm})\right)\\ &=&\prod_{l\in{\rm ne}(x_m)\backslash f_s}\mu_{f_l\rightarrow x_m}(x_m)\tag{8.69} \end{eqnarray}$

$\begin{eqnarray} \mu_{x\rightarrow f}(x)=1\tag{8.70} \end{eqnarray}$

$\begin{eqnarray} p({\bf x}_s)=f_s({\bf x}_s)\prod_{i\in{\rm ne}(f_s)}\mu_{x_i\rightarrow f_s}(x_i)\tag{8.72} \end{eqnarray}$

解答

$p(x_1)$ を積和アルゴリズムで求めます。

$\begin{eqnarray} p(x_1)&=&\underbrace{\prod_{s\in{\rm ne}(x_1)}\mu_{f_s\rightarrow x_1}(x_1)}_{(8.63)}\\ &=&\mu_{f_a\rightarrow x_1}(x_1)\ \ \ \ (\because {\rm ne}(x_1)=\{f_a\})\\ &=&\underbrace{\sum_{x_2}f_a(x_1,x_2)\prod_{m\in{\rm ne}(f_a)\backslash x_1}\mu_{x_m\rightarrow f_a}(x_m)}_{(8.66)}\\ &=&\sum_{x_2}f_a(x_1,x_2)\mu_{x_2\rightarrow f_a}(x_2)\ \ \ \ (\because {\rm ne}(f_a)\backslash x_1=\{x_2\})\\ &=&\sum_{x_2}f_a(x_1,x_2)\underbrace{\prod_{l\in{\rm ne}(x_2)\backslash f_a}\mu_{f_l\rightarrow x_2}(x_2)}_{(8.69)}\\ &=&\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)\ \ \ \ (\because {\rm ne}(x_2)\backslash f_a=\{f_b,f_c\})\\ &=&\sum_{x_2}f_a(x_1,x_2)\underbrace{\left(\sum_{x_3}f_b(x_2,x_3)\prod_{m\in{\rm ne}(f_b)\backslash x_2}\mu_{x_m\rightarrow f_b}(x_m)\right)}_{(8.66)}\underbrace{\left(\sum_{x_4}f_c(x_2,x_4)\prod_{m\in{\rm ne}(f_c)\backslash x_2}\mu_{x_m\rightarrow f_c}(x_m)\right)}_{(8.66)}\\ &=&\sum_{x_2}f_a(x_1,x_2)\Bigg(\sum_{x_3}f_b(x_2,x_3)\underbrace{\mu_{x_3\rightarrow f_b}(x_3)}_{=1\ (8.70)}\Bigg)\Bigg(\sum_{x_4}f_c(x_2,x_4)\underbrace{\mu_{x_4\rightarrow f_c}(x_4)}_{=1\ (8.70)}\Bigg)\ \ \ \ (\because {\rm ne}(f_b)\backslash x_2=\{x_3\},\ {\rm ne}(f_c)\backslash x_2=\{x_4\})\\ &=&\sum_{x_2}f_a(x_1,x_2)\sum_{x_3}f_b(x_2,x_3)\sum_{x_4}f_c(x_2,x_4)\tag{1}\\ &=&\sum_{x_2}\sum_{x_3}\sum_{x_4}f_a(x_1,x_2)f_b(x_2,x_3)f_c(x_2,x_4)\\ &=&\sum_{{\bf x}\backslash x_1}\underbrace{p({\bf x})}_{(8.59)}\tag{2} \end{eqnarray}$

式 $(2)$ より、積和アルゴリズムを用いて $x_1$ の正しい周辺分布が得られることが示せました。

$p(x_3)$ を積和アルゴリズムで求めます。

$\begin{eqnarray} p(x_3)&=&\underbrace{\prod_{s\in{\rm ne}(x_3)}\mu_{f_s\rightarrow x_3}(x_3)}_{(8.63)}\\ &=&\mu_{f_b\rightarrow x_3}(x_3)\ \ \ \ (\because {\rm ne}(x_3)=\{f_b\})\\ &=&\underbrace{\sum_{x_2}f_b(x_3,x_2)\prod_{m\in{\rm ne}(f_b)\backslash x_3}\mu_{x_m\rightarrow f_b}(x_m)}_{(8.66)}\\ &=&\sum_{x_2}f_b(x_3,x_2)\mu_{x_2\rightarrow f_b}(x_2)\ \ \ \ (\because {\rm ne}(f_b)\backslash x_3=\{x_2\})\\ &=&\sum_{x_2}f_b(x_3,x_2)\underbrace{\prod_{l\in{\rm ne}(x_2)\backslash f_b}\mu_{f_l\rightarrow x_2}(x_2)}_{(8.69)}\\ &=&\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)\ \ \ \ (\because {\rm ne}(x_2)\backslash f_b=\{f_a,f_c\})\\ &=&\sum_{x_2}f_b(x_3,x_2)\underbrace{\left(\sum_{x_1}f_a(x_2,x_1)\prod_{m\in{\rm ne}(f_a)\backslash x_2}\mu_{x_m\rightarrow f_a}(x_m)\right)}_{(8.66)}\underbrace{\left(\sum_{x_4}f_c(x_2,x_4)\prod_{m\in{\rm ne}(f_c)\backslash x_2}\mu_{x_m\rightarrow f_c}(x_m)\right)}_{(8.66)}\\ &=&\sum_{x_2}f_b(x_3,x_2)\Bigg(\sum_{x_1}f_a(x_2,x_1)\underbrace{\mu_{x_1\rightarrow f_a}(x_1)}_{=1\ (8.70)}\Bigg)\Bigg(\sum_{x_4}f_c(x_2,x_4)\underbrace{\mu_{x_4\rightarrow f_c}(x_4)}_{=1\ (8.70)}\Bigg)\ \ \ \ (\because {\rm ne}(f_a)\backslash x_2=\{x_1\},\ {\rm ne}(f_c)\backslash x_2=\{x_4\})\\ &=&\sum_{x_2}f_b(x_3,x_2)\sum_{x_1}f_a(x_2,x_1)\sum_{x_4}f_c(x_2,x_4)\\ &=&\sum_{x_2}\sum_{x_1}\sum_{x_4}f_a(x_3,x_2)f_b(x_2,x_1)f_c(x_2,x_4)\\ &=&\sum_{{\bf x}\backslash x_3}\underbrace{p({\bf x})}_{(8.59)}\tag{3} \end{eqnarray}$

式 $(3)$ より、積和アルゴリズムを用いて $x_3$ の正しい周辺分布が得られることが示せました。

${\bf x}_s=\{x_1,x_2\}$ とおいて、式 $(8.72)$ を適用します。

$\begin{eqnarray} p(x_1, x_2)&=&\underbrace{f_a(x_1,x_2)\prod_{i\in{\rm ne}(f_a)}\mu_{x_i\rightarrow f_a}(x_i)}_{(8.72)}\\ &=&f_a(x_1,x_2)\underbrace{\mu_{x_1\rightarrow f_a}(x_1)}_{=1\ (8.70)}\mu_{x_2\rightarrow f_a}(x_2)\ \ \ \ (\because {\rm ne}(f_a)=\{x_1,x_2\})\\ &=&f_a(x_1,x_2)\underbrace{\sum_{x_3}f_b(x_2,x_3)\sum_{x_4}f_c(x_2,x_4)}_{(1)}\\ &=&\sum_{x_3}\sum_{x_4}f_a(x_1,x_2)f_b(x_2,x_3)f_c(x_2,x_4)\\ &=&\sum_{{\bf x}\backslash\{x_1,x_2\}}\underbrace{p({\bf x})}_{(8.59)}\tag{4} \end{eqnarray}$

式 $(4)$ より、 $x_1$ および $x_2$ 上の正しい同時分布が得られることが示せました。

補足

式 $(8.74)-(8.85)$ を用いると、式がすっきりするかもしれません。