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

問題

図 $8.38$ に示されるグラフにおいて、すべてのノード $n\in\{1,\ldots,N-1\}$ に対して $p(x_n|x_N)$ を計算する推論問題を考える。
この問題を効率的に解くために $8.4.1$ 節で議論したメッセージパッシングアルゴリズムが利用できることを示し、
どのメッセージがどのように修正されるかについて議論せよ。

参照

図 $8.38$
f:id:olj611:20211003072433p:plain:h100

$\begin{eqnarray} p(x_n)&=&\frac{1}{Z}\\ &&\underbrace{\left(\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\cdots\left(\sum_{x_2}\psi_{2,3}(x_2,x_3)\left(\sum_{x_1}\psi_{1,2}(x_1,x_2)\right)\right)\cdots\right)}_{\mu_\alpha(x_n)}\\ &&\underbrace{\left(\sum_{x_{n+1}}\psi_{n,n+1}(x_n,x_{n+1})\cdots\left(\sum_{x_N}\psi_{N,N-1}(x_{N-1},x_N)\right)\cdots\right)}_{\mu_\beta(x_n)}\tag{8.52} \end{eqnarray}$

解答

観測値を $\widehat{x}_N$ と書くことにします。
この時、式 $8.52$ の $\mu_{\beta}(x_{N-1})=\displaystyle\sum_{x_N}\psi_{N,N-1}(x_N-1,x_N)$ は次のようになります。

$\begin{eqnarray} \mu_{\beta}(x_{N-1})&=&\sum_{x_N}\psi_{N,N-1}(x_{N-1},x_N)\cdot I(x_N,\widehat{x}_N)\tag{1}\\ &=&\psi_{N,N-1}(x_{N-1},\widehat{x}_N)\tag{2} \end{eqnarray}$

式 $(1)$ の関数 $I(x_N,\widehat{x}_N)$ は $x_N=\widehat{x}_N$ のとき $1$ 、そうでなければ $0$ を取る関数です。
式 $(2)$ より、 $p(x_n|x_N)$ は以下のように書けます。

$\begin{eqnarray} p(x_n|x_N)&=&\frac{1}{Z}\\ &&\underbrace{\left(\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\cdots\left(\sum_{x_2}\psi_{2,3}(x_2,x_3)\left(\sum_{x_1}\psi_{1,2}(x_1,x_2)\right)\right)\cdots\right)}_{\mu_\alpha(x_n)}\\ &&\underbrace{\left(\sum_{x_{n+1}}\psi_{n,n+1}(x_n,x_{n+1})\cdots\psi_{N,N-1}(x_{N-1},\widehat{x}_N)\cdots\right)}_{\mu_\beta(x_n)}\tag{3} \end{eqnarray}$

式 $(3)$ は式 $(8.52)$ と同じ形で書けているため、メッセージパッシングアルゴリズムが利用できます。
メッセージについては、式 $(2)$ で示したように $\mu_{\beta}(x_{N-1})$ は $x_N$ の和を取る必要が無くなりました。