機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

積和アルゴリズム

仮定

以下の議論では,モデルの持つすべての変数は離散的であると仮定します。
また、もともとのグラフは無向木、有向木あるいは多重木のいずれかであると仮定します。
すると、これを変換してできる因子グラフは木構造を持ちます。

因子グラフにおける同時分布 p({\bf x})

ある特定の変数ノード x 上の周辺分布 p(x) を求める問題から考えます。
周辺分布 p(x) は、以下のようになります。

\begin{eqnarray}
p(x)=\sum_{{\bf x}\backslash x}p({\bf x})\tag{1}
\end{eqnarray}

ここで、{\bf x}\backslash x{\bf x} の変数集合から変数 x を除いたものを示します。

グラフが木構造を持つので、同時分布の因子を変数ノード x
隣接する各因子ノードごとにグループ分けすることができます。
同時分布は以下の形の積で書けます。

\begin{eqnarray}
p({\bf x})=\prod_{s\in{\rm ne}(x)}F_s(x,X_s)\tag{2}
\end{eqnarray}

ここで、{\rm ne}(x)x に隣接する因子ノードの集合を表し、
X_s は因子ノード f_s を通して、変数ノード x に接続される部分木に属する全ての変数を表します。
また、F_s(x,X_s) は因子 f_s に関連するグループのすべての因子の積を表します。

因子ノードから変数ノードへのメッセージ \mu_{f\rightarrow x}(x)

(2) を式 (1) に代入します。

\begin{eqnarray}
p(x)&=&\sum_{{\bf x}\backslash x}\left(\prod_{s\in{\rm ne}(x)}F_s(x,X_s)\right)\tag{3}\\
&=&\sum_{X_1}\cdots\sum_{X_S}\left(\prod_{s\in{\rm ne}(x)}F_s(x,X_s)\right)\tag{4}\\
&=&\left(\sum_{X_1}F_1(x,X_1)\right)\cdots\left(\sum_{X_S}F_S(x,X_S)\right)\\
&=&\prod_{s\in{\rm ne}(x)}\left(\sum_{X_s}F_s(x,X_s)\right)\tag{5}\\
&=&\prod_{s\in{\rm ne}(x)}\mu_{f_s\rightarrow x}(x)\tag{6}
\end{eqnarray}

(4) で、{\bf x}\backslash x=X_1\cup\cdots\cup X_S としました。(x に隣接する因子ノードを f_1,\ldots,f_S としました。)
(6) で、以下で定義される関数 \mu_{f_s\rightarrow x}(x) を導入しました。

\begin{eqnarray}
\mu_{f_s\rightarrow x}(x)\equiv\sum_{X_s}F_s(x,X_s)\tag{7}
\end{eqnarray}

(7) は因子ノード f_s から変数ノード x へのメッセージと解釈できます。
(7) のイメージを以下の図1に記しました。

図1: \mu_{f_s\rightarrow x}(x) のイメージ
f:id:olj611:20211130233218p:plain:w400

(3) から式 (5) の式変形で積と和を入れ替わっていますが、これが積和アルゴリズムの肝です。

この積和の入れ替えが成り立つのは、木構造の因子モデルだからです。
実はこれに似た考え方を、連鎖における推論の式 (3) で既に説明しています。
分かりにくい場合は、そちらを参照してみてください。

変数ノードから因子ノードへのメッセージ \mu_{x\rightarrow f}(x)

各因子 F_s(x,X_s) も因子(部分)グラフによって記述されるので、以下のように書けます。

\begin{eqnarray}
F_s(x,X_s)&=&f_s(x,x_1,\ldots,x_M)G_1(x_1,X_{s1})\cdots G_M(x_M,X_{sM})\\
&=&f_s(x,x_1,\ldots,x_M)\left(\prod_{m\in{\rm ne}(f_s)\backslash x}G_m(x_m,X_{sm})\right)\tag{8}
\end{eqnarray}

ここで、x とともに因子 f_s に関連する変数を x_1,\ldots,x_M としました。
{\rm ne}(f_s) は因子ノード f_s に隣接する変数ノード集合であり、{\rm ne}(f_s)\backslash x はその集合から x を除いたものです。
X_{sm} は変数ノード x_m を通して、因子ノード f_s に接続される部分木に属する全ての変数を表します。
G_m(x_m,X_{sm}) は変数ノード x_m に接続されるf_s 以外の因子に関連するグループのすべての因子の積を表します。

(8) を式 (7) に代入します。

