深入理解机器学习——EM算法/最大期望算法（Expectation-Maximization Algorithm, EM）

分类目录：《深入理解机器学习》总目录

---

在前面的讨论中，我们一直假设训练样本所有属性变量的值都已被观测到，即训练样本是“完整”的。但在现实应用中往往会遇到“不完整”的训练样本。在这种存在“未观测”变量的情形下，是否仍能对模型参数进行估计呢？未观测变量的学名是“隐变量”（Latent Variable）。令$X$表示已观测变量集，$Z$表示隐变量集，$\Theta$表示模型参数。若欲对$\Theta$做极大似然估计，则应最大化对数似然：
$$LL(\Theta |X,Z)=\ln P(X,Z|\Theta )$$

然而由于$Z$是隐变量，上式无法直接求解。此时我们可通过对$Z$计算期望，来最大化已观测数据的对数“边际似然：
$$LL(\Theta |X)=\ln P(X|\Theta )=\ln \sum _{Z}P(X|\Theta )$$

EM（Expectation-Maximization）算法是常用的估计参数隐变量的利器，它是一种送代式的方法，其基本想法是：若参数$\Theta$已知，则可根据训练数据推断出最优隐变量$Z$的值（E步）；反之，若$Z$的值已知，则可方便地对参数做极大似然估计（M步）。

于是，以初始值${\Theta }^0$为起点，对上式，可选代执行以下步骤直至收敛：

• 基于${\Theta }^t$推断隐变量$Z$的期望，记为$Z^t$
• 基于已观测变量$X$和$Z^t$对参数$\Theta$做极大似然估计，记为${\Theta }^{t+1}$

这就是EM算法的原型。

进一步，若我们不是取$Z$的期望，而是基于${\Theta }^t$计算隐变量$Z$的概率分布$P(Z|X,{\Theta }^t)$，则EM算法的两个步骤是：

• E步（Expectation）：以当前参数${\Theta }^t$推断隐变量分布$P(Z|X,{\Theta }^t)$，并计算对数似然$LL(\Theta |X,Z)$关于$Z$的期望：$$Q(\Theta |{\Theta }^t)={\mathbb{E}}_{Z|X,{\Theta }^t}LL(\Theta |X,Z)$$
• M步卡（Maximization）：寻找参数最大化期望似然，即：$${\Theta }^{t+1}=\arg \underset{\Theta }{\max }Q(\Theta |{\Theta }^t)$$

简要来说，EM算法使用两个步骤交替计算：第一步是期望E步，利用当前估计的参数值来计算对数似然的期望值；第二步是最大化M步，寻找能使E步产生的似然期望最大化的参数值。然后，新得到的参数值重新被用于E步。直至收敛到局部最优解。事实上，隐变量估计问题也可通过梯度下降等优化算法求解，但由于求和的项数将随着隐变量的数目以指数级上升，会给梯度计算带来麻烦；而EM算法则可看作一种非梯度优化方法

参考文献：
[1] 周志华. 机器学习[M]. 清华大学出版社, 2016.