クラスター変分法にもとづく 確率伝搬型アルゴリズムの 性能評価 東北大学大学院情報科学研究科 情報基礎科学専攻 田中 和之 Kazuyuki Tanaka [email protected] 1 目次 1. 2. 3. 4. 5. 6. 7. 序論 確率的推論 クラスター変分法 確率伝搬型アルゴリズム 線形応答理論 数値実験 まとめ 2 序論 確率的推論と確率伝搬アルゴリズム ベイズの公式 確率的推論機構 確率モデル 信念 (Belief) 周辺確率分布 ループのある （木構造を持たない） 確率モデルでは 厳密ではないが 結果はでる． Belief Propagation ループのない （木構造を持つ） 確率モデルでは 厳密 一般論の必要性 3 序論 統計力学と確率伝搬型アルゴリズム Belief Propagation (Lauritzen, Pearl) ループのない確率モデルでは厳密 ループのある確率モデルでも使える ループのない確率モデル 転送行列法と Belief Propagation とは等価 転送行列法 周辺確率分布に対する漸化式 ループのある確率モデル ベーテ近似，菊池近似 クラスター変分法 4 序論 本講演の目的 •グラフィカルモデルを用いた確率的推 論機構と統計力学的モデルの関連． •クラスター変分法を用いた確率伝搬ア ルゴリズムの概説． •線形応答定理（久保公式）を用いた相 関関数． 5 確率的推論 確率的推論とベイジアンネット 6 確率的推論 確率的推論と確率モデル X1 X2 V24 V13 X3 V67 X7 V346 X6 X4 V568 P( X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 ) 1 V568 ( X 8 | X 5 , X 6 ) Z V25 V346 ( X 6 | X 3 , X 4 ) V67 ( X 7 | X 6 )V25 ( X 5 | X 2 ) X5 V24 ( X 4 | X 2 )V13 ( X 3 | X1 ) V1 ( X1 )V2 ( X 2 ) X8 7 確率的推論 確率モデルと信念(Belief) P( X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 ) Pi ( X i ) X \ Xi X1 V 24 V13 X3 V67 X7 (i 1,2,3,4,5,6,7,8) X2 V346 X6 確率・統計：周辺確率分布 V25 X4 V568 X8 X5 統計力学：１体分布関数 確率的推論：信念（Belief） 8 クラスター変分法 確率的推論と確率モデル P( X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 ) P568 ( X 5 , X 6 , X 8 ) P346 ( X 3 , X 4 , X 5 ) P67 ( X 6 , X 7 ) P6 ( X 6 ) 2 P5 ( X 5 ) P4 ( X 4 ) P25 ( X 2 , X 5 ) P24 ( X 2 , X 4 ) P13 ( X 1 , X 3 ) P3 ( X 3 ) P2 ( X 2 ) P ( X ) P( X ) X \ X ：周辺確率分布 X1 X2 V 24 V13 X3 V67 X7 V346 X6 V25 X4 V568 X8 X5 9 クラスター変分法 Reducibility Condition P( X ) P ( X ) X1 X2 V 24 V13 X4 X3 X3 X4 X3 X4 V346 X6 V67 X \ X X2 V25 P1 ( X 1 ) X5 X5 P13 ( X1 , X 3 ) X3 P2 ( X 2 ) P24 ( X 2 , X 4 ) X4 X6 X7 X2 X6 X6 V568 X8 X5 P25 ( X 2 , X 5 ) X5 10 クラスター変分法 確率モデルとギブス分布 exp E ( X ) P( X ) P( X1, X 2 ,, X 8 ) exp E( X ) X X1 X2 X3 V67 X7 E ( X ) lnV346 lnV568 V 24 V13 V346 X6 V25 X4 V568 X8 lnV13 lnV24 lnV25 lnV67 lnV1 lnV2 X5 11 クラスター変分法 ギブス分布と自由エネルギー exp E ( X ) arg minE ( X ) lnP( X ) P( X ) P( X ) exp E( X ) X exp E ( X ) exp E ( X ) KL P P ( X )lnP X ln 0 exp E ( X ) X exp E ( X ) X X 「カルバック・ライブラー情報量＝０」と 「自由エネルギー最小化の変分原理」は等価 12 クラスター変分法 クラスター変分法の戦略 •確率分布を少数ノードからなるクラス ターに対する周辺確率分布の積の形に近 似する．自由エネルギーの表式はこれに より周辺確率分布のみで近似的に表わさ れる． •各クラスターに対する周辺確率分布は Reducibility を拘束条件として近似自由エ ネルギーを最小にするように変分原理に よって決定する． 13 確率伝搬型アルゴリズム クラスター変分法における 自由エネルギーの極値条件 Z6 m6346 ( x6 ) Z 346 X1 X2 X3 X4 X6 V ( x 6 | x3 , x 4 ) m ( x )m ( x ) 313 3 424 4 x3 x4 m113 ( x1 ) m424 ( x4 ) m6346 ( x6 ) 統計力学：有効場 確率的推論：Message 14 確率伝搬型アルゴリズム Message による周辺確率分布の表現 P346 ( x3 , x4 , x6 ) 1 Z 346 V ( x6 | x3 , x4 )m313 ( x3 ) m424 ( x4 )m667 ( x6 )m6568 ( x6 ) X1 X2 X3 V346 X4 X6 X7 X5 X8 15 確率伝搬型アルゴリズム ここまでで何が得られた か？ P13 ( x1 , x3 ) X1 X2 V 24 V13 X3 V67 X7 V346 X6 V25 X4 V568 X8 X5 P24 ( x2 , x4 ) P346 ( x3 , x4 , x6 ) P25 ( x2 , x5 ) P568 ( x5 , x6 , x8 ) P67 ( x6 , x7 ) Reducibility により各ノードごとの Belief を 計算できる． 16 線形応答理論 線形応答理論とクラスター変分法 Xi X j Xi X j XiX j X i X j P( X ) X 確率モデル X i exp hX j P( X ) X lim h0 h exp hX j P( X ) X X i X i P( X) X exp hX j P X に対して X i の期待値 をクラスター変分法により計算することにより右辺の計算 が可能． 17 数値実験 周辺確率分布 P3 (1) 0.9896 P3 (1) 0.0104 P5 (1) 0.5500 P5 (1) 0.4500 Cluster Variation Method P8 (1) 0.5607 P8 (1) 0.4393 P3 (1) 0.9896 P3 (1) 0.0104 P5 (1) 0.5500 P5 (1) 0.4500 P8 (1) 0.5640 P8 (1) 0.4360 Exact X1 X2 V24 V13 X3 V67 X7 V346 X6 V25 X4 V568 X8 X5 18 数値実験 相関関数 X1 X 6 0.8544 X 2 X 6 0.0890 X 2 X 7 0.0828 X 3 X 8 0.1334 X1 X 6 0.8544 X 2 X 6 0.0890 X 2 X 7 0.0828 X 3 X 8 0.1402 Cluster Variation Method Exact X1 X2 V24 V13 X3 V67 X7 V346 X6 V25 X4 V568 X8 X5 19 まとめ 要約 確率的情報処理に対する確率伝搬型アルゴ リズムをクラスター変分法により構成し， 更に線形応答理論を用いて相関関数の計算 手法の定式化へと発展させた． 今後の課題 1. 一部の Belief や Correlation が厳密 計算の結果と一致しているがどのよう な場合にこのようなことが起こるの か？ 2. プログラム構成の完全自動化 20
© Copyright 2024 ExpyDoc
