← 返回Book 7目录

第22章：期望最大化算法

EM算法 - 迭代E步骤和M步骤

通过交替优化最大化对数似然函数

本章概要

EM算法：一种迭代算法，用于在含有潜在变量的模型中寻找参数的最大似然估计。是第21章中求解GMM参数的核心方法。

两步迭代：E步骤使用当前参数θ⁽ⁱ⁾计算后验概率p(Cₖ|x)。M步骤更新参数θ⁽ⁱ⁺¹⁾以最大化对数似然L(θ)。

收敛保证：每次迭代都单调增加L(θ)直到收敛到局部最大值。由于不存在闭式解，因此必须使用迭代优化。

22.1 EM算法介绍

🎯 核心动机

求解GMM需要估计K个簇的参数θ = {αₖ, μₖ, Σₖ}。 与具有闭式质心更新的K-Means不同，GMM参数没有解析解。 EM提供了一个保证收敛的迭代优化框架。

为什么需要EM：
  • • 潜在变量（簇分配）未知
  • • θ没有闭式解
  • • 由于对数求和结构，直接MLE不可行
EM提供什么：
  • • 对L(θ)的迭代坐标上升
  • • 单调收敛保证
  • • 计算上可行的更新

EM算法框架

E
期望步骤（E步骤）
计算关于后验分布p(Cₖ|x, θ⁽ⁱ⁾)的对数似然期望值。 在GMM中，这意味着计算每个数据点的后验概率。
p(Cₖ|xᵢ, θ⁽ⁱ⁾) = [αₖ⁽ⁱ⁾ · f(xᵢ|Cₖ, θ⁽ⁱ⁾)] / f(xᵢ|θ⁽ⁱ⁾)
M
最大化步骤（M步骤）
找到使期望对数似然Q(θ|θ⁽ⁱ⁾)最大的参数θ⁽ⁱ⁺¹⁾。 在GMM中，这给出了αₖ、μₖ和Σₖ的加权更新。
θ⁽ⁱ⁺¹⁾ = argmax Q(θ|θ⁽ⁱ⁾) = argmax Σᵢ Σₖ p(Cₖ|xᵢ, θ⁽ⁱ⁾) log[αₖ·f(xᵢ|Cₖ,θ)]
↻
迭代直到收敛
重复E步骤和M步骤，直到L(θ)的变化低于阈值ε或达到最大迭代次数。 每次迭代保证不会降低L(θ)。
停止条件：|L(θ⁽ⁱ⁺¹⁾) - L(θ⁽ⁱ⁾)| < ε

22.2 E步骤：计算后验概率

📊 从先验到后验

E步骤应用贝叶斯定理将先验概率αₖ和似然f(x|Cₖ)转换为后验概率p(Cₖ|x)。 这些后验概率充当每个数据点的"软分配"或"隶属度分数"。

计算流程：
1. 似然： f(x|Cₖ, θ⁽ⁱ⁾) = N(x | μₖ⁽ⁱ⁾, Σₖ⁽ⁱ⁾)
2. 联合概率： f(x, Cₖ | θ⁽ⁱ⁾) = αₖ⁽ⁱ⁾ · f(x|Cₖ, θ⁽ⁱ⁾)
3. 证据： f(x | θ⁽ⁱ⁾) = Σₖ f(x, Cₖ | θ⁽ⁱ⁾)
4. 后验： p(Cₖ|x, θ⁽ⁱ⁾) = f(x, Cₖ | θ⁽ⁱ⁾) / f(x | θ⁽ⁱ⁾)
🔄

1D EM算法迭代

观察参数通过E步骤和M步骤的演变

迭代次数：0 / 36初始
0.5x1.5x3x
α₁ (Prior C₁)
0.500
μ₁ (Mean C₁)
-1.000
σ₁ (Std C₁)
0.050
α₂ (Prior C₂)
0.500
μ₂ (Mean C₂)
1.000
σ₂ (Std C₂)
0.050
Log-Likelihood L(θ):-2.5000
目标：通过迭代E步骤和M步骤最大化L(θ)

似然和联合分布

x概率密度
f(x|C₁) Likelihood
f(x|C₂) Likelihood
α₁·f(x|C₁) Joint
α₂·f(x|C₂) Joint
f(x) = α₁·f(x|C₁) + α₂·f(x|C₂) Mixture

后验概率

0.00.20.40.60.81.00.5xp(Cₖ|x)
p(C₁|x) = α₁f(x|C₁)/f(x)
p(C₂|x) = α₂f(x|C₂)/f(x)
贝叶斯决策：
如果p(C₁|x) > p(C₂|x)，则将x分配给C₁，否则分配给C₂
随着EM迭代，后验曲线变得更加分离

