最大期望算法

亚瑟·登普斯特、楠·莱尔德和唐纳德·鲁宾在1977年的一篇经典论文中解释了EM算法并给出了它的名字。^[1]他们指出，这种方法由早期作者“在特殊情况下提出了很多次”。最早的方法之一是由塞德里克·史密斯提出的用于估计等位基因频率的基因计数法。^[2]罗尔夫·桑德伯格在与佩尔·马丁-洛夫和安德斯·马丁·洛夫合作之后，^{[3][4][5][6][7][8][9]}在他的学位论文和其他几篇论文中发表了关于指数族的EM方法的非常详细的论述。^[10][11][12]登普斯特-莱尔德-鲁宾在1977年的论文中推广了这种方法，并对更广泛的一类问题进行了收敛性分析。除开早期的创新发现之外，登普斯特-莱尔德-鲁宾在《皇家统计学会杂志》上发表的具有创新性的论文在皇家统计学会会议上受到热烈讨论，桑德伯格称这篇论文“非常出色”。登普斯特-莱尔德-鲁宾论文将EM方法确立为统计分析的重要工具。

登普斯特-莱尔德-鲁宾算法的收敛性分析是有缺陷的，正确的收敛性分析由吴建福于1983年发表。^[13]吴的证明在指数簇之外建立了EM方法的收敛性，正如登普斯特-莱尔德-鲁宾所声称的那样。^[13]

EM算法用于在方程不能直接求解的情况下找到统计模型的(局部)最大似然参数。典型情况下，这些模型除了未知参数和已知可观测到的数据之外，还涉及潜变量。也就是说，要么数据中存在缺失值，要么可以通过假设存在更多未观察到的数据点来更简单地建立模型。例如，可以通过假设每个观察到的数据点具有相应的未观察到的数据点或潜在变量，指定每个数据点所属的混合成分，来更简单地描述混合模型。

寻找最大似然解通常需要对所有未知值、参数和潜变量函数取似然函数的导数，同时求解所得方程。在包含潜变量的统计模型中，这通常是不可能的。相反，结果通常是一组互锁方程，其中参数的解需要知道潜变量的值，反之亦然，如果将一组方程代入另一组方程则会产生不可解方程。

EM算法是从观察到有一种方法可以用数值方法解决这两组方程开始的。可以简单地为两组未知数中的一组选取任意值，用它们来估计另一组，再用这些新的值来找到第一组更好的估计，然后在两者之间不断交替迭代，直到结果值都收敛到不动点。这是否有效还不清楚，但可以证明，在这种情况下它是有效，并且可能性的导数在该点(任意接近)为零，这意味着该点要么是极大值，要么是鞍点。^[13] 一般来说，可能会出现多个极大值，但不能保证会找到全局最大值。某些似然也存在奇点，即无意义的最大值。 例如，这样的一个解：在混合模型中，EM可以找到的方法包括将其中一个分量的方差设置为零，并且将同一分量的平均参数设置为等于其中一个数据点。

给定生成观察数据集合  的统计模型，一组未观察到的潜在数据或缺失值  ，以及似然函数  中的未知参数向量  ，最大似然估计是通过最大化观测数据的边缘似然来确定的

然而，这个量通常是难以处理的(例如，如果  是一个事件序列，那么数值的数量随着序列长度呈指数增长，因此求和的精确计算将非常困难)。

EM算法通过迭代应用这两个步骤来寻找边缘似然的最大似然估计：

求期望步骤：定义   对数似然函数的期望值为  ，就目前的条件分布而言  考虑到  和参数的当前估计  (d ):

最大化步骤(M步)：查找最大化此数量的参数:

 

应用EM的典型模型是将  作为一个潜在变量，表示在一组组中的成员:

1. 观察到的数据点  可以是离散的(取有限或可数无限集合的值)或连续的(取不可数无限集合的值)。与每个数据点相关联的可以是观察矢量。
2. 缺失的值(又名潜变量)  是离散的，从固定数量的值中提取，每个观察单位有一个潜在变量。
3. 参数是连续的，并且有两种：与所有数据点相关联的参数，以及与潜在变量的特定值相关联的参数(即，与对应潜在变量具有该值的所有数据点相关联的参数)。

然而，也可以将EM应用于其他类型的模型。

动机如下。如果参数的值  已知，通常情况下潜变量  的值可以通过最大化所有可能值的对数似然来找到，要么简单地迭代  或者通过隐马尔可夫模型的鲍姆-韦尔奇算法来计算。相反，如果我们知道潜变量  的值，我们要找到参数  的估计值相当容易，通常通过简单地根据相关联的潜在变量的值对观察到的数据点进行分组，并对每个组中的点的值进行平均或其他的操作。这提出了一种迭代算法，在这两种情况下  和  未知：

1. 首先，初始化参数  一些随机值。
2. 在给定  的情况下，计算每个  可能值的概率。
3. 然后，使用刚刚计算得到的  的值来计算更好的参数估计  。
4. 重复步骤2和3，直到收敛。

刚刚描述的算法单调地接近成本函数的局部最小值。

