December 31, 2009

PythonでLDAを実装してみる

Latent Dirichlet Allocationはテキストのような不連続データのための生成的確率モデル。入力はドキュメント。出力はドキュメントを特徴づける何か(tf-idfみたいなもん)。

基本的なアイディアは、あるドキュメントは潜在的ないくつかのトピックが混合していて、それぞれのトピックは語の分布で特徴づけられている、ということ。

論文[1]ではαとβというパラメータを用いてドキュメントが以下のように生成されると仮定している。
  1. ドキュメントのトピックの分布θがディリクレ分布Dir(α)に基づいて選ばれる。
  2. ドキュメントの語数N個になるまで以下を繰り返す。
    1. トピックznが多項分布Mult(θ)に基づいて選ばれる。
    2. 単語wnが確率p(wn|zn,β)で選ばれる。
ただし、トピックzの数をk個、単語wの種類をV個とすると、パラメータαはk次元のベクトル、βはk x V次元の行列でβij=p(wj|zi)。


Fig.1 LDAのグラフィカルモデル。Mはコーパス内のドキュメントの数。Nは各ドキュメントの語の数。αによって分布θが決まり、分布θに従ってzが選ばれ、zとβに従ってwが選ばれる。


ここで、ドキュメントにおけるαとβの値がわかれば、トピックがどんな割合であって(α)、そのトピックに関する語がどんな割合で存在するか(β)がわかる。つまり、ドキュメントが上のようなプロセスで生成されているとしてαとβの値はいくつかということを推定するのがLDAの目的。

αとβを推定する方法は変分ベイズEMアルゴリズムを利用するものやGibbs Samplerを利用するものなどが提案されています。また、いくつもの派生的なモデルも提案されています。

本稿では、論文[1]と
lda, a Latent Dirichlet Allocation package
http://chasen.org/~daiti-m/dist/lda/
のmatlabの方をパクっ参考にして、変分ベイズEMをPythonで実装してみました。

実行方法

要Numpy、SciPy。
python lda.py [-Nclasses] [-Iemmax] [-Ddemmax] [-Eepsilon] 入力ファイル名 出力ファイル名
classesはクラスの数。emmaxはEMの最大反復回数。demmaxは一つのドキュメントのEM最大反復回数。epsilonは収束条件。
たとえば、トピックの数が10個、「train」が入力で「model」に出力する場合は、
python lda.py -N10 train model

入力

テキストファイル。
1:1 2:4 5:2
1:2 3:3 5:1 6:1 7:1
2:4 5:1 7:1
ってな具合のフォーマット。行がドキュメント、<語のID>:<カウント>。SVMのライブラリでつかうフォーマットと似ている。上記の参考にしたサイトの上から1/3あたりのDownloadからcかmatlabバージョンをダウンロードして解凍するとtrainというファイルがありそのまま使える。

出力

<出力ファイル名>.alpha
<出力ファイル名>.beta
の二つ。alphaは長さがトピック数のリスト。betaはトピックの数×語の数の二次元リストになっている。はず。

References

[1] Blei et al., Latent Dirichlet Allocation, The Journal of Machine Learning Research, 2003.

ソース

lda.py


雑感

すごく…遅いです…