🔄 EM算法：E步骤使用当前参数θ计算后验概率p(Cₖ|x)。 M步骤更新参数θ以最大化对数似然L(θ)。 通过迭代，参数收敛并且簇出现。 观察μ₁和μ₂如何移向数据质心，σ₁和σ₂如何捕获散布，α₁和α₂如何反映簇的比例。

📝

EM算法：逐步分解

E步骤和M步骤公式的详细演练

进度：步骤 1 / 8
INIT

初始化参数θ⁽⁰⁾

从参数的初始猜测开始。对于K=2个簇：

公式：
θ⁽⁰⁾ = {α₁⁽⁰⁾, α₂⁽⁰⁾, μ₁⁽⁰⁾, μ₂⁽⁰⁾, σ₁⁽⁰⁾, σ₂⁽⁰⁾}
示例计算：
α₁ = 0.5, α₂ = 0.5
μ₁ = -1, μ₂ = 1
σ₁ = 0.05, σ₂ = 0.05
🎯 关键洞察
初始猜测可以是随机的或使用K-Means初始化。
🔵 E步骤总结
1. 计算似然f(x|Cₖ)
2. 计算证据f(x)
3. 计算后验p(Cₖ|x)
输出：软簇分配
🟢 M步骤总结
1. 使用后验更新先验α
2. 更新均值μ（加权平均）
3. 更新标准差σ（加权方差）
输出：新参数θ
🔁 迭代流程
θ⁽ⁱ⁾ → E步骤 → p(Cₖ|x)
p(Cₖ|x) → M步骤 → θ⁽ⁱ⁺¹⁾
重复直到收敛
目标：最大化L(θ)

🔄 为什么EM有效：E步骤和M步骤形成坐标上升算法。E步骤计算关于后验分布的对数似然期望值。M步骤最大化这个期望对数似然。每次迭代保证不会降低L(θ)，确保收敛到局部最大值。

22.3 M步骤：更新参数

🔧 加权参数更新

M步骤使用来自E步骤的后验概率p(Cₖ|xᵢ)作为权重来计算新参数。 这类似于加权平均，其中每个点按其在每个簇中的隶属度成比例地贡献。

更新先验αₖ：
后验的平均值
αₖ = (1/n)Σᵢ p(Cₖ|xᵢ)
更新均值μₖ：
加权平均
μₖ = Σᵢ p(Cₖ|xᵢ)·xᵢ / Σᵢ p(Cₖ|xᵢ)
更新协方差Σₖ：
加权方差
Σₖ = Σᵢ p(Cₖ|xᵢ)·(xᵢ-μₖ)(xᵢ-μₖ)ᵀ / Σᵢ p(Cₖ|xᵢ)

对数似然函数L(θ)

EM最大化的目标函数。它衡量模型对观测数据的解释程度。

L(θ) = Σᵢ log f(xᵢ|θ) = Σᵢ log[Σₖ αₖ · f(xᵢ|Cₖ, θ)]
为什么用对数？
将乘积转换为求和，使优化可行。 还有数值稳定性（避免下溢）。
为什么最大化？
更高的L(θ)意味着更好的拟合。EM找到使观测数据概率最大的参数。

22.4 收敛和迭代过程

📈

参数收敛可视化

观察参数在EM迭代过程中如何演化和收敛

迭代 0迭代 36

对数似然L(θ)收敛

-1.70-1.86-2.02-2.18-2.34-2.5009182736迭代次数L(θ)
L(θ)= -1.723
📊 收敛准则
EM停止条件：
• |L(θ⁽ⁱ⁺¹⁾) - L(θ⁽ⁱ⁾)| < ε（例如，ε = 10⁻⁵）
• 或达到最大迭代次数（例如，50或100）
L(θ)单调递增，由EM理论保证。
🎯 收敛速度
• L(θ)收敛最快（接近尾部的迭代大多是平的）
• 即使L(θ)稳定，参数仍在继续调整
• 分离良好的簇收敛更快
2D情况在11次迭代中收敛，而1D需要36次（更好的初始化）。

🔄 为什么L(θ)总是增加：每次EM迭代都保证不会降低对数似然函数L(θ)。 E步骤计算Q(θ|θ⁽ⁱ⁾)，M步骤选择θ⁽ⁱ⁺¹⁾以最大化Q。 根据Jensen不等式，这确保了L(θ⁽ⁱ⁺¹⁾) ≥ L(θ⁽ⁱ⁾)。 曲线在接近局部最大值时变平（收敛）。

🎯 收敛性质

