物理フラクチュオマティクス論 Physical Fluctuomatics 第9回 確率伝搬法 9th Belief propagation 東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka) kazu@smapip.is.tohoku.ac.jp http://www.smapip.is.tohoku.ac.jp/~kazu/ 11 June, 2009 物理フラクチュオマティクス論(東北大)

田中和之著：確率モデルによる画像処理技術入門，第8章，森北出版，2006． 今回の講義の講義ノート 田中和之著：確率モデルによる画像処理技術入門，第8章，森北出版，2006． 参考文献 J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, 1988. 汪金芳, 田栗正章, 手塚集, 樺島祥介, 上田修功: 統計科学のフロンティア/計算統計 I ---確率計算の新しい手法, 岩波書店, 2003. 11 June, 2009 物理フラクチュオマティクス論(東北大)

計算困難のポイントは何か 2L 通りの和が計算できるか？ L 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法 このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分， L=30個で約12日， L=40個で約34年かかる． 厳密に計算するのは一部の特殊な例を除いて難しい． L 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法 今回 次回 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率モデルと確率伝搬法 ベイジアンネットワーク ベイズの公式 確率モデル 確率的情報処理 確率伝搬法 （Belief Propagation） J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, 1988). C. Berrou and A. Glavieux: Near optimum error correcting coding and decoding: Turbo-codes, IEEE Trans. Comm., 44 (1996). 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法と平均場理論の類似性の指摘 一般化された確率伝搬法の提案 確率伝搬法の情報幾何的解釈 確率伝搬法の定式化 Y. Kabashima and D. Saad, Belief propagation vs. TAP for decoding corrupted messages, Europhys. Lett. 44 (1998). M. Opper and D. Saad (eds), Advanced Mean Field Methods ---Theory and　Practice (MIT Press, 2001). 一般化された確率伝搬法の提案 S. Yedidia, W. T. Freeman and Y. Weiss: Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Transactions on Information Theory, 51 (2005). 確率伝搬法の情報幾何的解釈 S. Ikeda, T. Tanaka and S. Amari: Stochastic reasoning, free energy, and information geometry, Neural Computation, 16 (2004). 11 June, 2009 物理フラクチュオマティクス論(東北大)

クラスター変分法という統計物理学の手法がその一般化の鍵 統計物理学による確率伝搬法の一般化 一般化された確率伝搬法 J. S. Yedidia, W. T. Freeman and Y. Weiss: Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Transactions on Information Theory, 51 (2005). クラスター変分法という統計物理学の手法がその一般化の鍵 R. Kikuchi: A theory of cooperative phenomena, Phys. Rev., 81 (1951). T. Morita: Cluster variation method of cooperative phenomena and its generalization I, J. Phys. Soc. Jpn, 12 (1957). 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の統計物理学的位置付け 木構造を持つグラフィカルモデルではベーテ近似は転送行列法と等価である． 閉路を持つグラフィカルモデル上のベイジアンネットでの確率伝搬法はベーテ近似またはその拡張版であるクラスター変分法に等価である（Yedidia, Weiss and Freeman, NIPS2000）． ベーテ近似 転送行列法 ||（木構造） もともとの確率伝搬法 クラスター変分法 （菊池近似） 一般化された確率伝搬法 11 June, 2009 物理フラクチュオマティクス論(東北大)

一般化された確率伝搬法の応用範囲 Image Processing Low Density Parity Check Codes K. Tanaka: Statistical-mechanical approach to image processing (Topical Review), J. Phys. A, 35 (2002). A. S. Willsky: Multiresolution Markov Models for Signal and Image Processing, Proceedings of IEEE, 90 (2002). Low Density Parity Check Codes Y. Kabashima and D. Saad: Statistical mechanics of　low-density parity-check codes (Topical Review), J. Phys. A, 37 (2004). S. Ikeda, T. Tanaka and S. Amari: Information geometry of turbo and low-density parity-check codes, IEEE Transactions on Information Theory, 50 (2004). CDMA Multiuser Detection Algorithm Y. Kabashima: A CDMA multiuser detection algorithm on the basis of belief propagation, J. Phys. A, 36 (2003). T. Tanaka and M. Okada: Approximate Belief propagation, density evolution, and statistical neurodynamics for CDMA multiuser detection, IEEE Transactions on Information Theory, 51 (2005). Satisfability Problem O. C. Martin, R. Monasson, R. Zecchina: Statistical mechanics methods and phase transitions in optimization problems, Theoretical Computer Science, 265　(2001). M. Mezard, G. Parisi, R. Zecchina: Analytic and algorithmic solution of random satisfability problems, Science, 297 (2002). 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率的情報処理における計算困難の打破の戦略 を厳密に計算するのは一部の特殊な例を除いて難しい． 一部の特殊な例とは何か？ 一部の特殊な例に適用できるアルゴリズムを一般 　の場合に近似アルゴリズムとして適用できるか． → アルゴリズム化できるか？動くか？ 精度はどの程度か？ 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル どの枝もそれぞれで独立に和がとれる． x 閉路のあるグラフ上の確率モデル それぞれで独立に和をとることが困難． x 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル 1 2 3 4 5 6 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル 1 2 3 4 5 6 1 2 4 3 6 5 11 June, 2009 物理フラクチュオマティクス論(東北大)

