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

田中和之著：確率モデルによる画像処理技術入門，第8章，森北出版，2006． 今回の講義の講義ノート 参考文献 田中和之著：確率モデルによる画像処理技術入門，第8章，森北出版，2006． 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009. 物理フラクチュオマティクス論(東北大)

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

確率モデルと確率伝搬法 ベイジアンネットワーク ベイズの公式 確率モデル 確率的情報処理 確率伝搬法 （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). 物理フラクチュオマティクス論(東北大)

確率伝搬法と平均場理論の類似性の指摘 一般化された確率伝搬法の提案 確率伝搬法の情報幾何的解釈 確率伝搬法の定式化 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). 物理フラクチュオマティクス論(東北大)

クラスター変分法という統計物理学の手法がその一般化の鍵 統計物理学による確率伝搬法の一般化 一般化された確率伝搬法 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). 物理フラクチュオマティクス論(東北大)

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

一般化された確率伝搬法の応用範囲 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). 物理フラクチュオマティクス論(東北大)

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

扱いやすい確率モデルのグラフ表現 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B B C D E A B B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B B C D E A B B C D E A B 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B B C D E A B B C D E A B A B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B C C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B C C D E X A B C C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B C C D E X A B C C D E B C 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E X A B C C D E X A B C C D E B C B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E A B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E A B C D E B C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E A B C D E B C D E C D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A B C D E A B C D E B C D E C D E D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A D C E B F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F A D C E B F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F A D D C E C E B F F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F A D D C E C E B F F D C E F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F A D D C E C E B F F D E C E F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 A D C E B F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 ＝ A D C E B F A D E C E E F B 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 ＝ ＝ A D C E B F A D E C E E F B D E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 ＝ ＝ ＝ A D C E B F A D E C E E F B D 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 ＝ ＝ ＝ A D C E B F A C D E C E C B E 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 ＝ ＝ メッセージに 対する漸化式 A D D C E C E B F 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 Step 1 Step 2 Step 3 A D C E B F B C 物理フラクチュオマティクス論(東北大)

扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 Step 1 Step 2 Step 3 A D C E B F A D 物理フラクチュオマティクス論(東北大)

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

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

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

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

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

確率的画像処理における 確率伝搬法(Belief Propagation) 物理フラクチュオマティクス論(東北大)

正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation) 着目画素とその近傍画素だけを残すと木構造になる． 物理フラクチュオマティクス論(東北大)

正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation) 着目画素とその近傍画素だけを残すと木構造になる． 確率伝搬法(Belief Propagation)の統計的近似アルゴリズムとしての転用 物理フラクチュオマティクス論(東北大)

周辺確率(Marginal Probability) 物理フラクチュオマティクス論(東北大)

周辺確率(Marginal Probability) 2 物理フラクチュオマティクス論(東北大)

周辺確率(Marginal Probability) 2 2 物理フラクチュオマティクス論(東北大)

周辺確率(Marginal Probability) 物理フラクチュオマティクス論(東北大)

周辺確率(Marginal Probability) 1 2 物理フラクチュオマティクス論(東北大)

周辺確率(Marginal Probability) 1 2 1 2 物理フラクチュオマティクス論(東北大)

正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation) 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. 物理フラクチュオマティクス論(東北大)

正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation) 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. 1 4 5 3 2 6 8 7 物理フラクチュオマティクス論(東北大)

正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation) 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. 2 1 7 6 8 1 4 5 3 2 6 8 7 物理フラクチュオマティクス論(東北大)

正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation) 3 2 1 5 4 Message Update Rule 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. 2 1 7 6 8 1 4 5 3 2 6 8 7 物理フラクチュオマティクス論(東北大)

閉路のあるグラフ上の確率モデル の確率伝搬法(Belief Propagation) 3 2 1 5 4 2 1 3 4 5 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム 物理フラクチュオマティクス論(東北大)

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

閉路のあるグラフ上の確率モデル の確率伝搬法(Belief Propagation) 3 2 1 5 4 2 1 3 4 5 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム メッセージに対する固定点方程式 平均，分散,共分散はこのメッセージを使ってあらわされる 物理フラクチュオマティクス論(東北大)

Fixed Point Equation and Iterative Method 物理フラクチュオマティクス論(東北大)

Fixed Point Equation and Iterative Method 物理フラクチュオマティクス論(東北大)

Fixed Point Equation and Iterative Method 物理フラクチュオマティクス論(東北大)

Fixed Point Equation and Iterative Method 物理フラクチュオマティクス論(東北大)

Fixed Point Equation and Iterative Method 物理フラクチュオマティクス論(東北大)

Fixed Point Equation and Iterative Method 物理フラクチュオマティクス論(東北大)

Fixed Point Equation and Iterative Method 物理フラクチュオマティクス論(東北大)

確率的画像処理における 確率伝搬アルゴリズムの基本構造 ４近傍の場合は3入力1出力の更新式 ひとつの画素ごとに４種類の更新パターン 画素上での 動作の様子 の一例 物理フラクチュオマティクス論(東北大)

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

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

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

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

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

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

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

確率伝搬法の情報論的解釈（７） 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. 物理フラクチュオマティクス論(東北大)

確率伝搬法の情報論的解釈（８） 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. 物理フラクチュオマティクス論(東北大)

= 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 = これはクラスター変分法のなかでもベーテ近似になる． 物理フラクチュオマティクス論(東北大)

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

本日のまとめ 確率伝搬法 転送行列法 ベーテ近似・クラスター変分法 反復法 次回 第10回 確率的画像処理と確率伝搬法 第11回 確率推論におけるベイジアンネットと確率伝搬法 物理フラクチュオマティクス論(東北大)

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

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

演習問題9－3 非線形方程式 x=tanh(Cx) を反復法を用いて数値的に解くプログラムを作成し，C=0.5, 1.0, 2.0 に対する解を求めよ．また C=0.5, 1.0, 2.0 のそれぞれに対して y=tanh(Cx) と y=x のグラフを書き，C の値により非線形方程式 x=tanh(Cx) がどのような解を持ち，初期値 x0 により反復法がどのような解に収束するかについて議論せよ． 物理フラクチュオマティクス論(東北大)