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

変分メッセージパッシング（へんぶんメッセージパッシング、英語: Variational message passing、VMP）はJohn Winnによって開発された、指数族の共役分布を用いた離散、連続ベイジアンネットワークを近似的に推論するための手法である。VMPはLatent Dirichlet allocation（LDA）などの手法で利用される近似的変分法を一般化した手法であり、各々のノードの周辺分布を、そのマルコフブランケット上に存在するメッセージを用いて逐次的に更新し、その近似解を求める。

尤度の下限

隠れ変数${\displaystyle H}$と観測データ${\displaystyle V}$の集合が与えられた場合、${\displaystyle V}$のデータのみで構成されたグラフィカルモデルの対数尤度の下限を近似的に求める問題について考える。(後に定義する)確率分布${\displaystyle Q}$を導入すると、${\displaystyle V}$の対数尤度は

${\displaystyle \ln P(V)=\sum _{H}Q(H)\ln {\frac {P(H,V)}{P(H|V)}}=\sum _{H}Q(H){\Bigg [}\ln {\frac {P(H,V)}{Q(H)}}-\ln {\frac {P(H|V)}{Q(H)}}{\Bigg ]}}$

となる。よって、下限${\displaystyle L}$は以下のように定めることができる:

${\displaystyle L(Q)=\sum _{H}Q(H)\ln {\frac {P(H,V)}{Q(H)}}}$

ゆえに、対象の対数尤度は上式の${\displaystyle L}$と、${\displaystyle PQ}$間の相対エントロピーの和によって表現できる。相対エントロピーは非負であるため、上で定義した関数${\displaystyle L}$は観測データの対数尤度の下限を表す。ここで、${\displaystyle P}$の周辺分布を厳密に計算しようとした場合に計算量が爆発してしまうような問題について考える。この場合、${\displaystyle P}$の周辺分布を直接求めるのではなく、まず分布${\displaystyle Q}$に対して周辺分布を計算しやすくなるような単純な性質を仮定する。次に下限である${\displaystyle L}$を最大化するような分布${\displaystyle Q}$を求める。最後に分布${\displaystyle Q}$から、周辺分布を近似的に求める。特に、VMPでは${\displaystyle Q}$に以下の独立の仮定を用いる:

${\displaystyle Q(H)=\prod _{i}Q_{i}(H_{i})}$

ここで、${\displaystyle H_{i}}$はグラフィカルモデルの一部を表す。

更新則の定義

上式で得られた下限はできるだけ大きくなることが望ましい。なぜならこれは下限であるので、下限を本来の尤度${\displaystyle \log P}$に近づけることは近似精度の向上に繋がるためである。先の独立の仮定を付与した分布${\displaystyle Q}$を代入することによって、隠れノード${\displaystyle H_{i}}$でパラメータ化された${\displaystyle L(Q)}$は単純に、${\displaystyle Q_{j}}$と下式によって定義された${\displaystyle Q_{j}^{*}}$間の相対エントロピーと、${\displaystyle Q_{j}}$に関与しない他の項の和によって表現される:

${\displaystyle Q_{j}^{*}(H_{j})={\frac {1}{Z}}e^{\mathbb {E} _{-j}\{\ln P(H,V)\}}}$

ここで、${\displaystyle \mathbb {E} _{-j}\{\ln P(H,V)\}}$は${\displaystyle Q_{j}}$を除くすべての分布${\displaystyle Q_{i}}$上での期待値を表す。ゆえに、${\displaystyle Q_{j}}$を${\displaystyle Q_{j}^{*}}$に設定した場合において、下限${\displaystyle L}$は最大化される。

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

親ノードが、子ノードに対してその十分統計量の期待値を送信する一方で、子ノードはその親ノードに対して、指数型分布族のパラメータを送信する。その際には、別の親のメッセージについても事前に受け取る必要がある。

指数型分布族との関係

グラフィカルモデル上のすべてのノードが指数型分布族であり、かつすべてのノードの分布がその子ノードに対して共役分布であった場合、その十分統計量の期待値は正規化定数を計算することによって求められる。

変分メッセージパッシングアルゴリズム

変分メッセージパッシングはまず、十分統計量の期待値を計算する。そして、対数尤度の下限が固定点に収束するまで、各々のノードに以下の操作を反復して行う:

1. 親ノードからすべてのメッセージを受け取る
2. 子ノードからすべてのメッセージを受け取る
3. 1, 2で得られた値を用いて、十分統計量の期待値を計算する

アルゴリズムの制約

このアルゴリズムでは、すべての子ノードはその親ノードの分布について共役の分布を持つ必要がある。ゆえに変分メッセージパッシングでは、分布の取り方についていくつかの制限がある。例を挙げると、ガウシアン分布の親ノードは(期待値のパラメータにおいて)ガウス分布をとるか、(精度パラメータにおいて)ガンマ分布を取らなければならない。同様に、離散変数の親はディリクレ分布、ポワソン分布と指数分布の親はガンマ分布を取らなければならない。しかしながら、共役分布を取りさえすれば、変分メッセージアルゴリズムは任意のグラフィカルモデルについて適用することができる。

参考文献

• J. M. Winn and C. Bishop (2005). Variational Message Passing., Journal of Machine Learning Research 6: 661-694.
• M. J. Beal (2003). Variational Algorithms for Approximate Bayesian Inference. PhD Thesis, Gatsby Computational Neuroscience Unit, University College London, 2003.

外部リンク

• Infer.NET: 変分メッセージパッシングの実装といくつかのサンプルを含んだ、推論フレームワーク
• VIBESでは変分メッセージパッシングの古典的な実装と、いくつかのサンプルを含む