メタデータとか

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 では、トピック数をとしたときに、

  • 初期化:
  • 更新:
  • サンプル:

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

LDAのサンプリング

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

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

  • : トピックID
  • : 文書内のインデックス
  • : 文書ID
  • : 単語
  • : 文書 においてトピック が割り当てられている単語総数
  • : 単語 にトピック が割り当てられている頻度
  • : トピック が割り当てられている頻度
  • : Dirichlet 分布のハイパーパラメータ
  • : 語彙数

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

document-by-document

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

ただし、

とする。 のどっちの項からサンプルするかを決めてからトピックをサンプルする: からサンプルした よりも小さければ からサンプルし、そうでなければ、 からサンプル。

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

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

  1. 割り当てられているトピックが関係する統計量から1減らす
  2. からトピック をサンプルする
  3. 新しいトピックが関係する統計量に1加える

という操作を行う。

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

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

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

word-by-word

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

ただし、

とする。

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

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

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

次にについて。これはがあるためにスパースになる。文書ごとに再計算の必要があるのでの累積和の配列を計算し、binary searchでサンプルを行う。 構築の計算量は で、サンプルの計算量は


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

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


その他

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