1 EM 算法概述
1.1 简介
EM ( expectation-maxinization）算法又称期望最大化算法，是 Dempster，Laind，Rubin 于1977 年提出的求参数极大似然估计的一种迭代优化策略，它可以从非完整数据集中对参数进行极大似然估计，是一种非常简单实用的学习算法。这种方法可以广泛地应用于处理缺损数据，截尾数据，带有噪声等所谓的不完全数据，EM 算法是在缺失数据等不完全数据下进行参数的极大似然估计或者极大后验估计一种行之有效的方法。
EM 算法作为一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），所有算法被称为 EM 算法。其基本思想是首先根据已经给出的观测数据估计出模型参数的值；然后再依据上一步估计出的参数值估计缺失数据的值，再根据估计出的缺失数据加上之前已经观测到的数据重新再对参数值进行估计，然后反复迭代，直至最后收敛，迭代结束。
1.2 作用
极大似然估计（maximum likelihood estimation）和 Bayes 统计作为当前统计领域主要的两大类计算方法同时也是研究最广泛的问题，从根本上来讲它们在计算过程中是有很大的相似成分的，因为极大似然函数估计（MLE）在计算方法上和 Bayes 估计的后验众数的计算类似，而且极大似然估计理论比较简单，Bayes 统计的计算方法一直以来都是科学研究的重点。Bayes 统计在计算方法上大体分为两大类，一类是拥有显式的后验分布，可以直接应用显式的后验分布进行估计，从而得到后验均值，这种方法一般应用于简单而且显然的似然函数；另一种方法是数据添加算法，有些时候可能数据存在缺失情况或者似然函数不是显示的难以直接计算，数据添加算法在这种情况下有很好地应用，它不是直接对复杂的后验分布进行计算，而是在已经得到的观测数据的基础上加上一些“潜在数据”，从而使得计算变得简单，完成极大化的工作。本文介绍的是一种常用的数据添加算法一一EM(expectation-maximization)算法。
EM 算法作为一种数据添加算法，在近几十年得到迅速的发展，主要源于当前科学研究以及各方面实际应用中数据量越来越大的情况下，经常存在数据缺失或者不可用的的问题，这时候直接处理数据比较困难，而数据添加办法有很多种，常用的有神经网络拟合、添补法、卡尔曼滤波法等等，但是 EM 算法之所以能迅速普及主要源于它算法简单，稳定上升的步骤能非常可靠地找到“最优的收敛值”。随着理论的发展，EM 算法已经不单单用在处理缺失数据的问题，运用这种思想，它所能处理的问题更加广泛。有时候缺失数据并非是真的缺少了，而是为了简化问题而采取的策略，这时EM算法被称为数据添加技术，所添加的数据通常被称为“潜在数据”，复杂的问题通过引入恰当的潜在数据，能够有效地解决我们的问题。
上面说到的“潜在数据”可以解释为数据本身并不存在缺失变量，但观察数据比较难以处理，如果添加上额外的变量，处理起来会变得比较简单。假设 $X$ 是已知的观测数据，想象由随机变量 $X$ 生成的观察数据连同来自随机变量 $Y$ 的缺失或未观测数据，得到 $Z=(X,Y)$ 为完全数据。给定观察数据 $X$，我们希望最大化似然函数 $L(\theta|x)$。由于数据缺失或者其他原因导致采用该似然函数会难以处理，而采用 $Z|\theta$ 和 $Y|(x,\theta)$ 的密度则比较容易处理。EM 算法通过采用这些较容易的密度 $p(\theta|z)$，避开了直接考虑 $p(\theta|x)$。
而在 Bayes 的应用中，兴趣通常集中在对后验分布 $p(\theta|x)$ 的众数的估计上。另外，优化有时可以考虑除感兴趣的参数 $\theta$ 外的未观测的随机变量 $\psi$ 而得到简化，这里的 $\psi$ 既可以是缺失或未观测的数据，也可以是缺失的参数，因为从 Bayes 的角度来看，它们都是随机变量。
2 缺失数据、边际化和符号
在 1.2 小节中提到过随机变量 $X$ 生成的观察数据连同来自随机变量 $Y$ 的缺失或未观测数据，$Z=(X,Y)$ 产生完全数据。无论将 $Y$ 视为缺失数据还是潜在数据，它都可以看作是通过应用某种多到少的映射 $X=M(Z)$ ，从而将其从完整数据 $Z$ 中删除掉了。设 $p(x|\theta)$ 和 $p(z|\theta)$ 分别表示观测数据和完全数据的密度， $p(y|x,\theta)$ 是在给定的已观测到的数据的条件下缺失数据的密度。可以认为潜在数据的假设等同于一个边际化模型，在该模型中，我们观测到 $X$ 有密度 $p(x|\theta) = \int_{\{ z:M(z)=x\}}p(z|\theta)dz$。并且，给定数据下缺失或潜在数据的条件密度为：
$$
p(y|x,\theta) = \frac{p(z|\theta)}{p(x|\theta)} = \frac{p(x,y|\theta)}{p(x|\theta)}
$$
就如同之前讨论的，关注参数 $\theta$ 在 Bayes 的后验密度函数的应用，有两种方式来考虑用后验来表示一个更加宽泛问题的边际化。第一，把似然函数 $L(\theta|X)$ 看作完全数据似然函数 $L(\theta|Z) = L(\theta|X,Y)$ 的边际化是合理的，这种情形缺失数据是 $y$ 。第二，接着考虑有缺失参数 $\psi$ ，即使 $\psi$ 本身无意义，但引入 $\psi$ 能简化 Bayes 的计算。在 Bayes 的框架下，这两种情形并没有实际上的区别。因为 $Y$ 和 $\psi$ 都被视为缺失的随机变量，用缺失变量的符号来表示未观测的数据还是参数无关紧要。
3 EM 算法原理和步骤
EM 算法是当存在数据缺失问题时，极大似然估计（MLE）的一种常用迭代算法，，因为其操作简便，收敛稳定，具有很强的适用性。它主要应用于以下常见的两种情况下的参数估计：
- 第一种，观测到的数据不完善，这是因为数据丢失或者观测条件受限；
- 第二种，似然函数不是显然的，或者函数的形式非常复杂导致难以用极大似然传统方法进行估计。
已知 $X$ 是观测数据，$Y$ 是潜在数据，EM 算法迭代是为了寻求关于 $\theta$ 最大化似然函数 $L(\theta|X)$ 。设 $\theta^{(k)}$ 表示在第 $k$ 次迭代时估计得到的最大值点，$k=1,2,\cdots$ 。定义 $Q(\theta|\theta^{(k)})$ 为观测数据 $X=\{x_1,x_2,\cdots,x_n\}$ 条件下完全数据的联合对数似然函数的期望，即，
$$
\begin{aligned}
Q(\theta|\theta^{(k)}) &= E\{\log L(\theta|Z)|x,\theta^{(k)}\}\\
&= E\{\log p(z|\theta)|x,\theta^{(k)}\}\\
&= \int\big[\log p(z|\theta) \big]\cdot p(y|x,\theta^{(k)})dy
\end{aligned}
$$
由上式可知一旦我们给定样本点 $X = \{x_1,x_2,\cdots, x_n\}$ ，则 $Y$ 就是 $Z$ 的唯一随机部分，通过对 $Y$ 求条件期望，就又把 $Y$ 给积掉了，使得 $Q(\theta|\theta^{(k)})$ 完全是一个 $\theta$ 的函数，这样就可以求使得 $Q(\theta|\theta^{(k)})$ 最大的 $\theta$ ，并记为 $\theta^{(k+1)}$ ，供下一次迭代使用。
EM 算法从 $\theta^{(0)}$ 开始，然后在两步之间交替：E 表示期望， M 表示最大化。该算法步骤可概括如下：
-
E 步： 在给定的观测数据 $X$ 和已经知道参数条件下，求 “缺失数据 $Y$” 的条件期望，即计算上面提到的对数似然函数的条件期望 $Q(\theta|\theta^{(k)})$ 。
-
M 步： 就像不存在缺失数据 $Y$ 一样（填充缺失数据后），针对完全数据下的对数似然函数的期望进行极大化估计，即求关于 $\theta$ 的似然函数 $Q(\theta|\theta^{(k)})$ 的最大化。设 $\theta^{(k+1)}$ 等于 $Q$ 的最大值点，更新 $\theta^{(k)}$。
$$
Q(\theta^{(k+1)}|\theta^{(k)}, X) = \max_\theta Q(\theta|\theta^{(k)},X)
$$ -
返回 E 步，直到满足某停止规则。一般
$$
||\theta^{(i+1)} - \theta^{(i)}|| \le \epsilon_1 \ \text或\ ||Q(\theta^{(i+1)}, \theta^{(i)}) - Q(\theta^{(i)}, \theta^{(i)})|| \le \epsilon_2
$$
则停止迭代。