ベイジアンネットと確率推論 変分原理からの再帰的確率推論アルゴリズムの解説

Presentation on theme: "ベイジアンネットと確率推論 変分原理からの再帰的確率推論アルゴリズムの解説"— Presentation transcript:

1 ベイジアンネットと確率推論 変分原理からの再帰的確率推論アルゴリズムの解説
東北大学 大学院情報科学研究科 田中　和之 参考文献 田中和之・樺島祥介編, “ミニ特集/ベイズ統計・統計力学と情報処理”, 計測自動制御学会誌「計測と制御」2003年8月号． 田中和之，田中利幸，渡辺治他著，“連載/確率的情報処理と統計力学　---様々なアプローチとそのチュートリアル---”，数理科学2004年11月号から開始． NC研究会 （2004年10月18日）

2 確率的情報処理と確率伝搬法 ベイズの公式 ベイジアンネット 確率モデル 確率的情報処理 確率伝搬法 J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kaufmann, 1988). NC研究会 （2004年10月18日）

3 進化する確率伝搬法 確率伝搬法と統計力学的近似解析手法との等価性 クラスター変分法による確率伝搬法の一般化の提案
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). クラスター変分法による確率伝搬法の一般化の提案 J. S. Yedidia, W. T. Freeman and Y. Weiss, Generalized belief propagation, Advances in Neural Information Processing Systems, 13 (2001, MIT Press). 情報幾何としての確率伝搬法の解釈 S. Ikeda, T. Tanaka and S. Amari: Stochastic reasoning, free energy, and information geometry, Neural Computation, Vol.16, No.9, pp , 2004. NC研究会 （2004年10月18日）

4 本チュートリアル講演のトピックス 確率推論における確率伝搬法 確率的画像処理における確率伝搬法
K. Tanaka: “Probabilistic inference by means of cluster variation method and linear response theory”, IEICE Transactions, E86-D (2003). 確率的画像処理における確率伝搬法 K. Tanaka, H. Shouno, M. Okada and D. M. Titterington: Accuracy of the Bethe Approximation for Hyperparameter Estimation in Probabilistic Image Processing, J. Phys. A: Math. & Gen., 37 (2004). NC研究会 （2004年10月18日）

5 確率の知識（１） 事象Ａの起こる確率 事象Aと事象Bの結合確率 条件付き確率と結合確率 A B NC研究会 （2004年10月18日）

6 確率の知識（２） 結合確率分布と周辺確率分布の一般的関係 Ａ Ｂ Ｃ Ｄ 周辺化 NC研究会 （2004年10月18日）

7 簡単な確率推論 A B C A B C NC研究会 （2004年10月18日）

8 複雑になるほどノードの個数は多くなり計算困難が深刻になる
より複雑な確率推論 複雑になるほどノードの個数は多くなり計算困難が深刻になる NC研究会 （2004年10月18日）

9 より複雑な確率推論 NC研究会 （2004年10月18日）

10 周辺確率分布 信念 （Belief） NC研究会 （2004年10月18日）

11 扱い易いモデルと計算困難なモデル 閉路のないグラフ上の確率モデル どの枝もそれぞれで独立に和がとれる． 閉路のあるグラフ上の確率モデル
それぞれで独立に和をとることが困難． NC研究会 （2004年10月18日）

12 より複雑なグラフ上の確率モデル NC研究会 （2004年10月18日）

13 周辺確率分布のメッセージによる近似表現 NC研究会 （2004年10月18日）

14 メッセージの固定点方程式 確率伝搬アルゴリズム NC研究会 （2004年10月18日）

15 確率モデルとカルバックライブラー情報量 ：周辺確率分布 NC研究会 （2004年10月18日）

16 試行関数 ：周辺確率分布 NC研究会 （2004年10月18日）

17 クラスター変分法の戦略 確率分布を少数ノードからなるクラスターに対する周辺確率分布の積の形に近似する．その近似形と元々の確率分布の間のKL情報量の表式を考える． 各クラスターγに対する周辺確率分布PＱQγ(aγ)を その規格化条件とReducibility を拘束条件として D[Q|P] を最小にするように変分原理によって決定する．（注意：Q(a) の規格化条件Σa f(a)=1 は要請しない変分で得られた f(a) がD[Q|P]≧0 を満たす保証はなくなる.） NC研究会 （2004年10月18日）