单调递增：由Jensen不等式保证L(θ⁽ⁱ⁺¹⁾) ≥ L(θ⁽ⁱ⁾)
局部最大值：EM收敛到局部（不一定是全局）最大值
收敛速度：线性收敛，接近最优时可能很慢
初始化重要：不同的起始点可能收敛到不同的解

⚙️ 实践考虑

停止准则：|L(θ⁽ⁱ⁺¹⁾) - L(θ⁽ⁱ⁾)| < ε 或最大迭代次数
初始化：使用K-Means结果或多次随机起始
数值问题：注意奇异协方差矩阵
解质量：多次运行，保留最好的L(θ)

22.5 多元GMM和EM

🎨 2D可视化：全局视图

对于2D数据，我们可以可视化整个EM过程：数据点、高斯椭圆（代表协方差）、质心和决策边界。 观察这些元素在迭代过程中的演变，可以深入了解EM的工作原理。

关键视觉元素：
• 椭圆：N(μₖ, Σₖ)的2σ置信域
• 质心：均值向量μₖ
• 决策边界：p(C₁|x) = p(C₂|x)的位置
• 数据着色：按argmax p(Cₖ|x)
🎯

2D EM算法：椭圆演化

观察高斯椭圆和决策边界在迭代过程中的演化

迭代次数：0 / 11初始
0.5x1x2x

高斯椭圆与决策边界

x₁x₂

🔵 簇1参数

先验 α₁
0.500
均值 μ₁
[1.00, 0.00]
协方差 Σ₁
[1.00, 0.00]
[0.00, 1.00]

🟢 簇2参数

先验 α₂
0.500
均值 μ₂
[-1.00, 0.00]
协方差 Σ₂
[1.00, 0.00]
[0.00, 1.00]

🎯 关键洞察

• 椭圆表示高斯分布的2σ轮廓
• 椭圆大小/形状由协方差矩阵Σₖ决定
• 质心(μₖ)向数据簇中心移动
• 决策边界随参数更新而移动
收敛：当EM收敛时椭圆稳定（第11次迭代）

🎯 2D EM可视化：这个可视化展示了核心EM算法过程。 椭圆表示两个高斯分量的2σ置信区域。 随着EM迭代，质心μₖ向簇中心移动，椭圆形状（由Σₖ决定）调整以匹配数据的散布和方向。 决策边界（蓝色/绿色背景）相应移动。 初始参数是糟糕的猜测，但到第11次迭代时，模型准确捕获了数据中的两簇结构。

比较1D与2D EM

1D情况（36次迭代）
  • • 参数：α、μ、σ（标量）
  • • 差的初始化→更多迭代
  • • 可视化：x轴上的PDF曲线
  • • 决策：x上的标量阈值
2D情况（11次迭代）
  • • 参数：α、μ（向量）、Σ（矩阵）
  • • 更好的初始化→更快收敛
  • • 可视化：椭圆和散点图
  • • 决策：2D边界曲线

本章总结

核心要点

🎯 核心算法

• E步骤：计算所有数据点的p(Cₖ|xᵢ, θ⁽ⁱ⁾)
• M步骤：使用加权公式更新θ⁽ⁱ⁺¹⁾
• 迭代：直到L(θ)收敛
• 输出：最优参数θ*和簇分配

📐 数学保证

• 单调性：L(θ⁽ⁱ⁺¹⁾) ≥ L(θ⁽ⁱ⁾)
• 收敛：到局部最大值
• 理论依据：Jensen不等式
• 速度：线性（可能很慢）

🔗 与GMM的联系

EM是拟合GMM参数的标准算法。 第21章从概念上介绍了GMM；本章展示了如何实际计算这些参数。 E步骤对应于基于后验概率对点进行"软分配"到簇。 M步骤对应于使用这些软分配作为权重来更新簇参数（先验、均值、协方差）。

🔄
迭代过程
E步骤↔M步骤直到收敛
📈
单调L(θ)
保证每次迭代增加
🎯
局部最优
建议多次启动

超越GMM：EM的应用

虽然我们专注于GMM，但EM是一个通用算法，适用于许多含有潜在变量的模型：

🔊 隐马尔可夫模型（HMM）
语音识别、生物信息学。E步骤：前向-后向算法。M步骤：Baum-Welch更新。
📊 缺失数据填补
E步骤：估计缺失值。M步骤：用完整数据更新参数。
🎭 主题建模（LDA）
用于文档聚类的隐狄利克雷分配。用于主题发现的EM变体。
🧬 生物信息学
模式发现、序列比对。处理缺失或不确定的生物数据。
🤖 推荐系统
具有缺失项的矩阵分解。协同过滤。
🖼️ 图像分割
用于像素聚类的混合模型。将图像分割成区域。