スライド 1 - Watanabe Lab.

ガウシアングラフィカルモデルに対する
確率伝搬法の分散値の厳密解と補正法
東京工業大学総合理工学研究科
知能システム科学専攻渡辺澄夫研究室
D2
西山悠
2008年5月29日
情報数物研究会＠東北大学
1/38
確率伝搬法とは・・・
（計算困難な）高次元確率分布の周辺確率を効率的に
求めるアルゴリズム．
（大規模な）確率的情報処理
ベイジアンネットワークにおける確率推論
誤り訂正符号に対する復号アルゴリズム
000101
noise
decode
000111
000101
移動体通信におけるマルチユーザ検出
確率的画像処理
劣化画像
復元画像
＊田中和之，確率モデルによる画像処理技術入門，森北出版，2006.
2008年5月29日
情報数物研究会＠東北大学
2/38
内容
問題意識
サイクルを含んだGaussian graphical model (GGM) 上で，
確率伝搬法を用いて確率推論を行ったとき，分散値はどれ
ほど真の値からずれるのか？LBPの近似精度は？LBPの
収束条件は？
目次
・Graphical model
・確率伝搬法(Belief Propagation)
・GGMのときの確率伝搬法
・1重サイクルのときの分散値の解析解
メイン
・任意topologicalグラフのときの分散値の評価
2008年5月29日
情報数物研究会＠東北大学
3/38
Graphical Model (GM)
y1
y2
y7
x1 y
5
x2
x7
y6
x6
x5
y4
隠れ変数
y3
x3
x  {x1 , x2 ,, xd }
観測変数
y  { y1, y2 ,, yd }
x4
G  {V , E}
確率推論・・・ y  { y1 , y2 ,, yd } が与えられた下で
隠れ変数 xi の分布を推定する問題．
2008年5月29日
情報数物研究会＠東北大学
4/38
周辺分布の計算は一般に計算困難
y1
y2
y7
x1 y
5
x2
y3
x7
y6
y4
x3
x5
x6
for(i=0;i<2;i++){
for(j=0;j<2;j++){
for(k=0;k<2;k++){
for(l=0;l<2;l++){
}
x4
}
例） x5 の事後分布
p5 ( x5 ) 
x2
}
指数オーダ

x1
}
x3
x4
x6
p( x1 , x2 , x3 , x4 , x5 , x6 , x7 | y}
x7
確率伝搬法
2008年5月29日
情報数物研究会＠東北大学
5/38
Gaussian Graphical Model (GGM)
y1
y2
y7
x1 y
5
x2
x7
y6
x5
x6
y4
確率変数 x, y が共に正規分布
y3
x3
に従うときを考える．
1 T T Vxx Vxy  x 
 }
P(x, y )  exp{ (x , y )

2
Vyx Vyy  y 
x4
G  {V , E}
確率推論・・・ y  { y1 , y2 ,, yd } が与えられた下で隠れ変数
xi
の事後平均  xi |yと事後分散  xi |yを求める問題．
2008年5月29日
情報数物研究会＠東北大学
6/38
厳密な推論
Vxx x|y  Vxyy
x|y  Vxx1
を満たす事後平均ベクトル  x|y 事後分散 ( x|y )i,i を解く問題
に帰着される．
d
3
逆行列計算 O(d )
 s11

 s21
(Vxx ) 1   s31

 
s
 d1
s12
s13
s22
s32
s23
s33


sd 2
sd 3
 s1d 

 s2 d 
 s3d 

  
 sdd 
d
反復的解法として確率伝搬法
2008年5月29日
情報数物研究会＠東北大学
7/38
確率伝搬法(Belief Propagation; BP)
x1
x7
x2
x3
x5
x6
1
P(x, y)   ij ( xi , x j ) ii ( xi , yi )
Z {ij}E
iV
x4
G  {V , E}
(Hammersley-Clifford theorem)
(messageの更新式)
1
M i(t 1j ) ( x j )  ~   ij ( xi , x j ) ii ( xi , yi )  M k(t) i ( xi )dxi
Z ij
kN \{ j }
i
1
M (jt1i ) ( xi )  ~
Z ji

ij
( xi , x j ) jj ( x j , y j )
M
(t )
k j
( x j )dx j {ij} E
kN j \{i}
(beliefの更新式)
bi(t ) ( xi ) 
 ii ( xi , yi )
M
( xi )
i V
Zi
kNi
 (x , y )
bij(t ) ( xi , x j )  ii i i  M k(t) i ( xi )  M k(t) j ( x j ) {ij} E
Z ij
kN i \{ j }
kN j \{i}
2008年5月29日
情報数物研究会＠東北大学
(t )
k i
8/38
message更新則
(messageの更新式)
1
M (jt1i ) ( xi )  ~
Z ji
1
M i(t 1j ) ( x j )  ~
Z ij

ij

( xi , x j ) jj ( x j , y j )
M
(t )
k j
( x j )dx j
kN j \{i}
ij
( xi , x j ) ii ( xi , yi )
M
(t )
k i
( xi )dxi
kN i \{ j }
111
((tt ))(((ttt)))
(((ttt))) dx
)

