電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 3 (2013年4月)

Presentation on theme: "電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 3 (2013年4月)"— Presentation transcript:

1 電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 3 (2013年4月)
本実験DのWebpage: 東北大学 大学院情報科学研究科 田中 和之 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

2 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
本講義の参考文献 田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009. 田中和之編著: 臨時別冊・数理科学SGCライブラリ「確率的情報処理と統計力学 ---様々なアプローチとそのチュートリアル」, サイエンス社，2006. 安田宗樹, 片岡駿，田中和之共著 (分担執筆): ---CVIMチュートリアルシリーズ--- コンピュータビジョン最先端ガイド3(八木康史，斎藤英雄編), 第6章．大規模確率場と確率的画像処理の深化と展開，pp , アドコム・メディア株式会社, December 2010. Kazuyuki Tanaka: Statistical-mechanical approach to image processing (Topical Review), Journal of Physics A: Mathematical and General, vol.35, no.37, pp.R81-R150, 2002. C. M. Bishop: Pattern Recognition and Machine Intelligence, Springer, 2007. M. Opper and D. Saad: Advanced Mean Field Method, MIT Press, 2001. H. Nishimori: Statistical Physics of Spin Glasses and Information Processing, ---An Introduction---, Oxford University Press, 2001. M. J. Wainwright and M. Jordan: Graphical Models, Exponential Families, and Variational Inference (Foundations and Trends® in Machine Learning), Now Publishers, 2008. M. Mezard and A. Montanari: Information, Physics, and Computation, Oxford University Press, 2009. April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

3 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
Contents 序論：確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--- 確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--- 確率推論とベイジアンネットワーク---グラフィカルモデルと確率伝搬法--- まとめ April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

4 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
計算困難のポイントは何か 2L 通りの和が計算できるか？ このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分， L=30個で約12日， L=40個で約34年かかる． 厳密に計算するのは一部の特殊な例を除いて難しい． L 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法 今回 次回 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

5 乱数による円周率の計算（モンテカルロ法）
1 n0 m0 nn+1 -1 1 区間[-1,1]において2個の 一様乱数a,bを発生 -1 緑の四角の枠の中に ランダムに点をプロットし， 赤い円の内部の点の個数 をカウントする． a2+b2≤1 No Yes 円周率 mm+1 試行回数 n が大きいほど 精度が上がる April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

6 乱数による円周率の計算（モンテカルロ法）
1 1個1個の点をランダムにプロットするという試行を行った時の x 座標，y 座標の平均 0, 分散は 1/2． -1 1 ランダムに n 個プロットした標本平均は平均が 0, 分散が 1/2n (中心極限定理)なので，その確率密度関数の幅は 1/n1/2 で減少する． -1 緑の四角の枠の中に ランダムに点を n 個プロットし， 赤い円の内部の点の個数 m を カウントする． 円周率 円周率の推定誤差は O(1/n1/2) 試行回数 n が大きいほど 精度が上がる April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

7 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
積分の計算（モンテカルロ法） 1 n0 m0 nn+1 -1 1 区間[-1,1]において2個の 一様乱数a,bを発生 -1 緑の四角の枠の中に ランダムに点をプロットし， その点の被積分関数の 値を求める操作を繰り返す． mm + f(a,b) 推定誤差は O(1/n1/2) 試行回数 n が大きいほど 精度が上がる 積分が高次元でも同様 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

8 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
確率推論でよく必要となる計算 周辺確率 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

9 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
計算のポイントは 与えられた確率分布 に従うN個の独立なサンプル x を生成するアルゴリズムが作れるか? 但し，1個のサンプルを生成するための計算量は L の多項式オーダーでなければならない． April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

10 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
簡単な確率過程：マルコフ連鎖 推移確率 w(x|y)≥0 (x,y=0,1) が与えられたとき 任意の P0(x) を初期値として 推移確率行列 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

11 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
簡単な確率過程：マルコフ連鎖 遷移確率行列は と対角化可能 極限分布 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

12 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
簡単な確率過程：マルコフ連鎖 定常分布または平衡分布 極限分布 が存在すれば定常分布は存在する 定常分布が存在しても極限分布が存在するとは限らない． Example は定常分布 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

13 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖の定常分布と詳細釣り合い ただし P1(x), P2(x), P3(x),…: マルコフ連鎖 詳細釣り合い を満たすように推移確率 w(x|y) を選ぶと その定常分布は P(x) になる． マルコフ連鎖の定常分布 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

14 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 が与えられたとき 確率分布 任意の を初期値として を繰り返し計算して， となるように を選ぶにはどうしたらよいか？ April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

15 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 ただし P1(x), P2(x), P3(x),…: マルコフ連鎖 詳細釣り合い を満たすように推移確率 を選ぶとその推移確率 の定常分布は になる． 推移確率 の マルコフ連鎖の定常分布 極限分布がただ一つ存在するとしたら定常分布のひとつが極限分布である． April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

16 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 ランダムに生成 τ が十分大きいときサンプルx[t], x[2t], x[3t], …, x[Nt] は独立 無駄弾 独立とみなせるか t をどれだけ大きくとるべきか→緩和時間 　　　　からのサンプリングとみなすことができる 精度は O(1/t1/2) April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

17 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 頻度 Xi ヒストグラムから周辺確率も計算できる April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

18 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 頻度 Xi ヒストグラムから周辺確率も計算できる April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

19 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 V：すべてのノードの集合 E：すべてのリンクの集合 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

20 ：ノード i とリンクで結ばれたすべてノードの集合
マルコフ連鎖モンテカルロ法 マルコフ確率場 E：すべての リンクの集合 ：ノード i とリンクで結ばれたすべてノードの集合 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

21 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

