Bag of ML Words

ML = Machine Learning, Music Love, and Miscellaneous things in daily Livings

CVB0へようこそ!

ここではMachine Learning Advent Calendarの一記事として、ベイズ推論の研究者の間で少しだけ認知され始めたCollapsed Variational Bayes(周辺化変分ベイズ、CVB)にもとづく推論のお話をします。

なお、私はあくまでユーザとしてCVBを使っているだけです*1。でも、多分間違ったことは書いていないと思います。もし間違ってたら教えていただけると嬉しいです。

そもそも確率的生成モデルとかが分からない方はPRMLや統数研の公開講座「確率的トピックモデル」の 資料などをご覧ください。

CVBのご利益

まずは、既存のベイズ推論手法に対してのadvantageです。

  • 高精度: 理論的には大域解を得られるはずのGibbs samplerに比しても、だいたい同程度、しばしばより良い解が得られます
  • 収束が早い: 多くの場合、素早く収束します
  • 実装が簡単(比較級): Gibbs samplerと比べて、メモリ管理等の観点で実装が簡単です
  • VBよりタイトな下限: 理論的に、VBの変分下限よりもタイトな下限を与えることが示されています。つまり、より真の事後分布に近い変分事後分布が求まるということです。

 こう見ると使わない理由がないですね!

ただし、Collapsed( 周辺化。なぜかMarginalizedとは言わない*2 )とあるように、推定したい確率モデルの中で解析的に周辺化(積分消去)可能な未知変量(パラメータ)があるモデル専用です。

CVB導出 on LDA

ここでは、現在最もCVBが猛威を振るっている*3、トピックモデルを例にして具体的にCVB解を導出します。

私の知っている範囲では、[Teh07]が初出です。ちゃんと導出の流れも書いてあるのですが、ただ、この論文はなかなか読むのが骨なんですよね・・・。また、[Asuncion09]が非常に良いまとめ論文を書いているのですが、いきなり結果だけなので勉強という意味では良くないです。

 

ということで、ここでは直接変分下限を定義して、そこから微分してゼロで導出して見せようと思います。まず、LDAの生成モデルです。太文字はベクトル、大文字は定数、大文字の太文字は集合だと思ってください。

d \in {1, ..., D}は文書のインデックス、k \in {1, ..., K}はトピックのインデックス、iは観測のインデックス、w \in {1, ..., W}は単語のインデックスです。

 

次に変分下限を表記します。PRMLの177ページを参考にすると、

LDAでは次のようになります。

ここでqは変分事後分布です。qは全てのコンポーネントが独立だと思います。

これを各変数のqごとに微分すれば普通の変分ベイズになります。

 

CVBでは、以下の変分下限を考えます。

お気づきのとおり、パラメータがありません。パラメータは概念になりました周辺化されています。ここでq(Z)について微分してゼロを取ればCVBの完成です。

さて、ちょっと技巧的ですが、上式を次のように書き替えます。

 

ここで\setminus (d,i)は{d,i}でインデキシングされる隠れ変数や観測量を除くという意味です。この下限に対して、q(z_{d,i})で微分してゼロ、をこなします。qの分布の独立性を使ってどんどん項を削ると、以下を得ます。

Eは変分事後分布上での期待値を意味します。下についている文字は期待値を取る変数です。この式がLDAのCVBの更新式となります。

 

まず、期待値の中身を具体的に計算します。パラメータが周辺化されていますが、LDAはDirichlet-Multinomialなので手で計算可能です。

ただし

 

さて、上記のlog確率を変分事後分布で期待値を取らないといけませんが、これは計算できません。何故かというと、Z\setminus (d,i) はすごく巨大な離散組み合わせ可能性があるからです。爆発です。

じゃあ、どうするかというと、これをテイラー展開で近似します!というのがCVBのテクニカルな特徴になります。一般にある関数f(x)をxの期待値a = E_x[x]の回りで展開してあげると

となります。両辺に変分事後期待値のEをかぶせると

となります。ここではさらに大胆に2次項も無視しましょう!

 

これをlog確率の2式に適用します。

同様に

つまり、カウント量n_{d,k}, n_{k,w}の変分事後分布上の期待値が計算できれば良いです。ただし、各変数の変分事後分布は独立と仮定しているので、\mathbb{I}(z)の部分を単にq(z)で置き換えるだけでOKというのがミソです。

