昨日の "Latent Dirichlet Allocations in Python" の続きで実験結果を載せようかと思ったけど、先にやっぱりもうちょっと LDA を説明しておこう。
LDA の初出は [Blei+ 2003] Latent Dirichlet Allocation 。
ただし [Blei+ 2003] で "LDA" としているのはトピック-単語分布がただの多項分布(事前分布無し)のもの。"LDA" としてよく目にするトピック-単語多項分布にディリクレ事前分布が入ったものは "Smoothed LDA" として記載されている(確かにβでスムージングしているのと等価)。
今回実装した LDA も後者の "Smoothed LDA"。
その LDA はこんな感じ。αとβはハイパーパラメータだから、チビ黒丸で書いて欲しいんだけどね。
(図は Wikipedia-en の LDA より)
こまかーく説明するとさすがに長いので、w が単語、z がその単語のトピック、θが文書に対してどのトピックが生起しやすいかの多項分布、φがトピックに対してどの単語が生起しやすいかの多項分布、それぞれの多項分布には(対称な)ディリクレ事前分布が入っていて、α＆βはそれぞれのハイパーパラメータ、というあたりで勘弁。
これを見ると LDA での推論とは、M 個の文書集合(m 番目の文書は N=N_m 個の単語 (w_mn) をもつ)が与えられたとき、もっともらしい z とかφとかθとか、場合によってはαとかβとかを推定する、ということになる。
[Blei+ 2003] ではそれを変分ベイズで解いているが、今回は実装の簡単さ最優先で collapsed Gibbs サンプリング[Griffiths+ 2004] を使っている。
通常の Gibbs サンプリングなら、観測変数以外の全ての確率変数が対象になるので、z だけでなくφやθも事後分布(full conditional, 日本語だと「全条件付分布」？)を求めてサンプリングしなければならないところを、φとθについては周辺化してつぶしてしまい、z だけサンプリングすればいい形に持って行くのが collapsed Gibbs サンプリング。名前通りつぶしているわけだ。*1
φやθは連続だが z は離散なので、こうすることで各単語のトピックに応じていくつかの量をカウントするだけで z の事後分布が求められる、つまり実装がとてもシンプルに済むというのが最大のポイント。
といっても通常は周辺化というのはとてもめんどくさい(必ずしも解析的に出来るとは限らない)わけだが、英語版 Wikipedia の LDA の項目にそこで必要になるディリクレ分布の積分がなかなかていねいに書かれている。一見ややこしいが、コツがわかると案外簡単(ガンマ関数の引数の整数差に持ち込む)。
今回の実装で使った full conditional は Wikipedia のとはちょっと記法や条件(ディリクレ分布が対称)が違うので、今回用のものを記しておこう。
ただし t は w_mn(つまり m 番目の文書の n 番目の単語)、V は単語の種類数(語彙数)、n_mz は m 番目の文書のトピック z の単語数、n_tz はトピック z をもつ単語 t の数、n_z はトピック z をもつ単語数、右肩に -mn と付いているのは、今サンプリングしようとしている z_mn の分は除外してね、ということ。
だから、n_mz と n_tz と n_z を保持しておいて、
- old_z = z_mn をとりだし、対応する n_mz と n_tz と n_z について -1
- 上の式から多項分布を求めて、それに従って new_z をサンプリング(ランダムに選ぶ)
- z_mn = new_z をセットし、対応する n_mz と n_tz と n_z について +1
これを全ての z_mn について何十回か繰り返すだけで、あら不思議、「もっともらしい z」が求まっているというのが collapsed Gibbs サンプリング for LDA の妙。
ホントにそんな簡単でいいの？ と最初は全く腑に落ちなかったのはナイショだｗ
あとは「もっともらしいφ」と「もっともらしいθ」だが、これらも n_mz たちから求めることが出来る。
ただし K はあらかじめ決めておいたトピック数、n_m は m 番目の文書の単語数。
「もっともらしいφ,θ」があればパープレキシティも簡単に求められる(N は全文書長)。ただし確率的な推論なので、パープレキシティは各イテレーションで必ず下がるとは限らない。
これで実装に必要な式は全部あるので、あとは初期化(オーソドックスには各単語にランダムなトピックを割り振る)さえ行えば LDA が実装できるだろう。
次回こそは実験結果。
参考
- [Blei+ 2003] Latent Dirichlet Allocation
- [Griffiths+ 2004] Finding scientific topics
*1:つぶしていると言うより、崩している(変形している)という方が正しいニュアンスなのかな？
