連鎖における推論 - 機械学習基礎理論独習

周辺分布 $p(x_n)$ の推論

以下の図1の(b)において、 $p(x_n)$ を考えます。

図1
f:id:olj611:20211003091958p:plain:h150

図1の(b)の同時分布は次のように書けます。

$\begin{eqnarray} p({\bf x})=\frac{1}{Z}\psi_{1,2}(x_1,x_2)\psi_{2,3}(x_2,x_3)\cdots\psi_{N-1,N}(x_{N-1},x_N)\tag{1} \end{eqnarray}$

$p(x_n)$ は $x_n$ 以外の全ての変数で周辺化することによって求められます。

$\begin{eqnarray} p(x_n)=\sum_{x_1}\cdots\sum_{x_{n-1}}\sum_{x_{n}}\cdots\sum_{x_{N}}p({\bf x})\tag{2} \end{eqnarray}$

ところで、式 $(2)$ をそのまま計算するのは計算効率が悪いので、効率よく計算する式は以下で与えられます。

$\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{3} \end{eqnarray}$

式 $(3)$ の計算をうまく表現するために、局所的なメッセージがグラフを伝播するという風に考えると、式 $(3)$ は以下のように書けます。

$\begin{eqnarray} p(x_n)=\frac{1}{Z}\mu_\alpha(x_n)\mu_\beta(x_n)\tag{4} \end{eqnarray}$

$\mu_\alpha(x_n)$ を、ノード $x_{n-1}$ からノード $x_n$ へ連鎖に沿って前向きに伝わるメッセージと考えます。
同様に $\mu_\beta(x_n)$ を、ノード $x_{n+1}$ からノード $x_n$ へ連鎖に沿って後ろ向きに伝わるメッセージと考えます。

$\mu_\alpha(x_n)$ は、以下のように再帰的に計算できます。

$\begin{eqnarray} \mu_\alpha(x_n)&=&\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\left(\sum_{x_{n-2}}\cdots\right)\\ &=&\sum_{x_{n-1}}\psi_{n-1,n}(x_{n-1},x_n)\mu_\alpha(x_{n-1})\tag{5} \end{eqnarray}$

最初に以下の式で $\mu_\alpha(x_2)$ を計算すれば、式 $(5)$ を再帰的に適用できます。

$\begin{eqnarray} \mu_\alpha(x_2)&=&\sum_{x_{1}}\psi_{1,2}(x_{1},x_2)\tag{6} \end{eqnarray}$

$\mu_\beta(x_n)$ は、以下のように再帰的に計算できます。

$\begin{eqnarray} \mu_\beta(x_n)&=&\sum_{x_{n+1}}\psi_{n,n+1}(x_{n},x_{n+1})\left(\sum_{x_{n+2}}\cdots\right)\\ &=&\sum_{x_{n+1}}\psi_{n,n+1}(x_{n},x_{n+1})\mu_\beta(x_{n+1})\tag{7} \end{eqnarray}$

最初に以下の式で $\mu_\alpha(x_{N-1})$ を計算すれば、式 $(7)$ を再帰的に適用できます。

$\begin{eqnarray} \mu_\alpha(x_{N-1})&=&\sum_{x_{N}}\psi_{N-1,N}(x_{N-1},x_N)\tag{8} \end{eqnarray}$

以上より、 $\mu_\alpha(x_n),\mu_\beta(x_n)$ が求めれば、式 $(4)$ の $Z$ は以下のように求まります。

$\begin{eqnarray} Z=\sum_{x_n}\mu_\alpha(x_n)\mu_\beta(x_n)\tag{9} \end{eqnarray}$

メッセージのイメージを以下の図2に示しました。

図2
f:id:olj611:20211003093612p:plain:h100

全てのノードの周辺分布 $p(x_n)$ の推論

今までは、ある $n$ について $p(x_n)$ 考えましたが、今度は全ての全てのノード $n\in\{1,\ldots,N\}$ の周辺分布 $p(x_n)$ について考えます。

$1$ つずつ求めると効率が悪いです。
そこで、始めにメッセージ $\mu_\beta(x_{N-1})$ をノード $x_N$ からノード $x_1$ まで後ろ向きに伝播させ、
同様にメッセージ $\mu_\alpha(x_2)$ をノード $x_1$ からノード $x_N$ まで前向きに伝播させます。
この伝播中のメッセージを保存しておきます。
こうすることにより、式 $(4)$ を適用するだけで、全てのノードの周辺分布 $p(x_n)$ が求められます。

$2$ つの隣接するノードの同時分布の $p(x_{n-1},x_n)$ の推論

連鎖上の $2$ つの隣接するノードの同時分布の $p(x_{n-1},x_n)$ について考えます。

$p(x_{n-1},x_n)$ を $x_{n-1}$ で周辺化したものが式 $(3)$ であるので、
式 $(3)$ から $\displaystyle\sum_{x_{n-1}}$ を取って周辺化をなくせば、 $p(x_{n-1},x_n)$ となります。
よって、 $p(x_{n-1},x_n)$ は以下の式で表せます。

$\begin{eqnarray} p(x_{n-1},x_n)&=&\frac{1}{Z}\\ &&\underbrace{\left(\sum_{x_{n-2}}\psi_{n-2,n-1}(x_{n-2},x_{n-1})\cdots\left(\sum_{x_1}\psi_{1,2}(x_1,x_2)\right)\cdots\right)}_{\mu_\alpha(x_{n-1})}\psi_{n-1,n}(x_{n-1},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)}\\ &=&\frac{1}{Z}\mu_\alpha(x_{n-1})\psi_{n-1,n}(x_{n-1},x_n)\mu_\beta(x_n)\tag{10} \end{eqnarray}$

偉人の名言

f:id:olj611:20211003102457p:plain:h300
弱気は相手を強気にさせる、
弱気は強気に押し切られる、
強気は弱気を制していく、
強気は強気を押し退ける
星野仙一

参考文献

パターン認識と機械学習下巻 p108-p112

周辺分布の推論

全てのノードの周辺分布の推論

つの隣接するノードの同時分布のの推論

偉人の名言

参考文献

周辺分布 $p(x_n)$ の推論

全てのノードの周辺分布 $p(x_n)$ の推論

$2$ つの隣接するノードの同時分布の $p(x_{n-1},x_n)$ の推論