\begin{eqnarray}
\mu_{f_s\rightarrow x}(x)&=&\sum_{X_s}f_s(x,x_1,\ldots,x_M)\left(\prod_{m\in{\rm ne}(f_s)\backslash x}G_m(x_m,X_{sm})\right)\\
&=&\sum_{x_1}\cdots\sum_{x_M}\sum_{X_{s1}}\cdots\sum_{X_{sM}}f_s(x,x_1,\ldots,x_M)\left(\prod_{m\in{\rm ne}(f_s)\backslash x}G_m(x_m,X_{sm})\right)\\
&=&\sum_{x_1}\cdots\sum_{x_M}f_s(x,x_1,\ldots,x_M)\sum_{X_{s1}}\cdots\sum_{X_{sM}}\left(\prod_{m\in{\rm ne}(f_s)\backslash x}G_m(x_m,X_{sm})\right)\\
&=&\sum_{x_1}\cdots\sum_{x_M}f_s(x,x_1,\ldots,x_M)\left(\sum_{X_{s1}}G_1(x_1,X_{s1})\right)\cdots\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}\left(\sum_{X_{sm}}\mu_{x_m\rightarrow f_s}(x_m)\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{9}
\end{eqnarray}

ここで、変数ノードから因子ノードへのメッセージ \mu_{x_m\rightarrow f_s}(x_m) を定義しました。

\begin{eqnarray}
\mu_{x_m\rightarrow f_s}(x_m)\equiv\sum_{X_{sm}}G_m(x_m,X_{sm})\tag{10}
\end{eqnarray}

ここまでのイメージを図2に記しました。

図2
f:id:olj611:20211201050533p:plain:w300

また、以下の図3より、G_m(x_m,X_{sm}) は次のように書けます。

図3
f:id:olj611:20211201053821p:plain:w300

\begin{eqnarray}
G_m(x_m,X_{sm})=\prod_{l\in{\rm ne}(x_m)\backslash f_s}F_l(x_m,X_{lm})\tag{11}
\end{eqnarray}

(11) を式 (10) に代入します。

\begin{eqnarray}
\mu_{x_m\rightarrow f_s}(x_m)&=&\sum_{X_{sm}}\left(\prod_{l\in{\rm ne}(x_m)\backslash f_s}F_l(x_m,X_{lm})\right)\\
&=&\sum_{X_{1m}}\cdots\sum_{X_{Lm}}\left(\prod_{l\in{\rm ne}(x_m)\backslash f_s}F_l(x_m,X_{lm})\right)\tag{12}\\
&=&\left(\sum_{X_{1m}}F_{1}(x_m,X_{1m})\right)\cdots\left(\sum_{X_{Lm}}F_{L}(x_m,X_{Lm})\right)\\
&=&\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}\underbrace{\mu_{f_l\rightarrow x_m}(x_m)}_{(7)}\tag{13}
\end{eqnarray}

(12) で、X_{sm}=X_{1m}\cup\cdots\cup X_{Lm} としました。(x_m に隣接する f_s を除く因子ノードを f_1,\ldots,f_L としました。)

(9),(13) より、
因子ノードから変数ノードへのメッセージ \mu_{f\rightarrow x}(x) を変数ノードから因子ノードへのメッセージ \mu_{x\rightarrow f}(x) で表すことができ、
その逆も表すことができることが分かりましたので、各メッセージは他のメッセージを用いて再帰的に計算できます。

葉ノードから辿る

x を根ノードとみなして、全ての葉ノードから辿ることを考えます。

葉ノードが変数ノードの場合のメッセージは、以下で与えられます。

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

(14) のイメージは、以下の図4です。

図4
f:id:olj611:20211201054509p:plain:w200

葉ノードが因子ノードの場合のメッセージは、以下で与えられます。

\begin{eqnarray}
\mu_{f\rightarrow x}(x)=f(x)\tag{15}
\end{eqnarray}

(15) のイメージは、以下の図5です。

図5
f:id:olj611:20211201054600p:plain:w200

後は、式(9),(13) を用いれば、再帰的にメッセージを計算できるので、周辺分布 p(x) が計算できます。

全てのノードに対して、周辺分布を計算する

グラフの各変数ノード上の周辺分布を、すべてのノードに対して計算したいとします。
これは単に、上のアルゴリズムをノードごとに実行し直せば実現できますが、効率が悪いので、次のようにします。

まず始めに,任意の(変数あるいは因子)ノードを選んでそれを根ノードとします。
そして、先の場合と同様に、すべての葉ノードから根ノードに向けてメッセージを伝播させます。
この時点で根ノードはすべての隣接ノードからメッセージを受け取ったことになるので、
すべての隣接ノードにメッセージを送ることができます。
根ノードからその隣接ノードにメッセージが送られると、
今度は根ノードの隣接ノードが(それら自身の)すべての隣接ノードからメッセージを受け取ったことになり、
根ノードから遠ざかる方向のすべてのリンクに沿ってメッセージを送ることができます。

このようにメッセージパッシングすると、計算せねばならないメッセージの数はグラフのリンク数の 2 倍であり、
周辺分布を 1 つだけ計算する場合の 2 倍で済みます。

このメッセージ‘パッシングの手続きがうまく機能する証明については、PRML演習問題 8.20(基本) wwwをご覧ください。

1 つの因子に関連する変数集合全体上の周辺分布

1 つの因子に関連する変数集合全体上の周辺分布 p({\bf x}_s) を計算したいとします。
({\bf x}_s={\rm ne}(f_s) だと思います。)

上と同様の議論を行えば、ある因子に関連する変数上の周辺分布が、
その因子ノードに到達するすべてのメッセージと、そのノードに対応する
(局所的な)因子との積で与えられることを、示すことができます。

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

(16) の証明については、PRML演習問題 8.21(標準) wwwをご覧ください。

具体例

PRML演習問題 8.25(標準) に積和アルゴリズムの具体例を用いた問題があります。

参考文献

パターン認識機械学習 下巻 p117-p125

関連リンク

連鎖における推論

目次へ戻る