ジャンクションツリーアルゴリズム
ジャンクションツリーの例

ジャンクションツリーアルゴリズム（別名「クリークツリー」）は、機械学習において一般的なグラフの周辺化を抽出するために使用される手法です。本質的には、ジャンクションツリーと呼ばれる修正されたグラフ上でビリーフプロパゲーションを実行することを意味します。グラフがツリーと呼ばれるのは、データの異なるセクションに分岐するためです。変数のノードが分岐となります。[ 1 ]基本的な前提は、サイクルを単一のノードにクラスタリングすることでサイクルを排除することです。複数の広範なクエリクラスを同時にコンパイルして、より大きなデータ構造にすることができます。[ 1 ]特定のニーズや計算内容に合わせて、さまざまなアルゴリズムが存在します。推論アルゴリズムは、データの新しい展開を収集し、提供された新しい情報に基づいて計算を行います。[ 2 ]

ジャンクションツリーアルゴリズム

Huginアルゴリズム

この最後のステップは、木幅の大きいグラフでは非効率的であることに注意してください。スーパーノード間で渡されるメッセージを計算するには、両方のスーパーノードの変数に対して正確な周辺化を行う必要があります。したがって、木幅kのグラフに対してこのアルゴリズムを実行すると、少なくとも1つの計算が必要になり、その時間はkの指数関数的になります。これはメッセージパッシングアルゴリズムです。[ 3 ] Huginアルゴリズムは、Shafer-Shenoyアルゴリズムと比較して、解を見つけるのに必要 な計算回数が少なくなります。

シェーファー・シェノイアルゴリズム

Shafer-Shenoyアルゴリズムは、ジャンクションツリーの積和である。 [ 6 ] Huginアルゴリズムよりもプログラムとクエリを効率的に実行できるため、このアルゴリズムが使用される。このアルゴリズムは、確信関数の条件文の計算を可能にする。[ 7 ] 局所的な計算を行うには、結合分布が必要である。 [ 7 ]

基礎理論

動的ベイジアンネットワークの例

最初のステップはベイジアンネットワークにのみ関係し、有向グラフを無向グラフに変換する手順です。これは、方向に関係なくアルゴリズムを普遍的に適用できるようにするためです。

2つ目のステップは、変数を観測値に設定することです。これは通常、条件付き確率を計算する際に必要となるため、条件付けする確率変数の値を固定します。これらの変数は、特定の値に固定されているとも呼ばれます。

弦グラフの例

3番目のステップは、グラフがまだ弦状でない場合、弦状になるようにすることです。これはアルゴリズムの最初の重要なステップです。このステップでは、次の定理が用いられます。[ 8 ]

定理:無向グラフ Gの場合、次の特性は同等です。

  • グラフ G は三角形に分割されます。
  • G のクリーク グラフにはジャンクション ツリーがあります。
  • G には、追加のエッジを生じない消去順序があります。

このように、グラフを三角形に分割することで、対応するジャンクション ツリーが存在することを確認します。これを行う通常の方法は、そのノードの削除順序を決定し、変数削除アルゴリズムを実行することです。変数削除アルゴリズムでは、異なるクエリがあるたびにアルゴリズムを実行する必要があります。[ 1 ]これにより、最初のグラフにエッジが追加され、出力が弦グラフになります。すべての弦グラフにはジャンクション ツリーがあります。[ 4 ]次のステップは、ジャンクション ツリーを構築することです。そのためには、前のステップのグラフを使用し、対応するクリーク グラフを形成します。[ 9 ]次の定理は、ジャンクション ツリーを見つける方法を示しています。[ 4 ]

定理:三角形グラフが与えられた場合、クリーク グラフのエッジを、隣接するクリーク A と B の交差点のカーディナリティ |A∩B| で重み付けします。すると、クリーク グラフの任意の最大重み全域木はジャンクション ツリーになります。

したがって、ジャンクションツリーを構築するには、クリークグラフから最大重み全域木を抽出するだけでよい。これは、例えばクラスカルのアルゴリズムを修正することで効率的に行うことができる。最後のステップは、得られたジャンクションツリーにビリーフプロパゲーションを適用することである。 [ 10 ]

用途：ジャンクションツリーグラフは、問題の確率を視覚化するために使用されます。この木は二分木になり、実際の木の構成を形作ることができます。[ 11 ]具体的な用途としては、グラフと通過ネットワークを大規模に自動的に組み合わせるオートエンコーダが挙げられます。 [ 12 ]

推論アルゴリズム

カットセットコンディショニング

ループ型信念伝播法：複雑なグラフを解釈するための別の手法。ループ型信念伝播法は、正確な解ではなく近似解が必要な場合に用いられる。[ 13 ]これは近似推論である。[ 3 ]

カットセット条件付け：変数の集合が小さい場合に用いられる。カットセット条件付けは、より読みやすいシンプルなグラフを作成することができるが、正確ではない。[ 3 ]

参考文献

  1. ^ a b cパスキン、マーク。「グラフィカルモデルの短期コース」（PDF）。スタンフォード。
  2. ^ 「推論アルゴリズム」www.dfki.de . 2018年10月25日閲覧。
  3. ^ a b c d「グラフィカルモデルの要約」（PDF）。
  4. ^ a b c d「アルゴリズム」（PDF） .マサチューセッツ工科大学. 2014年.
  5. ^ Roweis, Sam (2004). 「Hugin推論アルゴリズム」(PDF) . NYU .
  6. ^ 「推論のためのアルゴリズム」（PDF）マサチューセッツ工科大学。2014年。
  7. ^ a b Kłopotek、Mieczysław A. (2018-06-06)。 「データから得たデンプステリアンとシャフェリアンの信念ネットワーク」。arXiv : 1806.02373 [ cs.AI ]。
  8. ^バートレット、ピーター（2003年10月）「無向グラフィカルモデル：弦グラフ、分解可能グラフ、ジャンクションツリー、および因数分解」（PDF）バークレー。2025年12月14日閲覧。
  9. ^ 「Clique Graph」 . 2016年11月16日閲覧。
  10. ^ Barber, David (2014年1月28日). 「確率的モデリングと推論、ジャンクションツリーアルゴリズム」(PDF) .ヘルシンキ大学. 2016年11月16日閲覧。
  11. ^ラミレス、ジュリオ・C.、ムニョス、ギレルミナ、グティエレス、ルディビナ（2009年9月）。「ベイジアンネットワークを用いた産業プロセスにおける故障診断：ジャンクションツリーアルゴリズムの応用」。2009年エレクトロニクス、ロボティクス、自動車機械学会（CERMA） IEEE、pp.  301– 306. doi : 10.1109/cerma.2009.28 . ISBN 978-0-7695-3799-3。
  12. ^ Jin, Wengong (2018年2月). 「分子グラフ生成のためのジャンクションツリー変分オートエンコーダ」.コーネル大学. arXiv : 1802.04364 . Bibcode : 2018arXiv180204364J .
  13. ^ CERMA 2009 : proceedings : 2009 Electronics, Robotics and Automotive Mechanics Conference : 22-25 September 2009 : Cuernavaca, Morelos, Mexico . Institute of Electrical and Electronics Engineers. Los Alamitos, California: IEEE Computer Society. 2009. ISBN 9780769537993. OCLC  613519385 .{{cite book}}: CS1 メンテナンス: その他 (リンク)

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Junction_tree_algorithm&oldid=1327530853」から取得