ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻　渡辺研究室　 　　西山　悠，　渡辺澄夫

確率伝搬法(Belief Propagation; BP) 確率伝搬法とは・・・ 効率的な計算量 (高次元)確率分布 周辺確率 通り!

確率伝搬法の応用研究 (i) ベイジアンネットを用いた確率的推論 (ii) 誤り訂正符号 (Turbo, LDPC 符号) noise decode 000101 000111 000101 (iii) CDMA (符号分割多元接続) (iv) 確率的画像処理 復元アルゴリズム 劣化 画像 復元 画像

確率伝搬法の性質 ・グラフがループを持たないとき(BP) BPは，正確な周辺確率を計算 ・グラフがループを持つとき(Loopy BP;LBP) LBPは，近似的に周辺確率を計算 or LBPの解が収束しない場合もある． Ex. ・T. Heskes, ”On the Uniqueness of Loopy Belief Propagation Fixed Points”, Neural Computation 16(11), 2379-2414, 2004. ・Y. Weiss,”Correctness of belief propagation in graphical models with arbitrary topology”, Neural Computation 13(10), 2173-2200, 2001.

LBP解 = ベーテ近似解 LBP解 = ベーテ近似解 ベーテ自由エネルギー(汎関数) LBPによって計算される 近似周辺確率(LBP解)

目的 ループのある正規分布の場合に，ベーテ近似解(LBP解) を与え，ベーテ近似の近似精度を明らかにする． ・正規分布 の精度行列 が， (i)1重ループを表すとき ベーテ近似解析解(LBP解析解) LBPが収束するための必要条件 (ii)任意のグラフ構造を表すとき 相関が小さいときの ベーテ近似解析解の展開式 確率的画像処理 田中和之，確率モデルによる画像処理技術入門，森北出版，2006.

LBPアルゴリズム LBP解 ?

(i) 1重ループのとき ベーテ自由エネルギー 周辺密度 ベーテ近似解 ・メッセージの分布を正規分布とする．

メッセージの固定点(1重ループ) 定理1 ガウス分布が1重ループのグラフ構造を表すとき，ベーテ近似解を与えるメッセージの固定点は， で， で表わされる． は行列　 の余因子である．

メッセージの固定点の直観的意味 固定点 流入 流出

ベーテ近似解(1重ループ) 定理2 ガウス分布が1重ループのグラフ構造を表すとき，ベーテ近似解 (LBP解) は， で， ベーテ自由エネルギー 周辺密度 定理2 ガウス分布が1重ループのグラフ構造を表すとき，ベーテ近似解 (LBP解) は， で， 一方で，真の周辺密度は， で， ＊ベーテ近似の近似精度は で決められる．

LBP収束条件(1重ループ) 収束必要条件(1重ループ) 1重ル－プのLBPが収束するためには，精度行列 について， が成り立つことが必要である． 例． のとき

数値実験(1重ループ) LBP数値解 LBP数値解 真値 LBP解析解

の次元 に対する振る舞い ? ? ? 真値

(ii) 任意のグラフのとき ベーテ自由エネルギー(汎関数) 多重ループ 周辺密度 ベーテ近似解

周辺密度の固定点方程式（１） 補題 ベーテ近似解を与える周辺密度の精度 は， をそれぞれの項で任意にとるとした下で， からなるいずれかの連立方程式の組を満たす．

周辺密度の固定点方程式（２） 自明な条件 のとき周辺密度の精度が 自明な条件を成り立たせるのは をすべて にした 場合である．すなわち， の連立方程式のときである．

(ii)任意のグラフのとき（相関が小さいとき） ベーテ自由エネルギー(汎関数) 周辺密度の固定点方程式 の解をsについての低次からの 展開式として導出 周辺密度 1つのベーテ近似解 のとき

ベーテ近似解(相関が小さいとき) 定理3 補正 ガウス分布が任意のグラフ構造を表すとき，1つのベーテ近似解 (LBP解) は， で， について次のように展開される． 補正 一方で，真の周辺密度は， で， ＊木構造，1重ループのとき

(iii) メッセージを使わない確率伝搬法 更新パラメータ 個

メッセージを使わないLBPの更新式 STEP 1: 周辺密度の精度(分散の逆数) の初期値を設定する． STEP 2: 周辺密度の精度 を以下の更新式 に従って更新させる． STEP 3: 十分小さい について　　　　　　　　　　　　　を満たすとき 計算を終了する．さもなければ STEP2 へ戻る．

数値実験(相関が小さいとき) 通常の LBP メッセージを 使わないLBP LBP解析解 の展開式 LBP数値解 の補正 1重ループ 解析解 真値 木構造 (i) (ii) (iii) 9.898980 9.900000 9.797959 9.800000 9.693747 9.700000 6.468627 7.300000 4.790380 4.900000 9.487039 - -0.600000 (iv) (v) (vi) 9.900000 9.898980 9.800000 9.797959 9.795918 9.760000 9.752057 9.750000 8.920000 8.516626 8.312500 5.200000 5.097716 5.083333 9.880000 9.831310 9.803571 0.300000 - 0.202020 1重ループ 一様 全結合 全結合

まとめ ループの入った正規分布の場合にベーテ近似の近似精度を明らかにした． (i)1重ループのとき ベーテ近似解析解(LBP解析解)を導出し，LBPの収束条件，近似精度を決定している量を解析的に明らかにした． (ii)任意のグラフ構造のとき 相関が小さいときの，LBPの近似精度を決定している量を 解析的に明らかにした． (iii)メッセージを介さない確率伝搬法の更新式を与えた．

Belief Propagation (BP) 周辺分布構成式

Gaussian Distribution Target : Gaussian Distribution Message Update Rules Message

の性質 木構造，1重ループ 一様全結合 LBP数値解の補正 周辺密度関数 の精度 真値 LBP解析解の展開式 LBP数値解