EM算法_胡浩基
机器学习-白板推导系列(十)-EM算法（Expectation Maximization）学习笔记
EM公式：\(\theta^{(t+1)}=arg \max\limits_\theta\int_z\log P(x,z|\theta)\cdot P(z|x,\theta^{(t)})dz\)
EM算法的来源
\[\begin{gathered}E-step:&P(z|x,\theta^{(t)})\to E_{z|x,\theta^{(t)}}\left[\log P(x,z|\theta)\right]\\M-step:&\theta^{(t+1)}=arg\max_\theta E_{z|x,\theta^{(t)}}\left[\log P(x,z|\theta)\right]\end{gathered}
\]
\[\begin{aligned}\log P(x|\theta)&=\log P(x,z|\theta)-\log P(z|x,\theta)\\&=\log P(x,z|\theta)-\log q(z)-(\log P(z|x,\theta)-\log q(z))\\&=\log\frac{P(x,z|\theta)}{q(z)}-\log\frac{P(z|x,\theta)}{q(z)}\end{aligned}
\]
两边同时求期望：
\[\begin{aligned}
\text{左边}&=\int_zq(z)\log P(x|\theta)dz\\&=\log P(x|\theta)\int_zq(z)dz\\&=\log P(x|\theta)\\
\text{右边}&=\underbrace{\int_zq(z)\log\frac{P(x,z|\theta)}{q(z)}dz}_{ELBO=evidence\textit{ lower bound}}-\underbrace{\int_zq(z)\log\frac{P(z|x,\theta)}{q(z)}dz}_{KL(q(z)\|P(z|x,\theta))}\\
&=ELBO+KL(q(z)\|P(z|x,\theta))
\end{aligned}
\]
因为\(KL(q(z)\|P(z|x,\theta)) \ge 0\)，当\(q(z)=p(z|x,\theta)\)时成立，但因\(\theta\)值未知，\(q(z)\)取最接近\(p(z|x,\theta)\)的值，即为：\(q(z)=p(z|x,\theta^{(t)})\)，下面即是在KL散度最大，即\(q(z)\)确定时，ELBO的最大值。
\[\begin{aligned}
\int_zq(z)\log\frac{p(x,z|\theta)}{q(z)}dz&=\int_zp(z|x,\theta^{(t)})\log\frac{p(x,z|\theta)}{p(z|x,\theta^{(t)})}dz
\end{aligned}
\]
因为\(p(z|x,\theta^{(t)})\)与\(\theta\)无关，则可推出：
\[\hat{\theta}=\theta^{(t+1)}=arg \max_\theta \int_zp(z|x,\theta^{(t)})\log p(x,z|\theta)dz
\]
EM算法收敛性证明
\[\log P(x|\theta)=\log\frac{P(x,z|\theta)}{P(z|x,\theta)}=\log P(x,z|\theta)-\log P(z|x,\theta)
\]
\[\begin{aligned}\text{左边}&=\int_zP(z|x,\theta^{(t)})\cdot\log P(x|\theta)dz\\&=\log P(x|\theta)\int_zP(z|x,\theta^{(t)})dz\\&=\log P(x|\theta)\\
\text{右边}&=\underbrace{\int_zP(z|x,\theta^{(t)})\cdot\log P(x,z|\theta)dz}_{Q(\theta,\theta^{(t)})}-\underbrace{\int_zP(z|x,\theta^{(t)})\cdot\log P(z|x,\theta)dz}_{H(\theta,\theta^{(t)})}\end{aligned}
\]
根据\(\theta^{(t+1)}=arg \max\limits_\theta \int_zp(z|x,\theta^{(t)})\log p(x,z|\theta)dz\),可得\(Q(\theta^{(t+1)},\theta^{(t)}) \ge Q(\theta,\theta^{(t)})\)，而\(Q(\theta^{(t)},\theta^{(t)})\)属于\(Q(\theta,\theta^{(t)})\)，则可推出：\(Q(\theta^{(t+1)},\theta^{(t)}) \ge Q(\theta^{(t)},\theta^{(t)})\)
\[\begin{aligned}
H(\theta^{(t+1)},\theta^{(t)})-H(\theta^{(t)},\theta^{(t)})&=\int_zP(z|x,\theta^{(t)})\cdot\log P(z|x,\theta^{(t+1)})dz-\int_zP(z|x,\theta^{(t)})\cdot\log P(z|x,\theta^{(t)})dz\\&=\int_zP(z|x,\theta^{(t)})\cdot(\log P(z|x,\theta^{(t+1)})-\log P(z|x,\theta^{(t)}))dz\\&=\int_zP(z|x,\theta^{(t)})\cdot\log\frac{P(z|x,\theta^{(t+1)})}{P(z|x,\theta^{(t)})}dz\\
&=E_{z|x,\theta^{(t)}}(\log\frac{P(z|x,\theta^{(t+1)})}{P(z|x,\theta^{(t)})}) \le log E_{z|x,\theta^{(t)}}(\frac{P(z|x,\theta^{(t+1)})}{P(z|x,\theta^{(t)})})
\end{aligned}
\]
综上，可以证得：
\[log p(x,z|\theta^{(t+1)}) \ge log p(x,z|\theta^{(t)})
\]
高斯混合模型（GMM）与其EM推导
高斯混合模型：\(P(x)=\sum_{k=1}^K\alpha_kN(\mu_k,\Sigma_k),\mathrm{~}\sum_{k=1}^K\alpha_k=1\)
\[\begin{aligned}
Q(\theta,\theta^{(t)})&=\int_Z\log P(X,Z|\theta)\cdot P(Z|X,\theta^{(t)})\\&=\sum_Z\log\prod_{i=1}^NP(x_i,z_i|\theta)\cdot\prod_{i=1}^NP(z_i|x_i,\theta^{(t)})\\&=\sum_Z\sum_{i=1}^N\log P(x_i,z_i|\theta)\cdot\prod_{i=1}^NP(z_i|x_i,\theta^{(t)})\\&=\sum_Z[\log P(x_1,z_1|\theta)+\log P(x_2,z_2|\theta)+\cdots+\log P(x_N,z_N|\theta)]\cdot\prod_{i=1}^NP(z_i|x_i,\theta^{(t)})
\end{aligned}
\]
取其中一项出来进行计算：
\[\begin{aligned}
&\sum_{z_1,z_2,\cdots,z_N}\log P(x_1,z_1|\theta)\cdot\prod_{i=1}^NP(z_i|x_i,\theta^{(t)})\\=&\sum_{z_1,z_2,\cdots,z_N}\log P(x_1,z_1|\theta)\cdot P(z_1|x_1,\theta^{(t)})\cdot\prod_{i=2}^NP(z_i|x_i,\theta^{(t)})\\=&\sum_{z_1}\log P(x_1,z_1|\theta)\cdot P(z_1|x_1,\theta^{(t)})\sum_{z_2,\cdots,z_N}\prod_{i=2}^NP(z_i|x_i,\theta^{(t)})\\=&\sum_{z_1}\log P(x_1,z_1|\theta)\cdot P(z_1|x_1,\theta^{(t)})\sum_{z_2}P(z_2|x_2,\theta^{(t)})\sum_{z_3}P(z_3|x_3,\theta^{(t)})\cdots\sum_{z_N}P(z_N|x_N,\theta^{(t)})\\
=&\sum_{z_1}\log P(x_1,z_1|\theta)\cdot P(z_1|x_1,\theta^{(t)})
\end{aligned}
\]
整理得到：\(Q(\theta,\theta^{(t)})=\sum\limits_{i=1}^N\sum\limits_{z_i}logp(x_i,z_i|\theta)\cdot p(z_i|x_i,\theta^{(t)})\)
在GMM中：
\[\begin{aligned}
P(x)&=\sum_{i=1}^Kp_k\cdot N(x|\mu_k,\Sigma_k)
P(x,z)=P(z)\cdot \\
P(x|z)&=p_z\cdot N(x|\mu_z,\Sigma_z)\\
P(z|x)&=\frac{P(x,z)}{P(x)}=\frac{p_{_z}\cdot N(x|\mu_{_z},\Sigma_{_z})}{\sum_{i=1}^Kp_k\cdot N(x|\mu_k,\Sigma_k)}
\end{aligned}
\]
\[\begin{aligned}
Q(\theta,\theta^{(t)})&=\sum_{z_i}\sum_{i=1}^N\log[p_{z_i}\cdot N(x_i|\mu_{z_i},\Sigma_{z_i})]\cdot P(z_i|x_i,\theta^{(t)})\\
&=\sum_{k=1}^K\sum_{i=1}^N\log[p_k\cdot N(x_i|\mu_k,\Sigma_k)]\cdot P(z_i=C_k|x_i,\theta^{(t)})
\end{aligned}
\]
可以根据这个式子求得\(\theta^{(t+1)}=arg\max\limits_\theta Q(\theta,\theta^{(t)})\)，以\(p\)作为例子
\[\begin{cases}\max_p\sum_{k=1}^K\sum_{i=1}^N\log p_k\cdot P(z_i=C_k|x_i,\theta^{(t)})\\s.t.\quad\sum_{k=1}^Kp_k=1&&\end{cases}
\]
由拉格朗日乘数法可以得到：
\[L(p,\lambda)=\sum_{k=1}^K\sum_{i=1}^N\log p_k\cdot P(z_i=C_k|x_i,\theta^{(t)})+\lambda(\sum_{k=1}^Kp_k-1)
\]
对 \(p_k\) 求导，并令其为 0：
\[\frac{\partial L}{\partial p_k} = \sum_{i=1}^N \frac{1}{p_k} P(z_i = C_k | x_i, \theta^{(t)}) + \lambda = 0
\]
因此：
\[\sum_{i=1}^N P(z_i = C_k | x_i, \theta^{(t)}) + p_k \lambda = 0\]
由于此式对所有 \(p_k\) 均满足，故：
\[\sum_{i=1}^N \sum_{k=1}^K P(z_i = C_k | x_i, \theta^{(t)}) + \sum_{k=1}^K p_k \lambda = 0
\]
从约束条件可知 \(\sum_{k=1}^K p_k = 1\)。又因为 \(\sum_{k=1}^K P(z_i = C_k | x_i, \theta^{(t)})\) 为概率求和，所以 \(\sum_{k=1}^K P(z_i = C_k | x_i, \theta^{(t)}) = 1\)因此原式可以化为：
\[N + \lambda = 0\]
所以 \(\lambda = -N\)。再带入 \(\sum_{i=1}^N P(z_i = C_k | x_i, \theta^{(t)}) + p_k \lambda = 0\) 可得：
\[p_k^{(t+1)} = \frac{1}{N} \sum_{i=1}^N P(z_i = C_k | x_i, \theta^{(t)})
\]
