はじめに
機械学習プロフェッショナルシリーズの『トピックモデル』の勉強時に自分の理解の助けになったことや勉強会資料のまとめです。トピックモデルの各種アルゴリズムを「数式」と「プログラム」から理解することを目指します。
この記事は、3.5節「ギブスサンプリング」の内容です。崩壊型ギブスサンプリングにより、混合ユニグラムモデルにおけるパラメータを推定します。
この記事で用いる記号類や混合ユニグラムモデルの定義については3.1-2:混合ユニグラムモデル【『トピックモデル』の勉強ノート】 - からっぽのしょこをご確認ください。
【R言語で実装】
www.anarchive-beta.com
【前節の内容】
www.anarchive-beta.com
【他の節一覧】
www.anarchive-beta.com
【この節の内容】
3.5 ギブズサンプリング
3.5.1 マルコフ連鎖モンテカルロ法
変分ベイズ推定では、周辺尤度の下限を最大化することで事後分布の近似分布を求めた。ギブズサンプリングとはマルコフ連鎖モンテカルロ法の1種で、近似ではなく、(複雑な)真の事後分布からサンプリングすることで推定する方法である。
例えば、分布$p(z_1, \cdots, z_D | \mathbf{W})$を推定するとする。変数$z_d$以外の全ての変数が与えられたときの$z_d$の条件付き確率$p(z_d | z_1, \cdots, z_{d-1}, z_{d+1}, \cdots, z_D, \mathbf{W})$に従って$z_d$の値をサンプリングすることを全ての変数$d = 1, \cdots, D$に対して繰り返すことにより、目的の分布から事例を得る。十分多くの事例が得られれば目的の分布は次式の経験分布で近似できる。
$$
p(z_1, \cdots, z_D | \mathbf{W})
\simeq \frac{1}{S}
\sum_{s=1}^S \delta \left(
(z_1, \cdots, z_D),
(z_1^{(s)}, \cdots, z_D^{(s)})
\right)
$$
ここで、$S$はサンプリングした事例数、$z_d^{(s)}$は$s$番目にサンプリングした変数$z_d$の事例を表す。また、分布$p(z_1, \cdots, z_D, | \mathbf{W})$における関数$f(z_1, \cdots, z_D)$の真の期待値は
$$
\mathbb{E}[
f(z_1, \cdots, z_D)
]
\simeq \frac{1}{S} \sum_{s=1}^S f(z_1^{(s)}, \cdots, z_D^{(s)})
$$
(各変数のサンプルの和をサンプルサイズで割ること)で近似できる。
3.5.2 パラメータの周辺化
混合ユニグラムモデルには、3つの未知変数$\mathbf{z},\ \boldsymbol{\theta},\ \boldsymbol{\Phi}$がある。この節では、パラメータ$\boldsymbol{\theta},\ \boldsymbol{\Phi}$を周辺化(積分消去)し、トピック集合$\mathbf{z}$の事後分布$p(\mathbf{z} | \mathbf{W})$を推定する。
パラメータを周辺化したギブズサンプリングは、崩壊型ギブズサンプリング(周辺化ギブスサンプリング)と呼ばれる。パラメータを周辺化してサンプリングする変数の数を減らすことで、効率的な推定が可能となる。
パラメータ$\boldsymbol{\theta},\ \boldsymbol{\Phi}$を周辺化したときの文書集合$\mathbf{W}$とトピック集合$\mathbf{z}$の同時分布
$$
p(\mathbf{W}, \mathbf{z} | \alpha, \beta)
= \int \int
p(\mathbf{W}, \mathbf{z}, \boldsymbol{\theta}, \boldsymbol{\Phi} | \alpha, \beta)
d\boldsymbol{\theta} d\boldsymbol{\Phi}
$$
は、生成過程より次のように分解できる。
$$
p(\mathbf{W}, \mathbf{z} | \alpha, \beta)
= p(\mathbf{z} | \alpha)
p(\mathbf{W} | \mathbf{z}, \beta)
$$
ここで、トピック集合$\mathbf{z}$は$\alpha$から(トピック分布$\boldsymbol{\theta}$を通して)生成され、単語集合$\mathbf{W}$は$\mathbf{z}$と$\beta$から(単語分布$\boldsymbol{\Phi}$を通して)生成されるという、混合ユニグラムモデルの生成過程(3.1節)を利用して同時分布を分解している。
この式の1つ目の項は、周辺化している$\boldsymbol{\theta}$を明示して計算すると
$$
\begin{align}
p(\mathbf{z} | \alpha)
&= \int
p(\mathbf{z} | \boldsymbol{\theta})
p(\boldsymbol{\theta} | \alpha)
d\boldsymbol{\theta}
\\
&= \int
\prod_{d=1}^D
p(z_d = k | \boldsymbol{\theta})
p(\boldsymbol{\theta} | \alpha)
d\boldsymbol{\theta}
\\
&= \int
\prod_{k=1}^K
\theta_k^{D_k}
\frac{\Gamma(\sum_{k=1}^K \alpha)}{\prod_{k=1}^K \Gamma(\alpha)}
\prod_{k=1}^K
\theta_k^{\alpha-1}
d\boldsymbol{\theta}
\\
&= \frac{\Gamma(\alpha K)}{\Gamma(\alpha)^K}
\int \prod_{k=1}^K
\theta_k^{D_k+\alpha-1}
d\boldsymbol{\theta}
\\
&= \frac{\Gamma(\alpha K)}{\Gamma(\alpha)^K}
\frac{
\prod_{k=1}^K \Gamma(D_k + \alpha)
}{
\Gamma(\sum_{k=1}^K D_k + \alpha)
}
\\
&= \frac{\Gamma(\alpha K)}{\Gamma(\alpha)^K}
\frac{
\prod_{k=1}^K \Gamma(D_k + \alpha)
}{
\Gamma(D + \alpha K)
}
\tag{3.24}\\
&= \frac{\Gamma(\alpha K)}{\Gamma(D + \alpha K)}
\prod_{k=1}^K
\frac{\Gamma(D_k + \alpha)}{\Gamma(\alpha)}
\tag{3.24'}
\end{align}
$$
【途中式の途中式】
- 周辺化している$\boldsymbol{\theta}$を明示する。
- 項を分解する。
- 具体的な式に置き換える。
前の項は、$p(z_d | \boldsymbol{\theta}) = \mathrm{Categoical}(z_d | \boldsymbol{\theta})$であることから
$$
\begin{aligned}
p(\mathbf{z} | \boldsymbol{\theta})
&= \prod_{d=1}^D
p(z_d = k | \boldsymbol{\theta})
\\
&= \prod_{d=1}^D \theta_{z_d}
\\
&= \prod_{k=1}^K \theta_k^{D_k}
\end{aligned}
$$
となる。各文書が持つトピック$\mathbf{z}$について、同じトピックの項でまとめ直している。
これは例えば、文書$d = 1, 2, 3$のトピックがそれぞれ$k = 1, 1, 2$のとき、トピック1の文書数は$D_1 = 2$であり、トピック2の文書数は$D_2 = 1$になる。このときの同時確率分布は
$$
\begin{aligned}
p(z_1 = 1, z_2 = 1, z_3 = 2 | \boldsymbol{\theta})
&= \theta_1 * \theta_1 * \theta_2
\\
&= \theta_1^2 * \theta_2^1
\\
&= \prod_{k=1}^K \theta_k^{D_k}
\end{aligned}
$$
となる。
後の項はトピック分布の事前分布であり、$p(\boldsymbol{\theta} | \alpha) = \mathrm{Dirichlet}(\boldsymbol{\theta} | \alpha)$を仮定している。
- $\boldsymbol{\theta}$と関係のない正規化項を$\int$の外に出し、$\theta_k$をまとめる。
- ディリクレ分布の正規化項の導出過程(1.13)より、置き換える。
- トピック$k$が割り当てられた文書数$D_k$について$k$に関する和は、文書数$D$である。
- 不動点反復法を用いるために、分母を入れ替えて分母分子の$\alpha K$と$\alpha$を揃える。
となる。
同様に2つ目の項も、周辺化している$\boldsymbol{\Phi}$を明示して計算すると
$$
\begin{align}
p(\mathbf{W} | \mathbf{z}, \beta)
&= \int
p(\mathbf{W} | \mathbf{z}, \boldsymbol{\Phi})
p(\boldsymbol{\Phi} | \beta)
d\boldsymbol{\Phi}
\\
&= \int
\prod_{d=1}^D
p(\mathbf{w}_d | z_d = k, \boldsymbol{\phi}_k)
\prod_{k=1}^K
p(\boldsymbol{\phi}_k | \beta)
d\boldsymbol{\Phi}
\\
&= \int
\prod_{k=1}^K \prod_{v=1}^V
\phi_{kv}^{N_{kv}}
\prod_{k=1}^K
\frac{
\Gamma(\sum_{v=1}^V \beta)
}{
\prod_{v=1}^V \Gamma(\beta)
}
\prod_{v=1}^V
\phi_{kv}^{\beta-1}
d\boldsymbol{\Phi}
\\
&= \frac{\Gamma(\beta V)^K}{\Gamma(\beta)^{KV}}
\prod_{k=1}^K
\int \prod_{v=1}^V
\phi_{kv}^{N_{kv}+\beta-1}
d\boldsymbol{\phi}_k
\\
&= \frac{\Gamma(\beta V)^K}{\Gamma(\beta)^{KV}}
\prod_{k=1}^K
\frac{
\prod_{v=1}^V \Gamma(N_{kv} + \beta)
}{
\Gamma(\sum_{v=1}^V N_{kv} + \beta)
}
\\
&= \frac{\Gamma(\beta V)^K}{\Gamma(\beta)^{KV}}
\prod_{k=1}^K
\frac{
\prod_{v=1}^V \Gamma(N_{kv} + \beta)
}{
\Gamma(N_k + \beta V)
}
\tag{3.25}\\
&= \frac{\Gamma(\beta V)^K}{\Gamma(N_k + \beta V)}
\prod_{k=1}^K \prod_{v=1}^V
\frac{\Gamma(N_{kv} + \beta)}{\Gamma(\beta)^{KV}}
\tag{3.25'}
\end{align}
$$
【途中式の途中式】
- 周辺化している$\boldsymbol{\Phi}$を明示する。
- 項を分解する。
- それぞれ具体的な式に置き換える。
- 前の項は、$p(\mathbf{W} | \mathbf{z}, \boldsymbol{\Phi}) = \prod_{d=1}^D \prod_{n=1}^{N_d} \mathrm{Categoical}(w_{dn} | z_d = k, \boldsymbol{\phi}_k)$である。
- 後の項は単語分布の事前分布であり、$p(\boldsymbol{\Phi} | \beta) = \prod_{k=1}^K \mathrm{Dirichlet}(\boldsymbol{\phi}_k | \beta)$を仮定している。
- $\boldsymbol{\Phi}$と関係のない正規化項を$\int$の外に出し、$\phi_{kv}$をまとめる。
- ディリクレ分布の正規化項の導出過程(1.13)より、置き換える。
- トピック$k$が割り当てられた文書における語彙$v$の出現回数$N_{kv}$の$v$に関して和をとると、トピック$k$が割り当てられた文書における単語数$N_k$になる。
- 不動点反復法を用いるために、分母を入れ替えて分母分子で$\beta V$と$\beta$を揃える。
となる。
この2つの式を用いて、$z_d$のサンプリング式を導出する。
3.5.3 サンプリング式
ギブズサンプリングに必要な$z_d$の条件付き確率は、文書集合$\mathbf{W}$とトピック集合$\mathbf{Z}$の同時分布(周辺尤度)$p(\mathbf{W}, \mathbf{z} | \alpha, \beta)$に対して、ベイズの定理(1.4)を用いて
$$
\begin{aligned}
p(z_d = k | \mathbf{W}, \mathbf{z}_{\backslash d}, \alpha, \beta)
&= \frac{
p(\mathbf{w}_d, \mathbf{W}_{\backslash d}, z_d = k, \mathbf{z}_{\backslash d} | \alpha, \beta)
}{
p(\mathbf{w}_d, \mathbf{W}_{\backslash d}, \mathbf{z}_{\backslash d} | \alpha, \beta)
}
\\
&\propto
p(\mathbf{w}_d, \mathbf{W}_{\backslash d}, z_d = k, \mathbf{z}_{\backslash d} | \alpha, \beta)
\\
&= p(\mathbf{w}_d | \mathbf{W}_{\backslash d}, z_d = k, \mathbf{z}_{\backslash d}, \beta)
p(z_d = k | \mathbf{z}_{\backslash d}, \alpha)
p(\mathbf{W}_{\backslash d}, \mathbf{z}_{\backslash d} | \alpha, \beta)
\\
&\propto
p(\mathbf{w}_d | \mathbf{W}_{\backslash d}, z_d = k, \mathbf{z}_{\backslash d}, \beta)
p(z_d = k | \mathbf{z}_{\backslash d}, \alpha)
\end{aligned}
$$
と計算できる。文書集合の生成過程(3.1節)より分解している。また$z_d$に影響しない項を適宜省いて比例関係にのみ注目する。
ここで、トピック集合$\mathbf{z}$から文書$d$のトピック$z_d$を除いたトピック集合を$\mathbf{z}_{\backslash d} = (z_1, \cdots, z_{d-1}, z_{d+1}, \cdots, z_D)$で表し、文書集合$\mathbf{W}$から文書$d$の単語ベクトル$\mathbf{w}_d$を除いた文書集合を$\mathbf{W}_{\backslash d} = (\mathbf{w}_1, \cdots, \mathbf{w}_{d-1}, \mathbf{w}_{d+1}, \cdots, \mathbf{w}_D)$で表す。
この式の後の項は、式(3.24)に対してベイズの定理を用いることで求められる。
$$
\begin{align}
p(z_d = k | \mathbf{z}_{\backslash d}, \alpha)
&= \frac{
p(z_d = k, \mathbf{z}_{\backslash d} | \alpha)
}{
p(\mathbf{z}_{\backslash d} | \alpha)
}
\\
&= \frac{\Gamma(\alpha K)}{\Gamma(\alpha)^K}
\frac{
\Gamma(D_{k \backslash d} + 1 + \alpha)
\prod_{k' \neq k}
\Gamma(D_{k' \backslash d} + \alpha)
}{
\Gamma(D + \alpha K)
} \\
&\qquad
* \frac{\Gamma(\alpha)^K}{\Gamma(\alpha K)}
\frac{
\Gamma(D - 1 + \alpha K)
}{
\prod_{k'=1}^K
\Gamma(D_{k' \backslash d} + \alpha)
}
\\
&= \frac{
(D_{k \backslash d} + \alpha)
\Gamma(D_{k \backslash d} + \alpha)
\prod_{k' \neq k}
\Gamma(D_{k' \backslash d} + \alpha)
}{
(D - 1 + \alpha K)
\Gamma(D - 1 + \alpha K)
}
\frac{
\Gamma(D - 1 + \alpha K)
}{
\prod_{k'=1}^K
\Gamma(D_{k' \backslash d} + \alpha)
}
\\
&= \frac{
D_{k \backslash d} + \alpha
}{
D - 1 + \alpha K
}
\tag{3.26}
\end{align}
$$
【途中式の途中式】
- $p(A | B, C) = \frac{p(A, B | C)}{p(B | C)}$の関係を用いて式を立てる。
- 式(3.24)より、具体的な式に置き換える。
まずは分子の項について考える。
ここで$D_k$は、トピック$k$を割り当てられた文書数である。文書$d$のトピック$z_d$が$k$のとき、トピック$k$を割り当てられた文書$d$以外の文書数$D_{k \backslash d}$は$D_k - 1$である。つまり
$$
\begin{aligned}
D_{k \backslash d}
= \left\{
\begin{array}{ll}
D_k - 1 &\quad \text{if} \quad z_d = k \\
D_k &\quad \text{if} \quad z_d \neq k
\end{array}
\right.
\end{aligned}
$$
であることが分かる。これを$D_k$について解くと
$$
\begin{aligned}
D_k
= \left\{
\begin{array}{ll}
D_{k \backslash d} + 1 &\quad \text{if} \quad z_d = k \\
D_{k \backslash d} &\quad \text{if} \quad z_d \neq k
\end{array}
\right.
\end{aligned}
$$
となる。
これを式(3.24)に代入して、$p(z_d = k, \mathbf{z}_{\backslash d} | \alpha)$を求める。式(3.24)の後の項の分子についてみる。
$$
\begin{aligned}
\prod_{k=1}^K \Gamma(D_k + \alpha)
&= \Gamma(D_1 + \alpha) \cdots \Gamma(D_k + \alpha) \cdots \Gamma(D_K + \alpha)
\\
&= \Gamma(D_1 + \alpha) \cdots \Gamma(D_{k \backslash d} + 1 + \alpha) \cdots \Gamma(D_K + \alpha)
\\
&= \Gamma(D_{k \backslash d} + 1 + \alpha)
\prod_{k' \neq k}
\Gamma(D_{k' \backslash d} + \alpha)
\end{aligned}
$$
$z_d = k$であるためトピック$k$に関する項は$\Gamma(D_{k \backslash d} + 1 + \alpha)$となり、(項の形が異なるため)$\prod_{k=1}^K$から取り出している。それ以外の$\mathbf{z}_{\backslash d}$に関する項は、$\prod_{k' \neq k} \Gamma(D_{k' \backslash d} + \alpha)$としてまとめている。
同様に分母$p(\mathbf{z}_{\backslash d} | \alpha)$は、文書$d$を含まないため
$$
\prod_{k=1}^K \Gamma(D_k + \alpha)
= \prod_{k=1}^K \Gamma(D_{k \backslash d} + \alpha)
$$
となる。ただし分母については、文書$d$を除いた文書数$\sum_{k=1}^K D_{k \backslash d}$の計算になるため、$D - 1$となる。
- ガンマ関数の性質$\Gamma(x) = (x - 1) \Gamma(x - 1)$より、項を変形する。
- $\prod_{k'=1}^K \Gamma(D_{k' \backslash d} + \alpha) = \Gamma(D_{k \backslash d} + \alpha) \prod_{k'\neq k} \Gamma(D_{k' \backslash d} + \alpha)$なので、約分して式を整理する。
同様に1つ目の因子は、式(3.25)を用いて求める。
$$
\begin{align}
p(\mathbf{w}_d | \mathbf{W}_{\backslash d}, z_d = k, \mathbf{z}_{\backslash d}, \beta)
&= \frac{
p(\mathbf{W} | z_d = k, \mathbf{z}_{\backslash d}, \beta)
}{
p(\mathbf{W}_{\backslash d} | \mathbf{z}_{\backslash d}, \beta)
}
\\
&= \frac{
\Gamma(\beta V)^K
}{
\Gamma(\beta)^{KV}
}
\frac{
\prod_{v=1}^V
\Gamma(N_{kv \backslash d} + N_{dv} + \beta)
}{
\Gamma(N_{k \backslash d} + N_d + \beta V)
}
\prod_{k' \neq k}
\frac{
\prod_{v=1}^V
\Gamma(N_{k'v \backslash d} + \beta)
}{
\Gamma(N_{k' \backslash d} + \beta V)
} \\
&\qquad
* \frac{\Gamma(\beta)^{KV}}{\Gamma(\beta V)^K}
\prod_{k'=1}^K
\frac{
\Gamma(N_{k' \backslash d} + \beta V)
}{
\prod_{v=1}^V
\Gamma(N_{k'v \backslash d} + \beta)
}
\\
&= \frac{
\prod_{v=1}^V
\Gamma(N_{kv \backslash d} + N_{dv} + \beta)
}{
\Gamma(N_{k \backslash d} + N_{d} + \beta V)
}
\frac{
\Gamma(N_{k \backslash d} + \beta V)
}{
\prod_{v=1}^V
\Gamma(N_{kv \backslash d} + \beta)
}
\\
&= \frac{
\Gamma(N_{k \backslash d} + \beta V)
}{
\Gamma(N_{k \backslash d} + N_d + \beta V)
}
\prod_{v:N_{dv}>0}
\frac{
\Gamma(N_{kv \backslash d} + N_{dv} + \beta)
}{
\Gamma(N_{kv \backslash d} + \beta)
}
\end{align}
$$
【途中式の途中式】
- $p(A | B, C) = \frac{p(A, B | C)}{p(B | C)}$の変形を行う。ただし$z_d = k$は$\mathbf{W}_{\backslash d}$に影響しないことから省いている。
- 式(3.25)より、具体的な式に置き換える。
ここで、$N_{kv}$はトピック$k$が割り当てられた全文書における語彙$v$の出現回数(単語数)であり、$N_{dv}$は文書$d$における語彙$v$の出現回数である。文書$d$のトピック$z_d$が$k$のとき、トピック$k$が割り当てられた文書$d$以外の文書における語彙$v$の出現回数$N_{kv \backslash d}$は$N_{kv} - N_{dv}$となる。
また$z_d = k$のとき、トピック$k$が割り当てられた文書$d$以外の文書における単語数$N_{k \backslash d}$は、トピック$k$が割り当てられた全文書における単語数$N_k$から文書$d$の単語数$N_d$を除いたものとなる。
このことをまとめると
$$
\begin{aligned}
N_{kv \backslash d}
&= \left\{
\begin{array}{ll}
N_{kv} - N_{dv} &\quad \text{if} \quad z_d = k \\
N_{kv} &\quad \text{if} \quad z_d \neq k
\end{array}
\right.
\\
N_{k \backslash d}
&= \left\{
\begin{array}{ll}
N_k - N_d &\quad \text{if} \quad z_d = k \\
N_k &\quad \text{if} \quad z_d \neq k
\end{array}
\right.
\end{aligned}
$$
と表現できる。これをそれぞれ$N_{kv}$と$N_k$について解くと
$$
\begin{aligned}
N_{kv}
&= \left\{
\begin{array}{ll}
N_{kv \backslash d} + N_{dv} &\quad \text{if} \quad z_d = k \\
N_{kv \backslash d} &\quad \text{if} \quad z_d \neq k
\end{array}
\right.
\\
N_k
&= \left\{
\begin{array}{ll}
N_{k \backslash d} + N_d &\quad \text{if} \quad z_d = k \\
N_{k \backslash d} &\quad \text{if} \quad z_d \neq k
\end{array}
\right.
\end{aligned}
$$
となる。
これを式(3.25)に代入して、$p(\mathbf{W} | \mathbf{z}, \beta)$を求める。式(3.25)の後の項は
$$
\begin{aligned}
\prod_{k=1}^K
\frac{\prod_{v=1}^V \Gamma(N_{kv} + \beta)}{\Gamma(N_k + \beta V)}
&= \frac{\prod_{v=1}^V \Gamma(N_{1v} + \beta)}{\Gamma(N_1 + \beta V)}
\cdots
\frac{\prod_{v=1}^V \Gamma(N_{kv} + \beta)}{\Gamma(N_k + \beta V)}
\cdots
\frac{\prod_{v=1}^V \Gamma(N_{Kv} + \beta)}{\Gamma(N_K + \beta V)}
\\
&= \frac{\prod_{v=1}^V \Gamma(N_{1v} + \beta)}{\Gamma(N_1 + \beta V)}
\cdots
\frac{
\prod_{v=1}^V
\Gamma(N_{kv \backslash d} + N_{dv} + \beta)
}{
\Gamma(N_{k \backslash d} + N_d + \beta V)
}
\cdots
\frac{\prod_{v=1}^V \Gamma(N_{Kv} + \beta)}{\Gamma(N_K + \beta V)}
\\
&= \frac{
\prod_{v=1}^V
\Gamma(N_{kv \backslash d} + N_{dv} + \beta)
}{
\Gamma(N_{k \backslash d} + N_d + \beta V)
}
\prod_{k' \neq k}
\frac{
\prod_{v=1}^V
\Gamma(N_{k'v \backslash d} + \beta)
}{
\Gamma(N_{k' \backslash d} + \beta V)
}
\end{aligned}
$$
となる。$z_d = k$であるためトピック$k$に関する項を変形して、$\prod_{k=1}^K$から取り出している。それ以外の$\mathbf{z}_{\backslash d}$に関する項は、$\prod_{k' \neq k}$としてまとめている。
同様に分母$p(\mathbf{W}_{\backslash d} | \mathbf{z}_{\backslash d}, \beta)$は、文書$d$を含まないため
$$
\prod_{k=1}^K
\frac{
\prod_{v=1}^V
\Gamma(N_{kv} + \beta)
}{
\Gamma(N_k + \beta V)
}
= \prod_{k=1}^K
\frac{
\prod_{v=1}^V
\Gamma(N_{kv \backslash d} + \beta)
}{
\Gamma(N_{k \backslash d} + \beta V)
}
$$
となる。
- 約分して式を整理する。$k$に関する項のみが残る。
- 分子を入れ替えて式を整理する。
後の因子は、全ての語彙に関する項の積$\prod_{v=1}^V$である。文書$d$に含まれない(出現しない)語彙$N_{dv} = 0$に関する項については、分母分子が等しくなるため1になる。($\prod_{v=1}^V$のままでも計算上の影響はないが、)$\prod_{v: N_{dv}>0}$とすることで、文書$d$に含まれる語彙$N_{dv} > 0$の積(計算結果に影響する項の積)であることを明示している。
この式と式(3.26)を3.5.3項の始めに求めた式に代入すると、$z_d$のサンプリング式が求まる。
$$
\begin{align}
p(z_d = k | \mathbf{W}, \mathbf{z}_{\backslash d}, \alpha, \beta)
&\propto
p(z_d = k | \mathbf{z}_{\backslash d}, \alpha)
p(\mathbf{w}_d | \mathbf{W}_{\backslash d}, z_d = k, \mathbf{z}_{\backslash d}, \beta)
\\
&= \frac{D_{k \backslash d} + \alpha}{D - 1 + \alpha K}
\frac{
\Gamma(N_{k \backslash d} + \beta V)
}{
\Gamma(N_{k \backslash d} + N_d + \beta V)
}
\prod_{v:N_{dv}>0}
\frac{
\Gamma(N_{kv \backslash d} + N_{dv} + \beta)
}{
\Gamma(N_{kv \backslash d} + \beta)
}
\\
&\propto
(D_{k \backslash d} + \alpha)
\frac{
\Gamma(N_{k \backslash d} + \beta V)
}{
\Gamma(N_{k \backslash d} + N_d + \beta V)
}
\prod_{v:N_{dv}>0}
\frac{
\Gamma(N_{kv \backslash d} + N_{dv} + \beta)
}{
\Gamma(N_{kv \backslash d} + \beta)
}
\tag{3.27}
\end{align}
$$
式(3.26)の分母$\Gamma(N_{k \backslash d} + N_d + \beta V)$は$k$に影響しないため省く。
計算結果を文書ごとに、$k = 1$から$K$までの和で割ることで正規化できる。
1つ目の因子はトピック$k$が割り当てられた文書数に比例していて、割り当てられた文書数が多いトピックになりやすくなっている。また、2つ目以降の因子は文書$d$がトピック$k$に割り当てられたときの尤度(ポリヤ分布)であり、文書$d$がトピック$k$に割り当てられた文書集合と似ているほど、トピック$k$になりやすくなる。
・ハイパーパラメータの更新式の導出
不動点反復法を用いて文書集合$\mathbf{W}$とトピック集合$\mathbf{z}$の同時確率分布$p(\mathbf{W}, \mathbf{z} | \alpha, \beta)$を最大化することでハイパーパラメータ$\alpha,\ \beta$を推定する。
・Tips
次の関係性(2.7節)を用いて、不動点反復法が使えるように式を変形する。
$$
\begin{aligned}
\frac{\Gamma(x)}{\Gamma(n + x)}
&\geq
\frac{
\Gamma(\hat{x})
\exp\{(\hat{x} - x) b \}
}{
\Gamma(n + \hat{x})
}
,\quad
b = \Psi(n + \hat{x}) - \Psi(\hat{x})
\\ \\
\frac{\Gamma(n + x)}{\Gamma(x)}
&\geq
c x^a
,\quad
a = \Bigl(
\Psi(n + \hat{x}) - \Psi(\hat{x})
\Bigr)
\hat{x}
,\
c = \frac{\Gamma(n + \hat{x})}{\Gamma(\hat{x})}
\hat{x}^{-a}
\end{aligned}
$$
式(3.24')は、$\alpha K$と$\alpha$を$x$、$D$と$D_k$を$n$に対応させて
$$
\begin{aligned}
p(\mathbf{z} | \alpha)
&= \frac{\Gamma(\alpha K)}{\Gamma(D + \alpha K)}
\prod_{k=1}^K
\frac{\Gamma(D_k + \alpha)}{\Gamma(\alpha)}
\\
&\geq
\frac{
\Gamma(\hat{\alpha} K)
\exp \Bigl\{
(\hat{\alpha} K - \alpha K)
b_{\alpha}
\Bigr\}
}{
\Gamma(D + \hat{\alpha} K)
}
\prod_{k=1}^K
\frac{
\Gamma(D_k + \hat{\alpha})
}{
\Gamma(\hat{\alpha})
}
\hat{\alpha}^{-a_{\alpha}}
\alpha^{a_{\alpha}}
\end{aligned}
$$
と変形できる。
式(3.25')は、$\beta V$と$\beta$を$x$、$N_k$と$N_{kv}$を$n$に対応させて
$$
\begin{aligned}
p(\mathbf{W} | \mathbf{z}, \beta)
&= \frac{\Gamma(\beta V)}{\Gamma(N_k + \beta V)}
\prod_{k=1}^K
\prod_{v=1}^V \frac{\Gamma(N_{kv} + \beta)}{\Gamma(\beta)}
\\
&\geq
\frac{
\Gamma(\hat{\beta} V)
\exp \Bigl\{
(\hat{\beta} V - \beta V)
b_{\beta}
\Bigr\}
}{
\Gamma(N_k + \hat{\beta} V)
}
\prod_{k=1}^K \prod_{v=1}^V
\frac{
\Gamma(N_{kv} + \hat{\beta})
}{
\Gamma(\hat{\beta})
}
\hat{\beta}^{-a_{\beta}}
\beta^{a_{\beta}}
\end{aligned}
$$
と変形できる。
2つの式をまとめると、周辺尤度は
$$
\begin{aligned}
p(\mathbf{W}, \mathbf{z} | \alpha, \beta)
&= \frac{\Gamma(\alpha K)}{\Gamma(D + \alpha K)}
\prod_{k=1}^K
\frac{\Gamma(D_k + \alpha)}{\Gamma(\alpha)}
\frac{\Gamma(\beta V)}{\Gamma(N_k + \beta V)}
\prod_{k=1}^K
\prod_{v=1}^V \frac{\Gamma(N_{kv} + \beta)}{\Gamma(\beta)}
\\
&\geq
\frac{
\Gamma(\hat{\alpha} K)
\exp \Bigl\{
(\hat{\alpha} K - \alpha K)
b_{\alpha}
\Bigr\}
}{
\Gamma(D + \hat{\alpha} K)
}
\prod_{k=1}^K
\frac{
\Gamma(D_k + \hat{\alpha})
}{
\Gamma(\hat{\alpha})
}
\hat{\alpha}^{-a_{\alpha}}
\alpha^{a_{\alpha}} \\
&\qquad *
\frac{
\Gamma(\hat{\beta} V)
\exp \Bigl\{
(\hat{\beta} V - \beta V)
b_{\beta}
\Bigr\}
}{
\Gamma(N_k + \hat{\beta} V)
}
\prod_{k=1}^K \prod_{v=1}^V
\frac{
\Gamma(N_{kv} + \hat{\beta})
}{
\Gamma(\hat{\beta})
}
\hat{\beta}^{-a_{\beta}}
\beta^{a_{\beta}}
\equiv F
\end{aligned}
$$
と変形する。この式を$F$と置く。ここで
$$
\begin{aligned}
a_{\alpha}
&= \Bigl(
\Psi(D_k + \hat{\alpha})
- \Psi(\hat{\alpha})
\Bigr)
\hat{\alpha}
\\
b_{\alpha}
&= \Psi(D + \hat{\alpha} K)
- \Psi(\hat{\alpha} K)
\\
a_{\beta}
&= \Bigl(
\Psi(N_{kv} + \hat{\beta})
- \Psi(\hat{\beta})
\Bigr)
\hat{\beta}
\\
b_{\beta}
&= \Psi(N_k + \hat{\beta} V)
- \Psi(\hat{\beta} V)
\end{aligned}
$$
である。
・トピック分布のパラメータの更新式の導出
$F$から$\alpha$に関する項を取り出して対数をとった式を$F(\alpha)$と置く。
$$
\begin{aligned}
F(\alpha)
&= \log \Gamma(\hat{\alpha} K)
+ (\hat{\alpha} K - \alpha K)
\Bigl(\Psi(D + \hat{\alpha} K) - \Psi(\hat{\alpha} K) \Bigr)
- \log \Gamma(D + \hat{\alpha} K) \\
&\qquad
+ \sum_{k=1}^K \left\{
\log \Gamma(D_k + \hat{\alpha})
- \log \Gamma(\hat{\alpha})
- \Bigl(\Psi(D_k + \hat{\alpha}) - \Psi(\hat{\alpha}) \Bigr)
\hat{\alpha}
\log \hat{\alpha}
+ \Bigl(\Psi(D_k + \hat{\alpha}) - \Psi(\hat{\alpha}) \Bigr)
\hat{\alpha}
\log \alpha
\right\}
\end{aligned}
$$
この式を$\alpha$関して微分し、$\frac{\partial F(\alpha)}{\partial \alpha} = 0$となる$\alpha$を求める。
$$
\begin{aligned}
\frac{\partial F(\alpha)}{\partial \alpha}
=& - K \Bigl(\Psi(D + \hat{\alpha} K) - \Psi(\hat{\alpha} K) \Bigr)
+ \frac{1}{\alpha}
\sum_{k=1}^K
\Bigl(\Psi(D_k + \hat{\alpha}) - \Psi(\hat{\alpha}) \Bigr)
\hat{\alpha}
= 0 \\
&\alpha
= \hat{\alpha}
\frac{
\sum_{k=1}^K \Psi(D_k + \hat{\alpha}) - K \Psi(\hat{\alpha})
}{
K \Psi(D + \hat{\alpha} K) - K \Psi(\hat{\alpha} K)
}
\end{aligned}
$$
この式の$\hat{\alpha}$を現ステップのパラメータ$\alpha$とし、左辺の$\alpha$を更新後(次ステップ)のパラメータ$\alpha^{\mathrm{new}}$とした
$$
\alpha^{\mathrm{new}}
= \alpha
\frac{
\sum_{k=1}^K
\Psi(D_k + \alpha)
- K \Psi(\alpha)
}{
K \Psi(D + \alpha K)
- K \Psi(\alpha K)
}
\tag{3.28}
$$
がハイパーパラメータ$\alpha$の更新式となる。
・単語分布のパラメータの更新式の導出
同様に、$F$から$\beta$に関する項を取り出して対数をとった式を$F(\beta)$と置く。
$$
\begin{aligned}
F(\beta)
&= \log \Gamma(\hat{\beta} V)
+ (\hat{\beta} V - \beta V)
\Bigl(\Psi(N_k + \hat{\beta} V) - \Psi(\hat{\beta} V) \Bigr)
- \log \Gamma(N_k + \hat{\beta} V) \\
&\quad
+ \sum_{k=1}^K \sum_{v=1}^V \left\{
\log \Gamma(N_{kv} + \hat{\beta})
- \log \Gamma(\hat{\beta})
- \Bigl(
\Psi(N_{kv} + \hat{\beta}) - \Psi(\hat{\beta})
\Bigr)
\hat{\beta}
\log \hat{\beta}
+ \Bigl(
\Psi(N_{kv} + \hat{\beta}) - \Psi(\hat{\beta})
\Bigr)
\hat{\beta}
\log \beta
\right\}
\end{aligned}
$$
この式を$\beta$に関して微分し、$\frac{\partial F(\beta)}{\partial \beta} = 0$となる$\beta$を求める。
$$
\begin{aligned}
\frac{\partial F(\beta)}{\partial \beta}
=& - V \Bigl(\Psi(N_k + \hat{\beta} V) - \Psi(\hat{\beta} V) \Bigr)
+ \frac{1}{\beta}
\sum_{k=1}^K \sum_{v=1}^V
\Bigl( \Psi(N_{kv} + \hat{\beta}) - \Psi(\hat{\beta}) \Bigr)
\hat{\beta}
= 0
\\
&\beta
= \hat{\beta}
\frac{
\sum_{k=1}^K \sum_{v=1}^V
\Psi(N_{kv} + \beta)
- K V \Psi(\hat{\beta})
}{
V \sum_{k=1}^K
\Psi(N_k + \hat{\beta} V)
- K V \Psi(\hat{\beta} V)
}
\end{aligned}
$$
この式の$\hat{\beta}$を現ステップのパラメータ$\beta$とし、左辺の$\beta$を更新後(次ステップ)のパラメータ$\beta^{\mathrm{new}}$とした
$$
\beta^{\mathrm{new}}
= \beta
\frac{
\sum_{k=1}^K \sum_{v=1}^V
\Psi(N_{kv} + \beta)
- K V \Psi(\beta)
}{
V
\sum_{k=1}^K
\Psi(N_k + \beta V)
- K V \Psi(\beta V)
}
\tag{3.29}
$$
がハイパーパラメータ$\beta$の更新式となる。
参考書籍
- 岩田具治(2015)『トピックモデル』(機械学習プロフェッショナルシリーズ)講談社
おわりに
現在これら3章混合ユニグラムモデルの内容をRで組もうと色々試行錯誤しています。
2019/07/27:加筆修正しました。
単純なベイズの定理や乗法定理以外の条件付き確率の操作がまだよく分かっていません。別の本を仕入れているので、早くそれで勉強したいとは思いつつも、、、
2020/07/24:加筆修正しました。
白トピ本と須山ベイズ本により、それなりに理解できました!そちらの解説記事も書いてるので、よければ読んでね。
【次節の内容】
www.anarchive-beta.com