ガウシアン確率伝搬法の 近似精度に対する理論解析

Presentation on theme: "ガウシアン確率伝搬法の 近似精度に対する理論解析"— Presentation transcript:

1 ガウシアン確率伝搬法の 近似精度に対する理論解析
ガウシアン確率伝播法の近似精度に対する理論解析と題しまして　東京工業大学の西山が発表させて頂きます． 東京工業大学総合理工学研究科 知能システム科学専攻　渡辺研究室　 　　D1　西山　悠

2 背景 確率伝搬法(Belief Propagation;BP) (高次元)確率分布の周辺確率を 効率的に求める計算手法 Ex.
人工知能における確率推論 題名にもあります確率伝播法というのは，一言で言いますと確率分布の周辺確率，周辺分布を効率的な計算量で計算することのできる計算手法と言うことができまして，大規模な，高次元の確率分布においてその威力を発揮するものです．この確率伝播法は，広い分野で研究されていまして，ベイジアンネットワークを始めとする人工知能における確率推論や，Turbo符号，LDPC符号などの誤り訂正符号，無線run，携帯電話などの移動体通信とそれらの基地局間におけるユーザー検出の問題，劣化画像の画像修復として，ベイズ統計に基づいた確率的な画像処理などにおいて，確率伝播法の周辺分布を求めるアルゴリズムが研究されています． Turbo 符号,LDPC符号 CDMA 通信 確率的画像処理

3 背景 target確率分布が木構造 target確率分布がloop構造を持つ(LBP) 計算される周辺確率は厳密 収束性の問題，近似周辺確率
T. Heskes, ”On the Uniqueness of Loopy Belief Propagation Fixed Points”, この確率伝播法についてですが，性質として，確率伝播法はもともと周辺確率を計算したいtarget確率分布が木構造で表される確率分布のときに構成されるアルゴリズムでして，そのときに計算される周辺確率は厳密に正しい結果を与えるのですが，belief propagationをloop構造が存在するtarget確率分布に適用した場合には，理論的な保証がないために，BPのアルゴリズムがそもそも収束しないという問題が存在し，収束した場合には，収束値は正しい値ではなく近似的な周辺確率を与えることになります．このときのbelief propagationは前者と区別してLoopy Belief Propagationと呼ばれているのですが，このLBPが収束するための条件について，LBPの収束性はLBPの更新式の固定点の一意性と強く関係しているという信念の下に，LBP固定点の一意性の条件について研究されています． Neural Computation 16(11), , 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), , 2001.

4 目的 LBPを多次元正規分布に適用したときの 近似精度を解析的に明らかにする. 確率的画像処理
K. Tanaka, H. Shouno, M. Okada, “Accuracy of the Bethe approximation for hyperparameter estimation in probabilistic image processing”, このような確率伝播法について，本発表では，Loopy Belief Propagation を多次元正規分布に適用した場合の，LBPによって計算される近似周辺分布の真の周辺分布からのずれについてその近似精度を解析的に明らかにすることを目的とします． LBPを多次元正規分布に適用するという状況は，確率的画像処理において周辺尤度最大化 J.phys. A, Math. Gen., vol.37, no.36, pp ,2004. 田中和之, “確率モデルによる画像処理技術入門”, 森北出版, 2006.

5 内容 ・Belief Propagaton (BP) ・Loopy Belief Propagaton (LBP)
・Gaussian Distribution ・Main Results Single Loop Arbitrary graph ・Conclusion

6 BP algorithm Target Marginal distribution Tree-graph
(Singly-connected graph)

7 BP algorithm Marginal distribution

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

9 Loopy Belief Propagation (LBP)
周辺分布構成式 Graph with a loop 収束性の問題 近似周辺確率

10 Message　　　　の決定方法 Consistency Constraints 周辺分布構成式 ＋ Message Update Rules

11 Gaussian Distribution
Target : Gaussian Distribution Message Update Rules Message

12 Main Results Theorem 正規分布 のグラフ構造が１重ループのとき Message Update Rulesの固定点は, で
　　　　　 のグラフ構造が１重ループのとき Message Update Rulesの固定点は, で である．

13 Main Results Corollary , について このときLBPによって計算される周辺分布(belief)は， 分散の逆数 逆行列
分散の逆数　 , 逆行列 について である．

14 LBP ⇒ BP LBP True loop tree Loopy Belief Propagation

15 LBPの近似精度 Kullback-Leibler (KL)距離は 真の周辺分布 近似周辺分布

16 共分散値<<1 のときの周辺分布
Multiloopsを含む任意 のグラフ構造では？ 多重ループ のもとで における展開を導出

17 Beliefの固定点方程式 周辺分布 固定点方程式 Message 固定点方程式 Theorem 近似周辺分布の分散の逆数 は の
組からなる連立方程式のいずれかを 満たす． はそれぞれの項で任意にとる.

18 Beliefのs<<1での展開
(True) Theorem を満たす固定点方程式は の連立方程式に限り,これを満たす の展開式を持つ. は

19 LBPの結果とTrueとの比較 LBPの結果 True Theorem

20 まとめ 多次元正規分布の場合に, LBPの近似精度を 解析的に言及した. 特に (1)１重ループ構造のときLBPの近似精度は
の量で決められる. (2)任意のグラフ構造で共分散が小さいときの 　LBPの近似精度を明らかにした.

21 Future Works 数値実験による比較 LBPの補正アルゴリズムの構築 固定点への収束率のCCCPとの比較
高次の相関があるときへの拡張

22 A Single Loop + Tree Structures