18 周辺確率分布のメッセージによる近似表現 NC研究会 （2004年10月18日）

19 メッセージの固定点方程式 確率伝搬アルゴリズム NC研究会 （2004年10月18日）

20 固定点方程式と反復法 固定点方程式 反復法 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる．
NC研究会 （2004年10月18日）

21 数値実験 Belief Propagation Exact NC研究会 （2004年10月18日）

22 数値実験 確率伝搬法 NC研究会 （2004年10月18日）

23 ベイジアンネットの今後の動向 自動化が急務． パラメータのデータからの学習 EM アルゴリズム クラスター変分法の更なる拡張の試み
Region Graph Method Max-Product Method NC研究会 （2004年10月18日）

24 画像修復の確率モデル 雑音 通信路 原画像 劣化画像 NC研究会 （2004年10月18日）

25 ベイズの公式と確率的画像処理 事前確率 劣化過程 原画像 劣化画像 画素 事後確率 NC研究会 （2004年10月18日）

26 周辺尤度最大化によるハイパパラメータ推定
In the image restoration, we usually have to estimate the hyperparameters alpha and p. In statistics, the maximum likelihood estimation is often employed. In the standpoint of maximum likelihood estimation, the hyperparameters are determined so as to maximize the marginal likelihood defined by marginalize the joint probability for the original image and degraded image with respect to the original image. The marginal likelihood is expressed in terms of the partition functions of the a priori probabilistic model and the a posteriori probabilistic model. We can calculate these partition functions approximately by using the Bethe approximation. 周辺化 劣化画像 原画像 周辺尤度 NC研究会 （2004年10月18日）

27 画像修復の劣化過程と事前確率 劣化過程 事前確率 事後確率 NC研究会 （2004年10月18日）

28 周辺確率の導入 NC研究会 （2004年10月18日）

29 変分計算により得られる確率伝搬法の周辺確率密度関数の近似表式
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. NC研究会 （2004年10月18日）

30 確率伝搬法におけるメッセージ更新規則 固定点方程式 反復法 NC研究会 （2004年10月18日）
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. 固定点方程式 反復法 NC研究会 （2004年10月18日）

31 固定点方程式と反復法 固定点方程式 反復法 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる．
NC研究会 （2004年10月18日）

32 ガウシアングラフィカルモデル を用いた画像修復
原画像 劣化画像 確率伝搬法 厳密解 Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. MSE: 1512 MSE: 325 MSE:315 平滑化フィルター ウィーナーフィルター メジアンフィルター MSE: 411 MSE: 545 MSE: 447 NC研究会 （2004年10月18日）

33 ガウシアングラフィカルモデル を用いた画像修復
原画像 劣化画像 確率伝搬法 厳密解 MSE:306 MSE: 1409 MSE: 324 Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. 平滑化フィルター ウィーナーフィルター メジアンフィルター MSE: 268 MSE: 369 MSE: 259 NC研究会 （2004年10月18日）

34 確率的画像処理の今後の動向 理論的方向 実用的方向 パラメータのデータからの学習 ライン場の導入 適応画像処理フィルターへの発展 画像圧縮
領域分割 移動体検出 NC研究会 （2004年10月18日）

35 本チュートリアル講演のキーワード 確率伝搬法（Belief Propagation） 確率推論（Bayesian Network）
確率的画像処理(Markov Random Field) NC研究会 （2004年10月18日）

36 確率伝搬法の更なる応用 誤り訂正符号における低密度パリティ検査（LDPC）符号 移動体通信のCDMA復調方式
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復調方式 T. Tanaka: A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors, IEEE Transactions on Information Theory, 48 (2002). Y. Kabashima: A CDMA multiuser detection algorithm on the basis of belief propagation, J. Phys. A, 36 (2003). 充足可能性問題（SAT） 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). NC研究会 （2004年10月18日）

37 確率的情報処理の動向 田中和之・樺島祥介編著, “ミニ特集/ベイズ統計・統計力学と情報処理”, 計測自動制御学会誌「計測と制御」2003年8月号． 田中和之，田中利幸，渡辺治 他著，“連載/確率的情報処理と統計力学　---様々なアプローチとそのチュートリアル---”，数理科学2004年11月号から開始． NC研究会 （2004年10月18日）