EM算法之不同的推导方法和自己的理解

---

一、前言

EM算法主要针对概率生成模型解决具有隐变量的混合模型的参数估计问题。
对于简单的模型，根据极大似然估计的方法可以直接得到解析解；可以在具有隐变量的复杂模型中，用MLE很难直接得到解析解，此时EM算法就发挥作用了。
E步解决隐变量的问题，M步求解模型的参数值，也就是极大似然的方法求取模型的参数值。

---

二、概览

假设一组数据，\(X=\{x^i,x^2 \cdots ,x^n\}\), 包含 \(n\) 个独立的样本，这组样本由一组混合模型生成而来，我们希望 \(\theta\) 满足：
\[\arg\max_{\theta} logP(X|\theta)\]

可是X是由一组混合模型而来，与隐变量 \(Z\) 有关，\(Z\) 表示样本归属于哪一个模型。
直接使用极大似然估计的方法求取上式很难由解析解，通过EM算法，转而求解：
\[\theta^{(t+1)} = \arg\max_{\theta} \int_Z \; P(Z|X,\theta^{(t)})\;logP(X,Z|\theta)\]

通过不断的迭代求解，求得的\(\theta\) 可以使得 \(logP(X|\theta)\) 不断增大，达到我们的目的。

---

三、收敛性

通过上述方式得到的 \(\theta\) 真的可以达到我们的目的吗？即使得 \(logP(X|\theta)\) 极大。
\[
\begin{aligned}
logP(X|\theta) &=log \frac {P(X,Z|\theta)}{P(Z|X,\theta)}\\
&=log {P(X,Z|\theta)} - log{P(Z|X,\theta)}
\end{aligned}
\]

左右两边同时对 \(P(Z|X,\theta^{(t)})\) 求取积分：
\[
\begin{aligned}
左边&=\int_{Z}P(Z|X,\theta^{(t)}) log {P(X|\theta)} dZ\\
&=log {P(X|\theta)} \int_{Z}P(Z|X,\theta^{(t)})dZ\\
&=log {P(X|\theta)}
\end{aligned}
\]

\[
\begin{aligned}
右边&=\int_{Z}P(Z|X,\theta^{(t)}) \left[log {P(X,Z|\theta)} - log{P(Z|X,\theta)}\right] dZ\\
&=\int_{Z}P(Z|X,\theta^{(t)}) log {P(X,Z|\theta)} dZ - \int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta)} dZ\\
&Q(\theta,\theta^{(t)}) = \int_{Z}P(Z|X,\theta^{(t)}) log {P(X,Z|\theta)} dZ\\
&H(\theta,\theta^{(t)}) = \int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta)} dZ\\
&log {P(X|\theta^{(t+1)})} -log {P(X|\theta^{(t)})} = Q(\theta^{(t+1)},\theta^{(t)}) -Q(\theta^{(t)},\theta^{(t)}) + H(\theta^{(t)},\theta^{(t)}) -H(\theta^{(t+1)},\theta^{(t)})
\end{aligned}
\]

根据\(\theta^{(t+1)}\) 的求取公式，直接得出：
\[Q(\theta^{(t+1)},\theta^{(t)})\geq Q(\theta,\theta^{(t)})\]

此时令\(\theta = \theta^{(t)}\),则：
\[Q(\theta^{(t+1)},\theta^{(t)})\geq Q(\theta^{(t)},\theta^{(t)})\]

\[
\begin{aligned}
H(\theta^{(t)},\theta^{(t)}) -H(\theta^{(t+1)},\theta^{(t)}&=\int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta^{(t)})}- \int_{Z}P(Z|X,\theta^{(t)}) log{P(Z|X,\theta^{(t+1)})}dZ\\
&=\int_{Z}P(Z|X,\theta^{(t)}) [log{P(Z|X,\theta^{(t)})}-log{P(Z|X,\theta^{(t+1)})}]dZ\\
&=\int_{Z}P(Z|X,\theta^{(t)})log \frac{P(Z|X,\theta^{(t)})}{P(Z|X,\theta^{(t+1)})}dZ\\
&=KL(P(Z|X,\theta^{(t)}) \;||\; P(Z|X,\theta^{(t+1)})) \geq 0
\end{aligned}
\]

