変数の除去

変数消去（VE）は、ベイジアンネットワークやマルコフランダムフィールドなどの確率的グラフィカルモデルにおける単純で一般的な正確な推論アルゴリズムです。^{[1]これは、}最大事後確率（MAP）状態の推論や、変数のサブセットに対する条件付き分布または周辺分布の推定に使用できます。このアルゴリズムは指数関数的な時間計算量を持ちますが、適切な消去順序を使用すれば、実際にはツリー幅の狭いグラフに対して効率的です。

変数の因子（ポテンシャルとも呼ばれる）は、アルゴリズムの複雑さを大幅に軽減することを可能にし、変数の各インスタンスと非負の数（一般に と表記）との関係です。^[2]因子には必ずしも決まった解釈があるわけではありません。確率分布や条件付き分布など、異なる表現の因子に対して演算を実行することもできます。^[2]結合分布は、この演算の複雑さが指数関数的であるため、処理するには大きすぎることがよくあります。したがって、因数分解されたエンティティを計算するときに変数の削除がより実行可能になります。 ${\displaystyle f}$${\displaystyle V}$${\displaystyle v}$${\displaystyle f}$${\displaystyle f(x)}$

アルゴリズム1は、sum-out（SO）またはmarginalizationと呼ばれ、因子セットから1つの変数を削除し、 ^[3]結果の因子セットを返します。アルゴリズムcollect-relevantは、変数を含む因子を単に返します。 ${\displaystyle v}$${\displaystyle \phi}$${\displaystyle \phi}$${\displaystyle v}$

アルゴリズム1 sum-out( , ) ${\displaystyle v}$${\displaystyle \phi}$

${\displaystyle \Phi}$= 関連する要因を収集する${\displaystyle v}$

${\displaystyle \Psi}$= すべての因数の積${\displaystyle \Phi}$

${\displaystyle \tau =\sum _{v}\Psi }$

戻る ${\displaystyle (\phi -\Phi )\cup \{\tau \}}$

例

ここでは結合確率分布が与えられています。変数は インスタンス化の集合の間で合計することができ、その集合は残りの変数と最低でも一致する必要があります。合計される変数が である場合、の値は無関係です。 ^[2]${\displaystyle v}$${\displaystyle Vv}$${\displaystyle v}$

を除去した後、その参照は除外され、残りの変数と各インスタンス化の合計のみの分布が残ります。 ${\displaystyle V_{1}}$

合計演算の後に得られる分布は、について言及していないクエリに答えるのにのみ役立ちます。^[2]また、合計演算は可換であることにも注目すべきです。 ${\displaystyle V_{1}}$

複数の因子間の積を計算すると、各因子の単一のインスタンス化と互換性のある因子が得られる。^[2]

アルゴリズム2マルチファクタ( , ) ^[2]${\displaystyle v}$${\displaystyle \phi}$

${\displaystyle Z}$= 因子の積の間のすべての変数の和集合${\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})}$

${\displaystyle f}$=上 の因数 、すべての ${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

各インスタンスごとに${\displaystyle z}$

1から${\displaystyle m}$

${\displaystyle x_{1}=}$変数のインスタンス化は${\displaystyle X_{1}}$${\displaystyle z}$

${\displaystyle f(z)=f(z)f_{i}(x_{i})}$

戻る ${\displaystyle f}$

因数乗算は交換可能であるだけでなく結合性も備えています。

最も一般的なクエリタイプは、 の互いに素な部分集合である の形式であり、が値を取ることが観測されます。 p(X|E = e) を計算する基本的なアルゴリズムは、変数消去(VE)と呼ばれ、 で初めて提案されました。^[1]${\displaystyle p(X|E=e)}$${\displaystyle X}$${\displaystyle E}$${\displaystyle U}$${\displaystyle E}$${\displaystyle e}$

^[1]から引用したこのアルゴリズムは、離散ベイジアン ネットワーク B から計算を行います。VE は SO を呼び出して、変数を 1 つずつ削除します。より具体的には、アルゴリズム 2 では、は B の条件付き確率テーブル (以下、「CPT」) のセット C、はクエリ変数のリスト、は観測変数のリスト、は対応する観測値のリスト、は変数 の削除順序です( はを表します) 。 ${\displaystyle p(X|E=e)}$${\displaystyle \phi}$${\displaystyle X}$${\displaystyle E}$${\displaystyle e}$${\displaystyle \sigma}$${\displaystyle U-XE}$${\displaystyle XE}$${\displaystyle X\cup E}$

変数除去アルゴリズム VE( ) ${\displaystyle \phi ,X,E,e,\sigma }$

σが空でない間に適切なCPTで因数を乗算する

最初の変数を削除する${\displaystyle v}$${\displaystyle \sigma}$

${\displaystyle \phi}$= 合計${\displaystyle (v,\phi )}$

${\displaystyle p(X,E=e)}$= すべての因数の積${\displaystyle \Psi \in \phi }$

戻る ${\displaystyle p(X,E=e)/\sum _{X}p(X,E=e)}$

変数を削除する最適な順序を見つけることは NP 困難な問題です。そのため、順序によってパフォーマンスを最適化するために従うことができるヒューリスティックがあります。

1. 最小次数：可能な限り最小の因子を構成する変数を排除する。^[2]
2. 最小充填: すべてのCPTによって表現される変数関係を示す無向グラフを構築することにより、除去後に追加されるエッジが最も少なくなる変数を除去します。^[2]