Skip to content

算法Algorithm

期望最大化算法

施工中 · 内容逐步修订

Expectation-maximization algorithm · EM algorithm · EM 算法

交替计算潜变量的条件分布与提高完整数据期望对数似然,以迭代优化观测似然的算法。

形式陈述 ​

观测 x 固定,潜变量为 Z,模型联合密度为 pθ(x,z)。本页的对数似然与 KL 散度均用自然对数。最大似然估计要最大化

ℓ(θ)=log⁡pθ(x)=log⁡∫pθ(x,z)dz.

当直接处理积分外的对数很难、给定 Z 后却容易优化时,EM 从允许参数 θ(0) 出发重复两步:

  1. E 步: 求当前后验条件核 qt(z)=pθ(t)(z∣x),并在这个固定概率律下形成普通期望Q(θ∣θ(t))=Eqt[log⁡pθ(x,Z)].
  2. M 步: 选择 θ(t+1)∈arg⁡maxθQ(θ∣θ(t))。只保证 Q(θ(t+1)∣θ(t))≥Q(θ(t)∣θ(t)) 的版本称广义 EM。

这里始终固定已见资料 x,Q 是后验核下的逐点积分;它的有限性不要求把 log⁡pθ(X,Z) 在全部随机资料上另作全局有符号 L1 假设。精确 M 步还要求最大值达到并有预定的可实施选择;若只能找出提高 Q 的可行点,应如实报告为广义 EM。

输入还应包括迭代上限和数值容差。每轮检查参数是否仍可行、后验是否可归一化、目标值是否有限;达到上限或似然增量小于给定容差时停止并报告当前参数、目标值及停止原因。小增量是数值停止规则,不是全局最优证书。

本页给出一个足够明确的单调性合同:新旧参数的证据均有限正,E 步确实使用当前后验;在 qt 下,log⁡qt、log⁡pθ(t)(x,Z) 及 log⁡pθ(t+1)(x,Z) 都绝对可积,且 M 步至少不降低该 Q。

这些条件使下面新旧 Q、熵及 KL 均为有限数,每一个差和不等号都有定义。它们是本页所证明版本的充分条件,不声称覆盖所有扩展值 EM 变体。近似后验、蒙特卡洛噪声或不受控的数值优化不自动继承结论。

直觉

EM 不把缺失值填成一个最可能值后假装它已观测。E 步保留潜变量的整个当前分布;M 步在这个分布下平均完整数据的对数似然。比如混合模型中的一个观测可以以 0.7 和 0.3 的权重参与两个成分更新,而不是被永久扔进其中一个簇。

为什么似然不下降 ​

将证据下界用于固定参数的联合模型,记

F(q,θ)=Eq[log⁡pθ(x,Z)]−Eq[log⁡q(Z)].

这里 θ 是待优化参数,无须对它设先验。由KL 散度分解,

ℓ(θ)=F(q,θ)+DKL(q‖pθ(⋅∣x)).

E 步令缺口在旧参数处为零;M 步保持 qt 不变,因熵项不含 θ,提高 Q 就提高 F。因此

ℓ(θ(t+1))≥F(qt,θ(t+1))≥F(qt,θ(t))=ℓ(θ(t)).

证明的关键是旧位置处下界贴住似然。任意近似 qt 没有这个等号时,即使下界上升,原似然仍可能下降。

例子与边界

三个观测的一轮更新 ​

拟合两成分高斯混合,各成分采用正态密度,两方差固定为 1。数据为 (0,1,3),初值 π(0)=1/2,μ1(0)=0,μ2(0)=2。记 ri=P(Zi=1∣xi),E 步给出

ri=e−xi2/2e−xi2/2+e−(xi−2)2/2=11+e2xi−2,

故 r=(0.880797078,0.5,0.017986210)。第一成分的有效样本数为 N1=∑iri≈1.398783288。忽略与参数无关的项,M 步最大化

∑i[rilog⁡π+(1−ri)log⁡(1−π)−12ri(xi−μ1)2−12(1−ri)(xi−μ2)2].

本例 0<N1<3,两个均值方向的二阶导数分别为 −N1 与 −(3−N1),权重方向为 −N1/π2−(3−N1)/(1−π)2<0。因此目标分别严格凹,且权重趋端点时降至负无穷;由凹函数的切线判据,下面的驻点确实达到全局 M 步最大值。对均值和权重求导,得到加权平均和有效比例:

