ベーテ自由エネルギーに対するCCCPアルゴリズムの拡張

摘要

Belief Propagation (BP) is an efficient algorithm for computing marginal probabilities of a high-dimen sional probability distribution. The marginals computed by BP are equivalent to the extrema of Bethe free energy. Concave convex procedure (CCCP) has been studied for the optimization of Bethe free energy. In this paper, we extend the CCCP algorithm for Bethe free energy and present a new CCCP (NCCCP) algorithm. We practically apply NCCCP algorithm to multi-dimensional Gaussian distributions. As a result, NCCCP algorithm enables inner loop to converge even if all Lagrange multipliers in the loop are simultaneously updated. Moreover, we find that there exists an optimal point of the parameters introduced to NCCCP that can reduce the expensive computationalrncost.%高次元確率分布の周辺確率を効率的な計算量で計算するアルゴリズムに確率伝搬法が知られる．確率伝搬法によって計算される周辺確率は，ベーテ自由エネルギーの極値を与える確率分布に等しい．べーテ自由エネルギーの最適化にConcave Convex Procedure（CCCP）の方法が1つに用いられる.本稿では，べーテ自由エネルギーに適用されるCCCPを拡張し，拡張CCCPのアルゴリズムを与える．そして具体的に拡張CCCPを正規分布の場合に適用する．その結果，拡張CCCPは，Inner Loopを同期的に東新させるアルゴリズムの場合であっても極値に収束できることがわかった．また，拡張CCCPに導入したパラメータについて，計算コストを大きく削減するための最適なパラメータ点が存在することがわかった．