さて,複雑な確率分布を近似するためのものとして,平均場近似 (MFA = Mean field
approximation)[13,10]に
基づく手法がある. 目的の確率分布が
マルコフランダム場 (MRF = Markov random
field) あるいは
ベイジアンネットワーク (BN = Bayesian
network) といったグラフィカル
モデルによって記述されているとしよう.
自体がその形をしている場合もあるし,EDA のように問題構造を獲得する
ためのモデルとして利用することもできる.
グラフィカルモデルではよく知られているように単連結なグラフ (singly-connected graph) では確率値計算が容易で,最大値や期待値の計算も 動的計画法による再帰計算が可能である (Viterbi アルゴリズムなどが それにあたる). しかしながら,ループのあるグラフ (loopy-graph) では,なんらかの近似が 必要となる.
確率変数が
という
個の成分を持つとしよう.
最も単純なナイーブ平均場近似は,確率分布
を
![]() |
(17) |
ナイーブ平均場近似よりも精度を上げた近似としてベーテ (Bethe) 近似
というものがあるが,これは単連結グラフの場合に用いられる確率伝播法
(Belief-propagation) をループのあるグラフに局所的に適用したものに
一致している. このアルゴリズムを に対して適用すると,
の最大値(つまり
の最小値) を探索するアルゴリズムに
用いることができる.
がある条件を満たせばループのある
グラフであっても最大値を見つけられることがわかっている[18].