でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

Correspondence Topic Model の導出と実装

引き続き青いトピックモデル本から、対応トピックモデル(Correcpondence Topic Model; CTM)を実装した。サンプリング式の導出が詳しく載っていなかったので、詳しめに導出してみる。

トピックモデル (機械学習プロフェッショナルシリーズ)

トピックモデル (機械学習プロフェッショナルシリーズ)

CTM の出典は以下の論文。

http://www.cs.columbia.edu/~blei/papers/BleiJordan2003.pdf

Correspondence Topic Model

前回書いた結合トピックモデル(Joint Topic Model; JTM)と同じで、文書のモデリングをするときに文書についている付加情報も考慮するモデル。

JTMとCTMが違うのは以下の点だけ。ある文書 d について、付加情報のトピック y を生成するときに、JTMでは単語のトピック z とは独立に生成されるんだけど、CTMでは y は同じ文書 d の単語のトピック z のどれかから 選ばれる。つまり、文書 d に含まれるどの単語にも割り当てられていないトピック k はその文書内の付加情報には割り当てられない。

こうすることで、CTMはある文書の単語と付加情報とに全然関係ないばらばらのトピックが割り当てられることを防ぐ。

CTMのグラフィカルモデルは以下。

f:id:yamaguchiyuto:20170321125538p:plain

通常通り、白まるが非観測の確率変数で灰色のまるが観測された確率変数、黒い小さなまるがパラメータ(確率変数でない)を表す。生成過程を全部書くのは面倒くさいので簡単に説明すると、w, z, θ, φの生成過程はLDAと同じ。yの生成過程だけ特殊で、

{
y_{dm} \sim Cat(\frac{n_{d1}}{n_d}, \cdots, \frac{n_{dK}}{n_d})
}

Cat()はカテゴリカル分布(n=1の多項分布)、{n_d}は文書 d の単語数、{n_{dk}}は文書 d のなかでトピック k が割り当てられた単語の数。つまり、文書 d の単語に多く割り当てられたトピックほど {y_{dm}} に割り当てられる確率が高くなる。

ちなみに、元論文では w の生成が多項分布じゃなくてガウシアンになってたので、青いトピックモデル本に載ってるモデルとは違うっぽい。今回は青いトピックモデル本のとおり、多項分布で行く。

導出

周辺化ギブスサンプリングを導出する。以下のように {Z = \{z_{dn}\}}{Y = \{y_{dm}\}} のサンプリングをする。

Zのサンプリング

右肩の添字は、その集合から対応する添字の要素を除いたものとする。例えば、{Z^{dn}}{Z} から {z_{dn}} を除いたものとする。

{
p(z_{dn} = k | w_{dn} = v, Z^{dn}, W^{dn}, X, Y, \alpha, \beta, \gamma)
}

{
\propto \int p(z_{dn} = k, w_{dn} = v, Z^{dn}, W^{dn}, X, Y, \Theta, \Phi | \alpha, \beta, \gamma) d \Theta d\Phi
}

{
\propto \int p(w_{dn} = v | \phi_k) p(\phi_k | Z^{dn}, W^{dn}, \beta) d \phi_k
}

{
\times \int p(z_{dn} = k | \theta_d, y_d, z^{n}_d) p(\theta_d | z^n_d, y_d, \alpha) d \theta_d
}

ここで、一つ目の積分はLDAと同じで、{\frac{n^{dn}_{kv}+\beta}{\sum_v (n^{dn}_{kv}+\beta)}} となる。ただし、{n^{dn}_{kv}}{z_{dn}} を除いて、トピック k が単語 v に割り当てられた回数を表す。

2つめの積分について見ていくと、

{
\int p(z_{dn} = k | \theta_d, y_d, z^{n}_d) p(\theta_d | z^n_d, y_d, \alpha) d \theta_d
}

{
\propto \int p(z_{dn} = k | \theta_d, y_d, z^{n}_d)p(\theta_d, z^n_d, y_d | \alpha) d \theta_d
}

{
= \int p(z_{dn} = k, \theta_d, z^n_d, y_d | \alpha) d \theta_d
}

