ベーテ自由エネルギーに対する
CCCPアルゴリズムの拡張
東京工業大学総合理工学研究科
知能システム科学専攻 渡辺研究室
西山 悠， 渡辺澄夫
Background
Probabilistic information processing
• Inference for Bayesian networks
• Error correcting codes
000101
noise
decode
000111
000101
• CDMA multi-user detection
• Probabilistic image processing
degrade
image
restored
image
Task
High-dimensional distribution
Marginals
Intractable
Task
p( x1 , x2 ,, xd )
Intractable
 p( x , x ,, x )
x1
 xi
1
2
d
xd
• Belief propagation (Sum product algorithm)
Bethe free energy
Optimization techniques
• BO (M. Welling, et. al., 2001)
• CCCP (A. L. Yuille, 2002)
• SEQ (Tonosaki, et. al., 2007)
(Approximate) marginals
Performance of CCCP
CCCP
• guarantees to monotonically decrease Bethe free
energy unlike belief propagation.
• requires huge computational cost compared to
belief propagation.
• does not always converge for synchronous
update of inner loop.
Purpose
We extend CCCP algorithm for Bethe free energy
and present a new CCCP (NCCCP) algorithm.
New CCCP (NCCCP) algorithm
• includes conventional CCCP.
• guarantees to monotonically decrease Bethe free
energy.
• is more stable even for synchronous inner loop.
• can reduce huge computational cost underlying
CCCP.
Concave and convex procedure(CCCP)
CCCP algorithm guarantees to monotonically
decrease the function(al)
F (r)  Fvex (r)  Fcave (r) 
Convex
by the update rule
Fvex (r
(t 1)

)  Fcave (r ).
(t )
Extremum
Concave
Bethe free energy
Bethe free energy
FBethe ({ri }, {rij })    Sij   (| Ni | 1)Si    Eij  rij
d
{ij}B
{ij}B
i 1
Concave
Convex
Conventional CCCP
d
   Sij   Si 
{ij}B
i 1
 E
{ij}B
ij
 rij
d
  | N i | Si
i 1
Approximate marginals
Main result (Key idea)
NCCCP
Bethe free energy 
d

   Sij   Si 
{ij}B
i 1
 E
{ij}B
ij
 rij  f vex (r)
d
  | N i | Si  f vex (r)
i 1
Trivial pair creation 0 

f vex (r)
 f vex (r)
an arbitrary
convex
functional
NCCCP
d
   Sij   Si 
{ij}B
i 1
 E
{ij}B
ij
rij  f vex (r)
d
  | N i | Si  f vex (r)
i 1
d
Particularly,
f vex (r )   (1  ui ) Si .
i 1
Free parameters u U ,
u
CCCP
U

u
CCCP algorithm
NCCCP algorithm (u U )
Outer loop
Outer loop
Inner loop
u
Outer loop
Outer loop
Inner loop
u
u
u Inner loop
u
Inner loop
u
Outer loop
Outer loop
Approximate marginals
Approximate marginals
NCCCP algorithm for Bethe free energy
Theorem (Outer loop)
Outer loop of NCCCP algorithm for minimizing Bethe free
energy is given by as follows:
| N i |1 ui
ui
(t )
ri( t 1) ( xi )  (ri )
exp{ vi 
1
ui

jN i
ij ,i
( xi )},
i {1,, d },
rij(t 1) ( xi , x j )  Wij exp{vij ij,i ( xi ) ij, j ( x j )}, {ij}  B,
where {ui } satisfies ui
 0 for all i {1,, d}.
NCCCP algorithm for Bethe free energy
Theorem (Inner loop)
Inner loop of NCCCP is given by as follows:
| N i |1 ui
ui
(t )
exp{ vi( 1) }   (ri )
exp{ 
ik(,)i
ui
k N i
i {1,, d },
}dxi ,
{ij}  B,
exp{vij( 1) }   Wij exp{ij(,i) ij(, )j }dxj dxi ,
exp{(1 
exp{(1 
1 ( 1)
)ij,i } 
ui
1 ( 1)
)ij, j } 
ui

Wij exp{vij( )  ij(, )j }dx j
| N i |1 ui
ui
(t )
(ri )

