A Scalable Asynchronous Distributed Algorithm for Topic Modeling

Kento Nozawa
03 September 2017

メタデータとか

Hsiang-Fu Yu et al.の論文でWWW2015。LightLDAと同じ年で同じ会議。

背景

Collapsed Gibbs sampling (CGS) の LDA について並列計算せずに高速化を試みてるアルゴリズムとしては、以下が挙げられる。

  • SparseLDA, 2009
  • AliasLDA, 2014
  • LightLDA, 2015
  • F+LDA, 2015
  • warpLDA, 2016

SparseLDA 以外は並列計算についても言及されている。

このうち F+LDA と warpLDA については知らなかったので、前者についてアルゴリズムを読んだ。SparseLDA と F+LDA は CGS の高速化であるのに対して、これら以外は棄却サンプリング（MH法）を使う。

前準備

F+LDA では、トピック数を\(T\)としたときに、

  • 初期化: \(O(T)\)
  • 更新: \(O(\log T)\)
  • サンプル: \(O(\log(T))\)

を満たすデータ構造である F+tree を使う。F+Treeは、全ノードが値をもつ完全2分木。葉ノードに各トピックの（正規化されてない）確率値をもち、親ノードが子ノード値の和をもつ。詳しい図は論文の Fig. 1。

LDAのサンプリング

LDAのトピックのサンプル式は

\[p(z_{i, d}=t \mid w_{i, d} = w) \approx \frac{(n_{t, d} + \alpha_{t})(n_{t, w} + \beta_{w})}{n_{t} + V \beta}\]

から計算できる。ただし、

  • \(z, t\): トピックID
  • \(i\): 文書内のインデックス
  • \(d\): 文書ID
  • \(w\): 単語
  • \(n_{t, d}\): 文書 \(d\) においてトピック \(t\) が割り当てられている単語総数
  • \(n_{t, w}\): 単語 \(w\) にトピック \(t\) が割り当てられている頻度
  • \(n_t\): トピック \(t\) が割り当てられている頻度
  • \(\alpha, \beta\): Dirichlet 分布のハイパーパラメータ
  • \(V\): 語彙数

とする。以下、略記としてサンプル式の右辺を \(p(t)\) とする。論文では、2通りのサンプリング方法を示している。

document-by-document

サンプル式を以下のように変形する。

\[\begin{aligned} p(t) &= \beta \left(\frac{n_{t,d} + \alpha_t}{n_t + V\beta} \right)+ n_{t,w} \left(\frac{n_{t,d} + \alpha_t}{n_t + V \beta} \right) \\ &= \beta q_t + r_t \end{aligned}\]

ただし、

\[\begin{aligned} q_t &= \frac{n_{t,d} + \alpha_t}{n_t + V \beta} \\ r_t &= n_{t,w} q_t \end{aligned}\]

とする。\(q\) と \(r\) のどっちの項からサンプルするかを決めてからトピックをサンプルする：\(U(0, \sum(p_t))\) からサンプルした \(u\) が \(\sum(r_t)\) よりも小さければ \(r\) からサンプルし、そうでなければ、\(q\) からサンプル。

次に2つのそれぞれのサンプルについて見ていく。

CGS では1つの単語に対して

  1. 割り当てられているトピック\(z_{i d}\)が関係する統計量から1減らす
  2. \(p(t)\)からトピック \(z_{i, d}^{new}\)をサンプルする
  3. 新しいトピック\(z_{i,d}^{new}\)が関係する統計量に1加える

という操作を行う。

まず \(q_t\)について。この値は、全\(t\)に対して非ゼロになる。これは\(\alpha_t\) が Dirichlet 分布のパラメータであるため。1で更新をする場合、\(q_{z_{i,j}}\)のみが更新対象なので、先程導入したF+Treeを使う。なので更新に関する計算量は\(O(\log(T))\)。また、これは1つの文書の中では使いまわすことができる。2ではF+Treeの性質から\(O(\log(T))\)でサンプル。3では1と同様で更新があったトピックのみを更新。

次に\(r_t\)について。これは\(n_{t,w}\)があるためにスパースになる。しかし、文書内の単語ごとに全体を計算し直す必要があるのでF+Treeは使えない。このため、まず\(r_t\)の累積和の配列を計算する。この計算量は\(O(\mid T_w \mid )\) （単語\(w\)に割り当てられているトピックのユニーク数）。累積和の配列からbinary searchでサンプルを行う。この計算量は\(O(\log( \mid T_w \mid ))\)。

というわけでサンプルは常に対数オーダーになる。

word-by-word

document-by-documentと同じ手順になるが、分解方法を変える。まず、サンプル式を以下のように分解する。

\[\begin{aligned} p(t) &= \alpha_t \left(\frac{n_{t,w} + \beta}{n_t + V\beta} \right)+ n_{t,d} \left(\frac{n_{t,w} + \beta}{n_t + V\beta} \right) \\ &= \alpha_t q_t + r_t \end{aligned}\]

ただし、

\[q_t = \frac{n_{t,w} + \beta}{n_t + V \beta}\] \[r_t = n_{t,d} q_t\]

とする。

まず \(q_t\) については、全 \(t\) に対して非ゼロになる。これは \(\beta\) が Dirichlet 分布のパラメータであるため。\(q_t\)は単語\(w_{i,j}\)に依存するので毎回作り直す必要があるが、少し見方を変える。通常のLDAでは

for d in 1:D
    for i in 1:Dj
        sample(wdi, zdi)

のように文書ごとにそこに含まれる単語についてサンプルを行う。 ここでは、逆にして単語ごとみて、その単語が含まれる文書について順番にサンプルする。 こうすることでB+Treeを使いまわす。

次に\(r_t\)について。これは\(n_{t,d}\)があるためにスパースになる。文書ごとに再計算の必要があるので\(r_t\)の累積和の配列を計算し、binary searchでサンプルを行う。 構築の計算量は \(O(\mid T_d \mid)\)で、サンプルの計算量は \(O(\log(\mid T_d \mid ))\)。

この2つについてどちらがサンプルの計算量が優れているかを考える。前者は\(O(\log(\mid T_w \mid))\)で後者は\(O(\log(\mid T_d \mid))\)であった。今回はトピック数が\(T=1024\)のようにトピック数が多い場合について考えている。この場合、前者のほうが上限値が大きくなることが予想される。例えばtheのような高頻度語やストップワードではない高頻度語は、トピック数を超える頻度をもつため、\(O(\log(\mid T_w \mid))\)は最悪の場合、\(\mid T_w \mid =T\)となる。

一方で後者の上限は、文書長になるため（文書数が長くないデータセットでは）\(\mid T_d \mid < T = 1024\)となる。もちろん、この傾向はデータ依存で、論文の実験では、文書数が大きいデータ（NY times、文書数: \(298\,000\) ）では word-by-word のほうが速く、文書数が小さいデータ（Enron、文書数: \(37\,861\) ）では document-by-document が速いという結果が報告されている。ちなみに、小さいデータに関しては word-by-word は SparseLDA に負けている。

その他

warpLDA以外はC++の実装が公開されている。Document-by-documentのほうはjuliaで実装した。