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

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

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

Joint Topic Modelを実装した

LDAの簡単な拡張になっている Joint Topic Model を実装した。青いトピックモデル本で紹介されてた。この本はいろんなモデルが載ってるのでいいね。

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

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

実装したあとで気づいたけど既にnzw君が実装して実験してたのでこちらも参考に。

nzw0301.github.io

Joint Topic Model

Joint Topic Model (JTM) はLDAとほとんど同じなんだけど、文書に付加情報(カテゴリとか)がついてる場合、それも使うことができる。

どんな付加情報を扱えるかというと、基本的にはカテゴリ変数だけ。生成過程を見ると分かるように、付加情報の生成にはカテゴリカル分布が使われているので、何かしらの数値(レビュー文書のレーティングとか)が付加情報としてついていてもこのモデルではうまく扱えない(理論上は)。

このモデルが応用されている例として、対訳文書のモデリングをしてる以下の論文がある。

http://dirichlet.net/pdf/mimno09polylingual.pdf

この論文では文書として言語Aの文書、付加情報として言語Bの文書をモデルに与えて、両方の情報を用いてトピック推定をしている。JTMは複数の付加情報を同時にモデリングできるので、言語C, D, E, …の文書を同時にモデルに与えることも出来る。

実装

周辺化ギブスサンプリングで実装。ほとんどLDAと同じ。Z(トピック割り当て)のサンプリングの式がちょっと違うだけ。

Joint Topic Models

実験

JTMとLDAを比較してみた。PCもしくはFOODというカテゴリが与えられている文書がうまくモデリング出来るかを比較した。結果を見ると、JTMはカテゴリ情報をうまく使って、全く同じ単語が出現している文書にもうまくトピックを割り当てることが出来ている。LDAではカテゴリ情報が与えられていないので当然そういうことは出来ない。

JTM experiments

