NLP2012 のポスター発表にて、LDA の文字を見かけるたびに思わずフラフラ〜と近寄り、あーだこーだ無責任なことを述べていたら、決まって「 shuyo さんですよね？」
なんでも、お茶の水大の小林先生の研究室の学生さんはみなさん揃って（かな？）トピックモデルをなにがしか絡めて研究されており、このブログの LDA ネタを参照していただけているという。なんとも有り難いというか照れくさいというか。
なにがしかのお役に立てているのはもちろん嬉しい反面、n_shuyo は言語処理も機械学習も専門家ではないので、ここに書いてあることを鵜呑みにはしないでいただくことはやっぱりお願いしておかなければ。
というわけで、不足や間違いの指摘は絶賛大歓迎＞読者各位
で、ここまで前振り。
そうしたポスターの発表を拝見させていただいていた中で、パープレキシティ周りの扱いがちょっと気になったので、少し思うところをまとめてみた。なお、専門家ではないので鵜呑み(ry
まずは論より証拠と言うことで、LDA を Collapsed Gibbs Sampling(以下 CGS) 200周で解くにあたって、初期値(つまり各単語のトピック)をランダムに変えて 100回行い、そのパープレキシティがどういった分布になるか見てみたい。
具体的には、以前公開したLDAの実装を使って、以下のようなコマンドを100 回実行、200回イテレーションした後のパープレキシティでヒストグラムを描く。
$ ./lda.py -c0:50 --df=2 -k 10 -i 200
こうなった。
見てわかるとおり、結構バラつきがある。ちなみに、今回のトイサンプル(約3200語)程度であれば 200回もイテレーションすればパープレキシティの変化はすっかり落ち着くので、大きい値はまだ下がっている途中というわけではない。
つまりこれは LDA の CGS は初期値依存性が高いことを示している。
理論的にはエルゴード性が満たされていれば(そしておそらく満たされている)、MCMC は任意の初期値から定常分布におおむね収束する。つまり十分な回数回せば初期値との相関は 0 になるはずだが、200回程度のイテレーションではまだまだ足りないという事だ。
では一体何回回せばいいのか？
(ダメだろうなと思いつつ)試しにある初期値で10万回ほど回してみたが、200回目からほとんど変化がなかった。*1
実は Gibbs Sampling は職人芸を駆使しなくても棄却率が 0 の提案分布が得られるという大きなメリットと引き替えに、とてつもなく足が遅い(初期値非相関なサンプルを得るために必要なイテレーション回数が非常に多くなる)という特性がある。特に自然言語処理で使われる離散な Gibbs Sampling では、独立なサンプルを得るのは絶望的といっていいだろう。
根拠はないが、LDA の場合、上で試したデータサイズですら仮に 10^100 回イテレーションしたとしても、まだ相関 0 にはならないんじゃあないだろうか。試してみようにも先に宇宙が滅亡するので無理だけど。10^(10^100)回くらいイテレーションすればさすがに足りるのかなあ？？(自信なし)
MCMC の最先端では、現実的な時間で独立なサンプルを得るための研究が(きっと)日夜行われているわけだけど、ここで使われている MCMC は「非相関？ なにそれおいしいの？」と言わんばかりの sampling の真似事に過ぎないわけで、同じ言葉の別のものくらいに思っておいたほうがむしろ変な勘違いがなくていいのかもしれない。
まあそんなことはさておき、だからといってパープレキシティを指標として使えない使わないなんてことはない。
ただ、特性をわかってないと間違った考察や結論を導いてしまうかもしれない点は注意しておいた方がいいと思う。特にほかのモデルやパラメータでの結果と比較したい場合。
とはいえ、どうやっても真の値を求めることはできない以上たいしてできることはなく、初期値を変えて5〜10回とか推論を行い、一番いいパープレキシティを取るというのが関の山かなあ。まあそれだけでもずいぶん信頼感は上がる(気持ち的にｗ)。
今回は LDA での CGS を槍玉に上げたが、大域最適解が保証されている凸最適化でもない限り、常に当てはまりうる話。例えば EMA とか VB とか勾配法全般とかも全部 local minimum を求める手法だし。
*1:データがもっと大きくて、初期値を都合良く選べば、ちょっとした local minimum から脱出するところくらいは数千回程度で観察できるかも
