Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 8: K-Means. Gaussian Mixture Models (GMM). Expectation Maximization (EM)

目录 · ← l7 · l9 →

Lecture 8: K-Means. Gaussian Mixture Models (GMM). Expectation Maximization (EM)

概述

本讲进入无监督学习：K-Means（最经典的硬聚类算法）与高斯混合模型 GMM + 期望最大化 EM（软聚类/密度估计）。核心思想：数据存在隐藏结构（潜在变量）——每个样本属于哪个簇是我们看不到的。EM 算法为“带隐藏变量的最大似然估计”提供通用框架，是课程中最重要的算法范式之一。

核心概念与数学直觉

  • K-Means 聚类：
    • 问题定义：给定无标签数据 $\{x^{(1)},\dots,x^{(m)}\}$，把数据分成 $K$ 个簇，使簇内点尽量接近。
    • 直观解释：把每个簇想象成一个“引力中心”（质心）。算法交替做两件事：把每个点指派给最近的质心；把质心移动到其簇内点的均值。反复迭代直到稳定。
    • 数学形式：最小化簇内平方距离和（distortion）： $J(c, \mu) = \sum_{i=1}^{m} \| x^{(i)} - \mu_{c^{(i)}} \|^2$
      • $c^{(i)} \in \{1,\dots,K\}$：样本 $i$ 的簇指派（潜在变量）。
      • $\mu_k$：簇 $k$ 的质心（均值）。
    • 性质：坐标下降（每次更新 $c$ 或 $\mu$ 都使 $J$ 不增）⇒ 保证收敛到局部最优（不同初始化可能不同结果）。用随机初始化多次、选 $J$ 最小者。
  • 高斯混合模型 (GMM)：
    • 问题定义：数据由 $K$ 个高斯分布混合生成，但不知道每个样本来自哪个高斯。
    • 生成过程：先按 $\phi_j$ 抽类别 $z^{(i)} \sim \text{Multinomial}(\phi)$，再抽 $x^{(i)} \vert z^{(i)}=j \sim \mathcal{N}(\mu_j, \Sigma_j)$。$z$ 是隐藏/潜在变量。
    • 似然： $\ell(\phi, \mu, \Sigma) = \sum_{i=1}^{m} \log \sum_{j=1}^{K} \phi_j \cdot \frac{1}{(2\pi)^{d/2}\|\Sigma_j\|^{1/2}} \exp\left(-\frac{1}{2}(x^{(i)} - \mu_j)^T \Sigma_j^{-1} (x^{(i)} - \mu_j)\right)$
      • 注意 $\log$ 在求和（混合）外面——无法像单高斯那样闭式求解；直接对 $\ell$ 求导置零得不到闭式解（$\mu_j$ 与 $z$ 纠缠）。这就是 EM 登场的动机。
    • K-Means vs GMM：K-Means 是“硬”指派（每个点属于一个簇）；GMM 是“软”指派（每个点以概率属于各簇），且能给出数据的密度模型（可计算 $P(x)$，用于异常检测/生成）。
  • EM 算法（期望最大化）：
    • 核心思想：直接最大化 $\ell$ 太困难（log 套在求和里）。EM 用两步迭代绕开：
      1. E 步：固定参数，计算每个样本属于各簇的后验概率（“期望”）：$w_j^{(i)} = P(z^{(i)}=j \vert x^{(i)}; \phi,\mu,\Sigma)$。
      2. M 步：用这些后验概率作为权重，最大化加权对数似然，得到新参数（“最大化”）。
    • 理论保障（Jensen 不等式）：EM 构造似然的下界（ELBO），E 步使下界在该点紧（相等），M 步提升下界 ⇒ 每次迭代 $\ell$ 单调不减 ⇒ 收敛到（局部）最优。这是“优化难目标”的通用策略：优化一个容易的下界。
    • GMM 的 EM 更新（M 步）： $\phi_j = \frac{1}{m}\sum_i w_j^{(i)}, \qquad \mu_j = \frac{\sum_i w_j^{(i)} x^{(i)}}{\sum_i w_j^{(i)}}, \qquad \Sigma_j = \frac{\sum_i w_j^{(i)} (x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_i w_j^{(i)}}$
      • 形式与 GDA/朴素贝叶斯的 MLE 相同，只是每个样本按 $w_j^{(i)}$ 加权——权重就是“它属于簇 $j$ 的概率”。
    • EM 的更一般表述（L8 后半）：E 步计算 $Q(\theta, \theta^{old}) = \sum_i \sum_z Q_i(z) \log \frac{p(x^{(i)}, z; \theta)}{Q_i(z)}$；M 步最大化 $Q$。EM 可应用于任何带隐藏变量的模型（缺失数据、混合模型、因子分析、隐马尔可夫模型）。

算法伪代码与逻辑解说：K-Means

伪代码

输入:
    - 数据 X (m×d)，簇数 K，最大迭代 max_iters

输出:
    - 质心 mu_1..mu_K，簇指派 c^(1)..c^(m)

1. 初始化: 随机选 K 个样本作为初始质心 mu_1..mu_K
2. 循环 iter = 1..max_iters:
    2.1 指派步骤 (Assignment):
        对每个样本 i: c^(i) = argmin_j ||x^(i) - mu_j||^2
    2.2 更新步骤 (Update):
        对每个簇 j: mu_j = (1/|S_j|) * Σ_{i∈S_j} x^(i)   // S_j = 指派到 j 的样本集合
    2.3 若指派不再变化: 终止
3. 返回 (mu, c)

【算法逻辑解说】

  1. Step 2.1 指派：每个点认领“最近的质心” —— 对应 $J$ 对 $c$ 的坐标下降。复杂度 $O(mKd)$。
  2. Step 2.2 更新：质心移到簇内均值 —— 对应 $J$ 对 $\mu$ 的坐标下降。均值是“最小化平方距离和的中心”的闭式解。
  3. 单调性：两步都使 $J$ 不增 ⇒ 收敛；但 $J$ 非凸 ⇒ 收敛到局部最优。对策：多次随机初始化 + 选最小 $J$；或用 K-Means++ 初始化（让初始质心彼此远离）。
  4. 如何选 K：肘部法则（画 $J$ vs $K$，找拐点）；或根据下游任务/业务约束选择。
  5. 与 EM 的关系：K-Means 是 GMM 的 EM 在“硬指派 + 单位协方差”下的极限特例（$w_j^{(i)}$ 变成 0/1）。

算法伪代码与逻辑解说：GMM 的 EM

伪代码

输入:
    - 数据 X (m×d)，簇数 K（高斯数），最大迭代 max_iters，收敛阈值 epsilon

输出:
    - 混合权重 phi_1..phi_K，均值 mu_j，协方差 Sigma_j

1. 初始化 phi, mu, Sigma（如 K-Means 结果作为 mu 初值）
2. 循环 iter = 1..max_iters:
    // —— E 步: 计算后验（软指派）——
    2.1 对每个 i, j:
        w_j^(i) = phi_j * N(x^(i); mu_j, Sigma_j) / Σ_l phi_l * N(x^(i); mu_l, Sigma_l)
    // —— M 步: 加权最大似然 ——
    2.2 phi_j = (1/m) Σ_i w_j^(i)
    2.3 mu_j = Σ_i w_j^(i) x^(i) / Σ_i w_j^(i)
    2.4 Sigma_j = Σ_i w_j^(i) (x^(i)-mu_j)(x^(i)-mu_j)^T / Σ_i w_j^(i)
    2.5 计算对数似然 ell；若 |ell_new - ell_old| < epsilon: 终止
3. 返回 (phi, mu, Sigma)

【算法逻辑解说】

  1. E 步 (Step 2.1)：$w_j^{(i)} = P(z^{(i)}=j \vert x^{(i)})$ 由贝叶斯规则得到——分子是“簇 $j$ 的先验 × 该簇高斯密度”，分母是归一化（全概率）。这是软版本的 K-Means 指派：不是 argmax 而是概率分布。
  2. M 步 (Step 2.2–2.4)：形式上与 GDA 的 MLE 相同，只是每个样本按 $w_j^{(i)}$ 加权——权重大（很可能属于簇 $j$）的样本对 $\mu_j, \Sigma_j$ 影响大。
  3. 收敛：EM 保证对数似然单调不减；实践中监控 $\ell$ 变化。初始化影响结果（局部最优），常用 K-Means 结果初始化 $\mu$。
  4. 为什么 EM 而非直接梯度：E/M 两步都有闭式解，无需选择学习率；且天然处理“软指派”的不确定性。对比：直接对 $\ell$ 做梯度上升也可行但更慢、更繁琐。
  5. 潜在变量视角：$z^{(i)}$ 是“看不见的簇标签”——EM 是“用期望补全隐藏信息再优化”的通用范式，L15 的因子分析、隐马尔可夫模型都复用此框架。

关键要点

  1. K-Means：硬聚类、坐标下降、保证收敛到局部最优；用多次初始化缓解。
  2. GMM：软聚类 + 密度估计；似然中 log 与求和纠缠导致无闭式解 → 引入 EM。
  3. EM = E 步（算后验/期望）+ M 步（最大化加权似然），单调提升似然下界（Jensen），收敛到局部最优。
  4. K-Means 是 EM 的硬指派极限特例；两者共享“指派-更新”的交替结构。
  5. 潜在变量建模是处理“数据生成过程含隐藏结构”的通用思想（贯穿无监督学习与后续模型）。

常见误区与注意事项

  • K-Means 假设球形簇：基于欧氏距离的均值，对细长/异形簇效果差（各向异性协方差的 GMM 更合适）。
  • K-Means 前不标准化特征：量纲差异直接扭曲距离计算。
  • EM 收敛到局部最优就罢手：应多次随机初始化选最高似然；单次运行结果不可靠。
  • 协方差奇异（某簇样本少于维度）：$\Sigma_j$ 不可逆导致 $N(x;\mu_j,\Sigma_j)$ 溢出——加小对角项（$\Sigma_j + \epsilon I$）或限制协方差结构（对角/共享）。
  • 混淆 E 步与 M 步：E 步是概率计算（固定参数算后验），M 步是参数更新（固定后验优化参数）——两者角色不可颠倒。
  • 忽视 log 空间：GMM 的 $w_j^{(i)}$ 计算涉及指数与归一化，务必在 log 空间计算后验再 exp（防下溢）。

思考题

  1. 问题：为什么 GMM 的似然函数无法像单高斯那样闭式求解，而 EM 可以绕过？
    • 答案：单高斯 $\log \prod_i \mathcal{N}(x^{(i)};\mu,\Sigma)$ 中 log 直接作用在每个高斯密度上，求导闭式可得。GMM 的 $\log \prod_i \sum_j \phi_j \mathcal{N}(\cdot)$ 中 log 在混合求和之外，求导后 $\mu_j$ 的方程与所有簇的 $z$ 纠缠，无法解耦。EM 用 E 步的期望把“每个样本对每个簇的归属”固定下来，使 M 步退化为可闭式求解的加权 MLE。
  2. 问题：EM 每轮迭代保证 $\ell(\theta^{new}) \ge \ell(\theta^{old})$，请用 Jensen 不等式直观解释。
    • 答案：定义下界 $\mathcal{L}(\theta) = \sum_i \sum_z Q_i(z)\log\frac{p(x^{(i)},z;\theta)}{Q_i(z)}$，因 $\log$ 是凹函数，Jensen 给出 $\ell(\theta) \ge \mathcal{L}(\theta)$。E 步选 $Q_i(z) = P(z\vert x^{(i)};\theta^{old})$ 使 $\mathcal{L}(\theta^{old}) = \ell(\theta^{old})$（下界紧）；M 步最大化 $\mathcal{L}$ 得 $\theta^{new}$ ⇒ $\ell(\theta^{new}) \ge \mathcal{L}(\theta^{new}) \ge \mathcal{L}(\theta^{old}) = \ell(\theta^{old})$。
  3. 问题：K-Means 与 GMM 的 EM 有何异同？什么场景下 GMM 明显优于 K-Means？
    • 答案：相同：交替“指派（E）+ 更新（M）”，都收敛到局部最优。不同：K-Means 硬指派 0/1、无概率输出、假设簇为“球”；GMM 软指派概率、估计密度 $P(x)$、协方差可各向异性。场景：需要不确定性估计（软指派）、密度估计/异常检测（$P(x)$ 阈值）、簇形状不规则时，GMM 胜出；大规模高维数据上 K-Means 更快更简单。