はじめに
機械学習プロフェッショナルシリーズの『トピックモデル』の勉強時に自分の理解の助けになったことや勉強会資料のまとめです。トピックモデルの各種アルゴリズムを「数式」と「プログラム」から理解することを目指します。
この記事は、4.3節「最尤推定」の内容です。最尤推定により、トピックモデルにおけるパラメータを推定します。
この記事で用いる記号類や混合ユニグラムモデルの定義については前節の記事をご確認ください。
【R言語で実装】
www.anarchive-beta.com
【前節の内容】
www.anarchive-beta.com
【他の節一覧】
www.anarchive-beta.com
【この節の内容】
4.3 最尤推定
トピックモデルを最尤推定する手法は、確率的潜在意味解析(PLSA)と呼ばれる。
3.3節の混合ユニグラムモデルの最尤推定と同様に、EMアルゴリズムを用いて対数尤度$\log p(\mathbf{W} | \boldsymbol{\Theta}, \boldsymbol{\Phi})$を最大にするパラメータ$\boldsymbol{\Theta},\ \boldsymbol{\Phi}$を求める。
トピックモデルにおける文書集合$\mathbf{W}$の生成モデル(尤度)$p(\mathbf{W} | \boldsymbol{\Theta}, \boldsymbol{\Phi})$は、4.1節より
$$
\begin{aligned}
\log p(\mathbf{W} | \boldsymbol{\Theta}, \boldsymbol{\Phi})
&= \log \prod_{d=1}^D \prod_{n=1}^{N_d}
p(w_{dn} | \boldsymbol{\theta}_d, \boldsymbol{\Phi})
\\
&= \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}}
\end{aligned}
$$
【途中式の途中式】
- 単語ごとの生成確率に項を分解する
- 4.1節より、置き換える。
- 対数をとる。$\log A B = \log A + \log B$である。
となる。
ここに負担率$(q_{111}, \cdots, q_{dnk}, \cdots, q_{DN_DK})$を導入する。$q_{dnk}$は、文書$d$の$n$番目の単語に対するトピックの割り当て確率を表し、次の定義に従う。
$$
0 \leq q_{dnk} \leq1,\
\sum_{k=1}^K q_{dnk}
$$
この負担率$q_{dnk}$を$\frac{q_{dnk}}{q_{dnk}} = 1$として、分母分子を分割して導入する。またイェンゼンの不等式を用いて対数尤度の下限を求める。
$$
\begin{aligned}
\log p(\mathbf{W} | \boldsymbol{\Theta}, \boldsymbol{\Phi})
&= \sum_{d=1}^D \sum_{n=1}^{N_d}
\log \sum_{k=1}^K
q_{dnk}
\frac{
\theta_{dk} \phi_{kw_{dn}}
}{
q_{dnk}
}
\\
&\geq
\sum_{d=1}^D \sum_{n=1}^{N_d} \sum_{k=1}^K
q_{dnk}
\log \left(
\frac{
\theta_{dk} \phi_{kw_{dn}}
}{
q_{dnk}
}
\right)
\\
&= \sum_{d=1}^D \sum_{n=1}^{N_d} \sum_{k=1}^K
q_{dnk} (
\log \theta_{dk} \phi_{kw_{dn}}
- \log q_{dnk}
)
\\
&= \sum_{d=1}^D \sum_{n=1}^{N_d} \sum_{k=1}^K
q_{dnk} \log \theta_{dk} \phi_{kw_{dn}}
- \sum_{d=1}^D \sum_{n=1}^{N_d} \sum_{k=1}^K
q_{dnk} \log q_{dnk}
\equiv F
\end{aligned}
$$
【途中式の途中式】
- 対数関数は上に凸な関数であることから、イェンゼンの不等式(1.1.10項)を用いて下限を求める。
- 対数をとる。$\log \frac{A}{B} = \log A - \log B$である。
- 括弧を展開して、この式を$F$と置く。
対数尤度の下限を$F$と置く。この下限$F$を最大化するパラメータをEMアルゴリズムにより推定していく。
・Eステップ
Eステップでは、パラメータ$\boldsymbol{\Theta},\ \boldsymbol{\Phi}$を固定して、下限$F$を最大化する負担率を求める。
・負担率の更新式の導出
$\sum_{k=1}^K q_{dnk} = 1$の制約の下で下限$F$が最大となる$q_{dnk}$を、ラグランジュの未定乗数法を用いて求める。
$$
F(q_{dnk})
= \sum_{d=1}^D \sum_{n=1}^{N_d} \sum_{k=1}^K
q_{dnk} (
\log \theta_{dk} \phi_{kw_{dn}}
- \log q_{dnk}
)
+ \lambda \left(
\sum_{k=1}^K q_{dnk} - 1
\right)
$$
この式を$q_{dnk}$に関して微分して、$\frac{\partial F(q_{dnk})}{\partial q_{dnk}} = 0$となる$q_{dnk}$を求める。
$$
\begin{align}
\frac{\partial F(q_{dnk})}{\partial q_{dnk}}
= \log \theta_{dk} \phi_{kw_{dn}}
&- \log q_{dnk}
- q_{dnk} \frac{1}{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
)
\tag{1}
\end{align}
$$
この式の両辺を$k = 1$から$K$まで和をとると、$\sum_{k=1}^K q_{dnk} = 1$より
$$
\begin{aligned}
\sum_{k=1}^K q_{dnk}
&= \sum_{k=1}^K
\theta_{dk} \phi_{kw_{dn}}
\exp(\lambda - 1)
\\
1 &= \sum_{k=1}^K
\theta_{dk} \phi_{kw_{dn}}
\exp(\lambda - 1)
\\
\exp(\lambda - 1)
&= \frac{
1
}{
\sum_{k=1}^K
\theta_{dk} \phi_{kw_{dn}}
}
\end{aligned}
$$
となる。
これを式(1)に代入すると
$$
q_{dnk}
= \frac{
\theta_{dk} \phi_{kw_{dn}}
}{
\sum_{k'=1}^K \theta_{dk'} \phi_{k'w_{dn}}
}
\tag{4.1}
$$
が得られる。これが負担率の更新式となる。
負担率は、その文書のトピック分布とその単語のトピックが持つ単語分布に比例していることが分かる。
次は、更新した負担率を用いて(固定して)他のパラメータを更新する。
・Mステップ
Mステップでは、負担率が与えられた下で下限$F$を最大化するようにパラメータ$\boldsymbol{\Theta},\ \boldsymbol{\Phi}$を更新する。
・トピック分布の更新式の導出
Eステップと同様に、$\sum_{k=1}^K \theta_{dk} = 1$の制約の下で下限$F$が最大となる$\theta_{dk}$を、ラグランジュの未定乗数法を用いて求める。
$$
F(\theta_{dk})
= \sum_{n=1}^{N_d}
q_{dnk} (
\log \theta_{dk}
+ \log \phi_{kw_{dn}}
- \log q_{dnk}
)
+ \lambda \left(
\sum_{k=1}^K \theta_{dk} - 1
\right)
$$
この式を$\theta_{dk}$に関して微分して、$\frac{\partial F(\theta_{dk})}{\partial \theta_{dk}} = 0$となる$\theta_{dk}$を求める。
$$
\begin{align}
\frac{\partial F(\theta_{dk})}{\partial \theta_{dk}}
= \frac{
\sum_{n=1}^{N_d}q_{dnk}
}{
\theta_{dk}
}
+ \lambda
&= 0
\\
\theta_{dk}
&= \frac{
\sum_{n=1}^{N_d} q_{dnk}
}{
- \lambda
}
\tag{2}
\end{align}
$$
この式の両辺を$k=1$から$K$まで和をとると、$\sum_{k=1}^K \theta_{dk} = 1$より
$$
\begin{aligned}
\sum_{k=1}^K \theta_{dk}
&= \sum_{k=1}^K \frac{
\sum_{n=1}^{N_d} q_{dnk}
}{
- \lambda
}
\\
1 &= \frac{
\sum_{k=1}^K \sum_{n=1}^{N_d} q_{dnk}
}{
- \lambda
}
\\
- \lambda
&= \sum_{k=1}^K \sum_{n=1}^{N_d}
q_{dnk}
\end{aligned}
$$
となる。
これを式(2)に代入すると
$$
\theta_{dk}
= \frac{
\sum_{n=1}^{N_d} q_{dnk}
}{
\sum_{k'=1}^K \sum_{n=1}^{N_d} q_{dnk'}
}
\tag{4.2}
$$
が得られる。これが$\theta_{dk}$の更新式となる。
$\theta_{dk}$は、各文書に関する各トピックの割り当て確率に比例していることが分かる。
・単語分布の更新式の導出
これまでと同様に、$\sum_{kv}^V \phi_{kv} = 1$の制約の下で下限$F$が最大となる$\phi_{kv}$を、ラグランジュの未定乗数法を用いて求める。
$$
F(\phi_{kv})
= \sum_{d=1}^D
q_{dnk} (
\log \theta_{dk}
+ \log \phi_{kw_{dn}}
- \log q_{dnk}
)
+ \lambda \left(
\sum_{v=1}^V \phi_{dw_{dn}} - 1
\right)
$$
この式を$\phi_{kw_{dn}}$に関して微分して、$\frac{\partial F(\phi_{kw_{dn}})}{\partial \phi_{kw_{dn}}} = 0$となる$\phi_{kv}$を求める。
$$
\begin{align}
\frac{\partial F(\phi_{kw_{dn}})}{\partial \phi_{kw_{dn}}}
= \sum_{d=1}^D q_{dnk}
\frac{1}{\phi_{kw_{dn}}}
+ \lambda
&= 0
\\
\phi_{kw_{dn}}
&= \frac{\sum_{d=1}^D q_{dnk}}{- \lambda}
\\
\phi_{kv}
&= \frac{
\sum_{d=1}^D \sum_{n:w_{dn}=v}
q_{dnk}
}{
- \lambda
}
\tag{3}
\end{align}
$$
ここで$\sum_{n:w_{dn}=v}$は、$w_{dn} = v$である単語に関する和を表す。同一単語の負担率の和をとることで語彙$v$に変換している。
この式の両辺を$v = 1$から$V$までの和をとると、$\sum_{v=1}^V \phi_{kv}$より
$$
\begin{aligned}
\sum_{v=1}^V \phi_{kv}
&= \sum_{v=1}^V \frac{
\sum_{d=1}^D \sum_{n:w_{dn}=v} q_{dnk}
}{
- \lambda
}
\\
1 &= \frac{
\sum_{v=1}^V \sum_{d=1}^D \sum_{n:w_{dn}=v} q_{dnk}
}{
- \lambda
}
\\
- \lambda
&= \sum_{v=1}^V \sum_{d=1}^D \sum_{n:w_{dn}=v}
q_{dnk}
\end{aligned}
$$
となる。
これを式(3)に代入すると
$$
\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}
}
\tag{4.3}
$$
が得られる。この式が$\phi_{kv}$の更新式となる。
$\phi_{kv}$は、文書全体において語彙$v$に関する各トピックの割り当て確率に比例していることが分かる。
参考書籍
- 岩田具治(2015)『トピックモデル』(機械学習プロフェッショナルシリーズ)講談社
おわりに
ついにトピックモデルの章に突入しました。前章の混合ユニグラムモデルとの違いは、ここではそれぞれの文書ごとにトピック集合を持つという点です。そのため$\theta_{dk},\ q_{dnk}$のように次元が1つ増えています。
それ以外は大差なく式変形も同様に進められます。3.3節の記事ではより細かい説明を載せているのでそちらもご参照ください。
とは言え、この節は1人でさらっと実装まで1日でできてしまって感動してました。人って本当に成長するんだなぁ。
2019/07/29:加筆修正しました。
2020/08/24:加筆修正しました。
【次節の内容】
www.anarchive-beta.com