CCCP アルゴリズム

まず，Bethe自由エネルギーと concave-convex procedure (CCCP) に ついて述べる (Yuille [72], Yuille ら[73])．確率伝播法はタナーグラフに 短い閉路が多数存在すると収束しない場合があるが，CCCPはたとえタ ナーグラフに短い閉路が存在したとしても収束が保証されているアルゴリ ズムである．

2.3節で提案した BNPDアルゴリズムはタナーグラフが短い閉路を多 数持つとき，確率伝播法を適用することはできない．しかし，本節で述べ る「CCCPアルゴリズム」はタナーグラフに短い閉路が存在しても用い ることができ，これはBethe自由エネルギーFB(q)を最小化する方法で ある．Yedidia [70] は確率伝播法で求めた事後確率の Bethe 自由エネル ギーの勾配が 0，すなわち，∇FB(q) =0 であることを示している．

したがって，タナーグラフに閉路がないとき Bethe自由エネルギーを 最小にする belief q がちょうど事後確率に対応している．閉路があると

きは Bethe自由エネルギーを最小にするbelief と真の事後確率との偏り

が存在する．しかし，∇F_B(q) =0 かつF_B(q) ができるだけ小さくなる ような q を見つけることにより事後確率の近似値を得ることができる．

Bethe 自由エネルギーの定義

マルコフネットワークを定義し，その上で Bethe自由エネルギーを定 義する．I を無向グラフの頂点の集合とする．任意のi∈I に対して，有 限個の値をとる確率変数 W_i を考え，W = (W_i)_i∈I，Y をW の部分ベ クトルとし，Y は観測されているとする．i, j ∈I に対して，Wi とWj

が条件付独立となるような V ⊂ {W1, W2, . . . , W_|I|} \ {Wi, Wj}^が存在し ないとき，iとj が辺で結ばれているグラフをマルコフネットワークと呼 ぶ．マルコフネットワークの辺集合をT とする．

さらに，Wi の値をwi，観測ベクトルをyで表す．W の事前確率が次 のように与えられていると仮定する．

P(W =w|Y =y) =K ∏

(i,j)∈T

ψ_ij(w_i, w_j)∏

i∈I

ψ_i(w_i). (2.9)

ただし，w= (w_i)_i∈I である．ψ_i(w_i) とψ_ij(w_i, w_j) はポテンシャルと呼 ばれ，K は正規化定数である．ここで，yは固定されているので式 (2.9) の値は w_i のみによっており，y_i を省略して ψ_i(w_i) が1 変数関数である ことを強調しているが，ψ_i(w_i)はw_i とy_i の関数であることに注意する．

T は I×I の部分集合である．

このとき q=((

qi(wi))

i∈I,wi∈Wi,(

qij(wi, wj))

(i,j)∈T ,(wi,wj)∈Wi×Wj

)

とする．ただし，制約条件

∑

wi∈Wi

qi(wi) = 1 (i∈I),

∑

(wi,wj)∈Wi×Wj

q_ij(w_i, w_j) = 1 ((i, j)∈T),

∑

wi∈Wi

q_ij(w_i, w_j) =q_j(w_j) forw_j ∈ Wj ((i, j)∈T),

∑

wj∈Wj

q_ij(w_i, w_j) =q_i(w_i) forw_i ∈ Wi ((i, j)∈T).

を満たしているとする．このとき，Bethe 自由エネルギーは F_B(q) = ∑

(i,j)∈T

∑

(wi,wj)∈Wi×Wj

q_ij(w_i, w_j) log q_ij(w_i, w_j) ϕij(wi, wj)

−∑

i∈I

(|N(i)| −1) ∑

wi∈Wi

qi(wi) log q_i(w_i) ψi(wi)

(2.10)

と定義される．ただし，ϕij(wi, wj) =ψij(wi, wj)ψi(wi)ψj(wj)である．ま た，ψ(wi, wj) = 0のときqij(wi, wj) = 0，ψi(wi) = 0のとき qi(wi) = 0 と仮定する．

Bethe 自由エネルギーの最小化

CCCPはBethe自由エネルギーをある線形の制約条件のもとで最小に

する q を得るための方法である(Yuille [72])．CCCPはShibuya ら[56]

により，LDPC 符号の復号アルゴリズムにも応用されている．

CCCPでは次の自由エネルギーの最小化問題を考える．

最小化問題. q = (q1, . . . , qN) とし，F(q) が下に有界なエネルギー関 数でF(q) = F_vex(q) +F_cave(q) と表されるとする．ただし，F_vex(q) =

∑_N

i=1q_ilog(q_i/ψ_i) と F_cave(q) をそれぞれ q の下に凸と上に凸な関数と する．L個の線形な制約条件a_ℓ·q=b_ℓ (ℓ= 1, . . . , L) のもとでF(q) の 最小化を考える．ただし，a_ℓ = (a_ℓ1, . . . , a_ℓN) でb_ℓ は定数である．

条件付最小化問題において，更新式q^(t−1) 7→q^(t) は{α_ℓ}^とq^(t−1) が 得られたもとでq^(t) をF(q^(t)) を最小にするように選ぶので

∇Fvex(q^(t)) =−∇Fcave(q^(t−1))−

∑L ℓ=1

αℓaℓ

を満たすように与えられる．ただし，初期値q⁽⁰⁾ は考える問題に依存し て決定されるべきであり，得られる事後確率の推定値はこの初期値に依存 している．この更新式を用いると F(q) は単調に減少し∇F_B(q) =0 を 満たす q に収束する．α_ℓ (ℓ= 1, . . . , L) はℓ 番目の線形な制約条件に対 するラグランジュ乗数であり，a_ℓ·q^(t)=b_ℓ を保証するように選ばれる．

CCCP アルゴリズム (Yuille [72])

更新式は q^(t) について下に凸なエネルギー関数

F^(t)(q^(t)) =q^(t)·h+

∑N i=1

q^(t)_i logq_i^(t) ψ_i +

∑L ℓ=1

α_ℓ(a_ℓ·q^(t)−b_ℓ)

を最小化することに対応する．ただし，h=∇Fcave(q^(t−1)) である．ラグ ランジュ乗数のベクトル α= (α1, . . . , αL) 対し

q^(t)_i (α) =ψie^−(1+hi)

∏L ℓ=1

e^{−αℓaℓi} (2.11)

を満たす q^(t)(α) = (q₁^(t)(α), . . . , q^(t)_N(α)) はF^(t)(q^(t)) を最小にする．こ のとき，α は双対エネルギー

Fˆ^(t)(α) =−

∑N i=1

q_i^(t)(α)−

∑L ℓ=1

α_ℓb_ℓ. (2.12)

を最大にする α である．

CCCP アルゴリズムは2 重のloop からなるアルゴリズムである．つ まり，outer loop では式 (2.11) を計算し，inner loop では式 (2.12) の Fˆ^(t)(α) を最大にするα の値を計算する．また，以下の命題が成り立つ．

命題 3 (Yuille [72]). CCCPアルゴリズムは ∇F_B(q) =0 を満たす q に 収束する．さらに確率伝播法が収束するとき，この q は確率伝播法によ り求めた周辺事後確率と一致する．