確率推論に対する統計力学的アプローチ ---クラスター変分法と信念伝搬アルゴリズム--- 東北大学大学院情報科学研究科 情報基礎科学専攻 田中 和之 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 クラスター変分法 確率推論と確率モデル f X f X 0 D f P f ( X ) ln V X P X f ( X ) 1 P ( X ) P( X ) ：周辺確率分布 X1 X2 V 24 13 X X \ X 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 ) P ( X , X )P ( X , X )P ( X , X ) 25 2 5 24 2 4 13 1 3 P3 ( X 3 ) P2 ( X 2 ) D f P D13 D346 D24 D25 D67 D568 D3 D4 D5 2D6 ln Z V346 X8 X1 X2 V 24 V346 V25 X6 V67 X5 X4 X6 X7 X2 X4 X3 X3 X2 X4 X3 X5 V568 X7 V13 V25 X4 X6 V67 f ( X1, X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 ) X3 X6 X5 X6 V568 X8 X5 9 クラスター変分法 クラスター変分法の戦略 •確率分布を少数ノードからなるクラスターに 対する周辺確率分布の積の形に近似する．そ の近似形と元々の確率分布の間のKL情報量の 表式を考える． D f P D13 D346 D24 D25 D67 D568 D3 D4 D5 2D6 ln Z X1 X2 V24 V13 X3 V67 X7 V346 X6 V25 X4 V568 X5 X8 •各クラスターγに対する周辺確率分布Pγ(Xγ)P2 ( X 2 ) P24 ( X 2 , X 4 ) X4 を その規格化条件とReducibility を拘束条 P25 ( X 2 , X 5 ) 件として D[P|f] を最小にするように変分原 X5 理によって決定する．（注意：f(X) の規格化条件 ΣX f(X)=1 は要請しない変分で得られた f(X) が D[P|f]≧0 を満たす保証はなくなる.） 10 確率伝搬型アルゴリズム クラスター変分法における KL情報量の極値条件 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 11 確率伝搬型アルゴリズム 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 12 確率伝搬型アルゴリズム ここまでで何が得られた か？ 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 を 計算できる． 13 線形応答理論 線形応答理論とクラスター変分法 Xi X j Xi X j XiX j lim hi 0 h i X i X j P( X ) X 確率モデル X j exphi X i P ( X ) X exp h X P ( X ) i i X X i X i P( X) X exphXi P X に対して X j の期待値 をクラスター変分法により計算することにより右辺の計算 が可能． 14 数値実験 周辺確率分布 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 15 数値実験 相関関数 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 16 まとめ 要約 確率的情報処理に対する確率伝搬アルゴリ ズムをクラスター変分法により構成し，更 に線形応答理論を用いて相関関数の計算手 法の定式化へと発展させた． 今後の課題 1. 機械学習等への応用 2. プログラム構成の完全自動化 17
© Copyright 2024 ExpyDoc
