ガウシアン確率伝搬法の近似精度に対する理論解析東京工業大学総合理工学研究科知能システム科学専攻渡辺研究室 D1 西山悠背景確率伝搬法(Belief Propagation;BP) (高次元)確率分布の周辺確率を効率的に求める計算手法 Ex. 人工知能における確率推論 Turbo 符号,LDPC符号 CDMA 通信確率的画像処理背景 target確率分布が木構造計算される周辺確率は厳密 target確率分布がloop構造を持つ(LBP) 収束性の問題，近似周辺確率 T. Heskes, ”On the Uniqueness of Loopy Belief Propagation Fixed Points”, Neural Computation 16(11), 2379-2414, 2004. Y. Weiss, ”Correctness of local probability propagation in graphical models with loops”, Neural Computation 12(1), 1- 41, 2000. Y. Weiss,”Correctness of belief propagation in graphical models with arbitrary topology”, Neural Computation 13(10), 2173-2200, 2001. 目的 LBPを多次元正規分布に適用したときの近似精度を解析的に明らかにする. 確率的画像処理 K. Tanaka, H. Shouno, M. Okada, “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. 田中和之, “確率モデルによる画像処理技術入門”, 森北出版, 2006. 内容・Belief Propagaton (BP) ・Loopy Belief Propagaton (LBP) ・Gaussian Distribution ・Main Results Single Loop Arbitrary graph ・Conclusion M 23 ( x3 ) BP algorithm Target x2 W23 1 p(x)  Wij ( xi , x j ) Z {ij}B M 43 ( W x3 ) Marginal distribution 1 p( xl )   Wij ( xi , x j ) x\ xl Z {ij}B W12 x1 x6 x3 W56 34 x4 W35 x5 M53 ( x3 ) Tree-graph (Singly-connected graph)     p( x3 )   W23W12  W34  W35W56  x1 x6  x2  x4  x5   M 23 ( x3 )M 43 ( x3 )M53 ( x3 )  M kN (3) k 3 ( x3 ) BP algorithm Marginal distribution M 23 ( x3 ) x2 W12 x1 x6 W23 1 p( xl )   Wij ( xi , x j ) M 43 ( x3 ) W34 x\ xl Z {ij}B x4 x3 W35 x5 W56 M 65 ( x5 )      p( x3 , x5 )   W23W12  W34 W35 W56  x1  x2  x4   x6   M 23 ( x3 )M 43 ( x3 )W35M 65 ( x5 )        M k 3 ( x3 ) W35  M k 5 ( x5 )   kN (3)\5   kN (5)\3  Belief Propagation (BP) 周辺分布構成式 p( xi )  M kN (i ) k i ( xi )     p( xi , x j )    M k i ( xi ) Wij   M k  j ( x j )   kN (i )\ j   kN ( j )\i  N (i) N (i) xk1 xi xk1 xi xk2 N ( j) Wij xk1 xj Loopy Belief Propagation (LBP) 周辺分布構成式 p( xi )  M kN (i ) k i ( xi )     p( xi , x j )    M k i ( xi ) Wij   M k  j ( x j )   kN (i )\ j   kN ( j )\i  x1 x2 x6 x3 x4 x5 Graph with a loop 収束性の問題近似周辺確率 Message Mi j ( x j ) の決定方法 Consistency Constraints 周辺分布構成式 p( xi ) ＋ p(xi , x j )  p(x , x )  p(x ) i j j xi  p(x , x )  p(x ) i j i xj Message Update Rules Mi j ( x j )  Wij ( xi , x j ) xi M kN (i ) \{ j} k i ( xi ) Gaussian Distribution Target : Gaussian Distribution N (x | 0, S 1 ) xl M l i li xi xm Mjji i Mii  jj xj mi M mi Message Mi j N ( x j | 0, i1 j ) Message Update Rules 2 s ij ~  s Mi j(ixj j)  W~ij ( xi , x j ) M k i ( xi ) ii  sii   (ki)\{ij} x kN i kN (i ) \{ j} Main Results x1 xd x2 x3 Theorem １重ループ正規分布 N (x | 0, S 1 )のグラフ構造が１重ループのとき Message Update Rulesの固定点は, i {1,, d}で si,i1i,i1  si1,i2i1,i2  D ii1  2i1,i1 si,i1i,i1  si1,i2i1,i2  D ii1  2i1,i1 D  (det S)2  (1)d 4s12s23sd1 det S である． Main Results Corollary このときLBPによって計算される周辺分布(belief)は， ~ 分散の逆数 i , 逆行列 Si,i 1 について (1)d 4s12s23 sd1 det S i  1 ii det S  Ei ,i 1  i ,i ~  Si ,i 1    si ,i 1  である．  si ,i 1   Ei ,i 1   i 1,i 1  det S  D Ei,i 1   si,i 1i,i 1 2 LBP ⇒ BP LBP True (1)d 4s12s23 sd1 det S i  1 ii det S x1 s12 x2 s23 sd 1 xd s23  0 x3 loop Loopy Belief Propagation det S ii s12 x1 x2 sd 1 xd x3 tree Belief Propagation ＊BPが木構造のとき正しい周辺確率が得られる． LBPの近似精度 (1)d 4s12s23 sd1  det S Kullback-Leibler (KL)距離は 1 1 1 ~ KL( pi || pi )    1   log 1  2 2 2 真の周辺分布近似周辺分布共分散値<<1 のときの周辺分布 x1 x2 Multiloopsを含む任意のグラフ構造では？ x6 x3 x4 x5 多重ループ S  Sd  sSo のもとで s  1 における展開を導出 Beliefの固定点方程式 Message 固定点方程式周辺分布固定点方程式 Theorem 近似周辺分布の分散の逆数 i は 2 2 4 s s ji 2sii | N (i) | 2     1 i jN (i )  j i i {1,, d} d の 2 | N (i )| i 1 組からなる連立方程式のいずれかを満たす． はそれぞれの項で任意にとる. Beliefのs<<1での展開 s0 S  Sd  sSo i (s  0)  sii (True) Theorem i (s  0)  sii を満たす固定点方程式は 2sii | Ni | 2   i jNi 4s 2 s 2ji 1  j i i {1,, d} の連立方程式に限り,これを満たすi は i (s)  sii  d  j 1( i ) の展開式を持つ. s 2ji 2 4 s  O(s ) s jj LBPの結果とTrueとの比較 LBPの結果 i (s)  sii  d  j 1( i ) s 2ji 2 s  O(s 4 ) s jj True d s 2ji 2 det S  sii   s ii j 1( i ) s jj sii  tr[(Sd1So )3 {(Sd )ii1 (So )ii }3 ]s3  O(s4 ) 3 Theorem KL( pi || ~ pi )  O(s4 ) まとめ  多次元正規分布の場合に, LBPの近似精度を解析的に言及した. 特に (1)１重ループ構造のときLBPの近似精度は (1)d 4s12s23 sd1  の量で決められる. det S (2)任意のグラフ構造で共分散が小さいときの LBPの近似精度を明らかにした. Future Works  数値実験による比較  LBPの補正アルゴリズムの構築  固定点への収束率のCCCPとの比較  高次の相関があるときへの拡張 A Single Loop + Tree Structures x4 s14  s37 ss31 31 x1 x3 ss23  23 x7  ss12 12 x2 x5 s26 s78 x8 s25 x6 4s12s23s31 det S   i  1 ii det S  i {1,2,3} 2 s41   s11  s11 s44 2 2 s52 s62   s22  s22  s55 s66 2 s73   s33  s33 2 s87 s77  s88 2 s14 4  s44  2 s41 1  s44 2 s25 5  s55  2 s52 2  s55