確率伝搬法
↑ Weiss, Yair; Freeman, William T. (October 2001). “Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology”. Neural Computation 13 (10): 2173–2200. doi:10.1162/089976601750541769. PMID 11570995.
↑ Malioutov, Dmitry M.; Johnson, Jason K.; Willsky, Alan S. (October 2006). “Walk-sums and belief propagation in Gaussian graphical models”. Journal of Machine Learning Research 7: 2031–2064. http://jmlr.csail.mit.edu/papers/v7/malioutov06a.html 2009年3月28日閲覧。.
↑ Gaussian belief propagation solver for systems of linear equations. By O. Shental, D. Bickson, P. H. Siegel, J. K. Wolf, and D.
確率伝搬法は通常の場合、因子グラフ上でのメッセージを更新するアルゴリズムとして表現される。メッセージは変数ノードとその近傍である因子ノード間、もしくはその逆を含む。
ここで、グラフ上でのクラスター間におけるメッセージを考える。これが一般化された確率伝搬法アルゴリズムの一つである。そのようなメッセージを伝搬させる際にはまず対象のグラフ上におけるクラスターの集合を定義する必要があるが、それにはいくつかの方法がある。クラスター間でメッセージを交換するというアイデアは初めに物理学者である菊池良一が導入し、現在では菊池のクラスター変分法という名前で知られている。
確率伝搬法の精度を改良する際のもう一つの手法として、対象の場(メッセージ)の分布のレプリカ対称性を破る方法がある。この一般化によってsurvey propagation(SP)と呼ばれる新しい手法が導かれており、充足性やグラフ彩色問題などといったNP完全な問題に対して非常に効率的に解くことができる。
クラスター変分法とsurvey propagationは、確率伝搬法を2つの異なるアプローチによって発展させたアルゴリズムである。