说到期望 (E) 步骤有点用词不当。第一步的计算是固定的、依赖于数据的参数Q。一旦Q 的参数已知，在EM算法的第二步(M)中，它能被完全确定并被最大化。

虽然EM迭代确实增加了观测数据(即边缘)的似然函数，但不保证序列收敛到最大似然估计量。对于多模态分布，这意味着EM算法可以收敛到观察到的数据似然函数的局部最大值，这取决于起始值。存在各种启发式或元启发式方法来逃离局部最大值，例如随机重启爬山(从几个不同的随机初始估计开始 θ^(t))或应用模拟退火方法。

当似然是指数族时，EM特别有用：E步骤成为充分统计量的期望的和，M步骤则是最大化一个线性函数。在这种情况下，通常可以使用桑德伯格公式(罗尔夫·桑德伯格使用佩尔·马丁-洛夫和安德斯·马丁-洛夫未发表的结果发表)推导出每一步的封闭形式表达式来更新每一步。^{[11][12][5][6][7][8][9]}

在登普斯特、莱尔德和鲁宾的原始论文中，EM方法被修改为计算贝叶斯推断的最大后验估计。

还有其他方法可以找到最大似然估计，如梯度下降法、共轭梯度法或高斯-牛顿算法的变体。与EM不同，这种方法通常需要评估似然函数的一阶和/或二阶导数。

期望最大化有助于提高   而不是直接改善  。这里可以证明，对前者的改进意味着对后者的改进。^[14]

对任意概率  非零的  ，我们可以得到

我们对未知数据  的可能值在当前参数估计  下求取期望， 通过将两边乘以  并对  求和(或积分)。左边是一个常数的期望值，所以我们得到：

其中  由它所替换那部分求和的负数所定义。最后一个等式对于  的任何值都成立，包括  ，

从前面的等式中减去最后一个等式

然而，吉布斯不等式告诉我们  ，所以我们可以得出结论

换句话说，选择  使得  变大的程度至少有  变大的程度这么多。

EM算法可以看作两个交替的最大化步骤，一个例子是坐标上升。^[15][16]考虑以下函数:

其中 q 是未观测数据z 的任意概率分布，H(q) 是分布q 的熵。这个函数可以写为

其中  是给定观测数据情况下，未观测数据  的条件分布，  就是信息增益。

那么EM算法中的步骤可以看作：

期望步骤：选择  最大化  (d ):

  最大化步骤：选择  最大化  (d ):

EM经常用于机器学习和计算机视觉中的数据聚类。在自然语言处理中，该算法的两个突出例子是隐马尔可夫模型的鲍姆-韦尔奇算法和概率上下文无关文法的无监督归纳的内外算法。

EM经常用于混合模型的参数估计，^[17][18]尤其是在数量遗传学方面。^[19]

在心理测量学中，EM对于估计项目参数和项目反应理论模型的潜在能力几乎是不可或缺的。

凭借处理缺失数据和观察未知变量的能力，新兴市场正成为投资组合定价和风险管理的有用工具。

EM算法(及其更快的变体有序子集期望最大化)也广泛用于医学图像重建，尤其是正电子发射断层成像和单光子发射计算机断层成像。

在结构工程中，使用期望最大化的结构识别^[20]算法是一种使用传感器数据识别结构系统固有振动特性的纯输出方法。

卡尔曼滤波器通常用于在线状态估计，最小方差平滑器可以用于离线或批量状态估计。然而，这些最小方差解需要状态空间模型参数的估计。EM算法可用于解决联合状态和参数估计问题。

滤波和平滑EM算法通过重复以下两步过程产生:

E步骤

运行卡尔曼滤波器或用当前参数估计值设计的最小方差平滑器，以获得更新的状态估计值。

M步骤

使用最大似然计算中的滤波或平滑状态估计来获得更新的参数估计。

假设卡尔曼滤波器或最小方差平滑器对具有附加白噪声的单输入单输出系统的测量值进行操作。可以从最大似然计算中获得更新的测量噪声方差估计

其中  标量的输出估计是由滤波器或N个标量测量值  的平滑器计算得到的。上述更新也可以应用于更新泊松测量噪声强度。类似地，对于一阶自回归过程，更新过程的噪声方差估计可以通过下式计算

其中  和  是由过滤器或平滑器计算的标量状态估计。更新的模型系数估计通过以下方式获得

关于参数估计收敛性已经有了很成熟的研究。^{[21][22][23][24]}

目前已经提出了许多方法来加速EM算法，解决有时收敛速度缓慢的问题，例如使用共轭梯度和改进的牛顿方法(牛顿-拉夫森)。^[25]此外，EM算法还可以与约束估计方法一起使用。

参数扩展期望最大化 算法通常通过“利用‘协方差调整’来校正对M步的分析，强调估算的完整数据中捕获的额外信息”来加速。^[26]

期望条件最大化 用一系列条件最大化(CM)步骤替换每个M步，其中每个参数 θ_i 在其他参数保持不变的情况下，有条件地单独最大化。^[27]它可以扩展到期望条件最大化(ECME) 算法。^[28]

