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 6: Gaussian Discriminant Analysis. Naive Bayes, Laplace Smoothing

目录 · ← l5 · l7 →

Lecture 6: Gaussian Discriminant Analysis. Naive Bayes, Laplace Smoothing

概述

本讲转向生成式学习算法 (Generative Learning Algorithms)。与判别模型（逻辑回归直接建模 $P(y\vert x)$）不同，生成模型先建模每个类别的数据分布 $P(x\vert y)$，再用贝叶斯规则反推 $P(y\vert x)$。课程介绍两大生成算法：高斯判别分析 (GDA)（连续特征，假设各类别服从高斯分布）与朴素贝叶斯 (Naive Bayes)（离散/文本特征，假设特征条件独立），并给出拉普拉斯平滑解决零概率问题。

核心概念与数学直觉

  • 判别 vs 生成：
    • 判别模型：直接学习 $P(y\vert x)$ 或 $x \to y$ 的决策边界（逻辑回归、SVM、神经网络）。只关心边界，不关心数据如何产生。
    • 生成模型：学习 $P(x\vert y)$（各类别的分布）与 $P(y)$（先验），然后 $P(y\|x) = \frac{P(x\|y) P(y)}{P(x)} \propto P(x\|y) P(y)$（贝叶斯规则；$P(x)$ 对所有 $y$ 相同，可忽略）
    • 直观类比：判别模型像“只看轮廓就能区分猫狗”的边界；生成模型像“分别记住猫的长相分布和狗的长相分布，再比较新照片更像哪个”。
    • 何时生成更好：数据量少时（生成模型用更强的结构假设）、需要 $P(x)$（异常检测/生成样本）时；数据充足时判别模型通常更准（边界不需要精确建模分布）。
  • 高斯判别分析 (GDA)：假设 $y \sim \text{Bernoulli}(\phi)$，$x\vert y=0 \sim \mathcal{N}(\mu_0, \Sigma)$，$x\vert y=1 \sim \mathcal{N}(\mu_1, \Sigma)$（两类共享协方差 $\Sigma$）。
    • 参数：$\phi, \mu_0, \mu_1, \Sigma$，用 MLE 估计： $\phi = \frac{1}{m}\sum_i \mathbf{1}\{y^{(i)}=1\}, \quad \mu_k = \frac{\sum_i \mathbf{1}\{y^{(i)}=k\} x^{(i)}}{\sum_i \mathbf{1}\{y^{(i)}=k\}}, \quad \Sigma = \frac{1}{m}\sum_{i=1}^{m} (x^{(i)} - \mu_{y^{(i)}})(x^{(i)} - \mu_{y^{(i)}})^T$
      • $\phi$：类别 1 的先验比例；$\mu_k$：类别 $k$ 的样本均值；$\Sigma$：加权平均的类内协方差。
    • 决策边界：$P(y=1\vert x) = P(y=0\vert x)$ ⇒ 边界是二次曲面；当两类共享 $\Sigma$ 时退化为线性边界（与逻辑回归一致）。事实上可以证明：GDA 的假设蕴含逻辑回归的形式，但反之不成立——GDA 是更强的假设（高斯性），数据确实高斯时 GDA 更高效（需更少数据），假设不成立时逻辑回归更稳健。
    • 多分类 GDA：每类一个高斯（$\mu_j$ 各不同，$\Sigma$ 共享），Softmax 型决策。
  • 朴素贝叶斯 (Naive Bayes)：
    • 问题定义：文本分类等离散特征问题。特征 $x_j \in \{0,1\}$（如“词典中第 $j$ 个词是否出现”）。
    • 核心假设（朴素）：给定 $y$，各特征条件独立： $P(x_1, \dots, x_n \| y) = \prod_{j=1}^{n} P(x_j \| y)$
      • 直观解释：假设“出现‘银行’”与“出现‘贷款’”在已知是垃圾邮件后彼此独立——显然不真（相关词常共现），但该假设让参数数量从指数级降到线性级，实践中效果出奇地好。
    • 参数与 MLE：$\phi_{j\vert y=1} = P(x_j=1\vert y=1)$ 等： $\phi_{j\|y=1} = \frac{\sum_i \mathbf{1}\{x_j^{(i)}=1 \wedge y^{(i)}=1\}}{\sum_i \mathbf{1}\{y^{(i)}=1\}}, \quad \phi_y = \frac{\sum_i \mathbf{1}\{y^{(i)}=1\}}{m}$
    • 预测：$P(y=1\vert x) \propto P(y=1) \prod_j P(x_j\vert y=1)$，比较两个类别的得分。
    • 文本分类的变体：二元特征（词是否出现） vs 多项事件模型 (multinomial event model)（考虑词频，$x_j$ 是第 $j$ 个位置上的词，$x_j \in \{1..V\}$），后者用多项分布建模每个位置。
  • 拉普拉斯平滑 (Laplace Smoothing)：
    • 问题：若某个词 $x_j$ 从未在类别 $y=1$ 的训练样本中出现，MLE 得 $\phi_{j\vert y=1} = 0$ ⇒ 预测时 $\prod_j P(x_j\vert y=1)$ 整体为 0 ⇒ 模型武断否定该类。这是零概率问题。
    • 解法：给计数加 1： $\phi_{j\|y=1} = \frac{\sum_i \mathbf{1}\{x_j^{(i)}=1 \wedge y^{(i)}=1\} + 1}{\sum_i \mathbf{1}\{y^{(i)}=1\} + 2}$
      • 直觉：相当于假设“每个词在每个类别都至少预先见过一次”（伪计数）。对 $k$ 值特征：分子 $+1$、分母 $+k$（保证仍为合法概率分布）。$\phi_{j\vert y=1} + \phi_{j\vert y=0}$ 无需归一化问题——每类独立平滑。
    • 为什么有效：平滑只是贝叶斯先验的体现（均匀 Dirichlet 先验下的 MAP 估计）——再次呼应“先验/正则化”主线。