{
= \int p(y_d|z^n_d, z_{dn}=k)p(z_{dn} = k | \theta_d)p(\theta_d|z^n_d, \alpha) d \theta_d
}

{
= p(y_d|z^n_d, z_{dn}=k) \int p(z_{dn} = k | \theta_d)p(\theta_d|z^n_d, \alpha) d \theta_d
}

ここで、積分の中身はLDAと同じで {\frac{n^n_{dk} + \alpha}{\sum_k (n^n_{dk} + \alpha)}} となり、また

{
p(y_d|z^n_d, z_{dn}=k) = \left(\frac{n^n_{d1}}{n^n_d}\right)^{M_{d1}}\left(\frac{n^n_{d2}}{n^n_d}\right)^{M_{d2}}\cdots\left(\frac{n^n_{dk}+1}{n^n_d}\right)^{M_{dk}}\cdots\left(\frac{n^n_{dK}}{n^n_d}\right)^{M_{dK}}
}

{
 = \left(\frac{n^n_{dk}+1}{n^n_{dk}}\right)^{M_{dk}} \left(\frac{n^n_{d1}}{n^n_d}\right)^{M_{d1}}\left(\frac{n^n_{d2}}{n^n_d}\right)^{M_{d2}}\cdots\left(\frac{n^n_{dk}}{n^n_d}\right)^{M_{dk}}\cdots\left(\frac{n^n_{dK}}{n^n_d}\right)^{M_{dK}}
}

{
 = \left(\frac{n^n_{dk}+1}{n^n_{dk}}\right)^{M_{dk}} p(y_d|z^n_d)
}

{
\propto \left(\frac{n^n_{dk}+1}{n^n_{dk}}\right)^{M_{dk}}
}

となる。ただし、{n^n_{dk}} は単語 {z_{dn}} を除いて、文書 d 内の単語にトピック k が割り当てられた回数を表す。また、{n^n_{d} = \sum_k n^n_{dk}} 。さらに、{M_{dk}} は文書 d の付加情報のうちトピック k が割り当てられた回数を表す。

以上より、まとめると

{
p(z_{dn} = k | w_{dn} = v, Z^{dn}, W^{dn}, X, Y, \alpha, \beta, \gamma)
}

{
\propto (n^n_{dk} + \alpha) \frac{n^{dn}_{kv}+\beta}{\sum_v (n^{dn}_{kv}+\beta)} \left(\frac{n^n_{dk}+1}{n^n_{dk}}\right)^{M_{dk}}
}

Yのサンプリング

{
p(y_{dm} = k | x_{dm} = u, Z, W, X^{dm}, Y^{dm}, \alpha, \beta, \gamma)
}

{
= \int p(x_{dm}=u|y_{dm}=k, \Psi)p(y_{dm} = k|z_d)p(\Psi |X^{dm}, Y^{dm}, \gamma) d\Psi
}

{
= p(y_{dm} = k|z_d) \int p(x_{dm}=u|y_{dm}=k, \Psi)p(\Psi |X^{dm}, Y^{dm}, \gamma) d\Psi
}

{
\propto n_{dk} \int p(x_{dm}=u|y_{dm}=k, \Psi)p(\Psi |X^{dm}, Y^{dm}, \gamma) d\Psi
}

{
\propto n_{dk} \frac{n^{dm}_{ku}+\gamma}{\sum_u (n^{dm}_{ku}+\gamma)}
}

{n^{dm}_{ku}}{x_{dm}} を除いて、トピック k が割り当てられた付加情報 u の数を表す。

実装

{z_{dn}} をサンプリングするときに、{y_d} には割り当てられているのに {z^n_d} に割り当てられていないトピックがある場合は必ずそのトピックをサンプルするようになっているんだけど(式参照)、その場合0除算が発生してしまわないように場合分けをする。

Correspondence Topic Model

実験

適当なデータを作って Joint Topic Model と Correcpondence Topic Model を比較した。JTM は最後の文書で単語にはトピック 1 (windowsトピック)を割り当てているのに、付加情報(カテゴリ)にはトピック 0 (ipadトピック)を割り当ててしまっている。CTM はそうはならず、単語にも付加情報にも同じトピックが割り当てられている。

CTM experiments