Chow-Liu ツリー

Chow-Liu tree は すべてのエッジがルートから離れる方向に向かう"best possible" なツリー型の信念ネットワーク近似である．近似の品質は，真の分布とChow-Liu ツリーによって定義された分布の間のKullback-Leibler 距離を用いて測定される．データから学習する場合，"真の" 分布はオブザベーションの度数で定義される．

Chow と Liu (1968) は，最適ツリーがすべての変数上の最大重みスパンニング・ツリーとして見つけられることを示した．ここで，各エッジの重みは，エッジによって接続されている変数間の相互情報として与えられる．

Chow-Liuツリーは，以下のようにして構築できる：

• 各対 (X_i, X_j) についての相互情報MI(X_i, X_j) を計算する．
• 完全な MI-重みつきグラフを考える： {X,...,X_n} 上の完全無向グラフ．ここで，リンク (X_i, X_j) は重み MI(X_i, X_j) を持つ．
• 完全MI-重みつきグラフについて最大重みスパンニング・ツリーを構築する．
• どれかの変数をルートとして選んで，それから外へ向かうリンクの方向設定して，結果ツリーを方向づける．

参考文献

• C. K. Chow, C. N. Liu (1968). Approximating Discrete Probability Distributions with Dependence Trees.