Loading article…
ジャンクションツリー アルゴリズム(別名「クリーク ツリー」) は、機械学習で一般的なグラフの周辺化を抽出するために使用される方法です。本質的には、ジャンクション ツリーと呼ばれる修正されたグラフに対してビリーフ プロパゲーションを実行する必要があります。グラフは、データのさまざまなセクションに分岐するためツリーと呼ばれます。変数のノードがブランチです。[1]基本的な前提は、サイクルを単一のノードにクラスタ化することでサイクルを排除することです。複数の広範なクエリ クラスを同時にコンパイルして、より大きなデータ構造にすることができます。[1]特定のニーズや計算対象に合わせて、さまざまなアルゴリズムがあります。推論アルゴリズムは、データの新しい展開を収集し、提供された新しい情報に基づいて計算します。[2]
ジャンクションツリーアルゴリズム
Huginアルゴリズム
- グラフが有向である場合は、それを道徳化して無向にします。
- 証拠を提示してください。
- グラフを三角形に分割して弦グラフにします。
- 三角形グラフからジャンクション ツリーを構築します(ジャンクション ツリーの頂点を「スーパーノード」と呼びます)。
- ジャンクションツリーに沿って確率を伝播する（信念伝播経由）
この最後のステップは、ツリー幅の大きいグラフでは非効率的であることに注意してください。スーパーノード間で渡されるメッセージを計算するには、両方のスーパーノードの変数に対して正確な周辺化を行う必要があります。したがって、ツリー幅 k のグラフに対してこのアルゴリズムを実行すると、少なくとも 1 つの計算が必要になり、k の指数関数的な時間がかかります。これはメッセージ パッシングアルゴリズムです。[3] Hugin アルゴリズムは、Shafer-Shenoy アルゴリズムと比較して、解を見つけるのに 必要な計算が少なくなります。
シェーファー・シェノイアルゴリズム
- 再帰的に計算される[3]
- シェーファー・シェノイアルゴリズムの多重再帰は、ヒューギンアルゴリズムをもたらす[4]
- メッセージパッシング方程式[4]によって発見された
- セパレータ電位は保存されない[5]
Shafer-Shenoyアルゴリズムは、ジャンクションツリーの積和です。 [6]このアルゴリズムは、Huginアルゴリズムよりも効率的にプログラムとクエリを実行するために使用されています。 このアルゴリズムにより、信念関数の条件の計算が可能になります。[7] ローカル計算を行うには、結合分布が必要です。 [7]
基礎理論
最初のステップはベイジアン ネットワークのみに関係し、有向グラフを無向グラフに変換する手順です。方向に関係なくアルゴリズムを普遍的に適用できるようにするため、これを行います。
2 番目のステップは、変数を観測値に設定することです。これは通常、条件付き確率を計算するときに必要となるため、条件となるランダム変数の値を固定します。これらの変数は、特定の値に固定されているとも言われます。
3番目のステップは、グラフがまだ弦状でない場合は弦状になるようにすることです。これはアルゴリズムの最初の重要なステップです。次の定理を利用します: [8]
定理:無向グラフ Gの場合、次の特性は同等です。
- グラフ G は三角形に分割されます。
- G のクリークグラフにはジャンクションツリーがあります。
- G には、追加のエッジをもたらさない除去順序があります。
このように、グラフを三角形に分割することで、対応するジャンクション ツリーが存在することを確認します。これを行う通常の方法は、そのノードの削除順序を決定し、変数削除アルゴリズムを実行することです。変数削除アルゴリズムでは、異なるクエリがあるたびにアルゴリズムを実行する必要があります。[1]これにより、最初のグラフにエッジが追加され、出力が弦グラフになります。すべての弦グラフにはジャンクション ツリーがあります。[4]次の手順は、ジャンクション ツリーを構築することです。これを行うには、前の手順のグラフを使用して、対応するクリーク グラフを形成します。[9]次の定理は、ジャンクション ツリーを見つける方法を示しています。[8]
定理:三角形グラフが与えられた場合、クリーク グラフのエッジを、隣接するクリーク A と B の交差点の濃度 |A∩B| で重み付けします。すると、クリーク グラフの最大重み全域木はジャンクション ツリーになります。
したがって、ジャンクションツリーを構築するには、クリークグラフから最大重み全域木を抽出するだけでよい。これは、たとえば、クラスカルのアルゴリズムを変更することで効率的に実行できます。最後のステップは、得られたジャンクションツリーにビリーフプロパゲーションを適用することです。 [10]
使用法:ジャンクションツリーグラフは、問題の確率を視覚化するために使用されます。ツリーはバイナリツリーになり、ツリーの実際の構築を形成できます。[11]具体的な用途としては、グラフと通過ネットワークを大規模に自動的に組み合わせるオートエンコーダが挙げられます。 [12]
推論アルゴリズム
ループ型信念伝播法：複雑なグラフを解釈する別の方法。ループ型信念伝播法は、正確な解ではなく近似解が必要な場合に使用されます。[13]これは近似推論です。[3]
カットセット条件付け：より小さな変数セットで使用されます。カットセット条件付けにより、より読みやすい単純なグラフを作成できますが、正確ではありません。[3]
参考文献
- ^ abc Paskin, Mark. 「グラフィカルモデルに関する短期コース」(PDF)。スタンフォード。
- ^ 「推論アルゴリズム」www.dfki.de . 2018年10月25日閲覧。
- ^ abcd 「グラフィカルモデルの要約」（PDF）。
- ^ abc 「アルゴリズム」(PDF) .マサチューセッツ工科大学. 2014年.
- ^ Roweis, Sam (2004). 「Hugin 推論アルゴリズム」(PDF) . NYU .
- ^ 「推論のためのアルゴリズム」(PDF)。マサチューセッツ工科大学。2014年。
- ^ ab Kłopotek、Mieczysław A. (2018-06-06)。 「データから得たデンプステリアンとシャフェリアンの信念ネットワーク」。arXiv : 1806.02373 [cs.AI]。
- ^ ab Wainwright, Martin (2008年3月31日). 「グラフィカルモデル、メッセージパッシングアルゴリズム、変分法：パートI」（PDF）。Berkeley EECS 。 2016年11月16日閲覧。
- ^ 「Clique Graph」。2016年11月16日閲覧。
- ^ Barber, David (2014年1月28日). 「確率的モデリングと推論、ジャンクションツリーアルゴリズム」(PDF)。ヘルシンキ大学。 2016年11月16日閲覧。
- ^ ラミレス、ジュリオ C.、ムニョス、ギレルミナ、グティエレス、ルディビナ (2009 年 9 月)。「ベイジアン ネットワークを使用した産業プロセスにおける障害診断: ジャンクション ツリー アルゴリズムの適用」。2009エレクトロニクス、ロボティクス、自動車メカニクス カンファレンス (CERMA) 。IEEE。pp . 301– 306。doi :10.1109/ cerma.2009.28。ISBN 978-0-7695-3799-3。
- ^ Jin, Wengong (2018 年 2 月). 「分子グラフ生成のためのジャンクション ツリー変分オートエンコーダ」.コーネル大学. arXiv : 1802.04364 . Bibcode :2018arXiv180204364J.
- ^ CERMA 2009 : 議事録 : 2009 エレクトロニクス、ロボティクス、自動車メカニクス カンファレンス : 2009 年 9 月 22 ～ 25 日 : メキシコ、モレロス州クエルナバカ. 電気電子技術者協会。カリフォルニア州ロサンゼルスアラミトス: IEEE コンピュータ ソサエティ。2009 年。ISBN 9780769537993. OCLC 613519385.
{{cite book}}: CS1 メンテナンス: その他 (リンク)
さらに読む
- Lauritzen, Steffen L.; Spiegelhalter, David J. (1988). 「グラフィカル構造上の確率による局所計算とエキスパートシステムへの応用」.英国王立統計学会誌. シリーズ B (方法論) . 50 (2): 157– 224. doi :10.1111/j.2517-6161.1988.tb01721.x. JSTOR 2345762. MR 0964177.
- Dawid, AP (1992). 「確率的エキスパートシステムへの一般伝播アルゴリズムの応用」.統計とコンピューティング. 2 (1): 25– 26. doi :10.1007/BF01890546. S2CID 61247712.
- Huang, Cecil; Darwiche, Adnan (1996). 「信念ネットワークにおける推論: 手順ガイド」.国際近似推論ジャーナル. 15 (3): 225– 263. CiteSeerX 10.1.1.47.3279 . doi :10.1016/S0888-613X(96)00069-2.
- Lepar, V.、Shenoy, P. (1998)。「確率分布の周辺を計算するための Lauritzen-Spiegelhalter、Hugin、および Shenoy-Shafer アーキテクチャの比較」https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf