きういノート

一打粉砕に怒喝の心力を込め、万物を叩き割る剛剣の刃を生み出さん

トピックモデルを最尤推定する

段々と理解が進んできたのでアウトプットします。メモ書きみたいなのです。

概要

前回のナイーブベイズ分類は文書自体を{迷惑メール,普通メール}の2種類のトピックに分類するモデルだった。ただ文書には複数のトピックが混在している場合が少なくない。俺みたいにラブライブを取り上げて統計の話をするヤツも居るくらいなんだから。そんな時、その文書のトピックを{ラブライブ,統計学}のどちらか一方に分類するってのはナンセンス極まりない。

トピックモデルは文書に複数のトピックが混在していると仮定している。d番目の文書w_dに注目すると。そこにはその文書が含んでいるK個のトピックが\theta_d = (\theta_{d1},…,\theta_{dK}) という確率(割合)で存在している。

 

想定するモデル

f:id:kiui_4:20180602101045j:plain

D個の文書から構成された全文書集合 W =(w_1,…,w_D)

d番目の文書が持つ単語の数 N_d

D個の文書が持つトピック分布集合 \Theta =(\theta_{1},…,\theta_{D})

d番目の文書がトピックkを含んでいる確率*1 \theta_{d} = (\theta_{d1},…,\theta_{dK})

K個のトピックについて単語分布集合  \Phi =(\phi_{1},…,\phi_{K})

トピックkの時、全文書中のV種類の単語がそれぞれ生成する確率*2 \phi_{k} =(\phi_{k1},…,\phi_{kV})

 

図から分かるように、単語1つ1つの背景にトピックが存在しており、全ての単語をK個のトピックにクラスタリングするモデルとも言える。

 

単語,文書の生成過程

 今、d番目の文書 w_d の n番目の単語w_{dn}に注目すると、その単語はあるトピック z_{dn}を持っている。その単語 w_{dn}はトピック z_{dn} =k の時の単語分布\phi_{k}から生成されたと考えてよい。よって、単語w_{dn}が生成する確率は、トピック分布\theta_{d}と単語分布集合\Phiが与えられた時に、kについて和を取ることで

p(w_{dn}|\theta_{d},\Phi)= \sum_{k=1}^K p(z_{dn} =k|\theta_d) p(w_{dn}|\phi_{k}) =\sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}}

 と求められる。(単語w_{dn}=v  の時)

 

 トピック分布\theta_{d}と単語分布集合\Phiが与えられた下で単語の生成する確率は独立なので(条件付き独立)N_d個の単語から構成されたd番目の文書w_dが生成する確率は

p(w_{d}|\theta_{d},\Phi)= \prod_{n=1}^{N_{d}} p(w_{dn}|\theta_{d},\Phi) =\prod_{n=1}^{N_{d}} \sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}}

 で表される。(単語w_{dn}=v  の時)

 

更に全文書集合 Wが得られる確率は、トピック分布集合 \Thetaと単語分布集合\Phiが与えられた時

p(W | \Theta,\Phi) = \prod_{d=1}^D p(w_d|\theta_d,\Phi)= \prod_{d=1}^D \prod_{n=1}^{N_{d}} \sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}}

 で表される。(単語w_{dn}=v  の時)

 

最尤推定(Eステップ)

 全文書集合 W がデータから観測された時のパラメータ \Theta\Phi を推定していく。尤度 L

 L = p(W | \Theta,\Phi) = \prod_{d=1}^D \prod_{n=1}^{N_{d}} \sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}}

 なので対数尤度を考えると

\log L = \log ( \prod_{d=1}^D \prod_{n=1}^{N_{d}} \sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}} ) = \sum_{d=1}^D \sum_{n=1}^{N_{d}} \log \sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}}

