平均場近似の数理 ---確率伝搬法という名の物理と情報の交差点--東北大学大学院情報科学研究科田中和之 [email protected] http://www.statp.is.tohoku.ac.jp/~kazu/ 参考資料：第48回物性夏の学校講義ノート「統計力学と情報処理 --- 自由エネルギーの生み出す新しい情報処理技術---」 (田中和之著，物性研究 2004年 2 月号に掲載) http://www.statp.is.tohoku.ac.jp/~kazu/tutorial-lecture-note/SummerSchool-200308/ RMMFA2004 （2004年9月7日） 1 平均場理論が何故情報処理に有効？多くの情報処理は大規模確率モデル計算困難の問題近似で良いから，現実的計算時間で近い結果が得られれば満足．平均場理論の歴史は常にシステムサイズ無限大との戦いの歴史である．豊富な経験 RMMFA2004 （2004年9月7日） 2 確率的情報処理と平均場理論ベイズの公式確率モデルグラフィカルモデル確率的情報処理ベイジアンネット確率伝搬法たくさんのノードが関連しあって集まっている．要請：多様なデータに耐えうる推論システムゆらぎを系統的に扱える理論の必要性 RMMFA2004 （2004年9月7日）物理モデルとの共通の数理平均場理論の出番 3 この時間の主な内容確率についての基礎知識の復習確率的画像処理における平均場理論と確率伝搬法確率推論における確率伝搬法 RMMFA2004 （2004年9月7日） 4 確率の知識（１）事象Ａの起こる確率 Pr{A} 事象Aと事象Bの結合確率 PrA, B PrA  B 条件付き確率と結合確率 PrA, B PrB A  PrA  PrA, B  PrB APrA RMMFA2004 （2004年9月7日） A B 5 確率の知識（２）ベイズの公式の導出 A  PrA, B  PrB APrA  B PrA, B  PrA BPrB  PrB   PrA, B  A  PrA, B PrB APrA PrB APrA  PrA B   PrB PrB  PrB APrA A RMMFA2004 （2004年9月7日） 6 確率の知識（３）結合確率分布と周辺確率分布の一般的関係 PrB   PrA, B, C, D A C D ＡＢＣＤ周辺化 RMMFA2004 （2004年9月7日） 7 この時間の主な内容確率についての基礎知識の復習確率的画像処理における平均場理論と確率伝搬法確率推論における確率伝搬法 RMMFA2004 （2004年9月7日） 8 画像修復の確率モデル雑音通信路原画像劣化画像 Pr劣化画像| 原画像Pr原画像 Pr原画像| 劣化画像  Pr劣化画像 RMMFA2004 （2004年9月7日） 9 ベイズの公式と確率的画像処理 P f   f 事前確率 y 画素原画像  x Pg f ,  劣化過程 f  f x, y x, y  事後確率 g g 劣化画像 g  g x, y x, y   Pg f , P f   P f g, ,   Pg  ,  fˆx, y   zx, y Pz g, , dz RMMFA2004 （2004年9月7日） 10 周辺尤度最大化によるハイパパラメータ推定 ˆ ,ˆ   arg max Pg  ,  fˆx, y   zx, y Pz g,ˆ ,ˆ dz  ,  Pg  ,    Pg z, Pz  dz  y  P f   x 原画像 f  f x, y x, y   ZPOSg, ,   2  Pg f ,  f g  ZPR  g 周辺化 Pg  ,  周辺尤度 RMMFA2004 （2004年9月7日） g 劣化画像 g  g x, y x, y   11 画像修復の劣化過程と事前確率 f x, y , gx, y  , 劣化過程 Pg f ,    ( x, y ) 1  1  exp  2  f x, y  g x, y 2  2   2  事前確率 g x, y  f x, y  nx, y  nx, y ~ N 0,  2  1   2  2       P f  exp  f  f  f  f   x, y x 1, y x, y x, y 1  ZPR  ( x, y) 2  2  P f g,  ,    事後確率    Pg f ,  P f   Pg  ,     1  f x, y , f x 1, y  f x, y , f x. y 1    ZPOS g,  ,  ( x, y)         1  1 1 xx,',yy' f x, y , f x', y'  exp  2 f x, y  g x, y 2  2 f x', y'  g x', y' 2   f x, y  f x', y' 2  2 8  8  RMMFA2004 （2004年9月7日） 12 周辺確率の導入 Px, y ( f x, y )     f x, y  zx, y Pz g, , dz x ', y ' x, y P ( f x, y , f x', y ' )     f x, y  z x, y   f x', y '  z x', y ' Pz g, , dz ˆf  z Pz g, , dz  P  d x, y  x, y  x, y  RMMFA2004 （2004年9月7日） 13 平均場近似 mx, y   f x, y P f g, , df  f x,y  mx,y  f x1,y  mx1,y   0 Substitute  f x, y  f x1, y 2  f x, y2  2 f x, y f x1, y  f x1, y2  f x, y 2  f x 1, y 2  2 f x, y mx 1, y  2 f x 1, y mx, y  2mx, y mx 1, y        f x, y  mx, y 2  f x 1, y  mx 1, y 2  mx, y  mx 1, y 2 平均場方程式         1  Px, y f x, y    f x, y  z x, y Pz g, , dz  exp   f x, y  mx, y 2  2  2  g x, y  mx1, y  mx1, y  mx, y 1  mx, y 1 mx, y    4 RMMFA2004 （2004年9月7日） 14 平均場近似平均場方程式   1 2 Px, y  f x, y   exp    f x, y  mx, y   2  2  g x, y  mx1, y  mx1, y  mx, y 1  mx, y 1 mx, y    4 ( x, y 1) mx, y 1 ( x 1, y) mx 1, y ( x 1, y) ( x, y) mx, y 1 ( x, y 1) mx 1, y mx, y   RMMFA2004 （2004年9月7日）  dzx, y  Px, y z x, y  15 確率伝搬法（ベーテ近似） Px, y  f x, y    P   x 1, y x, y f x, y ( x, y 1) ( x, y 1) M xx,,yy 1 ( x 1, y) M xx,y1, y M xx,,yy 1 M xx,y1, y ( x 1, y) ( x 1, y) M xx,y1, y  M xx11,,yy1 Px, y f x, y  Z x, y M xx,y1, y ( x 1, y) ( x, y) ( x, y 1)    f x, y    f x, y M xx,y1, y   M xx,,yy 1 f x, y M xx,,yy 1 f x, y   M xx12,,yy ( x  2, y) M xx11,,yy1 M xx,,yy1 ( f x, y ) ( x, y 1)  ( x 1, y 1) M xx,,yy 1 ( x, y) 1 , zx1, y dzx1, y ( x 1, y 1)   1 Pxx,y1, y f x, y , f x1, y  x1, y xx,y1, y f x, y , f x1, y Z x, y         M xx12,,yy  f x1, y M xx11,,yy 1 f x1, y M xx11,,yy 1 f x1, y   M xx,y1, y f x, y M xx,,yy 1 f x, y M xx,,yy 1 f x, y RMMFA2004 （2004年9月7日） 16 確率伝搬法におけるメッセージ更新規則 M xx, y1, y     x 1, y  x, y  ,  M xx,y1, y  M xx,,yy 1 M xx,,yy 1 d    x 1, y  x, y  ,  'M xx,y1, y  M xx,,yy 1 M xx,,yy 1 d d '      ( x, y 1) M xx,,yy 1 ( x 1, y) M xx,y1, y ( x, y) M xx,',yy' ( )  M xx, y1, y  ( x 1, y) 固定点方程式 M xx,,yy 1 ( x, y 1)  xx,',yy'  1 x', y' x', y' 2  exp  x, y    x, y  2  2  反復法 RMMFA2004 （2004年9月7日）      M  M 17 固定点方程式と反復法固定点方程式反復法   *  * M  M 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる．         M1   M 0   M 2   M1   M3   M 2  y M1 * M1 M 0 RMMFA2004 （2004年9月7日） yx y  (x) M0 x 18 画像修復事前確率から生成された原画像に対する数値実験劣化画像 (  40) 原画像 (  0.001) 確率伝搬法（ベーテ近似）平均場近似 ˆ  0.000298 ˆ  29.1, MSE  538.5 MSE    2 1 ˆ f  f  |  | x, y x, y x, y 厳密解 ˆ  0.000784 ˆ  0.001090 ˆ  37.8,MSE  302.8 ˆ  39.4,MSE  297.6 RMMFA2004 （2004年9月7日） 19 対数周辺尤度事前確率から生成された原画像に対する数値実験原画像 (  0.001) 平均場近似 -5.0 (  40) 平均場近似 -5.0 確率伝搬法 1 ln Pg ˆ ,  | | 1 ln Pg  ,ˆ  | | -5.5 厳密解確率伝搬法 -6.0 10 劣化画像厳密解 20  50 30 40 平均場近似 ˆ  0.000298,ˆ  29.1 60 -5.5 確率伝搬法（ベーテ近似） ˆ  0.000784,ˆ  37.8 RMMFA2004 （2004年9月7日） 0 0.0010  0.0020 厳密解 ˆ  0.00109,ˆ  39.4 20 ガウシアングラフィカルモデルを用いた画像修復原画像劣化画像 MSE: 1512 MSE  厳密解平滑化フィルター MSE:315 MSE: 411   2 1 f x, y  fˆx, y  |  | x, y  平均場近似確率伝搬法 MSE: 591 MSE: 325 ウィーナーフィルターメジアンフィルター MSE: 545 RMMFA2004 （2004年9月7日） MSE: 447 21 ガウシアングラフィカルモデルを用いた画像修復原画像厳密解平均場近似確率伝搬法 MSE: 1409 MSE: 593 MSE: 324 ウィーナーフィルターメジアンフィルター MSE: 369 MSE: 259 平滑化フィルター MSE:306 MSE  劣化画像 MSE: 268   2 1 ˆ f  f  |  | x, y x, y x, y RMMFA2004 （2004年9月7日） 22 確率的画像処理の今後の動向理論的方向パラメータのデータからの学習ライン場の導入適応画像処理フィルターへの発展実用的方向画像圧縮領域分割移動体検出 RMMFA2004 （2004年9月7日） 23 この時間の主な内容確率についての基礎知識の復習確率的画像処理における平均場理論と確率伝搬法確率推論における確率伝搬法 RMMFA2004 （2004年9月7日） 24 確率推論に使う確率の知識 PrA, B, C  PrC A, BPrA, B A  PrC A, BPrB APrA  PrC BPrB APrA PrB A PrC A, B PrC B A A B B C C B C PrA, C PrA C  PrC B PrA, B, C   PrA, B, C A, B RMMFA2004 （2004年9月7日） 25 簡単なベイジアンネットの例 PrAC , AS , AR , AW   PrAW AC , AS , ARPrAR AC , ASPrAS ACPrAC  PrAW AS , ARPrAR ACPrAS ACPrAC AC AR AS AW RMMFA2004 （2004年9月7日） 26 閉路のないグラフ上の確率伝搬法 1 N 1 i1 PrA  a  Wi ai , ai1  Z i1 A1 A2 A3 Ak 1 Ak 3 閉路が無いことが重要!! Ak Ak 1 Ak 2 同じノードは２度通らない  k i1  Tk k 1 ak 1    Wi ai , ai1   Tk 1k ak Tk 2k ak Tk 3k ak Wkk 1 ak , ak 1  a1 a2 ak  i 1  ak RMMFA2004 （2004年9月7日） 27 扱い易いモデルと計算困難なモデル閉路のないグラフィカルモデル a どの枝もそれぞれで独立に和がとれる． b  AaB(b)C(c)D(d ) a b d c c d         A(a)   B(b)  C(c)   A(d )  a  b  c  d  閉路のあるグラフィカルモデル a それぞれで独立に和をとることが困難． b d c  Fa, b, c, d  a b c d RMMFA2004 （2004年9月7日） 28 より複雑なベイジアンネット A2 A1 W24 W13 A3 W67 A7 W346 A6 W25 A4 W568 A5 A8 複雑になるほどノードの個数は多くなり計算困難が深刻になる RMMFA2004 （2004年9月7日） 29 より複雑なベイジアンネット Pa   PrA1  a1, A2  a2 ,, A8  a8 1  W568 (a5 , a6 , a8 )W346 (a3, a4 , a5 )W67 (a6 , a7 ) Z W25(a2 , a5 )W24 (a2 , a4 )W13(a1, a3 ) A2 A1 a  ai i  1,2,,8 W24 W13 A3 W67 A7 RMMFA2004 （2004年9月7日） W346 A6 W25 A4 W568 A5 A8 30 周辺確率分布 Pa  PrA1  a1, A2  a2 ,, A8  a8  Pi (ai )   Pa a \ai  Pij (ai , a j )  信念（Belief） A2 A1 W24 W13  Pa A3 a \ai ,a j  Pijk (ai , a j , ak )   Pa a \ai ,a j ,ak  RMMFA2004 （2004年9月7日） W67 A7 W346 A6 W25 A4 W568 A5 A8 31 この場合の確率伝搬法の基本方針 P6 a6    P346a3, a4 , a6  a3 a4 M 6346( A6 ) A3 M667 ( A6 ) A7 P6 a6   A2 A1 M313( A3 ) A4 A3 A5 A6 A8 M667 ( A6 ) M 6568( A6 ) 1 M 6346 a6  Z6  M 6568 a6 M 667 a6  W346 A5 A6 A8 A7 P346 a3, a4 , a6   M 424( A4 ) A4 1 Z346 M 6568( A6 ) W346 a3, a4 , a6   M313 a3 M 424 a4   M 6568 a6 M 667 a6  RMMFA2004 （2004年9月7日） 32 確率伝搬法の固定点方程式 W346(a3, a4 , a6 )M313(a3)M424(a4 ) M 6346(a6 )  a3 a4 W346(a3, a4 , a6 )M313(a3)M424(a4 ) a3 a4 a6 A2 A1 M313( A3 ) A3 A4 M 424 ( A4 ) A2 A1 W24 W13 A3 M 6346( A6 ) A6 W67 確率伝搬アルゴリズム RMMFA2004 （2004年9月7日） A7 W346 A6 W25 A4 W568 A5 A8 33 固定点方程式と反復法固定点方程式反復法   *  * M  M 繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる．         M1   M 0   M 2   M1   M3   M 2  y M1 * M1 M 0 RMMFA2004 （2004年9月7日） yx y  (x) M0 x 34 数値実験 P8 (1)  0.5607 P8 (1)  0.4393 P58(1,1)  0.4736 P58(1,1)  0.0764 P58(1,1)  0.0871 P58(1,1)  0.3629 Belief Propagation P8 (1)  0.5640 P8 (1)  0.4360 P58(1,1)  0.4776 P58(1,1)  0.0864 P58(1,1)  0.0724 P58(1,1)  0.3636 Exact X1 X2 W24 W13 P8 (a8 )   P(a1, a2 , a3, a4 , a5, a6 , a7 , a8 ) a \a8  P58 (a5 , a8 )   P(a1, a2 , a3, a4 , a5, a6 , a7 , a8 ) a \a5 ,a8  RMMFA2004 （2004年9月7日） X3 W67 X7 W346 X6 W25 X4 W568 X5 X8 35 数値実験確率伝搬法   Pr ABronchitis  Present ADyspnea  Present   Pr ABronchitis  Present, ADyspnea  Present 0.3629    0.8261 Pr ADyspnea  Present 0.4393   A2 A1 W24 W13 A3 W3 W6 W67 A7 RMMFA2004 （2004年9月7日） A4 W346 W 4 A6 W568 W25 A5 W5 A8 36 ベイジアンネットの今後の動向自動化が急務．パラメータのデータからの学習 EM アルゴリズムクラスター変分法の更なる拡張の試み Region Graph Method Max-Product Method RMMFA2004 （2004年9月7日） 37 本講義を通してのまとめモノの理とコトの技の接点としての平均場理論キーワードは「ベイズの公式」と「たくさんが関連」ゆらぎを巧みに扱えるシステムのデザイン詳細はhttp://www.statp.is.tohoku.ac.jp/~kazu/SMAPIP-KazuKazu/ チュートリアル講義ノート，お試し用の基本プログラムも公開中 RMMFA2004 （2004年9月7日） 38 本講義で取り上げる題材の出典画像処理：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., Vol.37, No.36, pp.8675-8696 (2004) 確率推論：K. Tanaka, Probabilistic Inference by means of Cluster Variation Method and Linear Response Theory, IEICE Trans. on Information and Systems, Vol.E86-D, No.7, pp.1228-1242 (2003). RMMFA2004 （2004年9月7日） 39 本講義の参考文献西森秀稔，田中和之他著, “特集/知識情報処理の統計力学的アプローチ”, 数理科学1999年12月号. K. Tanaka: Statistical-mechanical approach to image processing (Topical Review), J. Phys. A: Math. & Gen.,vol.35, no.37, pp.R81-R150, September 2002. 田中和之・樺島祥介編, “ミニ特集/ベイズ統計・統計力学と情報処理”, 計測自動制御学会誌「計測と制御」2003年8月号甘利俊一，池田和司，田中和之，田中利幸他著, “特集/統計科学の最前線 ― 新しい情報科学への技術と手法 ―”, 数理科学2004年3月号. 田中和之，田中利幸，渡辺治，喜多一，堀口剛他著，“連載/ 確率的情報処理と統計力学 ---様々なアプローチとそのチュートリアル---”，数理科学2004年11月号から開始． RMMFA2004 （2004年9月7日） 40