因子グラフ

因子グラフによる因数分解

ある変数集合上の同時分布を因子の積の形で書いてみます。

$\begin{eqnarray} p({\bf x})=\prod_{s}f_s({\bf x}_s)\tag{1} \end{eqnarray}$

式 $(1)$ の ${\bf x}_s$ は変数の部分集合を表します。

有向グラフでは、以下の式

$\begin{eqnarray} p({\bf x})=\prod_{k=1}^Kp(x_k|pa_k)\tag{2} \end{eqnarray}$

によって、因数分解が定義されますが、これは式 $(1)$ の特別な場合です。

無向グラフでは、以下の式

$\begin{eqnarray} &&p({\bf x})=\frac{1}{Z}\prod_C \psi_c({\bf x}_C)\tag{2}\\ &&Z=\sum_{\bf x}\prod_C\psi_C({\bf x}_C)\tag{3} \end{eqnarray}$

によって、因数分解が定義されますが、これは式 $(1)$ の特別な場合です。

因子グラフにおいて、通常の円で描かれるノードは分布の各変数を表します。
一方、小さい正方形で描かれるノードは同時分布の各因子 $f_s({\bf x}_s)$ を表します。

例えば、以下の因数分解で表現される分布を考えます。

$\begin{eqnarray} p({\bf x})=f_a(x_1,x_2)f_b(x_1,x_2)f_c(x_2, x_3)f_d(x_3)\tag{4} \end{eqnarray}$

式 $(4)$ に対応する因子グラフは、以下で表現されます。

図1
f:id:olj611:20211129220404p:plain:h200

同一の変数集合上で定義される2つの因子 $f_a(x_1,x_2)$ および $f_2(x_1,x_2)$ が存在することに注意します。
無向グラフでは,このような2つの因子の積は1つのクリークポテンシャルに統合されたのでした。
同様に、 $f_c(x_2,x_3)$ および $f_d(x_3)$ も $x_2$ および $x_3$ 上の1つのポテンシャル関数に統合されたのでした。
しかし因子グラフでは、このような因子を陽に残し、内在する因数分解に関するより詳細な情報が表現されます。

無向グラフから因子グラフへの変換

まず、もともとの無向グラフの各ノードに対応する変数ノードを作り、
次に、極大クリーク ${\bf x}_s$ に対応する因子ノードを付け加えればよいです。
因子 $f_s({\bf x}_s)$ はクリークポテンシャル関数と同じにすればOKです。

ただし図2に例を示すように、複数の異なる因子グラフが1つの無向グラフに対応する場合があることに注意が必要です。

図2
f:id:olj611:20211129221127p:plain:h220

$(a)$ はクリークポテンシャル $\psi(x_1,x_2,x_3)$ を持つ無向グラフです。
$(b)$ は $(a)$ の無向グラフと同じ分布を表現する因子グラフです。
因子は $f(x_1,x_2,x_3)=\psi(x_1,x_2,x_3)$ です。
$(c)$ は $(a)$ の無向グラフと同じ分布を表現する因子グラフです。
このグラフの $2$ つの因子は $f_a(x_1,x_2,x_3)f_b(x_2,x_3)=\psi(x_1,x_2,x_3)$ を満たします。

有向グラフから因子グラフへの変換

有向グラフを因子グラフに変換するには、
まず有向グラフのノードに対応する因子グラフの変数ノードを作り、
次に条件付き分布に対応する因子を付け加える最後に適切なリンクを付加すればOKです。

この場合も、複数の因子グラフが $1$ つの有向グラフに対応することがあり得えます。
有向グラフから因子グラフへの変換の例を図3に示します。

図3
f:id:olj611:20211130022400p:plain:h220

$(a)$ は因数分解 $p(x_1)p(x_2)p(x_3|x_1,x_2)$ を表現する有向グラフです。
$(b)$ は $(a)$ の有向グラフと同じ分布を表現する因子グラフです。
因子は $f(x_1,x_2,x_3)=p(x_1)p(x_2)p(x_3|x_1,x_2)$ を満たします。
$(c)$ は $(a)$ の有向グラフと同じ分布を表現する因子グラフです。
因子はそれぞれ $f_a(x_1)=p(x_1),f_b(x_2)=p(x_2)$ および $f_c(x_1,x_2,x_3)=p(x_3|x_1,x_2)$ です。

木構造因子グラフ

有向木あるいは無向木を因子グラフに変換すると、得られる因子グラフも木構造を持ちます。

図4で例示するように有向多重木を無向グラフに変換すると、モラル化過程によってループができるが、
因子グラフに変換しても木構造のままです。

図4
f:id:olj611:20211130024113p:plain:h250

$(a)$ は有向多重木のグラフです。
$(b)$ は $(a)$ の有向多重木を無向グラフに変換したもので、ループができます。
$(c)$ は $(a)$ の有向多重木を因子グラフに変換したもので、木構造が保持されます。

実は有向グラフにおいて、あるノードに関する親同士をリンクで結ぶことによってできる局所的な閉路は、
適切な因子関数を定義して因子グラフに変換すれば除去されます。
この例を図5に示します。

図5
f:id:olj611:20211130024542p:plain:h230

$(a)$ は局所的な閉路を持つ有向グラフです。
$(b)$ は木構造を持つ因子グラフへの変換 $f(x_1,x_2,x_3)=p(x_1)p(x_2|x_1)p(x_3|x_1,x_2)$ です。

図6に、全結合の無向グラフと、それに対応する2つの異なる因子グラフの例を示します。
$(b)$ では同時分布は一般形 $p({\bf x})=f(x_1,x_2,x_3)$ で与えられます。
一方、 $(c)$ では同時分布はより限定された因数分解 $p(x)=f_a(x_1,x_2)f_b(x_1,x_3)f_c(x_2,x_3)$ で与えられる。
$(c)$ の形の分解が何の条件付き独立性をも表現しないことを強調しておきます。

図6
f:id:olj611:20211130033148p:plain:h200

参考文献

パターン認識と機械学習下巻 p113-p116