確率的情報処理と確率伝搬法によるアルゴリズム設計の数理構造

Presentation on theme: "確率的情報処理と確率伝搬法によるアルゴリズム設計の数理構造"— Presentation transcript:

1 確率的情報処理と確率伝搬法によるアルゴリズム設計の数理構造
東北大学 大学院情報科学研究科 田中 和之 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

2 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

3 確率的情報処理 不確実性の数学的表現→確率・統計 不確実性を伴うデータに耐えうる推論システム
モデル化 ネットワーク構造をもつ 数理モデル 確率的情報処理 頂点(Node)は事象・状態変数， 辺は結合確率 矢印は条件付き確率に対応 不確実性を伴うデータに耐えうる推論システム 単純な機能を持つたくさんの要素が関連し合い，互いに協力して複雑・高度な機能を生み出す． 重要な概念のひとつ 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

4 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

5 次世代情報処理技術とその応用＠早稲田大学研究開発センター
結合確率と条件付き確率 確率変数(Random Variable) 確率分布(Probability Distribution) 事象A=aの起こる確率 事象 A=a と事象 B=b の結合確率 状態変数(State Variable) 結合確率分布(Joiint Probability Distribution) 条件付き確率と結合確率 a b 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

6 次世代情報処理技術とその応用＠早稲田大学研究開発センター
結合確率と事象の独立性 確率変数A と Bが互いに独立である 確率変数A と B が互いに独立であるときの 条件付き確率 a b a b 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

7 次世代情報処理技術とその応用＠早稲田大学研究開発センター
周辺確率 確率変数Aの標本空間ΩAが互いに排反であるM 個の事象 A=0,A=1,…, A=M-1 によって ΩA =(A=0)∪ (A=1) ∪…∪ (A=M-1) と表されるとき a b Message a b = 結合確率 Pr{A=a,B=b} における事象 B=b の周辺確率　(Marginal Probability) 周辺化 (Marginalize) 簡略表記 事象 A の取り得るすべての互いに排反な状態についての和 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

8 次世代情報処理技術とその応用＠早稲田大学研究開発センター
結合確率と周辺確率 確率変数 B の周辺確率 a b a b Hyperedge Message c d c d 周辺化 Marginalize ハイパーグラフ (Hypergraph) 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

9 ベイズの公式(Bayes Formulas)
ベイジアンネットワーク a b 事後確率 (Posterior Probability) 事前確率 (Prior Probability) 周辺尤度(Marginal Likelihood) 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

10 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

11 次世代情報処理技術とその応用＠早稲田大学研究開発センター
画像修復の確率モデル 雑音 通信路 原画像 劣化画像 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

12 次世代情報処理技術とその応用＠早稲田大学研究開発センター
確率的情報処理における事前確率 xi xj xi xj x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 原画像の i 番目の画素の階調値 に対する状態変数 xi 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

13 加法的白色ガウスノイズ(Additive White Gaussian Noise)
劣化過程 加法的白色ガウスノイズ(Additive White Gaussian Noise) xi yi X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 原画像の i 番目の 画素の階調値に 対する状態変数 xi 劣化画像の i 番目の 画素の階調値に 対する状態変数 yi xi yi 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

14 ベイズ統計と画像処理 事前確率 劣化画像 原画像 事後確率 画像処理は平均，分散，共分散の計算に帰着 加法的白色ガウス雑音
または２元対称通信路 劣化画像 原画像 事後確率 画像処理は平均，分散，共分散の計算に帰着 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

15 Statistical Estimation of Hyperparameters
Hyperparameters a, s are determined so as to maximize the marginal likelihood Pr{Y=y|a,s} with respect to a, s. EM (Expectation Maximization) Algorithm Degraded Image Original Image 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. Marginalized with respect to X Marginal Likelihood 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

16 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

17 Gaussian Graphical Model (Gauss Markov Random Fields)
Multidimensional Gauss Integral Formulas Maximum Likelihood Estimation  EM Algorithm 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

18 次世代情報処理技術とその応用＠早稲田大学研究開発センター
1次元信号に対する例 127 255 100 200 Original Signal Degraded Signal Estimated Signal EM Algorithm 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

19 Bayesian Image Analysis by Gaussian Graphical Model
Iteration Procedure of EM algorithm in Gaussian Graphical Model EM 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. 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

20 Image Restoration by Gaussian Graphical Model and Conventional Filters
Degraded Image (s=40) MSE Gaussian Graphical Model 315 Lowpass Filter (3x3) 388 (5x5) 413 Median Filter 486 445 Original Image V:Set of all the pixels 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. Gaussian Graphical Model (3x3) Lowpass (5x5) Median 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

21 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

22 次世代情報処理技術とその応用＠早稲田大学研究開発センター
計算困難のポイントは何か 2N 通りの和が計算できるか？ このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分， L=30個で約12日， L=40個で約34年かかる． 厳密に計算するのは一部の特殊な例を除いて難しい． N 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法 今回 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

