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

隠れ変数${\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で得られた値を用いて、十分統計量の期待値を計算する