所以 \[log {P(X|\theta^{(t+1)})} -log {P(X|\theta^{(t)})} \geq 0\]

\[log {P(X|\theta^{(t+1)})} \geq log {P(X|\theta^{(t)})} \]

---

四、完整的推导

第一种推导方法
\[
\begin{aligned}
log {P(X|\theta)} &= log \int_{Z}P(X,Z|\theta)dZ=log \int_{Z} \frac{P(X,Z|\theta)}{q(Z)}q(Z)dZ\\
&=log E_{q(Z)}[\frac{P(X,Z|\theta)}{q(Z)}] \geq E_{q(Z)}[log \frac{P(X,Z|\theta)}{q(Z)}]
\end{aligned}
\]

取等号时是\(\frac{P(X,Z|\theta)}{q(Z)}=C\)
我们把\(E_{q(Z)}[log \frac{P(X,Z|\theta)}{q(Z)}]\)叫做 \(ELBO\)
换句话说就是 \(ELBO\) 是 \(log {P(X|\theta)}\) 的下界,不停的增大ELBO，就可以不断的增大 \(log {P(X|\theta)}\)

---

第二种推导方法
\[
\begin{aligned}
log {P(X|\theta)} &=log\frac{P(X,Z|\theta)}{P(Z|X,\theta)}\\
&=log P(X,Z|\theta) - log P(Z|X,\theta)\\
&=log \frac {P(X,Z|\theta)}{q(Z)} - \frac {log P(Z|X,\theta)}{q(Z)}
\end{aligned}
\]

等式两边同时关于分布 \(q(Z)\) 求期望（两边同时对 \(q(Z)\) 求积分）
左边还是等于左边（具体步骤参考上面）
\[
\begin{aligned}
右边 &= \int_{Z}q(Z)log \frac {P(X,Z|\theta)}{q(Z)}dZ-\int_{Z}q(Z)log \frac {log P(Z|X,\theta)}{q(Z)}dZ\\
& = ELBO+KL(q(Z)\;||\;P(Z|X,\theta))
\end{aligned}
\]

当 \(q(Z)与P(Z|X,\theta)\) 同分布时取等号。

因此：
E步：找到一个q = p
M步：(多种不同的形式)
\[
\begin{aligned}
&\arg\max_{\theta} \int_{Z}q(Z)log \frac {P(X,Z|\theta)}{q(Z)}dZ \\ &\arg\max_{\theta}\int_{Z}q(Z)log {P(X,Z|\theta)}dZ\\ &\arg\max_{\theta}\int_{Z}P(Z|X,\theta^{(t)})log {P(X,Z|\theta)}dZ\\
&\arg\max_{\theta}\sum_{Z}P(Z|X,\theta^{(t)})log {P(X,Z|\theta)}
\end{aligned}
\]

---

五、广义EM

\[logP(X|\theta) = ELBO+KL(q(Z)||P(Z|X,\theta))\]

令
\[L(q,\theta)=ELBO = E_{q(Z)}[ log\frac{P(X,Z|\theta)} {q(Z)}] \]

E-step:固定 \(\theta\),找出q,此时 \(logP(X|\theta)\)是定值：
\[
\begin{aligned}
q^{(t+1)} &= \arg\min_{q}KL(q||P) = \arg\max_{q}ELBO\\& = \arg\max_{q} L(q,\theta^{(t)})\\&=\arg\max_{\theta} E_{q(Z)}[ log\frac{P(X,Z|\theta^{(t)})} {q(Z)}]
\end{aligned}
\]

M-step:固定 \(q\),找出 \(\theta\)：
\[
\begin{aligned}
\theta^{(t+1)} &= \arg\max_{\theta}ELBO =\arg\max_{\theta} L(q^{(t+1)},\theta)\\&= \arg\max_{\theta} E_{q^{(t+1)}(Z)}[ log\frac{P(X,Z|\theta)} {q^{(t+1)}(Z)}]\\&=
\arg\max_{\theta} E_{q^{(t+1)}(Z)}[ log{P(X,Z|\theta)} ]
\end{aligned}
\]

---