π(1)=N1/3≈0.466261096,μ1(1)=∑irixiN1≈0.396028916,μ2(1)=∑i(1−ri)xi3−N1≈2.152139273.

把新旧参数代回包含正态归一化常数的观测对数似然,得到 −4.998032022→−4.839379547。均值和权重确实变了,而单调性比较的是同一个观测目标,不是两个不同轮次的 Q 值。

计算成本 ​

一般 EM 的成本取决于后验计算和 M 步优化,不能仅凭“两步交替”给出统一复杂度。对 N 个一维观测、K 个方差固定的高斯成分,每轮计算全部责任度并累计加权和需 O(NK) 时间,执行 t 轮需 O(tNK) 时间。保存整张责任度表需 O(NK) 空间;若每轮固定旧参数,逐个观测计算责任度并累计各成分的有效样本数与加权和,最后统一更新参数,则辅助空间可降为 O(K)。这里不计数据和模型本身的存储,也不把达到指定精度所需的轮数 t 当作已知常数。

单调不等于解决全部问题 ​

若似然有有限上界,单调性只保证似然值收敛;参数序列收敛、极限为驻点仍需额外正则条件,更不能推出全局最大。对称初值可能使两个成分持续重合;不同初值可能落入不同局部解。

若高斯方差也自由更新,方差趋零可能使似然无界。此时似然不断上升恰可能是在走向退化。某成分有效样本数为零时,均值更新还会出现除零;实现必须报告退化或采用明示的约束、重启规则,不能悄悄赋一个任意均值。

推论与应用

EM 适合“完整数据容易,观测数据困难”的结构,潜变量可以是缺失数值,也可以是从未观测过的类别。若后验计算本身困难,可转向变分推断等近似路线,但应重新说明优化目标和保证。

在零膨胀Poisson模型中,E步只给零记录分配潜在来源责任度,正记录的直接零责任度必为零;M步据此更新混合比例和Poisson有效暴露分母。该页列出一次可复算更新、观察似然与全零/无零边界,责任度不能在同一个M步里跟随新参数重算。

判断一次实现是否遵循 EM,可保存每轮观测对数似然,并在小型离散模型上直接枚举潜状态核对 E 步。只画 Q 曲线不足以验证单调性,因为 Q 的条件参数每轮都在改变。多起点有助于发现不同局部解,却不构成全局保证。

终点任务:更新、单位迁移与下界边界 ​

先复算上面的三点 E 步、M 步及两次观测似然。再把全部观测变为 yi=3xi−1,两成分初始均值相应变为 −1,5,已知方差变为 9,而初始权重不变。重算一次更新,并检查哪些量不变、哪些量按单位变化。

答案是责任度及更新权重原样保留,更新均值为 3μ1(1)−1≈0.188086749 与 3μ2(1)−1≈5.456417818。每个新密度是旧密度的 1/3,因此新旧两次对数似然都减去 3log⁡3,增量不变。若只变数据却忘记同步变噪声方差,这项责任度不变性便没有理由成立。

最后检验近似 E 步的边界。固定同一个观测 x,两候选参数的潜状态联合质量分别为 A=(0.792,0.008)、B=(0.35,0.35);剩余观测事件分别分配总质量 0.2,0.3,即可补成合法模型。始终使用近似 q=(1/2,1/2),则 F(q,A)=12log⁡(0.025344),而 F(q,B)=log⁡0.7,下界确实上升;观测证据却从 0.8 降到 0.7。原因是 q 并非 A 的真实后验 (0.99,0.01),旧位置没有贴合等号。

上述初值下,若把中间观测 x=1 硬分给第一成分,是否仍是同一次 EM 的 E 步?不是:正确条件概率是 1/2。硬指派改变了辅助分布,旧位置下界贴合条件不再成立,所以必须另行分析所得算法。

事件只知发生在两个检查时刻之间时,潜变量可以取其所属的候选支持区间。Turnbull 估计按当前区间质量分摊每个人的条件概率,再平均更新,提供一个可逐轮核验似然增加的非参数 EM 例子。

参考资料
关系图谱24 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

暂未标注直接上位概念。

下位 / 直接特例

类型化关系