PRML 13章の「HMM の最尤推定」を書き換えてみた

@shuyo: 社内PRML読書会。今日はHMMの最尤推定。EMAによる導出部分がムダに天下りすぎる。Mステップの対数同時分布の期待値の計算に必要な事後分布の統計量E[z_nk]をγ_nkとおくと、1-of-Kゆえγ_nk=p(z_nk=1|X)がわかる、って流れの方が自然だと思うんだが。

2011-10-25 19:30:45 via Janetter2

なあんて twitter でつぶやいてみたりしたけれど、言うだけなら誰でもできるので、実際に該当箇所を「自然だと思う流れ」で試しに書き換えてみちゃった。
ターゲットは PRML 下巻 p334 の式 (13.12) から (13.17) の間。ここは式 (13.12)→式 (13.17)→式 (13.15)&(13.16)→式 (13.13)&(13.14) の順序のほうがわかりやすいと思いこんでいるので、それにあわせて文章を書き換える、という方針。

HMM そのものではなく EMアルゴリズムの適用部分がターゲット、ということでいうと本来なら PRML 9章こそが書き換えてやりたい本丸なんだけど、こちらはコンパクトに一部分のみ書き換えてみるということが出来そうにないので、断念。
また $\gamma(z_{nk}), \xi(z_{n-1,j}z_{nk})$ はそれぞれ $\gamma_{nk}, \xi_{jk}^{(n)}$ などのように表記したかったのだが、該当箇所と差し替えて読んだときに前後と矛盾しないために記号の置き換えは控えた(ちなみに PRML 9章は前者の表記、PRML 10章は後者っぽい表記)。

この期待値は以下の関数 $Q(\bf{\theta},\bf{\theta}^{\text{old}})$ で定義される。

$Q(\bf{\theta},\bf{\theta}^{\text{old}})=\sum_{\bf{z}}p(\bf{Z}|\bf{X},\bf{\theta}^{\text{old}})\ln p(\bf{X},\bf{Z}|\bf{\theta}^{\text{old}})=\mathbb{E}[\ln p(\bf{X},\bf{Z}|\bf{\theta}^{\text{old}})]$ 　 (13.12 改)

この式に (13.10), (13.7) および (13.8) を代入することで次式を得る。

$Q(\bf{\theta},\bf{\theta}^{\text{old}})=\sum_{k=1}^K \mathbb{E}[z_{1k}]\ln \pi_k+\sum_{n=2}^N\sum_{j=1}^K\sum_{k=1}^K \mathbb{E}[z_{n-1,j}z_{nk}]\ln A_{jk}+\sum_{n=1}^N\sum_{k=1}^K \mathbb{E}[z_{nk}]\ln p(\bf{x}_n|\bf{\phi}_k)$ 　 (13.17 改)

本式から、Eステップでは事後分布の統計量 $\mathbb{E}[z_{nk}]$ および $\mathbb{E}[z_{n-1,j}z_{nk}]$ を求めればよいことがわかる。そこでこれらをそれぞれ $\gamma(z_{nk})$ および $\xi(z_{n-1,j}z_{nk})$ と表し、z_n=(z_nk) が 1-of-K 表現であることに注意すると、

$\gamma(z_{nk})=\mathbb{E}[z_{nk}]=\sum_{\bf{z}_n}p(\bf{z}|\bf{X},\bf{\theta}^{\text{old}})z_{nk}=p(z_{nk}=1|\bf{X},\bf{\theta}^{\text{old}})$ 　 (13.15 & 13.13 改)
$\xi(z_{n-1,j}z_{nk})=\mathbb{E}[z_{n-1,j}z_{nk}]=\sum_{\bf{z}_{n-1},\bf{z}_n}p(\bf{z}_{n-1},\bf{z}|\bf{X},\bf{\theta}^{\text{old}})z_{n-1,j}z_{nk}=p(z_{n-1,j}=1,z_{nk}=1|\bf{X},\bf{\theta}^{\text{old}})$ 　 (13.16 & 13.14 改)

を得る。
すなわち、 $\gamma(z_{nk})$ は周辺事後分布 $p(\bf{z}|\bf{X},\bf{\theta}^{\text{old}})$ を多項分布で表した場合の k 番目のパラメータであり、したがって各 n に対して $(\gamma(z_{nk}))$ は和が1となるK個の非負の数の集合を用いて記憶できる。同じく $\xi(z_{n-1,j}z_{nk})$ は同時事後分布 $p(\bf{z}_{n-1},\bf{z}_n|\bf{X},\bf{\theta}^{\text{old}})$ を多項分布で表した場合のパラメータの (j,k) 成分であり、やはり各 n に対して $(\xi(z_{n-1,j}z_{nk}))$ は和が1となる非負の数を成分とするK×K行列を用いて記憶することができる。

これらを効率的に求める方法については、すぐ後の 13.2.2 章から 13.2.4 章にかけて議論することにしよう。

EMA の E ステップでは、「Q(θ,θ^old) を整理したときに出てくる事後分布の統計量」を求めているんだ、ということを一言も言わずに、先回りして $\gamma(z_n)=p(z_n|X,\theta^{old})$ なんてやってしまうと、いつまでたっても何をしているのか理解できないと思うんだけどなあ。負担率って言いたいだけなんちゃう？　とか小一時間(ry