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

y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

LDA の逐次学習における活性化

Canini らの論文*1を読んでみました。LDA の逐次学習について述べた論文で、『トピックモデルによる統計的潜在意味解析』の 3.5.2 節は、この論文の方法を説明したものになっています。下記のウェブページで論文の PDF ファイルをダウンロードできます。
JMLR W&CP: Volume 5: AISTATS 2009

まず LDA の粒子フィルタでのリサンプリングについて、教科書には以下のように書かれていますが、これは論文の内容と異なっているように思われます。

さて、リサンプリングであるが、LDA では復元抽出による粒子の生成消滅を行わない。この理由として、各粒子は z(d,i)(s) なので、数十万の文書を扱う場合に実装が複雑になりコストもかかることが挙げられる。ケニニ (Canini) らは、過去のサンプルの活性化 (若返り) という方法によりリサンプリングを行っている。

論文のアルゴリズム (Algorithm 4) では、ESS が閾値を下回ったときには、まず 8 行目でリサンプリングを行い、その後 9 ~ 11 行目で活性化を行うようになっています。本文にも以下のように書かれています。

As in the resample-move algorithm of Gilks and Berzuini (2001), Markov chain Monte Carlo (MCMC) is used after particle resampling to restore diversity to the particle set in the same way that the incremental Gibbs sampler rejuvenates its samples, by choosing a rejuvenation sequence R(i) of topic variables to resample.

LDA の粒子フィルタのアルゴリズムを確認してみると、教科書の式 (3.172), 式 (3.175) とも z を含まない形になっているので、活性化を行わないのであれば z を各粒子の情報として保持する必要はなく、統計量である nk,v と nd,k を保持しておけば処理できます*2。nk,v はそれ自体が単語の異なりに比例する大きさになりますが、これはいずれにしても必要な情報なので、実装を工夫して保持する必要があります*3。これらのことから、活性化を行う目的は論文に書かれているように、リサンプリングによって失われる多様性を取り戻すことにあるのだろうと思います。

さて、活性化の処理自体については、教科書に書かれているように、R の大きさや、過去の観測列をどこまで遡って wl,m を選択するかが実用上の問題になります。R を大きくすれば実行速度が低下し、過去の観測列を長く保持すれば実行に必要なメモリ量が大きくなります。この点について、論文の実験では各パラメータの値を以下のように設定しています。

パラメータ 設定値
粒子数 100
ESS の閾値 20 または 10 (データセットによって変えている)
R 30 または 10 (データセットによって変えている)
wl,m の選択方法 過去のすべての観測列から一様にランダム選択

表に示したように、論文の実験では wl,m を過去のすべての観測列から選択しているので、この設定では文書を処理するたびに消費メモリ量が増えていくことになりそうです。

この点は Börschinger らの論文*4で指摘されていました。この論文は下記のウェブページに PDF ファイルがあります。なお Börschinger らはこの点について手法を工夫しているようですが、ちょっと難しくて内容は私にはよく分かりませんでした。
ACL Anthology » P12

また、May らは、reservoir sampling という手法を適用して、活性化のために保持する観測列の長さを限定しています*5。この論文は下記のウェブページに PDF ファイルがあります。May らの方法は論文の Algorithm 2 に書かれているとおりで、これは比較的簡単そうです。
ACL Anthology » P14

ところが、May らの論文では Canini らの方法との比較実験が行われているのですが、論文の結論では、そもそも活性化は重要ではなく、逐次学習の前に実行する (バッチ処理の) ギブスサンプリングによる初期化が重要だと述べられています。活性化を行うのがよいのか行う必要はないのか、よく分からなくなってきます。

*1:Kevin R. Canini, Lei Shi, and Thomas L. Griffiths. Online Inference of Topics with Latent Dirichlet Allocation. In Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics. 2009.

*2:出力として z そのものが欲しい場合はもちろん保持する必要がありますが、その場合でも大抵の用途では 1 文書の処理を終えるごとに捨てられるのではないかと思います。

*3:私が試みに実装したところでは、論文の Figure 1 のように粒子の親子関係を利用した木構造にすることで、かなりサイズを小さくできました。

*4:Benjamin Börschinger and Mark Johnson. Using Rejuvenation to Improve Particle Filtering for Bayesian Word Segmentation. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). 2012

*5:Chandler May, Alex Clemmer, and Benjamin Van Durme. Particle Filter Rejuvenation and Latent Dirichlet Allocation. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). 2014.