それぞれ隣接するノードから伝搬されるメッセージの積により表される． 閉路のないグラフ上の確率モデル 1 2 3 4 5 6 ノード１と２の周辺確率分布は それぞれ隣接するノードから伝搬されるメッセージの積により表される． 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法 (Belief Propagation) 閉路のないグラフ上の確率モデル ノード１から隣接ノード２に伝搬するメッセージは（ノード２を除く）ノード１の隣接ノードからノード１に伝搬されるメッセージの積により表される． 1 2 3 4 5 6 メッセージに対する固定点方程式 (Message Passing Rule) 11 June, 2009 物理フラクチュオマティクス論(東北大)

転送行列法＝確率伝搬法（1） 1次元鎖 11 June, 2009 物理フラクチュオマティクス論(東北大)

転送行列法＝確率伝搬法（2） パスはひとつ 漸化式 11 June, 2009 物理フラクチュオマティクス論(東北大)

閉路のないグラフ上の確率伝搬法 閉路が無いことが重要!! 同じノードは２度通らない 11 June, 2009 物理フラクチュオマティクス論(東北大)

B：すべてのリンクの集合 確率伝搬法 閉路のあるグラフ上の確率モデル ３ ４ １ ２ ５ 11 June, 2009 物理フラクチュオマティクス論(東北大)

閉路のあるグラフ上の確率モデル 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ２ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム ３ ４ １ ５ メッセージに対する固定点方程式 11 June, 2009 物理フラクチュオマティクス論(東北大)

繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 固定点方程式と反復法 固定点方程式 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる． 反復法 11 June, 2009 物理フラクチュオマティクス論(東北大)

Kullback-Leibler Divergence 確率伝搬法の情報論的解釈(1) Kullback-Leibler Divergence Free Energy 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（２） Free Energy KL Divergence 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（３） Free Energy KL Divergence Bethe Free Energy 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（４） 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（５） Lagrange Multipliers to ensure the constraints 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（６） Extremum Condition 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（７） Extremum Condition 1 4 2 5 3 1 4 5 3 2 6 8 7 In the Bethe approximation, the marginal probabilities are assumed to be the following form in terms of the messages from the neighboring pixels to the pixel. These marginal probabilities satisfy the reducibility conditions at each pixels and each nearest-neighbor pair of pixels. The messages are determined so as to satisfy the reducibility conditions. 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（８） Message Update Rule 1 4 2 5 3 1 4 5 3 2 6 8 7 In the Bethe approximation, the marginal probabilities are assumed to be the following form in terms of the messages from the neighboring pixels to the pixel. These marginal probabilities satisfy the reducibility conditions at each pixels and each nearest-neighbor pair of pixels. The messages are determined so as to satisfy the reducibility conditions. 11 June, 2009 物理フラクチュオマティクス論(東北大)

= 3 1 確率伝搬法の情報論的解釈（９） Message Passing Rule of Belief Propagation 1 4 5 2 6 8 7 The reducibility conditions can be rewritten as the following fixed point equations. This fixed point equations is corresponding to the extremum condition of the Bethe free energy. And the fixed point equations can be numerically solved by using the natural iteration. The algorithm is corresponding to the loopy belief propagation. 1 3 4 2 5 1 4 2 5 3 = これはクラスター変分法のなかでもベーテ近似になる． 11 June, 2009 物理フラクチュオマティクス論(東北大)

イジング模型の確率変数の期待値 平均場近似（ワイス近似） ベーテ近似 クラスター変分法（菊池近似） 厳密解（L. Onsager） 11 June, 2009 物理フラクチュオマティクス論(東北大)

本日のまとめ 確率伝搬法 転送行列法 ベーテ近似・クラスター変分法 反復法 次回 第11回 物理モデルから見た確率的画像処理 第12回 物理モデルから見た確率推論 ---ベイジアンネット 11 June, 2009 物理フラクチュオマティクス論(東北大)

確率変数 a, b, c, d, x, y の確率分布 P(a,b,c,d,x,y) を考える． 演習問題１０-１ 確率変数 a, b, c, d, x, y の確率分布 P(a,b,c,d,x,y) を考える． 確率変数 x, y の周辺確率分布 PXY(x,y) が次のように与えられることを示せ． 11 June, 2009 物理フラクチュオマティクス論(東北大)

演習問題１０-２ 以下の形に与えられる２つの周辺確率分布 を に代入することにより次の等式 を導出せよ． 11 June, 2009 を　　　　　　　　　　　　　　　に代入することにより次の等式 を導出せよ． 11 June, 2009 物理フラクチュオマティクス論(東北大)