LDA の Collapsed Variational Bayesian 推論

Collapsed Gibbs Sampling (以下 CGS)で LDA の推論を行う話は Latent Dirichlet Allocations(LDA) の実装について - 木曜不足にて書いたのだけど、今回はそれとは別の Collapsed Variational Bayesian (以下 CVB) で推論を行う話。

まず、LDA の原論文である [Blei+ 2003] では Variational Bayesian (変分ベイズ、以下 VB)で推論を行っていた。
これは LDA の確率変数 z, θ,φ に対し(観測変数 x は除く)、まず真の事後分布 q(z,θ,φ) を考える。
この真の事後分布において z,θ,φ が互いに独立ではないのだが、それを計算のために独立であると仮定してしまう。
この仮定が変分近似で、この仮定の下で q(z,θ,φ)≈Πq(z_ij)Πq(θ_j)Πq(φ_k) と p(z,θ,φ|x) との KL ダイバージェンスを最小化するように q を求める(変分推論)という手法。実際にはいきなり q が求まることはなく、KL ダイバージェンスを減少させる更新式を導出することになる。
この手法で LDA の推論が出来るわけだが、実際には z と θ,φ は非常に強く依存し合っており、それを独立と仮定してしまうことで発生する誤差が非常に大きいことがわかっている。そのため、先の Collapsed Gibbs Sampling (近似は無しで、mode を確率的に求めている)の方が一般にずっと良い精度が出てしまっていた。

そこで [Teh+ 2007] で提案されているのが CVB。
q(z,θ,φ) を次のように分解する。

q(z,θ,φ) = q(θ,φ|z)q(z) ≈ q(θ,φ|z)Πq(z_ij)

最初の分解は確率の乗法公式なので、近似無しの等価。
一方、LDA のグラフィカルモデルをじぃっと見ればわかるが、各 z_ij 間は独立ではない(θをしばったら条件付独立)。しかしそこに目をつむって q(z) を Πq(z_ij) と分解してしまおうというのが今回の変分近似。
同じくグラフィカルモデルからもわかるように、z_ij 間は少なくとも直接はつながっておらず、z と θ,φ 間を独立と仮定してしまうよりはずっと弱い仮定で済む。おかげで VB よりもかなり精度が良くなることが知られている。
この弱めた仮定の下で、さらに θ,φ を積分消去しつつ変分推論を行うのが CVB だ。
q(z_ij) は上の仮定だけから多項分布であることがわかり、そのパラメータの更新式を導出することが出来る。これが変分ベイズの嬉しいところ。

実際の導出の計算はかなり面倒なので、論文の結果を信じることにするｗ
更新式については、[Asuncion+ 2009] がすぐに実装できる形になっていてわかりやすい。
以下、更新式を記述するが、記号は下記のグラフィカルモデルのものに合わせている(こちらの記号の割り振りの方が良く見るので)。

(図は Wikipedia-en の LDA より)

この記号＆ CVB の仮定の下で、先ほど書いたとおり事後分布 q(z_ij) は K 次の多項分布であると定まるので、そのパラメータ γ_ij=(γ_ijk) の更新式が得られる。

$\gamma_{ijk} \propto \exp\left(\mathbb{E}_{q(\boldsymbol{z}^{-ij})}\left[p(\boldsymbol{x},\boldsymbol{z}^{-ij},z_{ij}=k)\right]\right)$
$=\exp\left(\mathbb{E}_{q(\boldsymbol{z}^{-ij})} \left[\log(n_{jk}^{-ij}+\alpha)+\log(n_{kw}^{-ij}+\beta)-\log(n_{k}^{-ij}+V\beta) \right] \right)$

ただし $w=x_{ij}$ , $n_{kw}=\sum_{i,j|x_{ij}=w} \gamma_{ijk}$ , $n_{jk}=\sum_{i} \gamma_{ijk}$ , $n_{k}=\sum_{ij} \gamma_{ijk}$ , 肩に -ij がついているものは γ_ij を除外して和を取ったもの、V は語彙数。
この式中にある E[log(...)] は解析的に計算することが出来ないため、ガウス近似(exp の中身をテイラー展開して2次までを取る)を行うことで、計算できる式になる。
ここで $V_{*}=\sum \gamma_{ijk}(1-\gamma_{ijk})$ , つまり分散的な値。和を取る範囲の条件は n_* と同様。

$\gamma_{ijk}\propto \frac{n_{kw}^{-ij}+\beta}{n_{k}^{-ij}+V\beta}(n_{jk}^{-ij}+\alpha)\cdot\exp\left(-\frac{V_{jk}^{-ij}}{2(n_{kj}^{-ij}+\alpha)^2}-\frac{V_{kw}^{-ij}}{2(n_{wk}^{-ij}+\beta)^2}+\frac{V_{k}^{-ij}}{2(n_{k}^{-ij}+V\beta)^2}\right)$

ただ、この式は若干面倒。
そこで [Asuncion+ 2009] ではテイラー展開の0次の項までを使って近似した CVB0 という更新式を提案している。

$\gamma_{ijk} \propto \frac{n_{kw}^{-ij}+\beta}{n_{k}^{-ij}+V\beta}(n_{jk}^{-ij}+\alpha)$

おいおいそれって近似ってレベル？　とか素人的には思うのだけど、こんな簡単な更新式で CVB や CGS と遜色ない精度をたたき出すのだから不思議。
ある程度学習が進んで局所解に十分近づいてくれば、2次の項はほとんど消えてしまうのだろう。

またこれらの更新式から、同じドキュメント j の同じ単語 w を指す x_ij と x_i'j があり、かつその γ_ij と γ_i'j が更新前に同じ値であったとしたら、更新後のγも同じ値になることがわかる。
よってそのように初期値を選んでおくことで、CVB の計算量は O(MK) (ただし M はドキュメントごとにユニークな単語数の総数) となる。
CGS の計算量が O(NK) (ただし N はコーパスの全単語数)であり、明らかに M << N なので、CVB は CGS より結構速い。サンプリングというそこそこ重い処理をしなくていいのも、実処理時間の短縮に貢献してくれる。

というわけで CVB0 による LDA の推論を実装したものを、例によって github に転がしてある。

https://github.com/shuyo/iir/blob/master/lda/lda_cvb0.py

実装量的には CGS のせいぜい2割増し程度か。VB はそこそこ手間がかかるイメージだったのだけど、積分消去されているおかげでとっても簡単になっている。
動かしてみた実験結果はまた今度。

ところで、今回の地震での計画停電などなどの情報を得ようにも、アクセスが集中したりして、見たいときになかなか見れなくて困ってたけど、三鷹市はそういう情報を twitter アカウント [twitter:@mitaka_tokyo] で流し始めてくれて、めちゃめちゃ助かってる。
そして今日市役所に行ったら、張り出されていた停電のグループ分け地区の情報をわざわざ見に来ている人が結構いたなあ。テレビは津波の映像をリピートしてばかり。あ、いや、今日は吉祥寺駅と三鷹駅と調布駅の映像ばっかりだったかな。そんなんでいいの？

References

[Teh+ NIPS2007] A Collapsed Variational Bayesian Inference Algorithm for Latant Dirichlet Allocation
[Asuncion+ UAI2009] On Smoothing and Inference for Topic Model