这个想法是在广义期望最大化(GEM) 算法的基础上进一步扩展，正如“作为最大化-最大化过程”部分所述，其中GEM在E步和M步中都只寻求目标函数F 的增加。^[15]GEM在分布式环境中进一步开发，并得到了不错的结果。^[29]

也可以将EM算法视为MM算法的子类(最大化/最小化或最小化/最大化，取决于上下文)。^[30]因此使用在更一般情况下开发的任何地方。

9.1 α-EM算法

EM算法中使用的Q函数是基于对数似然的。因此，它被视为对数EM算法。对数似然的使用可以推广到α对数似然比。然后，使用α对数似然比和α散度的Q函数可以与观测数据的α对数似然比的表示精确地等价。获得这个Q函数是一个广义的E步骤。它的最大化是一个广义的M步。这一对被称为α-EM算法^[31]其中包含log-EM算法作为其子类。因此，松山靖夫的α-EM算法是对数-EM算法的精确推广。不需要计算梯度或海森矩阵。通过选择合适的α，α-EM算法比对数-EM算法收敛速度更快。α-EM算法推导出了隐马尔可夫模型估计算法α-HMM的更快版本。^[32]

EM是一种部分非贝叶斯最大似然方法。它的最终结果给出了一个概率分布在整个潜变量(贝叶斯风格)连同一个点估计θ (最大似然估计或后验模式)。这可能需要一个完全贝叶斯版本，给出概率分布 θ 和潜变量。贝叶斯推断方法就是简单地对待θ 作为另一个潜在变量。在这个范例中，E和M步之间的区别消失了。如果使用如上所述的分解Q近似(变分贝叶斯)，求解可以迭代每个潜在变量(现在包括 θ )并一次优化一个。现在，k 需要每次迭代的步骤，其中k 是潜变量的号码。对于图形模型，这很容易做到，因为每个变量都是新的Q 只依赖于它的马尔可夫毯，所以局部消息传递可以用于有效的推理。

在信息几何中，E阶和M阶被解释为双仿射联络下的投影，称为E联络和M联络；也可以用这些术语来理解信息增益。

12.1 混合高斯分布

  是两个  维正态分布混合中  个独立观测的样本，   是决定观测起源的成分的潜变量。^[16]

  和  

其中

  和  

目标是估计表示多个高斯分布中的混合值的未知参数与每个高斯分布的均值和协方差：

其中不完全数据似然函数为

 ,

完整数据似然函数为

或者

其中  是一个指标函数，  是多元正态分布的概率密度函数。

在最后的等式中，对于每一个i，一个下标   等于零，一个下标等于一。因此，内和减少到一项。

E步

根据我们目前对参数的估计θ^(t)，Z_i 的条件分布由贝叶斯法则确定，是权重为τ 的正态密度的部分高度:

 。

这些被称为“成员概率”，通常被认为是E步的输出(尽管这不是下面的Q函数)。

该步骤对应于为Q的函数：

在上述求和中，  的期望是关于概率密度函数  的，每个不同训练集  的期望可能都不同。在采取步骤之前，E步骤中的所有内容都是已知的，除了  ，它是根据E步开始时的等式计算的。

这个完全条件的期望不需要一步计算，因为τ 和μ/σ以独立的线性项出现，因此可以独立地最大化。

M步

Q（θ | θ^(t))在形式上是二次的，意味着确定θ 相对简单。另外， τ，(μ₁,σ₁)和(μ₂,σ₂)都可以独立地最大化，因为它们都以单独的线性项出现。

首先，考虑τ，它有约束 τ₁ + τ₂=1:

这与二项分布的最大似然估计形式相同，所以

 。

对于下一个估计 (μ₁,Σ₁)：

 。

这与正态分布的加权最大似然估计形式相同，所以

  和  

对称地说

  和  。

结束

如果出现以下情况，则结束迭代过程  对于  低于某个预设阈值。

泛化

上述算法可以推广到两个以上多元正态分布的混合。

12.2 断尾回归和归并回归

EM算法已经应用在下面的线性回归模型存在时的情况，该模型解释了一些量的变化，但是实际观察到的值是模型中表示的值的删改或截断版本。^[33]这种模型的特殊情况包括来自一个正态分布的删改或截断观测。^[33]

EM通常收敛到局部最优，不一定是全局最优，一般情况下不限制收敛速度。它有可能在高维空间中是任意差的，并且可能有指数数量级的局部最优解。因此，需要替代方法来保证学习，特别是在高维环境中。新兴的替代方案在一致性方面有更好的保证，称为基于动量的方法 或者所谓的光谱技术。基于动量的概率模型参数学习方法最近越来越受关注，因为它们在某些条件下享有全局收敛性等保证，而不像EM那样经常被陷入局部最优的问题而困扰。具有学习保证的算法可以被导出用于许多重要的模型，例如混合模型、隐马尔科夫模型等。对于这些谱方法，不会出现虚假的局部最优，并且在某些规则条件下可以一致地估计真实参数。