読者です 読者をやめる 読者になる 読者になる

#14 Variational methods for the dirichlet process

論文100本ノック ICML

D. M. Blei and M. I. Jordan. In International Conference on Machine Learning, 2004.
2月は論文100本ノックが止まってたような感じですが、別に読んでなかったんじゃなくってwikipedia:en:Dirichlet_process(DP)についての論文読んでたけど難しくて分からないところばっかりだったので書けてなかっただけです。

有限混合モデルをDPMを使って無限大に拡張したモデルを変分ベイズでいかに推論するかについての論文。DPMによるモデルのグラフィカルモデルは以下のようになる。
http://img.skitch.com/20100222-prbfck17u1pnnua1yk1mynekxx.jpg
Vはパラメータ\mbox{Beta}(1, \alpha)から生成される確率変数、そのVを元にどのクラスタから生成されたかを示す変数Zが生成される(ZはパラメータVの多項分布に従う確率変数])。一方、どのクラスタから生成されたかが決まると\eta^\starをパラメータとする分布(ここでは指数分布族)からXが生成される、というようなモデル。\eta^\starにはハイパーパラメータである\lambdaがいる。サンプルごとに\eta^\starが生成されるかというと、そういうことはなくてDPのクラスタ効果によって同じパラメータが生成されることが普通にあって、サンプルの対数でクラスタの数が増加していく。

DPはstick-breaking constructionによっても表現できるというのが知られていて(Ishwaran & James, 2001)、これは変分ベイズと相性がよい。

推論の方法

この論文で使われている推論の方法は

  • 変分ベイズ
  • truncated DP Gibbs
  • collapsed DP Gibbs

の3つ。変分ベイズ使った推論の方法が本題(section 4)。下の二つはsection 3で書かれてる。

Collapsed Gibbs sampling

collapsed Gibbs samplingとGibbs samplingの違いがよく分かってないのであとで調べる。Gibbs samplingはパターン認識と機械学習 下 - ベイズ理論による統計的予測に乗ってる。一つ以外の変数と定数と見て、それからサンプリングしてくるという方法(大雑把)。この辺でちょっと書いてた。導出の付近は原論文(Neal, 2000)を見たほうがよいと思うけど、結果としては既存のクラスタkに属する確率が(7)式の
p(z_n^k = 1 | \mathbf{z}_{-n}, \alpha) = \frac{n_k}{\alpha + N - 1}
で、新しいクラスタに属する確率が(8)式の
p(z_n^k = 1 | \mathbf{z}_{-n}, \alpha) = \frac{\alpha}{\alpha + N - 1}
で書き表わせる。こやつを使うと(9)式のように事後予測分布を計算することができる。

Gibbs sampling for a TDP mixture

Collapsed Gibbs samplingの問題点は、クラスタ変数Z_nが以前にサンプリングされた他のクラスタ変数に依存しているので遅いということである。あれ、なんか日本語が変だ。。。

In the collapsed Gibbs sampler, the distribution of each cluster variable Zn depends on the previously sampled values of every other cluster variable. Thus, the Zn variables must be updated one at a time, which can slow down the algorithm compared with a blocking strategy.

ということで、Ishwaran and James (2001)では、TDP mixtureモデルを使っている。これはstick-breaking constructionで無限に折っていくんじゃなくって、有限のKで止めるというところが違うところ(Collapsed Gibbs samplingだとぐいぐい成長していったりする)。

Variational inference

平均場近似で攻める。グラフィカルモデルをもとに分布を分解できるとことは分解して、いく。基本的には指数分布族になってくれるのだが、(12)式の第三項だけが指数分布族になってくれないので、ごにょごにょと頑張る。

シュミレーションによる実験

シュミレーションによる実験が行なわれていて、3つの手法の負の対数尤度はどれもそれほど大きく違わないが、実行時間に大きな差が出ている。

  • 変分ベイズ
  • truncated DP Gibbs
  • collapsed DP Gibbs

の順に早い。まあ、変分ベイズとMCMC使って変分ベイズのほうが早いのは予想が付くことで、むしろ負の対数尤度が変わらないことのほうが重要なところか。