パターン認識と機械学習入門 第15回 参加メモ
資料
ベイジアンネットワーク上での推論
変数消去法は効率が悪い- 計算量は O(N^2 exp(w))
- N: 変数の数、w: 変数消去の途中に出現する因子の変数の数の最大値
枝刈り
クエリ集合 Q とエビデンス集合 E が与えられたとき、- Q に含まれない葉ノード(子を持たないノード)へ向かうエッジ
- E に含まれるノードから張られたエッジ
を除去する事が出来る．
また、枝刈りの結果孤立した Q, E に含まれないノードも除去する事が出来る．
最小次数法
- 常にインタラクショングラフ上で次数が最小の変数を消去する
=> 枝刈りと最小次数法でアルゴリズムの定数倍の部分はかなり小さくなる．ただしオーダーは大きく変わらない
ジョインツリーアルゴリズム
- O(N exp(w)) の計算量で厳密な推論を行うことができる
- ファクター消去法の特別な場合
