物理フラクチュオマティクス論 Physical Fluctuomatics 応用確率過程論 Applied Stochastic Process 第11回確率推論におけるベイジアンネットと確率伝搬法 11th Bayesian network and belief propagation in statistical inference 東北大学大学院情報科学研究科応用情報科学専攻田中和之(Kazuyuki Tanaka) [email protected] http://www.smapip.is.tohoku.ac.jp/~kazu/ 物理フラクチュオマティクス論(東北大) 1 今回の本講義の講義ノート 1. 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009. 2. 田中和之編著: 数理科学臨時別冊 SCG ライブラリ「確率的情報処理と統計力学 ---様々なアプローチとそのチュートリアル--」，pp.92-100，サイエンス社，2006．物理フラクチュオマティクス論(東北大) 2 ベイジアンネットと確率推論ベイズの公式確率モデルグラフィカルモデル確率推論医療診断故障診断ベイジアンネット不確実性を伴うデータに耐えうる推論システムたくさんのノードが関連しあって集まっている．計算困難を打破する高性能の近似アルゴリズムの必要性物理フラクチュオマティクス論(東北大) 3 確率の知識（１）事象Ａの起こる確率 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 物理フラクチュオマティクス論(東北大) A B 4 確率の知識（２）事象 B の周辺確率 PrB   PrA, B, C, D A C D A B C D 周辺化物理フラクチュオマティクス論(東北大) 5 確率推論に使う数学 P rA, B, C  P rC A, BP rA, B  P rC A, BP rB AP rA  P rC BP rB AP rA PrB A PrC A, B PrC B 因果独立の仮定 A P rA, C P rA C  P rC B  P rA, B, C  B C 物理フラクチュオマティクス論(東北大)  P rA, B, C A, B 6 簡単なベイジアンネットの例問題芝生がぬれているのは何故でしょうか？雨が降ったせいでしょうか？それともスプリンクラーを動かしたせいでしょうか？  P rAR  T AW  T P rAS  T AW  T?  物理フラクチュオマティクス論(東北大) 7 簡単なベイジアンネットの例 P rAC , AS , AR , AW   P rAW AC , AS , AR P rAC , AS , AR   P rAW AC , AS , AR P rAR AC , AS P rAC , AS   P rAW AC , AS , AR P rAR AC , AS P rAS AC P rAC   P rAW AS , AR P rAR AC P rAS AC P rAC  物理フラクチュオマティクス論(東北大) 8 簡単なベイジアンネットの例 P rAR  T , AW  T P rAR  T AW  T  P rAW  T P rAS  T , AW  T P rAS  T AW  T  P rAW  T 物理フラクチュオマティクス論(東北大) 9 簡単なベイジアンネットの例 P rAR  T, AW  T  P rAS  T, AW  T  PrAW  T    P rAC , AS , AR  T, AW  T  0.4581   P rAC , AS  T, AR , AW  T  0.2781 AC  T,F AS  T,F AC  T,F AR  T,F    PrA , A , A AC T,F AS T,F AR T,F C S R , AW  T  0.6471 物理フラクチュオマティクス論(東北大) 10 簡単なベイジアンネットの例 P rAR  T AW  T  P rAR  T , AW  T 0.4581   0.7079 P rAW  T 0.6471 PrAS  T AW  T  PrAS  T , AW  T 0.2781   0.4298 PrAW  T 0.6471 回答：芝生がぬれているのは雨が降ったせいだと考えられます．物理フラクチュオマティクス論(東北大) 11 ベイジアンネットと物理モデル（Ⅰ） PrA1  a1, A2  a2   W a1, a2  A1 一言でいえば公式 A2 a1  1, a2  1 z=exp(ln z) を使うということ． PrA1  a1 , A2  a2   explnPrA1  a1 , A2  a2   expF  h1a1  h2 a2  J12 a1a2  具体的には W (1,1)  expF  h1  h2  J12  W (1,1)  expF  h1  h2  J12  を満たすように係数を決めると確かめられる．ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる．物理フラクチュオマティクス論(東北大) 12 ベイジアンネットと物理モデル（Ⅱ） PrA1  a1 , A2  a2 , A3  a3   W12 a1 , a2 W23 a2 , a3  a1  1, a2  1, a3  1 P rA1  a1 , A2  a 2 , A3  a3  A1 A2   expF  exp F12  h112 a1  h212 a 2  J 12 a1 a 2 23 A3   h223 a 2  h323 a3  J 23 a 2 a3   expF  h1 a1  h2 a 2  h3 a3  J 12 a1 a 2  J 23 a 2 a3  ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる．物理フラクチュオマティクス論(東北大) 13 ベイジアンネットと物理モデル（Ⅲ） PrA1  a1, A2  a2 , A3  a3  W a1, a2 , a3  A2 A1 A3 a1  1, a2  1, a3  1 P rA1  a1 , A2  a2 , A3  a3   F  h1a1  h2 a2  h3 a3  J12 a1a2    exp   J 23 a2 a3  J13 a1a3  Ka1a2 a3  ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる．物理フラクチュオマティクス論(東北大) 14 ベイジアンネットと物理モデル（Ⅳ） AC AR AS AW ベイジアンネットで扱われるグラフィカルモデルは多体力を持つ磁性体の物理モデルに対応づけられる． P rAC  aC , AS  aS , AR  aR , AW  aW   F  hC aC  hS aS  hR aR  hW aW  J CSaC aS  J CRaC aR    exp   J SR aS aR  J SW aS aW  J RW aR aW  KRSW aR aS aW  物理フラクチュオマティクス論(東北大) 15 より複雑なベイジアンネット P1 ( x1 )   Px1, x2 , x3 ,, xL  x2 x3 xL 定義に基づいて厳密に計算するプログラム xi  T rue or False P  x1   0; for(x2  T , F){ for(x2  T , F){  for(xL  T , F){ ノード数とともに指数関数的に計算量が増加 OeL  2L1  expL 1ln 2 L 重の for 文 P  x1   P  x1   P  x1 , x2 ,  , xL ; } このプログラムでは  L=10個のノードで1秒かかるとしたら } L=20個で約17分，L=30個で約12日， } L=40個で約34年かかる．物理フラクチュオマティクス論(東北大) 16 確率伝搬法 1. 閉路を持たないグラフ上の確率モデルに対して厳密な結果を与える． 2. 閉路を持つグラフ上の確率モデルでは近似アルゴリズムとなる． P rX   P rX 8 X 5 , X 6 P rX 7 X 6     P r X 6 X 3 , X 4 P rX 5 X 2   P rX 4 X 2 P rX 3 X 1  P rX 1P rX 2  ８個程度のノードの簡単ではあるが閉路を含むグラフ上の確率モデルで確率伝搬法の構造を説明し，得られる近似結果と厳密な結果を比較してみる．物理フラクチュオマティクス論(東北大) 17 閉路を持つグラフ上の確率モデルの結合確率 PrX 1  x1 , X 2  x2 ,, X 8  x8   W568 (x5 , x6 , x8 )W346 ( x3 , x4 , x5 )W67 ( x6 , x7 ) W25 ( x2 , x5 )W24 ( x2 , x4 )W13 ( x1 , x3 ) X1 X2 W24 W13 有向グラフ X3 W25 X4 W346 W67 X7 物理フラクチュオマティクス論(東北大) X6 無向グラフ W568 X5 X8 18 周辺確率分布 Pi ( X i )  X1 X , X , X , X , X , X , X , X   Pr  1 2 3 4 5 6 7 8  PrX , X , X , X , X , X , X , X     1 2 3 4 5 6 7 8 W24 W13 X3 X \ Xi Pij ( X i , X j ) X2 W25 X4 W346 W67 X7 X6 W568 X5 X8 X \ Xi ,X j Pijk ( X i , X j , X k )  PrX , X    1 2 , X 3, X 4 , X 5 , X 6 , X 7 , X 8 X \ Xi ,X j ,Xk 物理フラクチュオマティクス論(東北大) 19 この場合の確率伝搬法の基本方針 P6 x6    P346 x3 , x4 , x6  x3 X1 M 6346 ( X 6 ) X3 M 667 ( X 6 ) X7 x4 X2 M 313 ( X 3 ) X4 X3 X6 X5 X8 M 667 ( X 6 ) M 6568 ( X 6 ) 1 P6 x6   M 6346 x6  Z6  M 6568 x6 M 667 x6  W346 X7 P346 x3 , x4 , x6   M 424 ( X 4 ) X4 X6 X5 X8 M 6568 ( X 6 ) 1 W346 x3 , x4 , x6  Z 346  M 313 x3 M 424 x4   M 6568 x6 M 667 x6  物理フラクチュオマティクス論(東北大) 20 確率伝搬法の固定点方程式  W 346 M 6346 ( x6 )  x3 ( x3 , x4 , x6 ) M 313 ( x3 ) M 424 ( x4 )  x4  W 346 x3 x4 ( x3 , x4 , x6 ) M 313 ( x3 ) M 424 ( x4 )  x6 A2 A1 M 313 ( X 3 ) X1 W24 W13 M 424 ( X 4 ) A3 X2 X3 A4 W346 M 6346 ( X 6 ) W67 A6 確率伝搬アルゴリズム物理フラクチュオマティクス論(東北大) W25 X4 X7 X6 W568 X5 X8 21 Message を用いた周辺確率分布の近似表式 W346 ( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 )     M 667 ( X 6 ) M 6568 ( X 6 )   P346 ( X 3 , X 4 , X 6 )  W346 ( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 )      M 667 ( X 6 ) M 6568 ( X 6 )  X3 X4 X6  X1 M 313 ( X 3 ) X2 X3 M 667 ( X 6 ) X7 W346 M 424 ( X 4 ) X4 X6 X5 X8 M 6568 ( X 6 ) 物理フラクチュオマティクス論(東北大) 22 Message Passing Algorithm  W 346 M 6346 ( X 6 )  ( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 )  X3 X4  W 346 ( X 3 , X 4 , X 6 ) M 313 ( X 3 ) M 424 ( X 4 )  X3 X4 X6 X1 X2 M 313 ( X 3 ) M 424 ( X 4 ) X3 X4 M 6346 ( X 6 ) X1 X2 W24 W13 X3 W3 W6 X6 W67 Message Passing Algorithm 物理フラクチュオマティクス論(東北大) X7 W346 X6 W25 X4 W4 W568 X5 W5 X8 23 固定点方程式と反復法固定点方程式反復法繰り返し出力を入力に入れることにより，固定点方程式の解が数値的に得られる．          M1   M 0    M 2   M1    M3   M2    *  * M  M yx y M1 0 y  (x) M * M1 物理フラクチュオマティクス論(東北大) M0 x 24 数値実験 P8 (1)  0.5607 P8 (0)  0.4393 Belief Propagation P58 (1,1)  0.4736 P58 (1,0)  0.0764 P58 (0,1)  0.0871 P58 (0,0)  0.3629 P8 (1)  0.5640 P8 (0)  0.4360 P58 (1,1)  0.4776 P58 (1,0)  0.0724 Exact P58 (0,1)  0.0864 P58 (0,0)  0.3636 P8 ( x8 )  X1 P( x , x , x , x , x , x , x , x )    1 2 3 4 5 6 7 W24 W13 X3 8 x \ x8 P58 ( x5 , x8 )  P( x , x , x , x , x , x , x , x )    1 2 3 4 5 6 7 x \ x5 , x8 物理フラクチュオマティクス論(東北大) X2 8 W67 X7 W346 X6 W25 X4 W568 X5 X8 25 数値実験確率伝搬法   Pr X Bronchitis  PresentX Dyspnea  Present PrX Bronchitis  Present, X Dyspnea  Present 0.3629    0.8261 PrX Dyspnea  Present 0.4393 X1 X2 W24 W13 X3 W3 W6 W67 X7 物理フラクチュオマティクス論(東北大) W346 X6 W25 X4 W4 W568 X5 W5 X8 26 線形応答理論（人為的に小さなゆらぎを与えてその応答を見ることで詳細を知ることができる．） X2 X1 Pij (m, n)  Pi (m) Pj (n)   Pj (n)    lim  hi 0 h i   X3 (i ) X4 X6 x  {xi | i  Ω} X7 X5 X8 ~ ~  Pj (n)  Pj ( n)  Pj ( n)    n, x j P( x )    n, x j P( x )  xx  (i ) Dev iationof Av erageat Node j with respect to ExternalField at Node i  1 ~ P ( x )  ~ P ( x )exp hi xi , m Z 物理フラクチュオマティクス論(東北大)  27 数値実験   P r X Tuberculos is  Present X Dyspnea  Present  P rX Tuberculos is  Present, X Dyspnea  Present P rX Dyspnea  Present 0.0082   0.0187 0.4393 X1 X2 W24 W13 X3 W3 W6 W67 X7 物理フラクチュオマティクス論(東北大) W346 X6 W25 X4 W4 W568 X5 W5 X8 28 確率推論のまとめベイジアンネットと確率伝搬法を用いた確率推論の概説線形応答定理を用いた高次の推論システムへの発展ベイジアンネットの最近の動向繁桝算男, 本村陽一, 植野真臣：ベイジアンネットワーク概説，培風館，2006．本村陽一, 岩崎弘利：ベイジアンネットワーク技術．東京電機大出版，2006．田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009. Microsoft社，Intel社，Nokia社などが実用化への研究 http://excalibur.brc.uconn.edu/~baynet/ http://www.research.microsoft.com/research/dtg/ 物理フラクチュオマティクス論(東北大) 29 演習問題11－1 以下の図と式の結合確率 Pr{X1,X2,…,X8} により与えられるベイジアンネットワークにおける各ノードごとに周辺確率 P(Xi) (i=1,2,…,8) の厳密な値を C 言語，Java または MatLab を用いて求めよ． PrX 1 , X 2 ,, X 8    PrX 8 X 5 , X 6 PrX 7 X 6 Pr X 6 X 3 , X 4  PrX 5 X 2 PrX 4 X 2 PrX 3 X 1   PrX 1PrX 2  各条件付き確率表は田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009 のp.50の図3.12と表3.11の値を用いよ． April, 2010 電気・通信・電子・情報工学実験D 30 演習問題11－2 以下の図と式の結合確率 Pr{X1,X2,…,X8} により与えられるベイジアンネットワークにおける各ノードごとに周辺確率 P(Xi) (i=1,2,…,8) の値を確率伝搬法により計算するプログラムを C 言語，Java または MatLab を用いて求めよ． PrX 1 , X 2 ,, X 8    PrX 8 X 5 , X 6 PrX 7 X 6 Pr X 6 X 3 , X 4   PrX 5 X 2 PrX 4 X 2 PrX 3 X 1PrX 1PrX 2  各条件付き確率表は「田中和之: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009」のp.50の図3.12と表3.11の値を用いよ．ヒント：具体的なアルゴリズムは「田中和之: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009」の7.2節参照． April, 2010 電気・通信・電子・情報工学実験D 31