確率的グラフィカルモデルの推論アルゴリズム
変数消去（VE）は、 ベイジアンネットワーク や マルコフ確率場 など の確率的グラフィカルモデル における、 単純かつ汎用的な 正確な推論 アルゴリズムです。 [1] 最大事後確率 （MAP）状態の推論や、変数のサブセットにおける 条件付き 分布や 周辺分布 の推定に使用できます。このアルゴリズムは指数関数的な時間計算量を持ちますが、 適切な消去順序を用いれば、 木幅 の狭いグラフに対しては実用上効率的です。
要因 アルゴリズムの複雑さを大幅に軽減する、変数の因子 （ポテンシャルとも呼ばれる）は、 変数の各インスタンス化 と非負数（一般的に と表記される）と の関係です 。 [2] 因子には必ずしも決まった解釈があるわけではありません。確率分布や条件付き分布など、異なる表現の因子に対して演算を行うこともできます。 [2] 結合分布は、この演算の複雑さが指数関数的に大きくなるため、処理するには大きすぎることがよくあります。したがって、因数分解されたエンティティを計算する際には、変数の除去がより現実的になります。 f {\displaystyle f} V {\displaystyle V} v {\displaystyle v} f {\displaystyle f} f （ × ） {\displaystyle f(x)}
基本操作
変数の合計 アルゴリズム1は、sum-out（SO）または周辺化と呼ばれ、 因子 集合 [3] から単一の変数を除去し、その結果得られた因子集合を返します。アルゴリズムcollect-relevantは、変数を含む 因子を単に返します 。 v {\displaystyle v} ϕ {\displaystyle \phi } ϕ {\displaystyle \phi } v {\displaystyle v}
アルゴリズム1 sum-out( , ) v {\displaystyle v} ϕ {\displaystyle \phi }
Φ {\displaystyle \Phi } = 関連する要因を収集する v {\displaystyle v} Ψ {\displaystyle \Psi} = すべての因数の積 Φ {\displaystyle \Phi } τ ＝ ∑ v Ψ {\displaystyle \tau =\sum _{v}\Psi } 戻る （ ϕ − Φ ） ∪ { τ } {\displaystyle (\phi -\Phi )\cup \{\tau \}}
例
ここでは結合確率分布 が 成り立つ 。変数 は、 インスタンス化の集合間で合計することができる。この場合、集合は 少なくとも残りの変数間で一致しなければならない。 の値は、 合計される変数が である場合は無関係である。 [2] v {\displaystyle v} V − v {\displaystyle Vv} v {\displaystyle v}
V 1 {\displaystyle V_{1}} V 2 {\displaystyle V_{2}} V 3 {\displaystyle V_{3}} V 4 {\displaystyle V_{4}} V 5 {\displaystyle V_{5}} P r （ 。 ） {\displaystyle Pr(.)} 真実 真実 真実 間違い 間違い 0.80 間違い 真実 真実 間違い 間違い 0.20
を除去した後 、その参照は除外され、残りの変数と各インスタンス化の合計のみの分布が残ります。 V 1 {\displaystyle V_{1}}
V 2 {\displaystyle V_{2}} V 3 {\displaystyle V_{3}} V 4 {\displaystyle V_{4}} V 5 {\displaystyle V_{5}} P r （ 。 ） {\displaystyle Pr(.)} 真実 真実 間違い 間違い 1.0
合計演算の後に得られる分布は、言及されていないクエリに答えるのにのみ役立ちます 。 [2] また、合計演算は可換であることにも注目すべきです。 V 1 {\displaystyle V_{1}}
因数乗算 複数の因子間の積を計算すると、各因子の単一のインスタンス化と互換性のある因子が得られる。 [2]
アルゴリズム2 マルチファクタ( , ) [2] v {\displaystyle v} ϕ {\displaystyle \phi }
Z {\displaystyle Z} = 因子の積の間のすべての変数の和集合 f 1 （ X 1 ） 、 。 。 。 、 f メートル （ X メートル ） {\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})} f {\displaystyle f} = 上の因数、 すべて の f {\displaystyle f} f {\displaystyle f} f {\displaystyle f} 各インスタンス化 について z {\displaystyle z} 1 ～ メートル {\displaystyle m} × 1 ＝ {\displaystyle x_{1}=} 変数のインスタンス化 は X 1 {\displaystyle X_{1}} z {\displaystyle z} f （ z ） ＝ f （ z ） f 私 （ × 私 ） {\displaystyle f(z)=f(z)f_{i}(x_{i})} 戻る f {\displaystyle f} 因数乗算は交換可能であるだけでなく結合性も備えています。
推論 最も一般的なクエリ型は という形式です。 ここで 、 と は の互いに素な部分集合であり 、 は という値を取ることが観測されます。p(X|E = e) を計算する基本的なアルゴリズムは 変数消去法 (VE)と呼ばれ、 [1] で初めて提案されました。 p （ X | E ＝ e ） {\displaystyle p(X|E=e)} X {\displaystyle X} E {\displaystyle E} あなた {\displaystyle U} E {\displaystyle E} e {\displaystyle e}
[1] から引用された このアルゴリズムは、 離散ベイジアンネットワーク B から計算を行います。VE は変数を一つずつ消去するために SO を呼び出します。より具体的には、アルゴリズム 2 において、 は B の条件付き確率表（以下「CPT」）の集合 C 、 はクエリ変数のリスト、 は観測変数のリスト、 は対応する観測値のリスト、 は 変数 の消去順序です （ただし は を表します ）。 p （ X | E ＝ e ） {\displaystyle p(X|E=e)} ϕ {\displaystyle \phi } X {\displaystyle X} E {\displaystyle E} e {\displaystyle e} σ {\displaystyle \sigma } あなた − X E {\displaystyle U-XE} X E {\displaystyle XE} X ∪ E {\displaystyle X\cup E}
変数除去アルゴリズム VE( ) ϕ 、 X 、 E 、 e 、 σ {\displaystyle \phi ,X,E,e,\sigma }
σが空でない間に適切なCPTで因数を乗算する 最初の変数を削除し ます v {\displaystyle v} σ {\displaystyle \sigma } ϕ {\displaystyle \phi } = 合計 （ v 、 ϕ ） {\displaystyle (v,\phi )} p （ X 、 E ＝ e ） {\displaystyle p(X,E=e)} = すべての因数の積 Ψ ∈ ϕ {\displaystyle \Psi \in \phi } 戻る p （ X 、 E ＝ e ） / ∑ X p （ X 、 E ＝ e ） {\displaystyle p(X,E=e)/\sum _{X}p(X,E=e)}
注文 変数を消去する最適な順序を見つけることはNP困難問題です。そのため、順序によってパフォーマンスを最適化するためのヒューリスティックがあります。
最小次数 ：可能な限り最小の因子を構成する変数を除去する。 [2] 最小充填：すべてのCPTによって表現される変数関係を示す無向グラフを構築することにより、除去後に追加されるエッジが最も少なくなる変数を除去します。 [2]
参考文献 ^ abc Zhang, Nevin L.; Poole, David ( 1994). 「ベイジアンネットワーク計算へのシンプルなアプローチ」. 第10回カナダ人工知能会議議事録 : 171–178 . 2025年 8月26日 閲覧 。 ^ abcdefgh Darwiche, Adnan (2009-01-01). ベイジアンネットワークによるモデリングと推論 . doi :10.1017/cbo9780511811357. ISBN 9780511811357 。 ^ Koller, D., Friedman, N.: 確率的グラフィカルモデル：原理と手法. MIT Press, Cambridge, MA (2009) 
