Interactive Topic Modeling を読む (Hu, Boyd-Graber and Satinoff ACL2011)

9/3 の ACL 読み会で読む [Hu+ ACL11] Interactive Topic Modeling(ITM) の資料です(途中ですが力尽きましたすいません……)。

【追記】
ディリクレ木と Interactive Adding Constraints and Unassigning(←これがこの論文のキモ！) についての説明を追加しました。
【／追記】

Interactive Topic Modeling(ITM) とは

通常の LDA は教師無しであり、結果の制御は基本的にできない
- baseball と football が同じトピックに入って欲しいと思っても、うまく分類されない場合はパラメータを変えて試行錯誤するとか、分類後にトピックをクラスタリングするか
ITM は LDA に「単語ＡとＢは同じトピックに入って欲しい」という制約を「後から」入れられるモデル

Notations

Ω_j : 同じトピックに属するべき単語の集合(制約)
- Ω_i∩Ω_j=∅ (i≠j)
- C_j = |Ω_j|
- Ω=∪Ω_j

K : トピック数
V : 語彙数
J : 制約数

w_dn : 文書 d の n 番目の単語
z_dn : w_dn の潜在トピック
θ_d : 文書 d のトピック分布
φ_k, π_kj : トピック-単語分布(Dirichlet Tree)

T_{d,k} : 文書 d 内のトピック k を持つ単語数
P_{k,w} : トピック k を持つ単語 w の個数
P_{k,j} : 制約 j に属する、トピック k を持つ単語数
- 論文には W_{k,j,w} = 制約 j に属する、トピック k を持つ単語 w の個数が導入されているが、制約は単語に対して高々1つなので、制約 j を持つ w に対しては常に P_{k,w} = W_{k,j,w} ゆえ不要。

Dirichlet Tree

ディリクレ木はディリクレ分布を階層化したもの
- 1階層目のディリクレ分布から「制約 or 制約無しの単語」を引く
- 制約を引いた場合は、さらに2階層目のディリクレ分布から「その制約に属する単語」を引く

[Hu+ ACL11] より

2階層目のディリクレ分布のパラメータηがβと同じ値の場合、元のディリクレ分布と等価(後述)
- ηをβより大きくすることで下図の(c)のような分布を構成できる(階層化していないディリクレ分布では(d)のような分布しか作れない)
  - (c) と (d) を間違っていたので、コメント欄でのご指摘により訂正(2011/9/7)

[Andrzejewski+ ICML09] より

LDA-DF (Andrzejewski+ ICML09) は、複数のディリクレ木の混合分布を用いる
- 「木」がいっぱいあるから「森」(=DF:Dirichlet Forest)

モデル

$P(\bf{W}, \bf{Z}, \bf{\theta}, \bf{\phi}, \bf{\pi})$
$= P(\bf{\phi}) P(\bf{\pi}) P(\bf{\theta}) P(\bf{Z}|\bf{\theta})) P(\bf{W}|\bf{Z}, \bf{\phi}, \bf{\pi})$
$= \prod_k\rm{Dir}(\bf{\phi}_k|\bf{\beta})\prod_{k,j}\rm{Dir}(\bf{\pi}_{kj}|\eta)\prod_d\rm{Dir}(\bf{\theta}_d|\alpha)\\\;\;\;\times\prod_{d,n}\rm{Multi}(z_{dn}|\bf{\theta}_d)\prod_{d,n}P(w_{dn}|z_{dn},\bf{\phi},\bf{\pi})$

ただし