ということで、上に掲載したlog確率の2式を

を使って計算してあげればlog q(z_{d,i} = k)が求まります。これを全てのk, i, dに繰り返し計算すればLDAをCVB, より正確には簡単バージョンであるCVB0で解いたことになります。なお、オリジナルのCVBはテイラー展開の2次項も使うバージョンですが、これはさすがにややこしいのでここでは割愛です。

 

さてこの形、詳しい人が見れば「Collapsed Gibbsそのものでは!?」となりますが、はい、その通りです。LDAのCVB0はCollapsed Gibbsをソフトアサインメントしただけの形になります。ですので、Collapsed Gibbsを理解している人にとってCVB0は非常にとっつきやすいと思います。

 

理論的解析

CVB(0)の実アルゴリズムは変分事後分布による期待値をテイラー展開で近似した上で下限の停留点を求めています。つまり、これは本物の変分下限ではありませんので、理論的にはVBよりタイトな変分下限が実現できるといっておきながらも実装上はそこへ収束する保障はありませんし、繰り返しごとに解がどこへさまよっていくのか不明です。しかも[Asuncion09]によれば、テイラー2次項までとったオリジナルCVBよりも近似の粗いCVB0の方が性能が良いことが実験的に示されています*4

 

つまり、現状、「実験的に上手く行くから使っている」以上のことが言えません。

 

これに対する唯一の反論が[Sato & Nakagawa, 2012]になります。

彼らの論文では、LDAに対してCVB, CVB0が何をしているのかをα-divergenceを使って解析しています。結論としては、CVB0はzero-forcing effect (学習時に変数をゼロ、つまりにスパースな方向に傾ける力)があまり働かない一方で、オリジナルの(テイラー2次近似の)CVBではこれがq(z_{d,i})の推定に働くことがわかりました。これは、CVBが観測のランダムネスに依存してピーキーな解を与えることを示唆しており、この事がCVBに対するCVB0の優位性につながっているのではないか、と結論しています。

しかし、この議論が成り立つのは現状LDAのみであり、他のモデルに対するCVBには何もいえません。さらに、どこに収束するか、そもそも無限回回したらどこかに収束することを保障できるのかも不明のままです。

CVBの理論解析は現時点で重要なopen problemの一つと言えるでしょう。

 

近年の進展

最後に、CVB周りの研究のまとめです。まず、LDAの無限クラスタ拡張であるHDP-LDAについては早いうちに解が導出されています[Teh08]。CVBはながらくトピックモデルだけだったのですが、HMM[Wang & Blumson13a], PCFG[Wang & Blumson13]もようやく解かれました。私が注目しているのはKDD13で発表されたStochastic Approximation解法[Foulds13]です。今後はこのようにより早く解けることが重要になると思います。

参考文献

[Teh07] Teh et al., "A Collapsed Variational Bayesian Inference Algorithm for Latent Dirichlet Allocation", Advances in Neural Information Processing Systems 19 (Proceedings of NIPS), 2007.

[Asuncion09] Asuncion et al., "On Smoothing  and Inference for Topic Models", in Proc. UAI, 2009.

[Sato & Nakagawa, 2012] Sato and Nakagawa, "Rethinking Collapsed Variational Bayes Inference for LDA", in Proc. ICML, 2012.

[Teh08] Teh et al., "Collapsed Variational Inference for HDP", in Proc. NIPS, 2008.

[Wang & Blunsom13a] Wang and Blunsom, "Collapsed Variational Bayesian Inference for Hidden Markov Models", in Proc. AISTATS, 2013.

[Wang & Blunsom13b] Wang and Blunsom, "Collapsed Variational Bayesian Inference for PCFGs", in Proc. ACL, 2013.

[Foulds13] Foulds et al., "Stochastic collapsed variational Bayesian inference for latent Dirichlet allocation", in Proc. KDD, 2013.

 

2015/10/04追記

LDAのCVBについては佐藤一誠先生の下記の本がダントツに良いです。

 

*1:つまり推論手法が研究対象ではありません

*2:理由をご存知の方、教えてください

*3:個人的感想

*4:わけがわからないよ!