平均場近似

さて，複雑な確率分布を近似するためのものとして，平均場近似 (MFA = Mean field approximation)[13,10]に 基づく手法がある． 目的の確率分布が マルコフランダム場 (MRF = Markov random field) あるいは ベイジアンネットワーク (BN = Bayesian network) といったグラフィカル モデルによって記述されているとしよう． $p_T(x)$ 自体がその形をしている場合もあるし，EDA のように問題構造を獲得する ためのモデルとして利用することもできる．

グラフィカルモデルではよく知られているように単連結なグラフ (singly-connected graph) では確率値計算が容易で，最大値や期待値の計算も 動的計画法による再帰計算が可能である (Viterbi アルゴリズムなどが それにあたる)． しかしながら，ループのあるグラフ (loopy-graph) では，なんらかの近似が 必要となる．

確率変数が $x=(x_1,\ldots,x_K)$ という $K$ 個の成分を持つとしよう． 最も単純なナイーブ平均場近似は，確率分布 $p(x)$ を

$$p(x)\simeq \prod_{i=1}^K p_i(x_i;\theta_i)$$ (17)

という形の分布で近似し，最も $p(x)$ に近くなるようにパラメータ $\theta_i$ を決める(変分ベイズ法と呼ばれるものも基本的には同じ)． 各変数の周辺分布としての $p_i(x_i;\theta_i)$ はかなりよい場合が多いが， 同時分布として見ると大きくずれている場合が多いと言われている．

ナイーブ平均場近似よりも精度を上げた近似としてベーテ (Bethe) 近似 というものがあるが，これは単連結グラフの場合に用いられる確率伝播法 (Belief-propagation) をループのあるグラフに局所的に適用したものに 一致している． このアルゴリズムを $p_T(x)$ に対して適用すると， $p_T(x)$ の最大値(つまり $f(x)$ の最小値) を探索するアルゴリズムに 用いることができる． $p_T(x)$ がある条件を満たせばループのある グラフであっても最大値を見つけられることがわかっている[18]．