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

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

Noisy Correspondence Topic Model の導出と実装

さらに引き続き青いトピックモデル本から。今回はノイズ有り対応トピックモデル (Noisy Correspondence Topic Model; NCTM) を導出して実装する。

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

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

出典は以下の論文。

http://www.kecl.ntt.co.jp/as/members/iwata/nips2009.pdf

Noisy Correspondence Topic Model

このモデルは Correspondence Topic Model (CTM) の拡張になっていて、CTM と同様に付加情報を考慮しながら文書のモデリングが出来る。どう拡張されているかというと、付加情報の中からノイズとノイズでないものを切り分けることが出来る。

付加情報のノイズについて、論文中でも取り上げられているソーシャルブックマークの例を使って説明する。ソーシャルブックマークでは、Webページ(文書)にタグ(付加情報)を付けることが出来る。タグの中には、文書のトピックを表すようなもの(例えば技術系のブログ記事に “TECH” とか)と、文書のトピックを表さないようなもの(例えば、"あとで読む" とか)の2種類がある。前者は文書のモデリングに役立ちそうだけど、後者は役立ちそうにないので、このモデルではノイズと呼ぶ。

ノイズでない付加情報は特定のトピックに偏って出てくるけど、ノイズである付加情報は偏り無く、全てのトピックにまんべんなく出てくる。つまり、「ノイズとは特定のトピックに偏り無く出現する付加情報」であると、(ある意味)定義していることになる。これ重要。

で、どう切り分けるかだけど、各付加情報について、それがノイズかノイズでないかを表す確率変数 {r \in {0,1}} を導入する。r が 0 のときは対応する付加情報はノイズで、1 のときはノイズでないとする。そんでその r が 0 なのか 1 なのかをデータから推定する。この r をスイッチ変数と呼ぶ。

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

f:id:yamaguchiyuto:20170322064202p:plain

CTM から変わったのはスイッチ変数の部分だけで、r は各付加情報ごとにある。生成過程も CTM とほぼおなじだけど、r は λ をパラメータとするベルヌーイ分布から生成され、λ は η をパラメータとするベータ分布から生成される。一件ごちゃごちゃしてるけど、拡張の系譜をたどると理解しやすい。

なぜスイッチ変数をデータから推定できるか?

トピックモデルを1ミリもわかってなかったときはなんでこの変数をデータから推定できるのか全くわからなかったんだけど、今は1ミリくらいは分かっているので直感的に説明してみる。トピックモデル(LDAから派生したモデル群)は基本的には単語のハードクラスタリングを行っている。言い換えると、「それぞれの単語は特定のトピック(クラスタ)から出現した」という仮定を入れている。 つまり、全てのトピックからまんべんなく出現する単語というのはモデル上有りえない。

じゃあどうするか。上記のクラスタリングをする前に、その単語が「特定のトピックから出現した」のか、「トピックに関係なく出現した」のか判別する。前者と判別されたらその単語がどのトピックから出現したのかをクラスタリングする。後者と判別されたらしない。当然、ノイズは「トピックに関係なく出現した」としたほうが、つまり r=0 としたほうが、モデルのもっともらしさは高くなるので、そのように推定されることになる。

導出

周辺化ギブスサンプリングのサンプリング式を導出する。Z のサンプリングは CTM と同じなので省略。前回と同様に右肩の添字はその集合から添字に対応する要素を抜くことを表す。

Y のサンプリング

Y のサンプリングも CTM とほぼ同じなので導出は省略するけど、 文書 d の m 番目の付加情報のトピック {y_{dm}} をサンプリングするときに、{r_{dm}} が 0 か 1 かでサンプリングの式が変わる。

{r_{dm}=1} のとき、つまりノイズでないときは CTM の時と同じ。

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

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

{n_{dk}} は文書 d の単語のうちトピック k が割り当てられたものの数を表し、{m^{dm}_{ku}}{x_{dm}} を除いて、トピック k が割り当てられた付加情報 u の数を表す。

{r_{dm}=0} のとき、つまりノイズであるときは CTM の時と少し違う。

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

{
\propto n_{dk}
}

つまり、付加情報 {x_{dm}} がノイズであるときは、その文書においてトピック k が割り当てられた単語数のみが考慮される。ちなみに、{x_{dm}} がノイズであるときは {y_{dm}} が他の変数のサンプリング式に影響をあたえることはないので、サンプリングする必要はない。

R のサンプリング

{r_{dm}} のサンプリングをするときは、{r_{dm}=0} の事後分布と {r_{dm}=1} の事後分布を両方計算して2つの合計が 1 になるように正規化すれば良い。

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

{
\propto \int p(r_{dm} = 1, x_{dm} = u, y_{dm} = k, Z, W, X^{dm}, Y^{dm}, R^{dm}, \Psi, \lambda | \alpha, \beta, \gamma, \eta) d\Psi d\lambda
}

{
\propto \int p(x_{dm} = u | r_{dm} = 1, y_{dm} = k, \psi_k)p(\psi_k|X^{dm}, Y^{dm}, R^{dm}, \gamma) d\psi_k
}

{
\times \int p(r_{dm} = 1 | \lambda )p(\lambda|R^{dm}, \eta) d\lambda
}

{
= \int \psi_{ku} p(\psi_k | X^{dm}, Y^{dm}, R^{dm}, \gamma)d\psi_k \times \int \lambda p(\lambda|R^{dm},\eta) d\lambda
}

{
\propto \frac{M^{dm}_{ku} + \gamma}{\sum_u (M^{dm}_{ku} + \gamma)} (M^{dm}_1 + \eta)
}

{M^{dm}_{ku}}{x_{dm}} を除いて、トピック k が付加情報 u に割り当てられた回数を表し、{M^{dm}_1}{x_{dm}} を除いて、ノイズでない付加情報の数を表す。

また同様に、

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

{
\propto \frac{M^{dm}_{0u} + \gamma}{\sum_u (M^{dm}_{0u} + \gamma)} (M^{dm}_0 + \eta)
}

{M^{dm}_{0u}}{x_{dm}} を除いて、付加情報 u がノイズであると判別された回数を表し、{M^{dm}_0}{x_{dm}} を除いて、ノイズである付加情報の数を表す。

実装

{r_{dm}}が 0 か 1 かでサンプリングとかの処理を変える必要があるので、その辺を注意。

Noisy Correspondence Topic Model

実験

CTM と NCTM を比較した。ノイズと判別されるべきの付加情報 “TOREAD” を加えて、それがちゃんと NCTM によってノイズと判別されるかを見てみる。結果を見ると、NCTM は “TOREAD” をしっかりとノイズと判別するため、他の単語及び付加情報にうまくトピックを割り当てることが出来ている。一方で CTM は “TOREAD” にトピック 0 (ipadとかと同じトピック) を割り当ててしまっているせいで、4番目の文書の単語 “apple” にトピック 0 を割り当ててしまっている。

NCTM experiment