Robust Large-Scale Machine Learning in the Cloud [KDD'16] を読んだ

KDD16で発表されてた論文。著者はかの有名なFactorization Machinesの人。Googleに行ってたのね。いままでとはちょっと違う研究をしてるように感じる。

論文はここから読める。

www.kdd.org

勉強会で紹介したので念のため、その時のスライドはこちら。

一言まとめ

一般化線形モデルの学習を Coordinate Descent で、めっちゃスケールさせるよ。

概要

Coordinate Descent (CD) はシングルマシン上では収束が早いアルゴリズムとして知られてるんだけど、分散には向かない。なぜなら、アルゴリズムの特性上、分散させると1つのワーカーに割り当てられる work load が小さくなってしまって、オーバヘッドを考えると分散効果が小さいから。CDはパラメータの更新を次元ごとに 逐次 繰り返していくことで収束するアルゴリズムなので、分散させるには基本的にはデータパラレルにすることになる。でもパラメータの1つの次元を更新するときの処理はそんなに重くないので、分散させるメリットがあまりないということ。

そこでこの論文では1つの次元ごとじゃなくて、次元の集合(ブロック)ごとに更新するのをくりかえす Scalable Coordinate Descent (SCD) というアルゴリズムを提案する。そうすることで分散させて1つのワーカーに割り当てる work load をある程度大きくすることが出来る。で、ブロックごとに更新しても収束するのか? という話だけど、パラメータの更新時にこれまでの値と更新後の値の間で line search してやると収束するらしい。なぜかは知らん(書いてない)。さらに、特徴次元をうまいことブロックに分割しれやれば、CDと全く同じ解が得られることも示した。

で、この SCD を Google Cloud 上に実装したらしい。論文中では実装時の細かいところの説明がされていた。この辺もさらっと書いてあるけどいろいろ試行錯誤して大変だったんだろなと思った。ポイントは、VM Preemptionがある環境を想定しているところなのかな? AWS の Spot instance とかがそれなんだけど、優先度が低いとみなされた VM(=worker) が勝手に強制終了されて、空いたリソースが別の優先度の高いVMに割り当てられてしまうという環境。

実際にGoogleが持ってる広告のデータを使って実装したらしい。サンプル数は1兆(!)で、特徴数は10億(!)のスケールのデータらしい。Google恐るべし。ちなみにこれはNetflix prizeの1万倍の規模らしい。結果はここでは省略するけどスケールしたとのこと。

無限潜在特徴モデルを実装した

引き続きノンパラベイズ。今回はノンパラベイズ本の7.4節で説明されてる無限潜在特徴モデル(Infinite latent feature model; ILFM)を実装した。

無限潜在特徴モデル

一言で言えば、潜在次元に無限次元を仮定する行列分解。

与えられたデータ行列 {Y \in \mathbb{R}^{N \times D}} をバイナリ行列 {Z \in \{0,1\}^{N \times K}} と特徴行列 {X \in \mathbb{R}^{K \times D}} の積に分解する。

バイナリ行列の要素 {z_{n,k}} はサンプル n が k 番目の潜在特徴を持つか持たないかを表している。k番目の潜在特徴は {X} のk番目の行ベクトル {x_k^T \in \mathbb{R}^D} で表されている。つまり、あるサンプルのデータベクトル {y_n} は無限個ある潜在特徴のうちのいくつかの和になっている。

通常の行列分解では分解後の行列の潜在次元数 K を予め決めなきゃいけないんだけど、このモデルはノンパラベイズなので決めなくて良い。データから勝手に決まる。さすがノンパラベイズ

モデルの説明とパラメータ推定の説明は上の本に詳しく書いてあるので割愛。

実装

特に注意すべき点はないと思うけど、強いて言うならサンプリングの事後分布を計算するときにunderflowしないように対数のまま正規化してやるくらい。

Infinite Latent Feature Model

実験

alphaを小さく設定してもどうしても真のKより大きな潜在次元数が推定されてしまう。何か間違ってるのかこういうもんなのか判断ができない。相対誤差は十分(?)小さくなってる。

ILFM experiment

無限混合ガウスモデルを実装した

ノンパラベイズ面白いね。佐藤一誠先生のノンパラメトリックベイズの本を読んで自分なりに理解できたので実装してみた。本読んで理解して、自分で導出して、実装・実験するの本当に重要。定着度がぜんぜん違う。

無限混合ガウスモデルは上の本の5.2節で説明されてるモデルで、ディリクレ過程混合ガウスモデル(Dirichlet Process Gaussian Mixture Model; DPGMM)とも呼ぶらしい。面倒くさいので以下DPGMMと書く。

DPGMM

普通の混合ガウスだと分割数(クラスタの数)K を事前に決めなきゃいけないんだけど、これが面倒くさいし、よほどそのデータに詳しいか超能力でも無い限り、いろんな K の値を試してみないといけない。面倒くさい。

そこでDPGMMの出番。予め K を決めなくてもデータから推定してくれる。便利。

感覚的にちょっと説明すると、あるデータ点のクラスタ割り当てを決めるとき、普通の混合ガウスだったらそのデータ点を生成したっぽいクラスタ(ガウシアン)に割り当てるんだけど、DPGMMだとどのクラスタからも生成されたっぽくないときは新しいクラスタが作られる。このクラスタ割り当てを何度も何度もやる(ギブスサンプリング)ことで、最終的に適切な数のクラスタが作られ、全てのデータ点が適切なクラスタに割り当てられる。

詳細は上の本を読むと良い。佐藤先生の本は本当に超わかりやすい。

実装

めっちゃ遅いけど実装した。本に書いてあるように、共分散行列は対角行列と仮定した。

Dirichlet Process Gaussian Mixture Model

実験

真のクラスタ数は3で、分散は全てのクラスタで1。クラスタ間が互いにかなり離れてるので簡単な設定になってる。

結果を見ると、クラスタ数を指定してないのに、クラスタが3つ作られて、全てのデータ点が適切なクラスタに割り当てられていることが分かる。

DPGMM experiment