"確率伝搬法"

1980年代後半Pearlが提案した確率伝搬法は，大規模なグラフィカルモデルに対する確率推論のための計算手法である．同等の手法は統計物理学，統計学，誤り訂正符号の復号法などにも存在し，広く用いられている．確率伝搬法は木の構造のグラフに対してはグラフの大きさに比例した計算量で厳密解が得られる．しかしループを持つグラフに対しては繰り返し計算の収束性，および得られた結果の近似精度ともに理論的には十分理解されていなかった．一方で確率伝搬法は実用上有効な手法であり，その性質を理論的に明らかにすることは重要 …

We present a result on the local stability of the Bethe CCCP algorithm, proposed by Yuille as an alternative to the belief propagation for solving minimization problems of Bethe free energies. We first show that the Bethe CCCP algorithm can be …