一般化された確率伝搬法(Generalized belief propagation, GBP)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/02/25 02:50 UTC 版)
「確率伝搬法」の記事における「一般化された確率伝搬法(Generalized belief propagation, GBP)」の解説
確率伝搬法は通常の場合、因子グラフ上でのメッセージを更新するアルゴリズムとして表現される。メッセージは変数ノードとその近傍である因子ノード間、もしくはその逆を含む。 ここで、グラフ上でのクラスター間におけるメッセージを考える。これが一般化された確率伝搬法アルゴリズムの一つである。そのようなメッセージを伝搬させる際にはまず対象のグラフ上におけるクラスターの集合を定義する必要があるが、それにはいくつかの方法がある。クラスター間でメッセージを交換するというアイデアは初めに物理学者である菊池良一が導入し、現在では菊池のクラスター変分法という名前で知られている。 確率伝搬法の精度を改良する際のもう一つの手法として、対象の場(メッセージ)の分布のレプリカ対称性を破る方法がある。この一般化によってsurvey propagation(SP)と呼ばれる新しい手法が導かれており、充足性やグラフ彩色問題などといったNP完全な問題に対して非常に効率的に解くことができる。 クラスター変分法とsurvey propagationは、確率伝搬法を2つの異なるアプローチによって発展させたアルゴリズムである。
※この「一般化された確率伝搬法(Generalized belief propagation, GBP)」の解説は、「確率伝搬法」の解説の一部です。
「一般化された確率伝搬法(Generalized belief propagation, GBP)」を含む「確率伝搬法」の記事については、「確率伝搬法」の概要を参照ください。
- 一般化された確率伝搬法のページへのリンク