期望最大化算法通常简称为 EM,是一种用于含有缺失观测或未观测变量的统计模型中进行最大似然估计的迭代算法。它交替执行两个步骤:在当前模型下计算期望,以及更新模型参数以最大化完整数据对数似然的期望。其一般形式适用于混合模型、缺失数据问题,以及统计学和机器学习中的其他应用。阿瑟·P. 邓普斯特、南·M. 莱尔德和唐纳德·B. 鲁宾于1977年提出并命名了这一通用框架,将此前针对特定问题开发的方法统一起来。(doi.org)
统计学表述
设 表示观测数据, 表示未观测量, 表示模型参数。模型规定了联合概率分布 。对 进行边缘化,即可得到观测数据的似然函数:
当 为连续变量时,求和改为积分。直接最大化这一表达式可能很困难,而完整数据的对数似然 可能具有更简单的结构。EM 正是利用了这一差异。未观测量不一定是实际缺失的测量值:在混合模型中,它们可以表示每个观测值由哪个分量生成。(arxiv.org)
与普通的缺失数据插补不同,EM 通常并不是用固定的估计值替换未知值,再将其视为已观测数据。其期望步骤是根据未知量的整个条件分布,对完整数据的对数似然取平均。当该对数似然依赖于缺失值的二阶矩或其他非线性函数时,这一区别尤为重要。(support.sas.com)
期望步骤与最大化步骤
从初始参数值 出发,EM 重复执行以下两个操作:
期望步骤,即 E 步。 计算
这一条件期望使用的是给定观测数据时, 在当前参数下的后验分布。在此步骤中,该分布保持固定,而 仍是所构造函数的自变量。因此,E 步得到的是一个关于候选参数的函数,而不只是一个期望数值。(support.sas.com)
最大化步骤,即 M 步。 令
有些模型的更新公式具有闭式解,另一些则需要采用数值数学优化方法。对于适当的指数族模型,只需计算完整数据充分统计量的期望,就足以完成更新。迭代持续进行,直到满足停止条件;这些条件通常依据似然或参数的变化来设定。(math.pku.edu.cn)
为什么似然不会下降
恒等式
将该下界与对数似然之间的差距表示为非负的KL散度。E 步选择精确的条件分布,使下界在当前参数处与对数似然相等。M 步则在保持 不变的同时提高这一下界。因此,精确执行的 EM 不会使观测数据的似然下降。(cs229.stanford.edu)
单调性并不保证能够达到全局最优,也不保证参数序列收敛。在适当的正则条件下,极限点是驻点,其中可能包括局部极大点或鞍点。C. F. Jeff Wu 在1983年的分析中,在明确的假设下确立了收敛性结果,并区分了似然收敛与参数收敛。(markirwin.net)
示例:高斯混合模型
一个典型应用是拟合高斯混合模型,用于密度估计或概率聚类分析。假设
其中混合权重满足 且 。每个分量都有均值 和协方差矩阵 。观测值所属的分量是未观测的,因此这是一个无监督学习问题。(cs229.stanford.edu)
E 步计算责任度,即观测值属于各分量的条件概率:
令 ,M 步进行如下更新:
责任度允许观测值以不同权重归属于多个簇,而不是强制将每个观测值划入一个簇。这些加权更新展示了如何将未观测的归属关系转化为计数和矩的期望。(cs229.stanford.edu)
扩展与局限
广义 EM 用仅需提高 值的更新替代精确最大化,从而保留似然非递减的性质。蒙特卡洛 EM 通过模拟来近似难以计算的 E 步,有时会使用马尔可夫链蒙特卡洛。由于存在模拟误差,单次更新不一定会提高精确似然,且收敛需要额外条件。(math.pku.edu.cn)
通过在 M 步的目标函数中加入先验分布密度的对数,EM 也可用于最大后验估计。最初的应用包括删失与截断观测、方差分量估计以及因子分析。(doi.org)
实际应用中的局限包括对初始化敏感、似然可能存在多个最优点,以及数值收敛可能较慢。迭代之间的变化很小,并不能证明已达到全局最优。实现的难易程度还取决于所选择的完整数据表示方式:只有当引入未观测量后产生的期望计算与最大化问题在计算上可处理时,这种做法才有用。(markirwin.net)
参考来源
- doi.org/10.1111/j.2517-6161.1977.tb01600.xdoi.org
- arxiv.org/abs/1206.4768arxiv.org
- support.sas.com/documentation/cdl/en/statug/68162/HTML/default/statug_mi_detail…support.sas.com
- math.pku.edu.cn/teachers/xirb/Courses/QR2013/ReadingForFinal/MCMC/dempsterlaird…math.pku.edu.cn
- cs229.stanford.edu/summer2023/cs229-notes8.pdfcs229.stanford.edu
- markirwin.net/stat221/Refs/wu1983.pdfmarkirwin.net
- cs229.stanford.edu/notes2020spring/cs229-notes7b.pdfcs229.stanford.edu