$\begin{eqnarray}P(w|z=k,\bf{\phi},\bf{\pi})=\left\{ \begin{array}{ll}\phi_{kj}\pi_{jw}\; & \rm{if}\;w\in\Omega_j \\\phi_{kw} & \rm{otherwise} \\\end{array} \right.\end{eqnarray}$

Collapsed Gibbs Sampling で推論

$P(\bf{W}, \bf{Z})=\int P(\bf{W}, \bf{Z}, \bf{\theta}, \bf{\phi}, \bf{\pi})d\bf{\theta}d\bf{\phi}d\bf{\pi}$
$\propto\prod_d\frac{\prod_k\Gamma(T_{dk}+\alpha)}{\Gamma(T_{d\cdot}+K\alpha)}\prod_k\frac{\prod_{w\notin\Omega}\Gamma(P_{kw}+\beta)\prod_j\Gamma(P_{kj}+C_j\beta)}{\Gamma(P_{k\cdot}+V\beta)}\prod_{kj}\frac{\prod_{w\in\Omega_j}\Gamma(P_{kw}+\eta)}{\Gamma(P_{kj}+C_j\eta)}$

この周辺分布から、次の full conditional を得る。

$P(z_{dn}=k|w_{dn}=w,\bf{Z}^{-dn},\bf{W}^{-dn})$
$\begin{eqnarray}\propto\left\{ \begin{array}{ll}(T_{dk}^{-dn}+\alpha)\cdot\frac{P_{kj}^{-dn}+C_j\beta}{P_{k\cdot}^{-dn}+V\beta}\cdot\frac{P_{kw}^{-dn}+\eta}{P_{kj}^{-dn}+C_j\eta}\; & \rm{if}\;w\in\Omega_j \\(T_{dk}^{-dn}+\alpha)\cdot\frac{P_{kw}^{-dn}+\beta}{P_{k\cdot}^{-dn}+V\beta} & \rm{otherwise} \\\end{array} \right.\end{eqnarray}$

トピック-単語分布の推定

P(w|z,φ,π)=Multi(ξ_k) とおいて、事後分布の平均によってξを推定

$\begin{eqnarray}\xi_kw=\left\{ \begin{array}{ll}\phi_{kj}\pi_{kjw}=\frac{P_{kj}+C_j\beta}{P_{k\cdot}+V\beta}\cdot\frac{P_{kw}+\eta}{P_{kj}+C_j\eta}\; & \rm{if}\;w\in\Omega_j \\\phi_{kw}=\frac{P_{kw}+\beta}{P_{k\cdot}+V\beta} & \rm{otherwise} \\\end{array} \right.\end{eqnarray}$

θ_k や perplexity は vanilla LDA と全く同様。

Interactive Unassignment

学習をある程度行ったところで、制約を追加することを考える
- 同じトピックに入って欲しい baseball と football が別のトピックに入ってしまった！
推論の更新式の項の中で、制約の影響を直接受けるのは P_kj のみ
- 追加・変更された制約について P_kj を数え直せば、それを初期値として新しいモデルの学習を行うことができる

pros: そこまで行った学習を活かすことができる
cons: すでに別々のトピックに割り振られた単語が多い場合、そこから Gibbs Sampling で抜け出すのは LDA の特性上難しい(イテレーションを数多く回さないといけない)

そこで部分的に単語のトピックの割り振り(つまり z_dn)を解除することで、その問題を解決する
- 実装的には、z_dn に -1 にセットして、対応するカウンタも減ずる
- 解除する範囲について、4通りの方針を提案

1. All: 全ての単語のトピック割り振りを解除する(つまり最初から学習をやり直す)
2. Doc: 「追加・変更された制約に属する単語を含む文書」の全単語のトピック割り振りを解除する
3. Term: 「追加・変更された制約に属する単語」のトピック割り振りを解除する
4. None: トピック割り振りを解除しない(P_kj の数え直しのみ行う)

論文は Doc が一番効率がよいと主張
手元で実験した感じでも、その主張に一致する印象(定量的な評価ではありません)
- None はもちろん、Term でも制約を入れた単語が同じトピックに割り振られるとは限らない
- baseball と football に制約を入れて、しかもそれらのトピックをリセットしても、それぞれと共起度の高い別の単語(例えば baseball - pitcher, football - goal)が多く属するトピックに引っ張られる
したがって共起しうる単語(つまり同じ文書の単語)をまとめてリセットする方が望む結果が得られやすい

モデルについて考察

制約がない場合、vanilla LDA と等価
β=ηのとき、vanilla LDA と等価(制約があっても)
CANNOT Link の無い LDA-DF にモデルとして等価
- というわけで Interactive Unassignment が ITM のキモ

「β=ηのとき、vanilla LDA と等価」の証明

簡単のため V=3, w_1 と w_2 に制約が入っている場合で説明すると、
P(w_1, w_2, w_3|z) = Multi(ξ_1, ξ_2, ξ_3) について
P(ξ) = P(ξ_1, ξ_2)・P(ξ_3|ξ_1, ξ_2) である
ただし P(ξ_1, ξ_2)=Dir(η, η), P(ξ_3|ξ_1, ξ_2) = Beta(β, 2β) ( Dir(β, 2β) と同等 )。
このときη=βなら、P(ξ) は Dir(β, β, β) を積に分解したものに一致する■

実装してみた

Usage: itm.py [options]

Options:
  -h, --help            show this help message and exit
  -m MODEL              model filename
  -f FILENAME           corpus filename
  -b CORPUS             using range of Brown corpus' files(start:end)
  --alpha=ALPHA         parameter alpha
  --beta=BETA           parameter beta
  --eta=ETA             parameter eta
  -k K                  number of topics
  -i ITERATION          iteration count
  --seed=SEED           random seed
  --df=DF               threshold of document freaquency to cut words
  -c CONSTRAINT         add constraint (wordlist which should belong to the
                        same topic)
  -u UNASSIGN, --unassign=UNASSIGN
                        unassign method (all/doc/term/none)

まとめ

結構おもしろい＆使えるかも
- もっといろいろ実験してみたい
- 実装公開したので興味のある人は試してみて
η(=100)が大きすぎる気がする(グラフの赤)
- apple や service(礼拝) など複数のトピックに分布する単語を全部同じ制約の単語に結びつけてしまう
- η=2 (グラフの黒)くらいでいいのでは？　収束が遅い？
- ヒューリスティックだが、ηを最初は大きく、徐々に小さくしていくとか。
- 制約ごとにηを変えてもいいかもしれない
多義性を持つ単語を制約に加えた場合の振る舞いも確認しておきたいところ

References

[Hu+ ACL11] Interactive Topic Modeling
[Blei+ 2003] Latent Dirichlet Allocation
[Andrzejewski+ ICML09] Incorporating Domain Knowledge into Topic Modeling via Dirichlet Forest Priors
[小林+ 2011] 論理制約付きトピックモデルのためのディリクレ森事前分布構成法