機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

ノードの連鎖から成るグラフでは、連鎖に沿ったメッセージの伝播によって、効率の良い推論ができることを確認しました。
実はより一般に、木と呼ばれる広いクラスのグラフでも同様の効率的な推論が可能です。

無向グラフの場合、木とは任意のノードの組の間に唯一の経路が存在するグラフとして定義されます。
したがって木はループを持ちません。

有向グラフの場合、木は根ノードと呼ばれる親を持たないノードを1つだけ持ち、
他のすべてのノードはそれぞれ親を1つずつ持つグラフとして定義されます。

親を2つ以上持つノードが存在しないため、有向木を無向木に変換する際、
モラル化によってリンクを付け加える必要はありません。
したがって、有向木のモラルグラフは必ず無向木となります。

有向木で表現される分布は無向木で表現される分布に簡単に変換でき、その逆も可能であることに注意が必要です。

2つ以上の親を持つノードが存在するが、任意の2ノード間の(矢印の方向を無視した)経路が
1つしかない有向グラフは多重木と呼ばれます。

以下の図3に無向木と有向木と有向多重木の例を示します。
図1で(a)が無効木、(b)が有向木、(c)が有向多重木です。

図1
f:id:olj611:20211003120451p:plain:h200

参考文献

パターン認識機械学習 下巻 p112-p113

目次へ戻る