22 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 w(x(t+1)|x(t)) x(t) x(t+1) True False xi = ○ or ● x x’ １回の更新にかかる計算量は変数の次元 L に対してO(1) April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

23 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
マルコフ連鎖モンテカルロ法 伊庭幸人, 種村正美: 統計科学のフロンティア/計算統計 II ---マルコフ連鎖モンテカルロ法とその周辺, 岩波書店, 2005. April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

24 確率伝搬法 (Belief Propagation)
を厳密に計算するのは一部の特殊な例を除いて難しい． 一部の特殊な例とは何か？ 一部の特殊な例に適用できるアルゴリズムを一般 　の場合に近似アルゴリズムとして適用できるか． → アルゴリズム化できるか？動くか？ 精度はどの程度か？ April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

25 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

26 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

27 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E X A B B C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

28 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E X A B B C D E A B B C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

29 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E X A B B C D E A B B C D E A B April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

30 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 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 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

31 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

32 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E X A B C C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

33 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E X A B C C D E X A B C C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

34 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E X A B C C D E X A B C C D E B C April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

35 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 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 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

36 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

37 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E A B C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

38 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E A B C D E B C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

39 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E A B C D E B C D E C D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

40 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A B C D E A B C D E B C D E C D E D E April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

41 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A D C E B F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

42 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

43 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F A D C E B F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

44 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A D A D C E C E B F B F A D D C E C E B F F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

45 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 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 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

46 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 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 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

47 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 A D C E B F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

48 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 A D C E B F A D E ＝ C E E F B April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

49 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 A D C E B F A D E ＝ C E E F B D E ＝ C E E F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

50 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 A D C E B F A D E ＝ C E E F B D D E ＝ ＝ C E C E E F F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

51 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 A D C E B F A C D E ＝ C E C B E F A D A C D E ＝ ＝ C E C E C B E F B F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

52 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 A D D ＝ ＝ C E C E B F F E C D F A B A メッセージに 対する漸化式 C E C E B April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

53 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 A D 周辺確率のメッセージを用いた表現 C E Step 1 B F A C B C E D E F Step 2 E C D F A B E C Step 3 E C D F E C D F A B E C A B E C April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

54 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
扱いやすい確率モデルのグラフ表現 周辺確率のメッセージを用いた表現 Step 1 A D C E B F Step 2 A D C E B F Step 3 A D C E B F April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

55 確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル 1 2 3 4 5 6 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

56 確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル 1 2 3 4 5 6 1 2 4 3 6 5 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

57 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
閉路のないグラフ上の確率モデル 1 2 3 4 5 6 ノード１と２の周辺確率分布は それぞれ隣接するノードから伝搬されるメッセージの積により表される． April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

58 確率伝搬法 (Belief Propagation)
閉路のないグラフ上の確率モデル ノード１から隣接ノード２に伝搬するメッセージは（ノード２を除く）ノード１の隣接ノードからノード１に伝搬されるメッセージの積により表される． 1 2 3 4 5 6 メッセージに対する固定点方程式 (Message Passing Rule) April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

59 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
閉路のないグラフ上の確率伝搬法 閉路が無いことが重要!! 同じノードは２度通らない April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

60 確率的画像処理における 確率伝搬法(Belief Propagation)
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

61 正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation)
着目画素とその近傍画素だけを残すと木構造になる． April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

62 正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(Belief Propagation)
着目画素とその近傍画素だけを残すと木構造になる． 確率伝搬法(Belief Propagation)の統計的近似アルゴリズムとしての転用 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

63 周辺確率(Marginal Probability)
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

64 周辺確率(Marginal Probability)
2 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

65 周辺確率(Marginal Probability)
2 2 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

66 周辺確率(Marginal Probability)
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

67 周辺確率(Marginal Probability)
1 2 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

68 周辺確率(Marginal Probability)
1 2 1 2 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

69 正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(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. April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

70 正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(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 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

71 正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(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 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

72 正方格子によるグラフ表現をもつ 確率モデルの確率伝搬法(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 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

73 閉路のあるグラフ上の確率モデル の確率伝搬法(Belief Propagation)
3 2 1 5 4 ２ １ ３ ４ ５ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

74 閉路のあるグラフ上の確率モデル の確率伝搬法(Belief Propagation)
3 2 1 5 4 ２ １ ３ ４ ５ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム メッセージに対する固定点方程式 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

75 閉路のあるグラフ上の確率モデル の確率伝搬法(Belief Propagation)
3 2 1 5 4 ２ １ ３ ４ ５ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム メッセージに対する固定点方程式 平均，分散,共分散はこのメッセージを使ってあらわされる April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

76 Fixed Point Equation and Iterative Method
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

77 Fixed Point Equation and Iterative Method
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

78 Fixed Point Equation and Iterative Method
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

79 Fixed Point Equation and Iterative Method
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

80 Fixed Point Equation and Iterative Method
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

81 Fixed Point Equation and Iterative Method
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

82 Fixed Point Equation and Iterative Method
April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

83 確率的画像処理における 確率伝搬アルゴリズムの基本構造
４近傍の場合は3入力1出力の更新式 ひとつの画素ごとに４種類の更新パターン 画素上での 動作の様子 の一例 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

84 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
閉路のあるグラフ上の確率モデル ２ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム ３ ４ １ ５ メッセージに対する固定点方程式 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

85 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
確率伝搬法の参考文献 田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009. M. J. Wainwright and M. Jordan: Graphical Models, Exponential Families, and Variational Inference (Foundations and Trends® in Machine Learning), Now Publishers, 2008. M. Mezard and A. Montanari: Information, Physics, and Computation, Oxford University Press, 2009. April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]

86 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]
まとめ 確率的計算技法の基礎 マルコフ連鎖モンテカルロ法 確率伝搬法 April, 2013 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 3]