PLSA

"Unsupervised learning by probabilistic Latent Semantic Analysis", JMLR, 2001

PLSAの詳しい説明は他所に譲るけど簡単に説明する。PLSAとは、文書の生成モデルで、以下のステップを経て文書が生成されるとする

確率 $P(d)$ で文書 $d$ が選ばれる
確率 $P(z|d)$ で潜在変数 $z$ が選ばれる
確率 $P(w|z)$ で単語 $w$ が選ばれる

ここで潜在変数 $z$ というのは文書のトピックみたいなものと考えれば良い。ある文書 $d$ は確率分布 $P(z|d)$ を持っていて、それにしたがってトピック $z$ が選ばれる。また、各トピック $z$ は確率分布 $P(w|z)$ を持っていて、それにしたがって単語 $w$ が選ばれる。このプロセスを何度も繰り返すことで文書が生成されるというモデルになっている。

以上の生成プロセスを式で書くと以下になる。

$P(d, w) = \sum_z P(w|z)P(z|d)P(d)$

潜在変数 $z$ は観測されないので、当然確率 $P(z|d)$ も $P(w|z)$ も分からない。

PLSAでやりたいことは、持っている文書データ $D=\{d_1, \cdots, d_n\}$ を使って $P(z|d)$ と $P(w|z)$ を推定すること。これを推定するためにEMアルゴリズムを使う。

対数尤度

ある文書と単語のペア $(d,w)$ について考える。

このペアの対数尤度は以下になる。

$\log P(d,w) = \log \sum_z P(w|z)P(z|d)P(d) \\ = \log P(d) + \log \sum_z P(w|z)P(z|d)$

しかし、対数の中に和があるのでこれの最大化は難しそうに見える。

一方で、ペア $(d, w)$ に潜在変数 $z$ が割り当てられていることがわかっているとすると、完全データ対数尤度は以下になる。

$\log P(d,w,z) = \log P(w|z)P(z|d)P(d) \\ = \log P(d) + \log P(w|z) + \log P(z|d)$

これの最大化は簡単そうに見える（対数の中の和がなくなってる）。

対数尤度そのままの最大化は難しいが、完全データ対数尤度の最大化は簡単そうということで、EMアルゴリズムの出番となる。

E-step

E-stepでやることは潜在変数の事後分布 $P(z|d,w)$ を計算することだった。

$P(z|d,w) = \frac{P(w|z)P(z|d)}{P(w|d)} \\ = \frac{P(w|z)P(z|d)}{\sum_z P(w|z)P(z|d)}$

これはベイズの定理により簡単に求まった。

M-step

Mステップでは、 $q(z) = p(z|d,w)$ と固定して、Q関数を最大化するパラメータを求める。PLSAにおいて求めたいパラメータは $P(z|d)$ と $P(w|z)$ であることを思い出す。

あるペア $(d,w)$ に注目すると、Q関数は以下となる。（Q関数は完全データ対数尤度を潜在変数zの事後分布について期待値をとったものだったことを思い出そう。）

全体の文書データ $D=\{d_1, \cdots, d_n\}$ 、つまり全文書単語ペア $(d,w)$ について考えると、Q関数は以下となる。

$Q = \sum_d \sum_w n(d,w) \sum_z P(z|d,w) [\log P(w|z) + \log P(z|d) + \log P(d)]$

ただし、 $n(d,w)$ は文書 $d$ に単語 $w$ が出現した回数を表す。

$P(z|d)についてQ関数を最大化$

$\sum_z P(z|d) = 1$ の制約があるため、ラグランジュ定数 $\lambda_d$ を用いて

$H = Q + \sum_d \lambda_d(\sum_z P(z|d) - 1)$

と置き、 $H$ を最大化する。

$H$ を $P(z|d)$ で微分して $0$ と置くと

$\frac{\partial H}{\partial P(z|d)} = \sum_w n(d,w)P(z|d,w) \cdot \frac{1}{P(z|d)} + \lambda_d = 0$

となり、 $P(z|d)$ について整理すると

$P(z|d) = - \frac{\sum_w n(d,w)P(z|d,w)}{\lambda_d}$

となる。 $z$ について和を取ると

$\sum_z P(z|d) = 1 = \sum_z - \frac{\sum_w n(d,w)P(z|d,w)}{\lambda_d}$

となり、 $\lambda_d$ について整理すると

$\lambda_d = - \sum_z \sum_w n(d,w)P(z|d,w) = - \sum_w n(d,w)$

となる。したがって $P(z|d)$ が求まる。

$P(z|d) = \frac{\sum_w n(d,w)P(z|d,w)}{\sum_w n(d,w)}$

$P(w|z)についてQ関数を最大化$

$\sum_w P(w|z) = 1$ の制約があるため、ラグランジュ定数 $\lambda_z$ を用いて

$J = Q + \sum_z \lambda_z(\sum_w P(w|z) - 1)$

と置き、 $J$ を最大化する。

$J$ を $P(w|z)$ で微分して $0$ と置くと

$\frac{\partial J}{\partial P(w|z)} = \sum_d n(d,w)P(z|d,w) \cdot \frac{1}{P(w|z)} + \lambda_z = 0$

となり、 $P(w|z)$ について整理すると

$P(w|z) = - \frac{\sum_d n(d,w)P(z|d,w)}{\lambda_z}$

となる。 $w$ について和を取ると

$\sum_w P(w|z) = 1 = \sum_w - \frac{\sum_d n(d,w)P(z|d,w)}{\lambda_z}$

となり、 $\lambda_z$ について整理すると

$\lambda_z = - \sum_w \sum_d n(d,w)P(z|d,w)$

となる。したがって $P(w|z)$ が求まる。

$P(w|z) = \frac{\sum_d n(d,w)P(z|d,w)}{\sum_w \sum_d n(d,w)P(z|d,w)}$

まとめ

以上より、EMアルゴリズムを用いたPLSAのパラメータ推定の手続きは

適当な値で $P(w|z)$ 、 $P(z|d)$ を初期化する
$P(z|d,w) = \frac{P(w|z)P(z|d)}{\sum_z P(w|z)P(z|d)}$ を計算する
$P(z|d) = \frac{\sum_w n(d,w)P(z|d,w)}{\sum_w n(d,w)}$ を計算する
$P(w|z) = \frac{\sum_d n(d,w)P(z|d,w)}{\sum_w \sum_d n(d,w)P(z|d,w)}$ を計算する
収束するまで2-4を繰り返す

となる。