形式陈述
观测 x 固定,潜变量为 Z ,模型联合密度为 p θ ( x , z ) 。本页的对数似然与 KL 散度均用自然对数。最大似然估计 理路 最大似然估计 Maximum likelihood estimation · MLE 在参数空间内选择使已观测数据似然达到上确界的参数估计方法。 要最大化
ℓ ( θ ) = log p θ ( x ) = log ∫ p θ ( x , z ) d z . 当直接处理积分外的对数很难、给定 Z 后却容易优化时,EM 从允许参数 θ ( 0 ) 出发重复两步:
E 步: 求当前后验条件核 理路 条件分布 Conditional distribution · Regular conditional distribution 给定观测值后随机量的概率律,以及它与原联合分布相容的核表示。 q t ( z ) = p θ ( t ) ( z ∣ x ) ,并在这个固定概率律下形成普通期望 理路 期望 Expectation · Expected value 实值或复值随机变量关于概率测度的 Lebesgue 积分,概括加权平均与总体质量平衡。 Q ( θ ∣ θ ( t ) ) = E q t [ log p θ ( x , Z ) ] .
M 步: 选择 θ ( t + 1 ) ∈ arg max θ Q ( θ ∣ θ ( t ) ) 。只保证 Q ( θ ( t + 1 ) ∣ θ ( t ) ) ≥ Q ( θ ( t ) ∣ θ ( t ) ) 的版本称广义 EM。
这里始终固定已见资料 x ,Q 是后验核下的逐点积分;它的有限性不要求把 log p θ ( X , Z ) 在全部随机资料上另作全局有符号 L 1 假设。精确 M 步还要求最大值达到并有预定的可实施选择;若只能找出提高 Q 的可行点,应如实报告为广义 EM。
输入还应包括迭代上限和数值容差。每轮检查参数是否仍可行、后验是否可归一化、目标值是否有限;达到上限或似然增量小于给定容差时停止并报告当前参数、目标值及停止原因。小增量是数值停止规则,不是全局最优证书。
本页给出一个足够明确的单调性合同:新旧参数的证据均有限正,E 步确实使用当前后验;在 q t 下,log q t 、log p θ ( t ) ( x , Z ) 及 log p θ ( t + 1 ) ( x , Z ) 都绝对可积,且 M 步至少不降低该 Q 。
这些条件使下面新旧 Q 、熵及 KL 均为有限数,每一个差和不等号都有定义。它们是本页所证明版本的充分条件,不声称覆盖所有扩展值 EM 变体。近似后验、蒙特卡洛噪声或不受控的数值优化不自动继承结论。
直觉
EM 不把缺失值填成一个最可能值后假装它已观测。E 步保留潜变量的整个当前分布;M 步在这个分布下平均完整数据的对数似然。比如混合模型中的一个观测可以以 0.7 和 0.3 的权重参与两个成分更新,而不是被永久扔进其中一个簇。
为什么似然不下降
将证据下界 理路 证据下界 Evidence lower bound · ELBO · Variational lower bound 将对数边缘似然分解为任意辅助分布下的可计算期望与到真实后验的非负 KL 缺口。 用于固定参数的联合模型,记
F ( q , θ ) = E q [ log p θ ( x , Z ) ] − E q [ log q ( Z ) ] . 这里 θ 是待优化参数,无须对它设先验。由KL 散度 理路 KL 散度 Kullback–Leibler divergence · Relative entropy 同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。 分解,
ℓ ( θ ) = F ( q , θ ) + D KL ( q ‖ p θ ( ⋅ ∣ x ) ) . E 步令缺口在旧参数处为零;M 步保持 q t 不变,因熵项不含 θ ,提高 Q 就提高 F 。因此
ℓ ( θ ( t + 1 ) ) ≥ F ( q t , θ ( t + 1 ) ) ≥ F ( q t , θ ( t ) ) = ℓ ( θ ( t ) ) . 证明的关键是旧位置处下界贴住似然。任意近似 q t 没有这个等号时,即使下界上升,原似然仍可能下降。
例子与边界
三个观测的一轮更新
拟合两成分高斯混合 理路 有限混合模型 Finite mixture model · 有限混合分布 先抽取有限个潜在成分之一,再由该成分生成观测,并通过边缘化得到观测分布的统计模型。 ,各成分采用正态密度 理路 正态分布 Normal distribution · Gaussian distribution · 高斯分布 具有指数平方密度、在仿射变换与独立求和下封闭的概率分布族。 ,两方差固定为 1 。数据为 ( 0 , 1 , 3 ) ,初值 π ( 0 ) = 1 / 2 , μ 1 ( 0 ) = 0 , μ 2 ( 0 ) = 2 。记 r i = P ( Z i = 1 ∣ x i ) ,E 步给出
r i = e − x i 2 / 2 e − x i 2 / 2 + e − ( x i − 2 ) 2 / 2 = 1 1 + e 2 x i − 2 , 故 r = ( 0.880797078 , 0.5 , 0.017986210 ) 。第一成分的有效样本数为 N 1 = ∑ i r i ≈ 1.398783288 。忽略与参数无关的项,M 步最大化
∑ i [ r i log π + ( 1 − r i ) log ( 1 − π ) − 1 2 r i ( x i − μ 1 ) 2 − 1 2 ( 1 − r i ) ( x i − μ 2 ) 2 ] . 本例 0 < N 1 < 3 ,两个均值方向的二阶导数分别为 − N 1 与 − ( 3 − N 1 ) ,权重方向为 − N 1 / π 2 − ( 3 − N 1 ) / ( 1 − π ) 2 < 0 。因此目标分别严格凹,且权重趋端点时降至负无穷;由凹函数的切线判据 理路 凸函数 Convex function 函数在任意凸组合处不超过相同权重下函数值的凸组合。 ,下面的驻点确实达到全局 M 步最大值。对均值和权重求导,得到加权平均和有效比例:
π ( 1 ) = N 1 / 3 ≈ 0.466261096 , μ 1 ( 1 ) = ∑ i r i x i N 1 ≈ 0.396028916 , μ 2 ( 1 ) = ∑ i ( 1 − r i ) x i 3 − N 1 ≈ 2.152139273 . 把新旧参数代回包含正态归一化常数的观测对数似然,得到 − 4.998032022 → − 4.839379547 。均值和权重确实变了,而单调性比较的是同一个观测目标,不是两个不同轮次的 Q 值。
计算成本
一般 EM 的成本取决于后验计算和 M 步优化,不能仅凭“两步交替”给出统一复杂度。对 N 个一维观测、K 个方差固定的高斯成分,每轮计算全部责任度并累计加权和需 O ( N K ) 时间,执行 t 轮需 O ( t N K ) 时间。保存整张责任度表需 O ( N K ) 空间;若每轮固定旧参数,逐个观测计算责任度并累计各成分的有效样本数与加权和,最后统一更新参数,则辅助空间可降为 O ( K ) 。这里不计数据和模型本身的存储,也不把达到指定精度所需的轮数 t 当作已知常数。
单调不等于解决全部问题
若似然有有限上界,单调性只保证似然值收敛;参数序列收敛、极限为驻点仍需额外正则条件,更不能推出全局最大。对称初值可能使两个成分持续重合;不同初值可能落入不同局部解。
若高斯方差也自由更新,方差趋零可能使似然无界。此时似然不断上升恰可能是在走向退化。某成分有效样本数为零时,均值更新还会出现除零;实现必须报告退化或采用明示的约束、重启规则,不能悄悄赋一个任意均值。
推论与应用
EM 适合“完整数据容易,观测数据困难”的结构,潜变量可以是缺失数值,也可以是从未观测过的类别。若后验计算本身困难,可转向变分推断 理路 变分 Bayesian 推断 Variational Bayesian inference · Variational inference · VI 在可计算分布族内优化与真实后验的散度,以确定性或随机优化换取受限族中的快速后验近似。 等近似路线,但应重新说明优化目标和保证。
在零膨胀Poisson模型 理路 零膨胀Poisson模型 Zero-inflated Poisson model · ZIP model · Zero-inflated Poisson regression · 零膨胀泊松回归 将零点质量与Poisson部件混合,推导零责任度、EM和可识别条件,并区分观测分布、潜在标签以及门槛模型的概率范围。 中,E步只给零记录分配潜在来源责任度,正记录的直接零责任度必为零;M步据此更新混合比例和Poisson有效暴露分母。该页列出一次可复算更新、观察似然与全零/无零边界,责任度不能在同一个M步里跟随新参数重算。
判断一次实现是否遵循 EM,可保存每轮观测对数似然,并在小型离散模型上直接枚举潜状态核对 E 步。只画 Q 曲线不足以验证单调性,因为 Q 的条件参数每轮都在改变。多起点有助于发现不同局部解,却不构成全局保证。
终点任务:更新、单位迁移与下界边界
先复算上面的三点 E 步、M 步及两次观测似然。再把全部观测变为 y i = 3 x i − 1 ,两成分初始均值相应变为 − 1 , 5 ,已知方差变为 9 ,而初始权重不变。重算一次更新,并检查哪些量不变、哪些量按单位变化。
答案是责任度及更新权重原样保留,更新均值为 3 μ 1 ( 1 ) − 1 ≈ 0.188086749 与 3 μ 2 ( 1 ) − 1 ≈ 5.456417818 。每个新密度是旧密度的 1 / 3 ,因此新旧两次对数似然都减去 3 log 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 ) = 1 2 log ( 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 估计 理路 Turnbull 区间删失估计 Turnbull estimator 用区间概率建立非参数似然,再以自洽质量更新估计区间删失分布,不伪造精确事件日。 按当前区间质量分摊每个人的条件概率,再平均更新,提供一个可逐轮核验似然增加的非参数 EM 例子。
参考资料