(∵  \log \prod_{i=1}^n x_i = \sum_{i=1}^n \log x_i

 ここで、文書dのn番目の単語がトピックkに属する確率を q_{dnk} *3として、式に加組み込みます。(q_{dnk} の正体は後述)

 \log L =  \sum_{d=1}^D \sum_{n=1}^{N_{d}} \log \sum_{k=1}^K q_{ndk} \frac{\theta_{dk} \phi_{kw_{dn}}}{q_{ndk}}(∵ 分母分子に掛けただけ)

 イェンゼンの不等式を用いて対数尤度の下限を求めます。

イェンゼンの不等式

 

f:id:kiui_4:20180602123405j:plain

x軸上の点x_1,x_2\phi_2 : \phi_1 に内分する点X = \sum_{i=1}^2 \phi_i x_i を取り、上に凸な単調増加の関数 f(x) を考える。

この時 X'f(x_1),f(x_2)\phi_2 : \phi_1 に内分している点なので、X' = \sum_{i=1}^2 \phi_i f(x_i)と書ける。

 図よりf(X)X'の大小関係は常にf(X) ≧ X'であることが言える。つまり

f(\sum_{i=1}^2 \phi_i x_i) ≧ \sum_{i=1}^2 \phi_i f(x_i)

 が言えて、一般的に\phi_i ≧0, (i=1,2,...,n) \sum_{i=1}^n \phi_i =1を満たす\phiと上に凸な単調増加の関数f(x)に対して

f(\sum_{i=1}^n \phi_i x_i) ≧ \sum_{i=1}^n \phi_i f(x_i)

 が成り立つ。これを使うと対数尤度の式の下限を求めることが出来る。

 

q_{dnk}≧0, \sum_{k=1}^K q_{dnk} =1 を満たすq_{dnk}f(x) =\log x について 

  \sum_{d=1}^D \sum_{n=1}^{N_{d}} \log \sum_{k=1}^K q_{ndk} \frac{\theta_{dk} \phi_{kw_{dn}}}{q_{ndk}} ≧ \sum_{d=1}^D \sum_{n=1}^{N_{d}} \sum_{k=1}^K q_{ndk} \log \frac{\theta_{dk} \phi_{kw_{dn}}}{q_{ndk}}

が成り立つ。この時、右辺は

 (右辺) = \sum_{d=1}^D \sum_{n=1}^{N_{d}} \sum_{k=1}^K q_{ndk} \log \theta_{dk} \phi_{kw_{dn}} - \sum_{d=1}^D \sum_{n=1}^{N_{d}} \sum_{k=1}^K q_{ndk} \log q_{dnk}

の様に書き換えられる。(∵ \log \frac{a}{b} = \log a - \log b

 この形にすることで解析的な解が得られので、この式から未知のパラメータq_{dnk},\Theta,\Phiを求めます。

 

 ラグランジュの未定乗数法

 制約付きの変数q_{dnk}に関する最大化問題を

F(q_{dnk},\lambda )=  \sum_{d=1}^D \sum_{n=1}^{N_{d}} \sum_{k=1}^K q_{ndk} \log \theta_{dk} \phi_{kw_{dn}} - \sum_{d=1}^D \sum_{n=1}^{N_{d}} \sum_{k=1}^K q_{ndk} \log q_{dnk} + \lambda (\sum_{k=1}^K q_{dnk} - 1)

 の\frac{dF(q_{dnk},\lambda)}{d q_{dnk}} =0,\frac{dF(q_{dnk},\lambda)}{d \lambda} =0 を解くことで求める。\lambdaに関する微分

 \frac{ d F(q_{dnk},\lambda)}{d \lambda} = \sum_{k=1}^K q_{dnk} - 1 =0 なので \sum_{k=1}^K q_{dnk} =1 の制約を満たすことが出来る。

q_{dnk} に関する微分

 \frac{ d F(q_{dnk},\lambda)}{d q_{dnk}} = \log \theta_{dk} \phi_{kw_{dn}} -1 - \log q_{dnk} + \lambda より、これが 0 となる時

 \log q_{dnk} = \log \theta_{dk} \phi_{kw_{dn}} + \lambda -1 

 ∴q_{dnk} =\theta_{dk} \phi_{kw_{dn}} \exp( \lambda -1)

 q_{dnk}は k に関して和を取ると 1 なので

 \sum_{k=1}^K q_{dnk} =\exp( \lambda -1) \sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}} =1

 \exp(\lambda -1) について解いて上の式に代入すると

  q_{dnk} = \frac{\theta_{dk} \phi_{kw_{dn}}}{\sum_{k=1}^K \theta_{dk} \phi_{kw_{dn}}}  で q_{dnk} を点推定できる。

 

 最尤推定(Mステップ)

 詳細は省いてしまうが、q_{dnk} と同様にラグランジュの未定乗数法を用いると\theta_{dk},\phi_{kv}に関しても

 \theta_{dk} = \frac{\sum_{n=1}^{N_{d}} q_{dnk}}{\sum_{k'=1}^K \sum_{n=1}^{N_{d}} q_{dnk'}},\phi_{kv} = \frac{\sum_{d=1}^D \sum_{n:w_{dn}=v} q_{dnk}}{\sum_{v'=1}^V \sum_{d=1}^D \sum_{n:w_{dn}=v'} q_{dnk} }

 で点推定できる。(\sum_{n:w_{dn} =v} w_{dn} = v を満たす場合の n に関する和)

 

