ICML 2014 Best Paper斜め読み

LDA (Latent Dirichlet Allocation) ?

とても分かりやすいLDAの紹介
Latent Dirichlet Allocation(LDA)を用いたニュース記事の分類

ICML 2014 Best PaperなLDAの論文
Understanding the Limiting Factors of Topic Modeling via Posterior Contraction Analysis
ICML 2014 Awards Sponsored by Baidu

斜め読みした適当な意訳

Abstract

LDAはよく知られた機械学習のtopic modelで、成功した応用例も沢山あるけれど、LDAの振る舞いを説明するきちんとした理論というものはほとんど無かったから、何がLDAの精度を左右するのかよく分からなかった。
そこで、この論文ではデータ増加に伴う収束性を示す定理を証明したのち、実際のWebデータ使って確かめることで、そこらへんの問題にアプローチするよ。

Posterior Contraction Analysis of Topic Polytope in the LDA

変数名はこんな感じ。

• V：vocabulary：wordの集合
• φ：topic：wordの出現確率ベクトル（独立同分布）
• η：document：topicが重み付きで足しあわされたもの
• N：document数
• D：documentに含まれるword数
• α：ベイズ推定のハイパーパラメータ
• β：ベイズ推定のハイパーパラメータ
• K：topic数
• G：topicの集合の凸包

NやDを増やしたときに、推定されたtopicの集合がどうなるかについて議論したい。
Gにmetricを入れる。

Euclidean distance metric

d_M(G, G') = max(d(G, G'), d(G', G))
ここで、
d(G, G') = max[φ∈extr(G)] min[φ'∈extr(G')] ||φ - φ'||
ここで、
extr(G)はGのextreme pointの集合。

Contraction of the Posterior of Topic Polytope

*が付いているものは理想的な変数、それ以外は推定された変数、を表す。

Theorem 1

K* = K であった場合、
log(log(D)) <= log(N) ∈ o(D)であるようにNとDを∞に飛ばすと、
d_M(G, G*)は(log(D)/D + log(N)/D + log(N)/N)^(1/2)の定数倍で抑えられる。

Theorem 2

K* < K < |V| であった場合、
log(log(D)) <= log(N) ∈ o(D)であるようにNとDを∞に飛ばすと、
d_M(G, G*)は(log(D)/D + log(N)/D + log(N)/N)^(1/2(K - 1))の定数倍で抑えられる。

Experiments on Synthetic Data

人工的なデータで色々試してみた。

1. N固定でD増やす
2. D固定でN増やす
3. N=DでN,D増やす

Experiments on Real Data Sets

WikipediaとNewYorkTimesとTwitterの実データで試してみた。
それぞれtrainingに使ったdocument数は10000、documentの平均word数は300~400くらい。
twitterはword数が少なすぎるから同じユーザのtweetくっつけた。それから、Wikipediaの記事のうちword数が50に満たないものは取り除いた。
metricは、実データなので理想的なtopicなんて分からないから、Point-wise Mutual Informationというものを使ったよ。

Implications and guidelines for lay users of the LDA

1. document数
   • document数はある程度必要だが、多すぎてもそんなに精度上がらない。
   • 経験的には数千もあれば充分。
2. documentのword数
   • documentのword数もある程度必要だが、多すぎてもそんなに精度上がらない。
   • documentのword数がかなり多いときは、適当にサンプリングして構わない。
3. topic数
   • 理想的なtopic数よりも多すぎると精度落ちるので、topic数の推測は頑張って！
4. topicの性質
   • 各topicにあまりwordが含まれてない時、精度出るよ。
5. hyperparameter
   • 各documentが少ないtopicから構成されていそうなら、αは小さくしよう。（0.1とか）
   • 各topicにあまりwordが含まれてなさそうなら、βは小さくしよう。（0.01とか）