物理フラクチュオマティクス論 Physical Fluctuomatics 第9回 確率伝搬法 9th Belief propagation

Slides:



Advertisements
Similar presentations
PRML読書会第11回 8.4 グラフィカルモデルによる推論 SUHARA YOSHIHIKO (id:sleepy_yoshi)
Advertisements

第 5 章 2 次元モデル Chapter 5 2-dimensional model. Contents 1.2 次元モデル 2-dimensional model 2. 弱形式 Weak form 3.FEM 近似 FEM approximation 4. まとめ Summary.
菊池自由エネルギーに対する CCCPアルゴリズムの拡張
多数の疑似システムを用いた システム同定の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
Approximation of k-Set Cover by Semi-Local Optimization
クラスター変分法と確率的情報処理 --Belief Propagation と画像処理アルゴリズム--
確率モデルによる 画像処理技術入門 --- ベイズ統計と確率的画像処理 ---
統計力学と情報処理 ---自由エネルギーの生み出す新しい情報処理技術--- 2003年8月12日前半
確率モデルによる画像処理における統計的学習理論
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Practice (2014年4月)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎 第1部講義(2009年4月)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Practice (2012年4月)
点素パス問題に対するアルゴリズム 小林 佑輔 東京大学 大学院情報理工学系研究科 組合せ最適化セミナー 2012 年 7月 13日
正規分布における ベーテ近似の解析解と数値解 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
はじめに: 平均場理論を用いた情報処理の最近の動向
領域ベースの隠れ変数を用いた画像領域分割
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
確率伝搬法と量子系の平均場理論 田中和之 東北大学大学院情報科学研究科
統計力学と情報処理 ---自由エネルギーの生み出す新しい情報処理技術--- 2003年8月14日後半
確率的情報処理と確率伝搬法によるアルゴリズム設計の数理構造
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 2(2014年4月)
ベイジアンネットと確率推論 変分原理からの再帰的確率推論アルゴリズムの解説
物理フラクチュオマティクス論 Physical Fluctuomatics 第9回 確率伝搬法 9th Belief propagation
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Practice (2013年4月)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
量子系における 確率推論の平均場理論 田中和之 東北大学大学院情報科学研究科
電気・通信・電子・情報工学実験D 確率的情報処理の基礎 第1部講義(2006年4月17日,4月18日,4月25日,5月9日)
科研費特定領域研究 「確率的情報処理への統計力学的アプローチ」平成16年度第2回公開シンポジューム “確率推論の数理”
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
確率的情報処理の最近の動向 東北大学 大学院情報科学研究科 田中 和之
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
統計解析 第1回 条件付き独立性と確率的グラフィカルモデル 本講義の全体像
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
確率を手なづける秘伝の計算技法 ~古くて新しい確率・統計モデルのパラダイム~ その2:ベイジアンネットと確率推論の数理
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Practice (2015年4月)
ガウシアン確率伝搬法の 近似精度に対する理論解析
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 4 (2015年4月)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
物理フラクチュオマティクス論 応用確率過程論 (2006年5月9日)
確率的画像処理アルゴリズム入門 東北大学 大学院情報科学研究科 田中 和之
確率の生み出す新しい情報処理技術 東北大学 大学院情報科学研究科 田中 和之
東北大 情報科学 田中和之,吉池紀子 山口大 工 庄野逸 理化学研究所 岡田真人
確率モデルを用いた 情報通信技術入門 ー誤り訂正符号を中心にー
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 5 (2012年4月)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 3 (2013年4月)
ポッツスピン型隠れ変数による画像領域分割
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
物理フラクチュオマティクス論 応用確率過程論 (2006年4月11日)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
統計力学と情報処理 ---自由エネルギーの生み出す新しい情報処理技術--- 2003年8月14日前半
領域ベースの隠れ変数を用いた決定論的画像領域分割
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
ゆらぎが生み出す新しい情報処理技術 確率伝搬法と確率的画像処理
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 5 (2013年4月)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 1(2013年4月)
Q状態イジング模型を用いた多値画像修復における 周辺尤度最大化によるハイパパラメータ推定
ガウシアングラフィカルモデルにおける一般化された確率伝搬法
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 4 (2012年4月)
電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Practice (2019年4月)
Time Reversal E-Text: pp.80-83(PDF: pp.49-50) FM08002 太神 諭
Presentation transcript:

物理フラクチュオマティクス論 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 ノード1と2の周辺確率分布は それぞれ隣接するノードから伝搬されるメッセージの積により表される. 11 June, 2009 物理フラクチュオマティクス論(東北大)

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

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

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

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

B:すべてのリンクの集合 確率伝搬法 閉路のあるグラフ上の確率モデル 3 4 1 2 5 11 June, 2009 物理フラクチュオマティクス論(東北大)

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

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

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

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

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

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

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

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

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

確率伝搬法の情報論的解釈(8) 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 確率伝搬法の情報論的解釈(9) 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) を考える. 演習問題10-1 確率変数 a, b, c, d, x, y の確率分布 P(a,b,c,d,x,y) を考える. 確率変数 x, y の周辺確率分布 PXY(x,y) が次のように与えられることを示せ. 11 June, 2009 物理フラクチュオマティクス論(東北大)

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