EMアルゴリズムとは

  1. パラメータ \Theta\Phi を制約の下で乱数を用いて設定。
  2. \Theta\Phiを用いて q_{dnk} を点推定。(Eステップ)
  3.  q_{dnk}を用いてパラメータ\Theta\Phiを更新。(Mステップ)
  4. 更新した\Theta\Phiを用いて  q_{dnk} を再び点推定して更新。
  5. 更新した  q_{dnk}を用いてパラメータ\Theta\Phiを再び更新。

 ・・・

 とこれを延々と続けていき、 q_{dnk},\Theta , \Phi がある値に収束するまで繰り返す方法のことである。

 

q_{dnk} の正体

対数尤度L とその下限F の差を考える。q_{dnk} = p(w_{dn} =k | \theta_d)となるから

L-F = \sum_{d=1}^D \sum_{n=1}^{N_{d}} \sum_{k=1}^K q_{dnk} \log p(w_{dn} | \Theta,\Phi) - \sum_{d=1}^D \sum_{n=1}^{N_{d}} \sum_{k=1}^K q_{dnk} \log \frac{p(k|\theta_d )p(w_{dn}|\phi_k )}{q_{dnk}}  

 これを変形すると

L-F =  \sum_{d=1}^D \sum_{n=1}^{N_{d}}  \sum_{k=1}^K q_{dnk} \log \frac{q_{dnk}}{p(k|w_{dn},\Theta,\Phi)} =  \sum_{d=1}^D \sum_{n=1}^{N_{d}} KL(q_{dn},p(z_{dn}|w_{dn},\Theta,\Phi))

 下限F を最大化することと、2つの分布のKLダイバージェンスを最小化することは同義である。(この辺の式変形ちょっとよく分かってない、、、)

 

KLダイバージェンス 

 2つの分布p,q がある時 KL(p,q) = p \log \frac{p}{q} で定義される。

 KL(p,q) = 0 の時、2つの分布の関係は p = q である。

 

p(z_{dn}|w_{dn},\Theta,\Phi) はパラメータ  \Theta,\Phi が与えられた時の単語 w_{dn} がどのトピックに含まれているかを示した分布である。よってFを最大化した時のq_{dnk}p(z_{dn}|w_{dn},\Theta,\Phi)  の近似値となっている。

 

 最後に

 疲れた。このモデルは例えばD人のブロガーがN_d 個の記事を書いていた時に、その記事をK個のトピックにカテゴリ分けすることも出来そうだし、色々と応用が利くっぽい。

まぁ後は勉強の方向性を少し変えようかなと思う。そろそろテーマとかしっかり選ばないとなぁと思うし。

 

でゎ。

 

*1:\theta_{dk} ≧0,\sum_{k=1}^K \theta_{dk} =1

*2:\phi_{kv} ≧0,\sum_{v=1}^V \phi_{kv} =1

*3:q_{dnk}≧0, \sum_{k=1}^K q_{dnk} =1