変分メッセージパッシング

変分メッセージパッシング（へんぶんメッセージパッシング、、VMP）はJohn Winnによって開発された、指数族の共役分布を用いた離散、連続ベイジアンネットワークを近似的に推論するための手法である。VMPはLatent Dirichlet allocation（LDA）などの手法で利用される近似的変分法を一般化した手法であり、各々のノードの周辺分布を、そのマルコフブランケット上に存在するメッセージを用いて逐次的に更新し、その近似解を求める。
尤度の下限.
隠れ変数formula_1と観測データformula_2の集合が与えられた場合、formula_2のデータのみで構成されたグラフィカルモデルの対数尤度の下限を近似的に求める問題について考える。(後に定義する)確率分布formula_4を導入すると、formula_2の対数尤度は
となる。よって、下限formula_7は以下のように定めることができる:
ゆえに、対象の対数尤度は上式のformula_7と、formula_10間の相対エントロピーの和によって表現できる。相対エントロピーは非負であるため、上で定義した関数formula_7は観測データの対数尤度の下限を表す。ここで、formula_12の周辺分布を厳密に計算しようとした場合に計算量が爆発してしまうような問題について考える。この場合、formula_12の周辺分布を直接求めるのではなく、まず分布formula_4に対して周辺分布を計算しやすくなるような単純な性質を仮定する。次に下限であるformula_7を最大化するような分布formula_4を求める。最後に分布formula_4から、周辺分布を近似的に求める。特に、VMPではformula_4に以下の独立の仮定を用いる:
ここで、formula_20はグラフィカルモデルの一部を表す。
更新則の定義.
上式で得られた下限はできるだけ大きくなることが望ましい。なぜならこれは下限であるので、下限を本来の尤度formula_21に近づけることは近似精度の向上に繋がるためである。先の独立の仮定を付与した分布formula_4を代入することによって、隠れノードformula_20でパラメータ化されたformula_24は単純に、formula_25と下式によって定義されたformula_26間の相対エントロピーと、formula_25に関与しない他の項の和によって表現される:
ここで、formula_29はformula_25を除くすべての分布formula_31上での期待値を表す。ゆえに、formula_25をformula_33に設定した場合において、下限formula_7は最大化される。
変分メッセージパッシングでのメッセージ.
親ノードが、子ノードに対してその十分統計量の期待値を送信する一方で、子ノードはその親ノードに対して、指数型分布族のパラメータを送信する。その際には、別の親のメッセージについても事前に受け取る必要がある。
指数型分布族との関係.
グラフィカルモデル上のすべてのノードが指数型分布族であり、かつすべてのノードの分布がその子ノードに対して共役分布であった場合、その十分統計量の期待値は正規化定数を計算することによって求められる。
変分メッセージパッシングアルゴリズム.
変分メッセージパッシングはまず、十分統計量の期待値を計算する。そして、対数尤度の下限が固定点に収束するまで、各々のノードに以下の操作を反復して行う:
アルゴリズムの制約.
このアルゴリズムでは、すべての子ノードはその親ノードの分布について共役の分布を持つ必要がある。ゆえに変分メッセージパッシングでは、分布の取り方についていくつかの制限がある。例を挙げると、ガウシアン分布の親ノードは(期待値のパラメータにおいて)ガウス分布をとるか、(精度パラメータにおいて)ガンマ分布を取らなければならない。同様に、離散変数の親はディリクレ分布、ポワソン分布と指数分布の親はガンマ分布を取らなければならない。しかしながら、共役分布を取りさえすれば、変分メッセージアルゴリズムは任意のグラフィカルモデルについて適用することができる。