(
x
,
y
)
M
M


(
(
x
x
,
,
x
x
)
)


(
(
x
x
,
,
y
y
)
M
)
M
dx
M
~
41
43
23
4
3
44
44
4
4
4
4
2
4

4
2
2
4242dx4242
12
24
21
1
2
2
1
4
11
22
22
1
2
2
1
2
2
4

4
1

1
2
1
3


(
x
,
x
)

(
x
,
y
)
M
M

14
1 4 1 31
~
42 14 42 11
44 1 4 1 4 2
1
Z
43
23
41
24
21
Z12
14
23
1
tt11)) ( x )  1
)) dx
M3(3(
3234((xx33,,xx24))
3333((xx33,, yy33))M
M4(2(tt
M
~  
24 ( x24)  ~
33dx33
ZZ3234
(tttt
1
111))))((x
x4431)) 
M
M1124((24(24



2
M

44
231 ( x2
2 
2008年5月29日
情報数物研究会＠東北大学
9/38
belief計算
(beliefの更新式)
bi(t ) ( xi ) 
 ii ( xi , yi )
M
(t )
k i
( xi )
Zi
kNi
 (x , y )
bij(t ) ( xi , x j )  ii i i  M k(t) i ( xi )  M k  j ( x j )
Z ij
kN i \{ j }
kN j \{i}
b1* ( x1 ) 
b2* ( x2 ) 
b3* ( x3 ) 
b4* ( x4 ) 
2008年5月29日
情報数物研究会＠東北大学
 11 ( x1 , y1 )
Z1
 22 ( x2 , y2 )
Z2
 33 ( x3 , y3 )
Z3
 44 ( x4 , y4 )
Z4




10/38
*
i
*
b
(
x
),
b
固定点のbelief
ij ( xi , x j )
i
(i)グラフ G がサイクルを持たないとき
固定点のbelief b ( xi ), b ( xi , x j )
*
i
*
ij
y1
y7
x1
x7
y6
は正確な周辺分布を計算．
(ii)グラフ G がサイクルを持つとき
アルゴリズムの収束も保証されない．
Loopy BPの近似精度は？
収束する条件は？
2008年5月29日
情報数物研究会＠東北大学
y5
x2
y3
x5
y4
x3
x6
x4
acyclic graph
*
*
固定点のbelief bi ( xi ), bij ( xi , x j )
は近似的な周辺分布を計算．
y2
y1
y7
x1
x7
y6
x6
y2
y5
x2
y3
x5
y4
x3
x4
graph with cycles
11/38
Gaussian Graphical Model (GGM) のとき
Loopy BPが収束した場合, 事後平均は正確な値を計算．
しかし，事後分散は真の分散値からずれる．
Y. Weiss, “Correctness of Belief Propagation in Gaussian
Graphical Models of Arbitrary Topology”, 2001.
Loopy BPが計算する分散値の近似精度は？
（問題意識）
2008年5月29日
情報数物研究会＠東北大学
12/38
ベーテ自由エネルギー
ベーテ自由エネルギー
x1
x7
x2
x3
x5
x6
x4
belief bi , bij
Loopy BPの固定点
を与えるbelief bi* , bij*
ベーテ自由エネルギーの
極値条件を満たすbelief bi* , bij*
BO (M. Welling, et. al., 2001)
CCCP (A. L. Yuille, 2002)

SEQ (Tonosaki, et.al., 2007)
2008年5月29日
New CCCP (Yu Nishiyama, 3月NC研, 2008)
(Yu Nishiyama, ICANN2008)
情報数物研究会＠東北大学
13/38
GGMのときのLBP Algorithm
y1
y2
 11
x1
 14
1 T T Vxx Vxy  x 
 }
P(x, y )  exp{ (x , y )

2
Vyx Vyy  y 
 22
 12
x2
y3
y4  24
 23 
 44
33
x4
x3
 34
P(x, y) 
1
 ij ( xi , x j ) ii ( xi , yi )

Z {ij}E
iV
(Hammersley-Clifford theorem)
＊ローカルポテンシャルへの分解
x1
 41s44
44 s44
x4
(  44 
x2
y4

iN ( 4 )
2008年5月29日
42 s44
43s44
4i
 24
x3
  24 s22
1
 exp{ ( x2 , x4 )
2
 s42
 x2 
 }
 42 s44  x4 
  44 s44
 (Vxy ) 44
(Vxy ) 44  x4 
 }
(Vyy ) 44  y4 
1
2
 44  exp{ ( x4 , y4 )
s24
 1)
情報数物研究会＠東北大学
14/38
y1
y2
 11
x1
 14
 12
 22
P(x, y) 
y3
y4  24
 23 
 44
33
x4
 34
{ij}E

x2
x3

ij
( xi , x j ) ii ( xi , yi )
iV
 xi 
 xi 
1
1


}
exp
{

(
x
,
x
)
V
}
exp
{

(
x
,
y
)
V


i
j
ij 
i
i
ii 


x
2
2
{ij}E
 yi 
 j  iV
  i  j sii
Vij  
 s ji


 j i s jj 
sij
(Vii )1,1  ii sii
＊ポテンシャルへの分解の不定性はパラメータ {i j }が担う．
message
i j
i j
exp{
( x j  i  j ) 2 }
2
2
 j i
 j i
M j i ( xi ) 
exp{
( xi   j i ) 2 }
2
2
M i j ( x j ) 
belief
i

exp{ i ( xi  i ) 2 }
2
2
|  ij |
1
bij ( xi , x j ) 
exp{ ( xi  i , x j   j ) ij ( xi  i , x j   j )T }
2
(2 )
2
bi ( xi ) 
2008年5月29日
情報数物研究会＠東北大学
{ij} E
i V
{ij} E
15/38
GGMのときのLBP Algorithmの更新式
(messageの更新式)
2
M
s
1
( x )  ~i jsiiij ( xi , x j ) ii ( xi ,jiyi )  M k(t) i ( xi )dxi
Z ij
 s   s kNi \{ j}(t )
( t 1) ( t 1)
i  j j j i
分散の逆数
j i
M
j j
jj

k j
kN ( j ) \{i}
jj
sij2
1
(t )
( x )  ~j is 
ij ( xi , x j ) jj ( x j , y j )  M k  j ( x j )dx j
jj 
Z ji
j \{i} ( t )
i j sii  i i sii  kN
k i
( t 1) ( t 1)
j i i i j
sij ( i i sii ~ii 
i(t 1j )  
平均値
kN ( i ) \{ j }
(t )
(t )
k i k i
kN ( i ) \{ j }
(beliefの更新式)


t)
(i 
j (  i  j sii   i i sii 
s ji (  j  j s jj ~ jj 
 (jt1i)  
{ij} E
)

)

)
(t )
k i
kN ( i ) \{ j }
(t )
(t )
k j k j
kN ( j ) \{i}

(jt) i (  j i s jj   j  j s jj 
 (kt) j )
{ij} E
kN ( j ) \{i}
(it )  
iii(i sxiii ,yi ) (kt) i(t )
b ( xi ) 
kN
( i ) M k i ( xi )

Z
kNi
i

i V
(t )
i

 i  j sii  i i sii   (kt) i

sij
(t )
(t )
 ii ( xi , yi )

kN( t()i ) \{ j }
(t )
bij ( xi , xj ij)  
M k i ( xi )
M k j (x j )

(t )
Z
k

N
\{
j
}
k

N
\{
i
}
ij
i
j
s

s


s




ji
j i jj
j  j jj
k j 

k

N
\{
i
}
j


2008年5月29日
情報数物研究会＠東北大学


{ij} E
16/38
~
更新式の変形 (i j  i j   j i s jj )
(messageの更新式)
sij2
~(t 1)
i  j  
sii 
分散の逆数
 j i  
s jj 
(it )  sii 
kN ( i ) \{ j }
2
ji
s
~(t 1)
(beliefの更新式)
~
(t )

 k i
~(t )

{ij} E
k j
kN ( j ) \{i}
~
 k(t) i
i V
kN ( i )

~
 sii   k(t) i

kN ( i ) \{ j }
(ijt )  
s ji




sij

~(t ) 
s jj   k  j 

kN j \{i}

{ij} E
~
＊{i j }の更新式はパラメータ {i j }によらない．
2008年5月29日
情報数物研究会＠東北大学
17/38
Single Cycleのときのmessageの固定点
y1
y2
yd
x1
x2
xd
y5
y4
x5
x4
y3
x3
 s11

 s21
Vxx  S  


s
 d1
s12
s22
s32
s23
s33



sd ,d 1
s1d 




sd 1,d 
sdd 
Theorem 1(messageの固定点)
グラフ G が1重サイクルのときmessageの固定点は, 分散値につ
いて
*i i 1 

*
i i 1

si ,i 1 i ,i 1  (2  i 1i  1) si 1,i 1 i 1,i 1  si  2,i 1 i  2,i 1  D
2 i 1,i 1
si ,i 1 i ,i 1  (2  i 1i  1) si 1,i 1 i 1,i 1  si  2,i 1 i  2,i 1  D
2 i 1,i 1
i V
D  (det S )2  (1)d 4s12 s23s34 sd 1,d sd ,1 det S
2008年5月29日
情報数物研究会＠東北大学
18/38
証明の概要(Theorem 1)
LBPの分散の逆数に対する固定点方程式は，
2
sd 1
d 1  
sd2 1,d
sdd 
sd2  2,d 1
sd 1,d 1 
sd2 3,d  2
sd  2 , d  2 

2
s23
s33 
s122
s22 
~
s11  d*1
~*
を満たす．式変形することで，2次方程式
~
~
11 (d*1 ) 2  (det S  2sd ,1 d ,1 )d*1  sd21 d ,d  0
~*
{

に帰着する．他の i j } はindexの置換操作で得られる．
2008年5月29日
情報数物研究会＠東北大学
19/38
Single Cycleのときのbeliefの固定点
y1
y2
x1
x2
y5
y4
x5
x4
yd
xd
 s11

 s21
Vxx  S  


s
 d1
y3
x3
s12
s22
s32
s23
s33



sd ,d 1
s1d 




sd 1,d 
sdd 
Theorem 2(LBPが計算するbeliefの固定点)
グラフ G が1重サイクルのとき，ループの入った確率伝搬法
(LBP)が計算するbeliefの固定点は，分散値について
*i 
det S
1 
 ii
である．ここで

 Ei ,i 1


*i ,i 1   ii
 si ,i 1

(1) d 4s12 s23 s34  sd 1,d sd ,1
det S
Ei ,i 1 

si ,i 1 

Ei ,i 1 

 i 1,i 1 
i V
det S  D
 si ,i 1 i ,i 1
2
である．
2008年5月29日
情報数物研究会＠東北大学
20/38
Single CycleのときのLBPの近似精度
・確率伝搬法が計算するbeliefの事後分散の逆数
det S
(1) d 4s12 s23 s34  sd 1,d sd ,1
*
i 
1 
i V

 ii
det S
・真の事後分散の逆数
det S
*
i 
i V
 ii
＊1重サイクルのときのLBPの近似精度は の値が決める．
y1
y2
yd
x1
x2
xd
y5
y4
x5
x4
2008年5月29日
y3
 0
x3
y1
y2
yd
x1
x2
xd
y5
y4
x5
x4
 0
情報数物研究会＠東北大学
y3
x3
21/38
式の意味すること



通常Chainに対する転送行列法において, 周期的境界条
件を強引に課したときの転送行列法が計算するずれ．
1重サイクルにおけるベーテ自由エネルギーの最小値
1重サイクルのとき，アルゴリズム(BO, CCCP,
SEQ,…,etc)によらず，必ずこの値を計算．
2008年5月29日
情報数物研究会＠東北大学
22/38
Single Cycleのときの収束必要条件
・確率伝搬法が計算するbeliefの事後分散の逆数
det S
(1) d 4s12 s23 s34  sd 1,d sd ,1
*
i 
1 
i V

 ii
det S
Condition 1(Single Cycleのときの収束必要条件)
1重サイクルにおいて，loopy BPが収束するためには(ベーテ自由
エネルギーの最小値が存在するためには)，

(1) d 4s12 s23 s34  sd 1,d sd ,1
det S
 1
が必要条件である．
例)
10 9 1 


S   9 10 5 
 1 5 10


2008年5月29日
のとき   9
情報数物研究会＠東北大学
23/38
数値実験(Single Cycle)
 10  9.9 1 


S1    9.9 10 0.4 
 1
0.4 10 

1 
10 9 0


9
10
4
0


S2  
0 4 10 1.9 


 1 0 1.9 10 


LBP数値解
LBP数値解
LBP解析解
  41.684211
2008年5月29日
情報数物研究会＠東北大学
真値
  25.786993
24/38
Cycleの長さに対して
d 3

 の値の変化は？
d 4
 4.9 
 10  4.9


  4.9 10  4.9



S3 (d ) 
 4.9 10




  4.9 

  4.9
 4.9 10 


4.9 
 10 4.9


 4.9 10 4.9



S 4 (d ) 
4.9 10 




4
.
9


 4.9
4.9 10 

真値
d
2008年5月29日
情報数物研究会＠東北大学
d
25/38
Single Cycle + Treesのときでは？
s12
x7
x2
x8
x4
x4
x1
x1

s12
s13
s23
x3
x7
x5
x2
x8
x6
det S 
 
1 

 ii
*
i

s23

s13
x3
x5
x6
 s23
 s31

(1)3 4s12

det S 
i {1,2,3}
＊グラフが1重サイクルと任意の木を持つときであっても
の値がLBPの近似精度，収束必要条件を与える．
2008年5月29日
情報数物研究会＠東北大学
26/38
任意のTopologyを持つグラフについて
グラフ G が多重サイクルを持つときLBPが計算する固定点は？
y1
y2
y7
x1 y
5
x7
y6
x5
x6
x2
y3
y4
x3
x4
G  {V , E}
 s11

 ss21
Vxx  S   ss31

 ss41
 ss
 51
ss12
ss13
ss14
s22
ss32
ss23
s33
ss24
ss34
ss42
ss43
s44
ss52
ss53
ss54
ss15 

ss25 
ss35   S d  sS o

ss45 
(s  1)
s55 
とおいたとき, beliefの固定点について
*i (s) 
s による低次からの展開式
を導出する．
2008年5月29日
情報数物研究会＠東北大学
27/38
Edgeに対する符号属性
任意topologicalグラフに対するLBP固定点の集合： 
各edge {ij}  E への符号(+1, -1)の割り当て： sgn(i, j )
各edge {ij}  E の符号の組み合わせベクトル： e
edgeの符号の組み合わせe に対する全体集合：C

x1
x7


x6
2008年5月29日


x5
x2

e  {1,1,1,1,1,1,1,1}

x3

x4
{e}  C
(| C | 2|E| )
e  {1,1,1,1,1,1,1,1}
e  {1,1,1,1,1,1,1,1}
情報数物研究会＠東北大学
28/38
LBP固定点の必要十分条件
Theorem 3 (Gaussian graphical modelにおけるLBP固定点)
1つのedgeの符号の組み合わせ e  C が与えられた下で，
2s
| N (i ) | 2  ii 
i

sgn(i, j ) 1 
jN ( i )
4s 2 s 2ji
 j i
i V
*
{

の連立方程式の解 i } の集合を e と表したとき，LBP固定点の
集合  は，
   e
で表わされる．
eC


2008年5月29日
e 
情報数物研究会＠東北大学
e 
29/38
証明の概要(Theorem 3)
精度の更新式
sij2
~(t 1)
i  j  
sii 
s 2ji
~(t 1)
~(t )
 k i
 j i  
s jj 
kN ( i ) \{ j }
~
 k(t) j
{ij} E
kN ( j ) \{i}
とそれから導かれるbeliefの更新式
(it )  sii 
~
 k(t) i
i V
kN ( i )
~
に対して, {i(t 1j ) } を消去し，belief直接の更新則を考えれば得られる．
2008年5月29日
~
{i(t 1j ) }
~(t )
{i
j}
~
{i(t 1j ) }
{(it 1) }
{(ti ) }
{(it 1) }
情報数物研究会＠東北大学
30/38
1つの (自然な) LBP固定点
*

s  0 のとき i  sii を満たしてほしい．
 s11

 ss21
S   ss31

 ss41
 ss
 51
ss12
ss13
ss14
s22
ss32
ss23
s33
ss24
ss34
ss42
ss43
s44
ss52
ss53
ss54
ss15 

ss25 
ss35   S d  sS o

ss45 
s55 
Theorem 4 (1つのLBP固定点の展開式)
*i (0)  sii を満たす固定点は， e に含まれ，その解は
*i ( s)  sii 
d
s 2ji
j 1(  i )
s jj

s 2  O( s 4 )
i V
に展開される．

2008年5月29日

e 
情報数物研究会＠東北大学
e 
31/38
任意グラフのときのLBPの近似精度
・beliefの事後分散の逆数の展開式
2
d
s
ji 2
*i ( s)  sii  
s  O( s 4 )
j 1(  i ) s jj
i V
i s3の値をLBPの数値
解に加えて補正．
・真の事後分散の逆数の展開式
d
s 2ji 2
det S
 sii  
s   i s 3  O( s 4 )
 ii
j 1( i ) s jj
i V
s
 i  ii tr[(Sd1So )3  {( Sd )ii1 (So )ii }3 ]  2sii  sij sik s jk
3
( j ,k )
i
( sij 
sij
sii s jj
)
＊任意topologicalグラフで変数間の相関が小さいとき (s  1)
 i の値がLBPの近似精度を(支配的に)決定する．
2008年5月29日
情報数物研究会＠東北大学
32/38
 i の意味
i 
sii
tr[(S d1So )3  {( S d )ii1 ( So )ii }3 ]  2sii  sij sik s jk
3
( sij 
( j ,k )
i
x1
x7
x2
x3
x5
x6
x4
sii s jj
)
1  2s11 (s15 s52 s21 )
 2  2s22 (s25 s51s12  s23s35 s52 )
 3  2s33 (s32 s25 s53 )
4  0
5  2s55 (s53s32 s25  s52 s21s15 )
6  0
7  0
＊パスの長さ=3のサイクルを構成するノードに対して
長さ=3のサイクルの存在を考慮した補正．
2008年5月29日
sij
情報数物研究会＠東北大学
 i が存在．
33/38
メッセージを使わない確率伝搬法
( 0)
( 0)
( 0)

,

,

,

STEP 1: beliefの精度(分散の逆数)の初期値 1
2
d
を設定する．
(t )
(t )
(t )
STEP 2: beliefの精度 1 , 2 ,, d を以下の更新式
に従って更新させる．
( t 1)
i

2sii

2 | N (i ) | 

1
jN ( i )
STEP 3: 十分小さい  0 について
4sij2
(it ) (tj )
d
( t 1)
(t )
|



 i
i |   0 を満たすとき
i 1
計算を終了する．さもなければ STEP2 へ戻る．
2008年5月29日
情報数物研究会＠東北大学
34/38
LBPの数値実験の結果
通常の
LBP
メッセージを
使わないLBP
S5 , (1 )
S6
S7
S8
S9 , (1 , 4 )
S9 , ( 2 , 3 )
S10 , ( 2 )
LBP解析解
の展開式
1重ループ
解析解
真値
(i)
(ii)
(iii)
(iv)
(v)
(vi)
9.898980
9.898980
9.900000
0.000000
9.898980
9.898980
9.797959
9.797959
9.800000
0.000000
9.797959
9.795918
9.693747
9.693747
9.700000
0.060000
9.752057
9.750000
6.468627
6.468627
7.300000
1.620000
8.516626
8.312500
4.790380
4.790380
4.900000
0.300000
5.097716
5.083333
9.487039
9.487039
9.700000
0.180000
9.831310
9.803571
-
-
-0.600000
0.900000
-
0.202020
10 1 0 0 


 1 10 1 0 
S5  
0 1 10 1 


 0 0 1 10


10 1 0 1 


 1 10 1 0 
S6  
0 1 10 1 


 1 0 1 10


10 1 1 7 


1
10
1
1


S9  
1 1 10 1 


 7 1 1 10


10 9 1 


S10   9 10 5 
 1 5 10


2008年5月29日
 i の値
10 1 1 1 


 1 10 1 1 
S7  
1 1 10 1 


 1 1 1 10


情報数物研究会＠東北大学
10 3 3 3 


 3 10 3 3 
S8  
3 3 10 3 


 3 3 3 10


35/38
まとめ
ガウシアングラフィカルモデル上の推論問題に対して，効率的
であるLoopy BPを考えた場合に，事後分散の精度を解析的に
求めLBPの近似精度を与えた．それに派生して，LBPの収束条
件，補正法を与えた．
(i)1重サイクル
(ii)1重サイクル+木構造
・LBPの近似精度： 
・LBPの収束条件： 
 1
(iii)任意グラフ(相関が小さい場合)
・LBPの近似精度：
・LBPの補正：
2008年5月29日
i
i
情報数物研究会＠東北大学
36/38
今後の展望
(i) 今回は，1つの正規分布に対しての確率伝搬法の解析で
あったが，混合正規分布への確率伝搬法の拡張は可能
か？そのときの近似精度は？
(ii) 一般に菊池自由エネルギーを考えたときの事後分散の近
似精度は？
・1重サイクルのとき厳密に計算できる？
・任意グラフのときも展開式であれば導出可能？
TAP自由エネルギーでは？（誰かやりませんか？）
(iii) 何か共同研究・・・？
2008年5月29日
情報数物研究会＠東北大学
37/38
渡辺研究室としての位置づけ
混合分布[K. Watanabe]
自由エネルギー
F (n)
縮小ランク回帰[Nakajima]
変分ベイズ（平均場近似）
 2 log n  (m2 1) loglog n
隠れマルコフモデル[Hosino]
ニューラルネットワーク[Nakano]
ベイジアンネット[K. Watanabe]
確率伝搬法，ベーテ近似，菊池近似に基づいた
学習アルゴリズムの漸近論．
ボルツマンマシン[Nishiyama]
ベイズ学習
 1 log n  (m1 1) loglog n
縮小ランク回帰[Aoyagi]
隠れマルコフモデル[Yamazaki]
ベイジアンネット[Yamazaki]
n 学習サンプル数
混合分布[Yamazaki]
漸近領域
2008年5月29日
ボルツマンマシン[Yamazaki]
ニューラルネットワーク[Aoyagi]
情報数物研究会＠東北大学
38/38

Download Report