( )
i
exp{v

(r )
ui
kN i \{ j }
uj
exp{v
( )
j


kN j \{i}

{ij}  B,
,
}
Wij exp{vij( )  ij(,i) }dxi
| N j |1 u j
(t )
j


( )
ik ,i
( )
jk , j
uj
,
}
{ij}  B.
Update Manner of Inner Loop
Asynchronous update
time 
time   1
time   2
Theorem (Inner loop)
Inner loop of NCCCP is given by as follows:
| N |1 u
ik(,)i
u
( 1)
(t )
exp{ vi
}   (ri )
i
i
i
exp{ 
ui
k N i
}dxi ,
exp{vij( 1) }   Wij exp{ij(,i) ij(, )j }dxj dxi ,
1
exp{(1  )ij(,i1) } 
ui
CCCP guarantees to converge.
Synchronous update
time 
time   1
1
exp{(1  )ij(, j 1) } 
ui
W
ij
(t )
(ri )
exp{vij( )  ij(, )j }dx j
| N i |1 ui
ui
W
ij
( )
i
exp{v

kN i \{ j }
uj
ui
,
}
exp{vij( )  ij(,i) }dxi
| N j |1 u j
(rj(t ) )

ik(,)i
exp{v (j ) 

kN j \{i}
 (jk ,) j
uj
time   2
CCCP does not always converge.
NCCCP converges.
.
}
Role of free parameters u
When u are small
When u are large
Outer loop
Outer loop
slow
or
Outer loop
Outer loop
convergence
slow
or
convergence
Approximate marginals
Outer loop
Outer loop
Outer loop
Outer loop
fast
fast
fast
fast
Approximate marginals

There exist optimal values u .
Numerical Results(1/2)
(i) Asynchronous inner loop
S  (10, 2, 5)
CCCP
S  (10, 0.1, 20)
CCCP
Numerical Results (2/2)
(ii) Synchronous inner loop
S  (10, 0.1, 5)
CCCP
S  (10, 2, 5)
CCCP
Conclusion
We presented a new CCCP (NCCCP) algorithm for
Bethe free energy.
New CCCP (NCCCP) algorithm
• includes conventional CCCP.
• guarantees to monotonically decrease Bethe free
energy.
• is more stable even for synchronous inner loop.
• can reduce huge computational cost underlying
CCCP.
Future works
• To design efficient NCCCP algorithm based on
the optimality of free parameters.
• To apply NCCCP algorithm to practical problems
such as CDMA multi-user detection problems or
decoding algorithm for LDPC codes.
1.外崎幸徳，樺島祥介, “CCCPに基づくCDMAマルチユーザ検出アルゴリズム,”
電子情報通信学会論文誌 D, vol. J89-D, no. 5, pp. 1049-1060, 2006.
2.T. Shibuya, K. Harada, R. Tohyama, and K. Sakaniwa, “Iterative Decoding
Based on the Concave-Convex Procedure,” IEICE Trans. Fundam. Electron.
Commu. Comput. Sci., vol. E88-A, no. 5, pp. 1346-1364, 2005.
Example: Gaussian Distributions
NCCCP algorithm= Outer loop + Inner loop
Theorem (Outer loop in Gaussian distributions)
| Ni | 1  ui (t ) 1
i  ij,i ,
ui
ui jNi
si ,i  ~ij,i
si , j 
~


~ ,
~
s
s


j ,i
j, j
ij , j 

(it 1) 
~
Sij(t 1)
i {1,, d },
{ij}  B.
Theorem (Inner loop in Gaussian distributions)


( 1)
ij ,i
( 1)
ij , j
si2, j
ui
| N | 1  ui (t ) 1
1

{

 i
i 
1
ui  1 | Ni |
u
ui
( )
i
 ij,i
| Nj |
si2, j
| N j | 1  u j (t ) 1
1

{


j 
1
u j 1 | N j |
u
uj
( )
j
 ij, j
| Ni |
uj
  },
{ij}  B,
 
{ij}  B.
( )
ik ,i
kN i \{ j }
kN j \{i}
( )
jk , j
},

2 - レーザー学会

営業時間 - S3 amazonaws com

このニュースに関する資料はこちら