ジャンクション ツリー

ベイジアンネットワークでの推論とインフルエンス・ダイアグラムでの推論は，ジャンクション・ツリーと呼ばれる二次構造で実行されます．ネットワークのジャンクション・ツリーは，編集モード から 実行モードに切り替えるときに生成されます．ネットワークのジャンクション・ツリーは， 表示メニューのジャンクション・ツリーを表示項目を選択して開かれる別のウィンドウに表示されます．

図１は，Asia ネットワークのジャンクション・ツリーを示します．

図 1: Asia ネットワークのジャンクション・ツリー
 

ジャンクション・ツリーが何であり，どんなことに使用できるかを理解するには，次のような記事があります．

また重要なことは，矛盾するエビデンスを検出して究明するためにジャンクション・ツリーがどのように使用できるか，ということです．

ジャンクション・ツリーとは何か?

ネットワークでの推論は，そのジャックション・ツリー表現でのメッセージ伝達の方法で行われます．ジャンクション・ツリーは，モラリゼーション（道徳化）と三角化のプロセスに関係する変換を通して得られます．それは，ベイジアンネットワークの正確な推論が，（暗黙的または明示的な）モラリゼーションと三角化を必要とすることを示します．

モラリゼーションのステップでは，まず共通の子を持つ接続されていない親ノードの各ペアの間に無向リンクを追加します．つぎに，すべての有効リンクを無向リンクに変換します．このプロセスの結果は，いわゆるモラル・グラフと呼ばれています．

三角化のステップは，結果のグラフが三角化グラフ（または弦グラフ)であるようなモラル・グラフに（無向）リンクを追加します．無向グラフとは，弦（すなわち，パスの非連続ノード間のリンク）なしで，３より大きい長さの巡回を含まない（すなわち，最初と最後のノードが同一であることを除く，離散ノードのパス）弦グラフです．グラフの最大の完全に接続されたコンポーネントまたはサブ・グラフ（すなわち，ノードの各ペアが互いに接続ｓれている）をクリークと呼びます．

ジャンクション・ツリーのノードを形成することは，三角化グラフのクリークです．各クリークは，クリークのノードのステート空間のデカルト積にわたる指標のテーブルに関係づけられています ．したがって，各クリークは，クリークのすべてのノードにわたる関数の表現を保持します．すなわち，クリークのノードにわたる結合確率分布が，クリーク・テーブル内で表現されます．

明らかに，各クリークは，より多くのノードが追加されるので，サイズが指数的に成長するテーブルに関係づけられているので，我々はクリークをできるだけ小さくしたいのです．しかしながら，さまざまな三角化の数は， ｎ階（ｎはネットワークのノード数）まであり得えて，結果のジャンクション・ツリーの表現と計算の複雑さは，さまざまな三角化でかなり変化するので，最適な三角化を発見するのはとても難しいかもしれません．実際，この最適化問題の複雑さは，NP-hard (適正な時間内では不可能なことを示す数学用語）に属します．

Hugin Decision Engine (HDE) は，さまざまな三角化アルゴリズムを提供しており，それらのほとんどは，greedy one-step look ahead （欲張りワンステップ先読み）ヒューリスティクスに基づいています．多くの場合，しかながら，最適な（近似的最適な）三角化が，実際には発見できます．HDEは，（近似的）最適三角化の手法を提供しており，それは多くの場合，他の（ヒューリスティックな）三角化手法を用いて生成されるよりも，かなり複雑さの低いジャンクション・ツリーの結果を提供します．詳細は， コンパイル 機能の説明を参照してください．

ベイジアンネットワークが切断されると，ジャンクション・ツリーも切断されることに留意してください．切断されたジャンクション・ツリーは，ジャンクション･フォレストとも呼ばれます．

ジャンクション・ツリーでの推論

上記で言及されたように，ネットワークでの推論は，ネットワークのジャンクション・ツリー表現でのメッセージ伝達に依拠します．

推論ステップ（プロパゲーション＝伝播とも呼ばれる）は，2つの主要なフェーズからなります．

あるクリークCは，Cが他の隣合うどのクリークからメッセージを受け取り，それがまだDに送られていないときは，隣のクリークDにメッセージを送ることができます．

クリークCから隣のクリークDへのメッセージは，CとDの両方のメンバーであるノードでのマージナル・テーブル（周辺表）で構成されます． より正確に言えば，メッセージは，DのメンバーでないCのノードに対応する次元を除去したCの表から計算されます．一般的に，除去は総和（加重）で実行されます．もっともよくあるコンフィギュレーション（most probable explanation (MPE)とも呼ばれる）とそのコンフィギュレーションの確率を計算するために，除去は，しかしながら，最大化を用いて実行されます．

ツールと諸機能

ジャンクション・ツリーのクリークは，（図２のような）長方形で表示されます．長方形の上部は，クリークのメンバーであるノードの一覧からなり，下部はそのクリークを根元とするサブ・ツリーで入力されたエビデンスに関する矛盾測度を示す矛盾バーからなります． データの矛盾分析の詳細は，データの矛盾分析 の節を参照してください．

図 2: Asia ジャンクション・ツリーのクリーク

クリークは，左マウスボタンをクリックして選択できます．クリークの縁を選択するとグレーから黒に変わります．シフトキーを押しながらクリックして，複数のクリークを選択することが可能です．１つまたは複数のクリークを選択すると，選択されたクリークのノードがネットワーク・パネルで選択されます．
ジャンクション・ツリー・パネルは，その他たくさんの機能を提供します．それらは，下部のツールバーとプルダウン・メニューで利用できます（図３）．

図 3: Asia ジャンクション・ツリーのクリーク

プリンタ・ボタンは，ジャンクション・ツリーを印刷することを可能にします．ジャンクション・ツリーは，プリンタまたはファイルに出力できます． ネットワークの印刷と同様，印刷ダイアログ中の"ジャンクション・ツリー"タブで適切な拡大縮小率を設定することにより，印刷を複数のページに分割することができます．

拡大鏡ボタンは，よりよい表示を得るためにズームイン，ズームアウトの機能を提供します．

記号のボタンは，異なるクリークをツリーのルートとして選択することを可能にします．この機能は，正確に1つのクリークが選択されているときだけ可能です．異なるクリークをルートとして選択することは，ローカルな矛盾を調査することに役立ちます．

記号のボタンは，全体の矛盾測度が正値であるときに使用できます．詳細は，データの矛盾分析 を参照してください．

記号のボタンは，通常の総和伝播機能を提供します．

記号のボタンは，このページとデータの矛盾分析の節と同じ情報を提供するヘルプ・ページを起動します．

エビデンスは，エビデンス･ノードをハイライトさせる（それらのノード記号の色がエビデンスの色に変わる）ことで示されます．エビデンス・ノードを表示するために，2つのモードがあります．エビデンス・ノードのすべてのインスタンスがハイライトされるか，エビデンスが入力された場所のクリーク内に現れるそれらのインスタンスのみのいずれかです．（ノードは複数のクリークのメンバーであり得ることに注意．）好みの表示モードの選択のために，プルダウン・メニュー（上記参照）が提供されています．

Back

翻訳者：多田くにひろ（マインドウェア総研）