算法伪代码与逻辑解说：朴素贝叶斯（二元特征 + 拉普拉斯平滑）

伪代码

输入:
    - 训练集: m 个样本，每个样本 x^(i) ∈ {0,1}^n（n 个词特征），标签 y^(i) ∈ {0,1}

输出:
    - 参数: phi_y, phi_j|y=0, phi_j|y=1 (j = 1..n)
    - 分类器: 对新样本 x 输出 argmax_y P(y) * Π_j P(x_j|y)

训练阶段:
1. 统计: c1 = 样本中 y=1 的个数; c0 = m - c1
2. phi_y = (c1 + 1) / (m + 2)                    // 平滑后的先验
3. 对 j = 1..n:
    3.1 n11[j] = 样本中 (x_j=1 且 y=1) 的个数; n10[j] = (x_j=1 且 y=0) 的个数
    3.2 phi_j|y=1 = (n11[j] + 1) / (c1 + 2)      // 拉普拉斯平滑 (+1 分子, +2 分母)
    3.3 phi_j|y=0 = (n10[j] + 1) / (c0 + 2)
4. 保存所有 phi

预测阶段:
5. 对新样本 x:
    score_1 = log(phi_y) + Σ_{j: x_j=1} log(phi_j|y=1) + Σ_{j: x_j=0} log(1 - phi_j|y=1)
    score_0 = log(1 - phi_y) + Σ_{j: x_j=1} log(phi_j|y=0) + Σ_{j: x_j=0} log(1 - phi_j|y=0)
6. 返回 argmax(score_1, score_0)

