ベイジアンネットワークの計算アルゴリズム

ベイジアンネットワークによる確率推論は観測された変数の確定値（evidence:$e$）から， 知りたい確率変数（$X$）の確率，すなわち事後確率 $P(X\vert e)$を求め， それにより期待値や確信度最大の値（MAP値），ある仮説の確信度（いくつかの変数が 特定の値の組をとる同時確率）などを評価することである． すなわち，i) 観測された変数の値$e$をノードにセットする， ii) 親ノードも観測値も持たないノードに事前確率分布を与える， iii) 知りたい対象の変数$X$の事後確率$P(X\vert e)$を得る， という手順で計算を行なうことがベイジアンネットワークの上の確率推論である．

iii)における事後確率を求めるために，evidenceからの確率伝播(変数間の局所計算) によって各変数の確率分布を更新していくbelief propagationと呼ばれる計算が ベイジアンネットワークの上の計算アルゴリズムの特徴である．ここでは簡単な 図3の構造での計算の例を示す．

$X_j \rightarrow X_{j+1}$の条件付き依存性が成立しており，計算するノードから 先の親ノードに与えられるevidenceを$e^+$, 計算するノードから先の子ノードに 与えられるevidenceを$e^-$とする．ベイズの定理より，ノード$X_j$の確率は

$$P(X_j\vert e) = P(X_j\vert e^+,e^-)$$

$$= \frac{P(e^-\vert X_j,e^+)P(X_j\vert e^+)}{P(e^-\vert e+)}.$$

$\alpha = \frac{1}{P(e^-\vert e+)}$を$X_j$の値によらない正規化定数とし， $e^+$と$e^-$は$X_j$が与えられると条件付き独立になるので，

$$P(X_j\vert e) = \alpha P(e^-\vert X_j)P(X_j\vert e^+).$$ (2)

となる． このうち$e^+$による$X_j$への寄与分,$P(X_{j}\vert e^+)$は親ノードの確率， $P(X_{j-1}\vert e^+)$と $X_j$のCPTを使った周辺化とよぶ計算, 式(4)によって求めることができる．

$$P(X_j\vert e^+) = \sum_{X_{j}} P(X_{j}\vert X_{j-1})P(X_{j-1}\vert e^+).$$ (3)

$P(X_{j-1}\vert e^+)$は式(4)を再帰的に適用して次の親ノードとCPTから求まる ．最終的にはevidenceノードでは$e^+$，それより先に親ノードが存在しないノードの場合は 事前確率分布を代入する．

一方，子ノード側の$e^-$の寄与分，$P(e^-\vert X_j)$を計算するためには， $X_{j+1}$に関する条件付き確率 $P(X_{j+1}\vert X_j)$を使った周辺化を行なう．

$$P(e^-\vert X_j) = \sum_{X_{j+1}} P(e^-\vert X_j,X_{j+1})P(X_{j+1}\vert X_j)$$

ここで，$X_{j+1}$を固定した時には，$X_j$より下にある$e^-$は$X_j$の値に よらず独立であるから，

$$P(e^-\vert X_j) = \sum_{X_{j+1}} P(e^-\vert X_{j+1})P(X_{j+1}\vert X_j).$$ (4)

ここで， $P(e^-\vert X_{j+1})$は，式(5)を再帰的に適用していき， CPTと次の子ノードより求まる．最終的にはevidenceノードでは観測値，それより下に 子ノードを持たない最終のノードでは一様分布を代入する． したがって，以上式(4),(5)を式3に 代入して掛け合わせ$\alpha$により正規化することで，各ノード$X_j$の 事後確率$P(X_j\vert e)$が求まる(図3)．

図 3: ベイジアンネットワーク上の確率伝播

この局所的な変数間を伝播するような確率計算が繰り返し行なわれ， 観測値として確定値の代入されたevidenceを起点にしてネットワーク全体をくまなく 伝播することで各ノードの確率値が得られる．

ただし，一般的なグラフの場合にはノードには複数の親，子ノードが存在し， また観測値$e$が多数入ることもある．そのため，計算の複雑性はグラフの構造や 観測値の入り方により大きく影響を受け，高速な計算のためにはネットワーク内の伝播を 効率的に行うことが重要になる． 任意の二つのノード間にパス⁵が一つしか存在しない singly connectedグラフの場合には最悪計算量がノードの数にたいしては線形オーダー となる効率の良い確率伝播アルゴリズムが複数の研究者により提案されている [Pearl 88,Lauritzen 88]．

ノード間のパスが複数存在してもよい一般のグラフ構造, multiply connectedグラフの場合には，最悪計算量がNP困難になるという問題がある[Cooper 90]． そこで，この場合には複数のノードを併合してグラフ構造を一つのsingly connectedグラフに 変換する(clustering)，確率変数を複数の値に場合分けして，複数のsingly connectedグラフに変換する (conditioning)，モンテカルロサンプリングを行う，などの様々な近似的な解決法がある． とくに最近では，さらに現実的な計算効率の良いアルゴリズムとして，グラフをいくつかの部分的な無向グラフと それらを結合した木に変換して計算を限定的に行うjunction treeアルゴリズムと呼ばれるものが，また 理論的な近似アルゴリズムとしてvariational method(変分法) ⁶と平均場近似の応用 [Jordan 98,Wiegerinck 98,Tanaka 00]が注目されている．