階層ディリクレ過程を実装してみる (5) HDP-LDA の更新式を導出 (パープレキシティ)

HDP-LDA の更新式を実装できたら、それが正しく動いているのか、そして収束したかどうかを確認するために perplexity を求めたいところだが、こちらも例によって論文には詳細な数式は書き下されていないので、最後にこれをやっつけよう。

$\displaystyle\exp\left(-\frac 1I\;\log p(w_1,\cdots,w_I|\text{Training corpus})\right)$

論文ではパープレキシティはこのような式で定義されている。
LDA の眷属は bag-of-words モデルなので、単語はすべて i.i.d. であることを使って展開していくと、

$p(w_1,\cdots,w_I|\text{Training corpus})=\prod_{w\in\text{Test data}}p(w|\boldsymbol{X})$
$=\prod_{w\in\text{Test data}}\sum_z p(z|\boldsymbol{X})p(x=w|z,\boldsymbol{X})$

ここで事後分布 p(z|X) と p(x|z,X) はそれぞれ次のようになる。

$p(z_{ji}|\boldsymbol{X})\sim\text{DP}\left(\alpha+n_j,\;\;\frac{\alpha}{\alpha+n_j}H+\frac{1}{\alpha+n_j}\sum_k n_{jk}\delta_{\phi_k}\right)$
$p(x|z=k,\boldsymbol{X})\sim\text{Dir}\left(\beta+n_{k1},\;\cdots,\;\beta+n_{kV}\right)$

ディリクレ分布の事後分布は PRML 等でもおなじみのものだが、ディリクレ過程の事後分布はなかなか見たこと無い人も多いかと。かの Ferguson の原典にはもちろんちゃんと書かれているんだけど、普通それ読まないし読めない。
で、なんかいいのないのかなあと探してたら、まさに Teh さんのサイトで Springer の Encyclopedia of Machine Learning の Dirichlet Process の項の原稿なのかな？　が公開されていた。

(Yee Whye Teh) Dirichlet Process

百科事典の項目なのでさすがに導出過程などは全部省かれて入るものの、ディリクレ過程の性質が CRF やら stick breaking やら、そして事後分布までひと通り網羅されていて、もちろん今風の記法で書かれているので、とりあえず DP を扱う上で知っておかないといけないことを抑えておきたいという人にはおすすめかと。

話を元に戻して。
これらの事後分布の分布を perplexity に放り込むには厳密には更に周辺化とかうんぬんしなくといけなくて、そんな計算出来そうにない積分しだしたら頭が痛くなってくるので、それぞれの期待値で代用していいことにしよう(つまり点推定したものを使うわけだが、だいたいこれは p(z|X) と p(w|z,X) が独立であるという仮定を入れることに相当する）。*1

そこで期待値 θ_jk, φ_kv を求めるとそれぞれ

$\theta_{jk}=\mathbb{E}[p(z_{ji}=k|X)]=\begin{cases}\frac{1}{n_j+\alpha}\left(n_{jk}+\alpha\cdot\frac{m_k}{m_{\cdot}+\gamma}\right)\hspace{20px}&\text{if }k\text{ is used}\\ \frac{1}{n_j+\alpha}\left(\alpha\cdot\frac{\gamma}{m_{\cdot}+\gamma}\right)&\text{if }k\text{ is new,}\\\end{cases}$

$\phi_{kv}=\mathbb{E}[p(x_{ji}=v|z_{ji}=k,\;X)]=\begin{cases}\frac{n_{kv}+\beta}{n_k+V\beta}\hspace{20px}&\text{if }k\text{ is used}\\\frac 1V&\text{if }k\text{ is new}\\\end{cases}$

となる。
あとはこのθとφを使って $\prod_{x_{ji}\in\text{Test data}}\sum_k\theta_{jk}\phi_{kx_{ji}}$ を求めれば良い。

ちなみに本来なら perplexity を求めるのに用いるテストデータは訓練データと関係ない未知のドキュメントであることが望ましいわけだが、p(z|X) を未知のドキュメントに対して求めるのは骨が折れる。
そこでコーパスの各ドキュメントの単語の 90% を訓練に使って、推定されたθ_jkと残りの 10% の単語で perplexity を求めるということがよくやられるようだ。

今回の記事まとめ、そして DP-MRM の実装のために１年前の HDP-LDA の自分の実装を見なおしていたわけだけど、当時は全く理解せずにかろうじてわかったつもりの部分から実装しているから、いやあ本当にひどいコードでよく動いているなと自分でも関心（苦笑）。
今だったらだいぶすっきり書けると思うので、コードの見通し優先で実装し直したいところ。まあそうやって実装しなおしても、１年後くらいに「うわ、これはひどい……」とか言ってそうな気もするけどｗ

*1:という流れだと解釈しているんだけど、あってるかな？