【算法逻辑解说】

  1. 训练阶段本质是数数：朴素贝叶斯没有迭代优化——MLE 参数只是条件频率计数 + 平滑。这是它极快、极稳的原因。
  2. 拉普拉斯平滑的位置 (Step 3.2)：分子 $+1$ 保证“未见过的词”概率不为零；分母 $+2$ 保证 $\phi_{j\vert y} + (1-\phi_{j\vert y}) = 1$ 仍成立（二元特征）。
  3. 预测阶段用 log：连乘 $\prod_j$ 在 $n$ 大时下溢为 0；取对数把连乘变连加，数值稳定且单调性不变（$\arg\max$ 不变）。这在所有概率模型中都是标准工程技巧。
  4. 为什么条件独立假设是关键：若不独立，$P(x_1,\dots,x_n\vert y)$ 需 $2^n$ 个参数；独立假设下只需 $2n$ 个。参数爆炸与“维度灾难”由此缓解。

关键要点

  1. 判别模型建模 $P(y\vert x)$（边界），生成模型建模 $P(x\vert y)$ 再经贝叶斯规则反推——数据少、需 $P(x)$ 时生成模型占优。
  2. GDA 假设高斯：共享 $\Sigma$ 得线性边界；高斯假设成立时数据效率高于逻辑回归，不成立时逻辑回归更稳健。
  3. 朴素贝叶斯的核心是条件独立假设——用强假设换参数效率，文本分类中效果极佳。
  4. 拉普拉斯平滑解决零概率问题，本质是均匀先验下的 MAP 估计。
  5. 概率模型实现务必用 log 空间防下溢。

常见误区与注意事项

  • 混淆 GDA 与逻辑回归的适用性：GDA 更强假设、更少数据即可；数据量大且非高斯时逻辑回归更安全。经验法则：优先逻辑回归（稳健），数据极少且高斯假设合理时用 GDA。
  • 忽视平滑：不平滑的朴素贝叶斯遇到未登录词会直接输出 0 概率，分类完全失效。
  • 误以为条件独立假设“必须为真”：它几乎从不为真，但模型仍常工作良好（偏差小收益大）；只有当依赖关系对分类至关重要时才需更复杂模型。
  • 二元特征用词频模型：二元伯努利模型忽略词频信息；长文本分类用多项事件模型通常更好。
  • 对 GDA 的 $\Sigma$ 不共享：两类各用各的 $\Sigma$ 时决策边界变为二次——更灵活但参数翻倍、更易过拟合。

思考题

  1. 问题：证明当两类共享协方差时，GDA 的决策边界是线性的。
    • 答案：比较 $\log P(y=1\vert x)$ 与 $\log P(y=0\vert x)$，高斯密度中的二次项 $-\frac{1}{2}(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)$ 展开后 $x^T\Sigma^{-1}x$ 项在两类间抵消（$\Sigma$ 相同），仅剩 $x$ 的线性项与常数项 ⇒ $\log\frac{P(y=1\vert x)}{P(y=0\vert x)} = w^T x + b$，边界 $\{x: w^Tx+b=0\}$ 是超平面。
  2. 问题：训练集中类别 1 有 0 个样本包含词“比特币”，类别 0 有 5 个。不加平滑时预测含“比特币”的邮件会怎样？加平滑后呢？
    • 答案：不加平滑：$\phi_{\text{btc}\vert y=1} = 0$ ⇒ $P(x\vert y=1)$ 连乘为 0 ⇒ 该邮件被武断判为类别 0（即使其他特征强烈支持类别 1）。加平滑（$+1$）：$\phi = 1/(c_1+2)$，只略降该词贡献，分类由所有特征共同决定——更稳健。
  3. 问题：为什么朴素贝叶斯即使在条件独立假设明显不成立时仍表现良好？
    • 答案：分类只需 $\arg\max_y P(y)\prod_j P(x_j\vert y)$ 的排序正确，而不需概率值精确。独立假设带来的偏差在各类别间往往系统性相似（互相抵消），且它大幅降低方差（参数少）。偏差小幅上升换方差大幅下降——再次体现偏差-方差权衡。