EM算法

机器学习

---

我们经常会从样本观察数据中，找出样本的模型参数。 最常用的方法就是极大化模型分布的对数似然函数。但是在一些情况下，观察数据中有未观察到的隐含数据，因而无法直接用极大化对数似然函数得到模型分布的参数。EM算法也称期望最大化算法(Expectation-Maximum, EM)。

---

1. 何时使用EM

• 观测数据$X=\{x_1,x_2,\cdots,x_n\}$
• 观测数据$Z=\{z_1,z_2,\cdots,z_k\}$
• 完整数据$Y=\{X,Z\}$
• 模型参数$\theta$有待估计

(1) 观测数据条件下的似然函数难以求得 $L(\theta|X)=P(X|\theta)$
(2) 完全数据条件下的似然函数容易求得 $L(\theta|Y)=P(Y|\theta)$
(3) 观测数据条件下的隐变量容易求得 $P(Z|X,\theta)$

---

2. EM算法

• 输入：观测数据$X$，隐变量数据$Z$，联合分布$P(X,Z|\theta)$，条件分布$P(Z|X,\theta)$.
• 输出：模型参数$\theta$.

(1) 初始化$\theta^{(0)}$
(2) E步：记$\theta^{(i)}$为第$i$次迭代参数$\theta$的估计值，在第$i+1$次迭代E步，计算

$$\begin{aligned} Q(\theta,\theta^{(i)})&=E_Z(\log P(X,Z|\theta)|X,\theta^{(i)})\\ &=\sum_{z}^{}{}P(Z|X,\theta^{(i)})\log P(X,Z|\theta) \end{aligned}$$

(3) M步：求使$Q(\theta,\theta^{(i)})$极大化的$\theta$，确定第$i+1$次迭代的参数的估计值$\theta^{(i+1)}$

$$\theta^{(i+1)}=\arg\max_\theta(Q(\theta,\theta^{(i)}))$$

(4) 重复第(2)(3)步，直到收敛。

---

3. EM算法的推导

目标是极大化观测数据$X$关于参数$\theta$的对数似然，即最大化

$$\begin{aligned} L(\theta|X)&=\log{P(X|\theta)}=\log{\sum_z{P(X,Z|\theta)}}\\ &=\log\left({\sum_z{P(X|Z,\theta)P(Z|\theta)}}\right) \end{aligned}$$

EM算法通过迭代逐步近似极大化$L(\theta)$。假设我们在第$i$次迭代后$\theta$的估计值是$\theta^{(i)}$，我们希望下一次的估计值能够使得$L(\theta)$增加，即$L(\theta)>L(\theta^{(i)})$。考虑两者作差：

$$\begin{aligned} L(\theta)-L(\theta^{(i)})&=\log\left(\sum_{Z}^{}{P(X|Z,\theta)P(Z|\theta)}\right)-\log P(X|\theta^{(i)})\\ &=\log\left[ \sum_{z}^{}{}P(Z|X,\theta^{(i)})\frac{P(X|Z,\theta)P(Z|\theta)}{P(Z|X,\theta^{(i)})} \right]-\log{P(X|\theta^{(i)})}\\ &\geq\sum_{z}^{}{}P(Z|X,\theta^{(i)})\log\frac{P(X|Z,\theta)P(Z|\theta)}{P(Z|X,\theta^{(i)})} -\log P(X|\theta^{(i)})\\ &=\sum_{z}^{}{}P(Z|X,\theta^{(i)})\log\frac{P(X|Z,\theta)P(Z|\theta)}{P(Z|X,\theta^{(i)})} -\sum_{z}^{}{}P(Z|X,\theta^{(i)})\log P(X|\theta^{(i)})\\ &=\sum_{z}^{}{}P(Z|X,\theta^{(i)})\log\frac{P(X|Z,\theta)P(Z|\theta)}{P(Z|X,\theta^{(i)})P(X|\theta^{(i)})} \end{aligned}$$

中间一步用到了Jenson不等式：对于一个凸函数，有

$$\sum_{i}^{}{\lambda_if(x_i)}\geq f(\sum_{i}^{}{\lambda_ix_i})\\ 其中\lambda_i\geq0,\sum_{i}^{}{\lambda_i=1}$$

换一种写法，就是

$$E(f(x)) \geq f(E(x))$$

由于$L(\theta)-L(\theta^{(i)})$是凹函数，所以$f(E(x))\geq E(f(x))$

令

$$B(\theta,\theta^{(i)})=L(\theta^{(i)})+\sum_{z}^{}{}P(Z|X,\theta^{(i)})\log\frac{P(X|Z,\theta)P(Z|\theta)}{P(Z|X,\theta^{(i)})P(X|\theta^{(i)})}$$

所以

$$L(\theta)\geq B(\theta,\theta^{(i)})$$

$B(\theta,\theta^{(i)})$是 $L(\theta)$的一个下界。因此能使$B(\theta,\theta^{(i)})$增大的$\theta$也可以使$L(\theta)$增大。选择$\theta^{(i+1)}$使$B(\theta,\theta^{(i)})$达到极大：

$$\begin{aligned} \theta^{(i+1)}&=\arg\max_\theta{B(\theta,\theta^{(i)})}\\\ &=\arg\max_\theta\left[L(\theta^{(i)})+\sum_{z}^{}{}P(Z|X,\theta^{(i)})\log\frac{P(X|Z,\theta)P(Z|\theta)}{P(Z|X,\theta^{(i)})P(X|\theta^{(i)})} \right]\\\ &=\arg\max_\theta\left[ \sum_{z}^{}{}P(Z|X,\theta^{(i)})\log(P(X|Z,\theta)P(Z|\theta)) \right]\\ &=\arg\max_\theta\left[ \sum_{z}^{}{}P(Z|X,\theta^{(i)})\log P(X,Z|\theta) \right]\\ &=\arg\max_\theta\left[E_Z(\log P(X,Z|\theta)|X,\theta^{(i)})\right]\\ &=\arg\max_\theta(Q(\theta,\theta^{(i)})) \end{aligned}$$