鴨川η

not δ

SparseLDAの導出

はじめに

間違っていたらnzwまでお願いします.

pythonでLDAの実装をしましたが,遅くて使い物になりません. そこで高速化するSparse LDAの論文を読んで実装したいと思いました.

モデル自体はBlei+, 2003と等価で,サンプリング式の計算を工夫して高速化します. topicModel

この論文の3.4を読んでまとめました. 論文の式番号とこの投稿にでてくる式番号は一致します.

本題

単語にトピックを割り当てる確率は以下の式に比例する.

\begin{eqnarray} p(z=t|w) \propto (\alpha_{t} + n_{t|d}) \frac{\beta + n_{w|t}}{\beta V + n_{\cdot|t}} \tag{5} \end{eqnarray}

上の値をと表記し,以下の連続一様分布から実数値を1つサンプルする.

\begin{eqnarray} U \sim {\cal u}(0, \sum_{z} q(z)) \end{eqnarray}

先の一様分布からサンプルしたを使って,以下の式を満たすようなをトピックとして単語に割り当てる.

\begin{eqnarray} \sum_{z=1}^{t-1} q(z) < U < \sum_{z=1}^{t} q(z) \end{eqnarray}

ただし,これを順番に計算する必要があり,計算を軽くしたい.

まず,式(5)を展開して依存関係をわかりやすくする.

\begin{eqnarray} p(z=t \mid w) \propto \frac{\alpha_t\beta}{\beta V + n_{\cdot \mid t}} + \frac{n_{t \mid d}\beta}{\beta V + n_{\cdot \mid t}} + \frac{(\alpha_t+ n_{t|= \mid d})n_{w \mid t}}{\beta V + n_{\cdot \mid t}} \tag{6} \end{eqnarray}

  • 第1項:全文書に対して固定
  • 第2項:現在の単語タイプに対して独立

変形した結果から と表せる.

ただし, \begin{eqnarray} s &=& \sum_{t} \frac{\alpha_{t} \beta}{\beta V + n_{\cdot \mid t}} \tag{7} \\ r &=& \sum_{t} \frac{n_{t \mid d}\beta}{\beta V + n_{\cdot \mid t}} \tag{8} \\ q &=& \sum_{t} \frac{(\alpha_{t}+ n_{t \mid d})n_{w \mid t}}{\beta V + n_{\cdot \mid t}} \tag{9} \\ \end{eqnarray}

以上より,のサンプル式は以下のように書き換えることができる.

\begin{eqnarray} U \sim {\cal u}(0, s+r+q) \end{eqnarray}


以下ではこれらの項ごとに条件分岐を行う.

“smoothing only” bucket

のときは,式(7)の総和の中身 だけを順番に加算していく.

つまり以下を満たすようなを見つけることになる.

\begin{eqnarray} \sum_{z=1}^{t-1} \frac{\alpha_{z} \beta}{\beta V + n_{\cdot \mid z}} < U < \sum_{z=1}^{t} \frac{\alpha_{z} \beta}{\beta V + n_{\cdot \mid z}} \end{eqnarray}

の部分を使わないので,計算量が減っている.

“document topic” bucket

のとき,に注目する. は,現在の単語が含まれる文書依存なので,文書に現れるトピックだけを考慮すればよい. つまり, だけを走査する.

\begin{eqnarray} \sum_{z=1}^{t-1} \frac{n_{t \mid d}\beta}{\beta V + n_{\cdot \mid z}} < U-s < \sum_{z=1}^{t} \frac{n_{t \mid d}\beta}{\beta V + n_{\cdot \mid z}} \end{eqnarray}

このあたりは参考文献[2]を見るとわかりやすい.

“topic word” bucket

if のときはの項に注目する. この項は,現在の単語に依存する. “document topic” bucketと似ていて, だけを走査はすればよい.

\begin{eqnarray} \sum_{z=1}^{t-1} \frac{(\alpha_{z}+ n_{z \mid d})n_{w \mid z}}{\beta V + n_{\cdot \mid z}} < U-(s+r) < \sum_{z=1}^{t} \frac{(\alpha_{z}+ n_{z \mid d})n_{w \mid z}}{\beta V + n_{\cdot \mid z}} \end{eqnarray}

条件分岐ここまで.


の計算

一様分布のパラメータに出てくるため, の値を計算する必要がある.

  • はDicichlet分布のパラメータが更新したら更新
  • は,1つの文書をgibbs samplingする前に一旦を計算し,gibbs samplingで更新したらを更新

だけやや複雑になる. まず,を以下のように2つの項に分解する.

ここで,単語に依存しないは,各トピックごとにキャッシュしておく. キャッシュした項との積からを求められる. また,ほとんどであるのでこのとき,キャッシュしておく項は, となる. なので,更新する必要があるキャッシュは,その文書に割り当てられているトピック数が非零なトピックの部分だけで済む.


論文では,の値が小さいと約90%くらいは”topic word” bucketに落ちると言及している. (例えば,ディリクレ分布のパラメータが全体的に小さいとのっぺりとした分布になるので,単語が特定のトピックが偏らないで配分されるので,”topic word” bucketに落ちるという認識をしました,また実際問題は小さい値なのでこの特徴は重要)

このことから”word topic” bucketにかかる時間を高速化する. ここで式(10)の中身は,の比に見えるので, (できるだけ大きい方から計算したほうが見つかりやすいために)を降順に求めることで “topic word” bucketで示した大小関係を満たすトピックを速く見つける.

これについては,計算式ではなくて,データ構造を工夫する. (, )のタプルを32ビットの整数で1つで表現する. この整数のビットを,を割り当てる部分とトピック番号を割り当てる部分の2つに分割する. トピックに必要なビット数は,をみたすようなで末尾ビットで残りをを表現するのに使用する. (完全に余談だけど,ノンパラメトリックベイズのような場合はどうなるんだろうか)

このデータ構造への操作は以下通りビット演算を使用する

  • を加える場合,だけ左シフトしてトピックの番号だけ加算
  • とトピックを読み出す場合
    • タプルの整数表記をだけ右シフトしてを読み出す(右シフトするとの情報が落ちる)
    • タプルの整数表記から下桁を取り出すビットマスクをかけて,トピック番号を読み出す

単語ごとに上記のタプルの整数表記を要素に持つ配列に格納する. ただし,は格納しない.

この構造のメリットは以下の2つ

  1. 単語に対して,トピック数次元の配列が不要
  2. は上位ビットなので,トピックを意識せずに頻度順にソート可能

これによってHashMapで同じ構造ことを行った場合と比べて2倍高速化したらしい.

このデータ構造について具体的にみてみる. トピック数として,単語”book”がトピック1に3回,トピック16に10回配分されたとする. このとき,トピックの番号に使うビット数は,である.

  • .
  • .
  • .

以下Jupyterで計算する.

確かにトピック番号とが取り出せている.

終わりに

これらを実装すればLDAが速くなります.

実装はそのうち上げると思います.

参考文献など

  1. Efficient methods for topic model inference on streaming document collections (論文)
  2. Efficient Inference for Multinomial Mixed Membership Models(スライド)