唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

『言語処理のための機械学習入門』のPLSA(アスペクトモデル)のEMアルゴリズムの導出(例題3.4)

言語処理のための機械学習入門 (自然言語処理シリーズ)』(いわゆる高村本)で研究室の後輩が勉強会をしていて、自分でも一瞬わからなかったのでメモ。
PLSAとかPLSIとかアスペクトモデルとか名前がいろいろあってよくわからないです。

同時確率

文書をx、単語をy、トピック(クラスタ)をcとしたとき同時確率は以下のようになる。
P(X=x, Y=y)=\sum_c P(x, y, c)=\sum_cP(x|c)P(y|c)P(c)

Q関数

q_{x,c}=P(x|c), r_{y,c}=P(y|c),p_c=P(c)とおくと
Q関数は
Q(\theta;\theta')=\sum_{x,y}n_{x,y}\sum_c P(c|x,y;\theta')\log q_{x,c} r_{y,c}p_c
突然n_{x,y}が出てきて説明が無いですが、たぶんX=x, Y=yになる回数とか頻度とかです。

Eステップ

P(c|x,y;\theta')=\frac{P(x, y, c;\theta')}{P(x, y;\theta')}=\frac{P(x, y, c;\theta')}{\sum_c P(x, y, c;\theta')}=\frac{q'_{x,c}r'_{y,c}p'_c}{\sum_c q'_{x,c}r'_{y,c}p'_c}

Mステップ

確率なので、以下の制約を満たさなければならない。
\sum_x q_{x,c}=1,\sum_y r_{y,c}=1,\sum_c p_c=1
このときラグランジュ関数
L(\theta,\alpha,\beta,\gamma)=Q(\theta;\theta')+\sum_c \alpha_c(\sum_x q_{x,c}-1)+\sum_c \beta_c(\sum_y r_{y,c}-1)+\gamma(\sum_c p_c-1)

q_{x,c}について

q_{x,c}偏微分して
\frac{\partial L(\theta,\alpha,\beta,\gamma)}{\partial q_{x,c}}=\sum_y n_{x,y}P(c|x,y;\theta')\frac{1}{q_{x,c}} + \alpha_c=0
式変形すると
q_{x,c} = -\frac{1}{\alpha_c}\sum_y n_{x,y}P(c|x,y;\theta')
制約\sum_x q_{x,c}=1より
 -\frac{1}{\alpha_c}\sum_x\sum_y n_{x,y}P(c|x,y;\theta') = 1
よって
 \alpha_c = -\sum_x\sum_y n_{x,y}P(c|x,y;\theta')
式変形後の式に代入すると
q_{x,c} = \frac{\sum_y n_{x,y}P(c|x,y;\theta')}{\sum_x\sum_y n_{x,y}P(c|x,y;\theta')}

r_{y,c}について

q_{x,c}と同様。
\frac{\partial L(\theta,\alpha,\beta,\gamma)}{\partial r_{y,c}}=\sum_x n_{x,y}P(c|x,y;\theta')\frac{1}{r_{y,c}} + \beta_c=0
r_{y,c} = -\frac{1}{\beta_c}\sum_x n_{x,y}P(c|x,y;\theta')
制約\sum_y r_{y,c}=1より
 \beta_c = -\sum_y\sum_x n_{x,y}P(c|x,y;\theta')
r_{y,c} = \frac{\sum_x n_{x,y}P(c|x,y;\theta')}{\sum_y\sum_x n_{x,y}P(c|x,y;\theta')}

p_cについて

q_{x,c}, r_{y,c}と同様。
\frac{\partial L(\theta,\alpha,\beta,\gamma)}{\partial p_c}=\sum_x\sum_y n_{x,y}P(c|x,y;\theta')\frac{1}{p_c} + \gamma=0
p_c = -\frac{1}{\gamma}\sum_x \sum_y n_{x,y}P(c|x,y;\theta')
制約\sum_c p_c=1より
 \gamma = -\sum_c\sum_x\sum_y n_{x,y}P(c|x,y;\theta')
p_c = \frac{\sum_x\sum_y n_{x,y}P(c|x,y;\theta')}{\sum_c\sum_x\sum_y n_{x,y}P(c|x,y;\theta')}

余談(他の定義)

↑の記事とかを見ると書いてあるんですが、PLSAは式\sum_cP(x|c)P(y|c)P(c)の他にも\sum_c P(y|c)P(c|x)P(x)の形で定義されているときもあります。

参考文献

言語処理のための機械学習入門 (自然言語処理シリーズ)

言語処理のための機械学習入門 (自然言語処理シリーズ)