23 周辺確率(Marginal Probability)
を厳密に計算するのは一部の特殊な例を除いて難しい． 一部の特殊な例とは何か？ 一部の特殊な例に適用できるアルゴリズムを一般 　の場合に近似アルゴリズムとして適用できるか． → アルゴリズム化できるか？動くか？ 精度はどの程度か？ 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

24 次世代情報処理技術とその応用＠早稲田大学研究開発センター
扱いやすい確率モデルのグラフ表現 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

25 次世代情報処理技術とその応用＠早稲田大学研究開発センター
扱いやすい確率モデルのグラフ表現 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 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

26 次世代情報処理技術とその応用＠早稲田大学研究開発センター
扱いやすい確率モデルのグラフ表現 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 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

27 次世代情報処理技術とその応用＠早稲田大学研究開発センター
扱いやすい確率モデルのグラフ表現 a b c d e a b c d e b c d e c d e d e 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

28 次世代情報処理技術とその応用＠早稲田大学研究開発センター
扱いやすい確率モデルのグラフ表現 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 f 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

29 確率的画像処理における 確率伝搬法(Belief Propagation)
着目画素とその近傍画素だけを残すと木構造になる． 確率伝搬法(Belief Propagation)の統計的近似アルゴリズムとしての転用 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

30 周辺確率(Marginal Probability)
2 2 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

31 周辺確率(Marginal Probability)
1 2 1 2 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

32 確率的画像処理における 確率伝搬法(Belief Propagation)
3 1 2 4 1 2 5 Message Update Rule 8 1 2 6 7 3 8 1 4 5 2 6 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. 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

33 閉路のあるグラフ上の確率モデル の確率伝搬法(Belief Propagation)
3 2 1 5 4 3 4 1 2 5 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム メッセージに対する固定点方程式 平均，分散,共分散はこのメッセージを使ってあらわされる 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

34 Fixed Point Equation and Iterative Method
10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

35 確率的画像処理における 確率伝搬アルゴリズムの基本構造
４近傍の場合は3入力1出力の更新式 ひとつの画素ごとに４種類の更新パターン 画素上での 動作の様子 の一例 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

36 確率伝搬法(Belief Propagation) とEMアルゴリズム
Input Update Rule of BP ２ １ ３ ４ ５ BP EM Output 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

37 Maximization of Marginal Likelihood by EM Algorithm
Exact 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. Loopy Belief Propagation 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

38 Image Restoration by Gaussian Graphical Model
Original Image Degraded Image Belief Propagation Exact MSE: 1512 MSE:325 MSE:315 Lowpass Filter Wiener Filter Median Filter 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: 411 MSE: 545 MSE: 447 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

39 Digital Images Inpainting based on MRF
Markov Random Field Input Output M. Yasuda, J. Ohkubo and K. Tanaka: Proceedings of CIMCA&IAWTIC2005. 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

40 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

41 Mean Square Error の標本平均 Additive White Gaussian Noise
標本平均による統計的性能 Mean Square Error の標本平均 スピングラス理論による解析的評価が可能 Additive White Gaussian Noise Posterior Probability 脳の物理モデル の記憶容量， パーセプトロンの容量 の評価に類似の議論 Signal Observed Data Estimated Results 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

42 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Statistical Performance Estimation in Image Restoration for Bayesian Image Analysis Mean Square Error Spin Glass Theory in Statistical Mechanics s=40 s=1 a a 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

43 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

44 Belief Propagation for Bayesian Networks
10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

45 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Factor Graph Representations of Bayesian Networks and Belief Propagations 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

46 Error Correcting Codes and Belief Propagation
Fundamental Concept for Turbo Codes and LDPC Codes 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

47 Satisfactory Problem (3-SAT)
10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

48 次世代情報処理技術とその応用＠早稲田大学研究開発センター
Contents 序論 ベイズ統計の基礎 確率的画像処理 ガウシアングラフィカルモデル 確率伝搬法 統計的性能評価 さまざまのベイジアンモデリング まとめと展開 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

49 次世代情報処理技術とその応用＠早稲田大学研究開発センター
確率モデルによる確率的情報処理技術入門 ベイズ統計をつかった画像処理 画像処理の事前分布 確率伝搬法（Belief Propagation） 様々の応用 磁性体の統計理論による統計的性能評価 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター

50 次世代情報処理技術とその応用＠早稲田大学研究開発センター
References 田中和之編著: 臨時別冊・数理科学SGCライブラリ「確率的情報処理と統計力学 ---様々なアプローチとそのチュートリアル」, サイエンス社, 2006年9月. 田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006年9月. 田中和之著: ベイジアンネットワークの統計的推論の数理，コロナ社, 2009年10月． 安田宗樹, 片岡駿，田中和之共著 (分担執筆): ---CVIMチュートリアルシリーズ--- コンピュータビジョン最先端ガイド3, 第6章．大規模確率場と確率的画像処理の深化と展開，アドコム・メディア株式会社, 2010年12月. 10 November, 2011 次世代情報処理技術とその応用＠早稲田大学研究開発センター