Clustering Algorithms: 推导/描述 EM 算法的两步，并说明为什么它单调提升似然。

Core Concept: E 步算后验责任度，M 步最大化期望完全数据对数似然；每轮提升（或不变）观测似然。

EM 的推导：设隐变量 z（如 GMM 中样本属于哪个分量），完全数据对数似然为 log p(x,z|θ)。因 z 不可观测，改用其<strong>期望</strong>——E 步计算 z 的后验分布 γ_{ik}=P(zᵢ=k|xᵢ,θᵗ)（对 GMM 即'责任度'：样本 i 属于分量 k 的概率）；M 步最大化 Q(θ|θᵗ)=E_{z|x,θᵗ}[log p(x,z|θ)]=ΣᵢΣₖγ_{ik}log[p(xᵢ,zᵢ=k|θ)/γ_{ik}]。<strong>单调性证明</strong>：log p(x|θ)=Q(θ|θᵗ)−H(θ|θᵗ)+KL(γ‖p(z|x,θ))，其中最后一项 ≥0；M 步使 Q 增大（或不变），而 E 步选择 γ 使 KL=0。因此 log p(x|θᵗ⁺¹) ≥ log p(x|θᵗ) + [Q(θᵗ⁺¹|θᵗ)−Q(θᵗ|θᵗ)] ≥ log p(x|θᵗ)。即<strong>每轮迭代观测似然单调不减</strong>，配合有界性保证收敛（到局部最优或鞍点）。

实践要点：① <strong>收敛性局限</strong>——单调不减保证收敛，但只到<strong>局部最优</strong>（似然可能多峰），且收敛可能是鞍点；故需<strong>多次随机重启</strong>（不同初始化）取最优似然。② <strong>收敛速度</strong>——EM 通常前几步快、后期慢（线性收敛，接近最优时步长变小）；可用 Aitken 加速或改用二阶方法（但代价高）。③ <strong>初始化策略</strong>——K-means 的结果常作为 GMM 的初始化（均值取 K-means 中心）；或用多次随机初始化。④ <strong>与梯度上升的关系</strong>——EM 可视为'用 Jensen 不等式构造的下界做坐标上升'，它自动保证单调性（无需调学习率），但每步计算量更大（需算全部责任度）。⑤ <strong>退化问题</strong>——GMM 中若某分量塌缩到单个点，协方差趋于 0、似然趋于无穷（病态解）；解法是加协方差下界（regularization）、或使用贝叶斯 GMM（加先验）。⑥ <strong>变体</strong>——变分 EM（VI）、Monte Carlo EM（M 步用采样近似）用于更复杂模型。