4.3 拉普拉斯平滑

拉普拉斯平滑

在朴素贝叶斯算法中，我们以邮件分类器为例介绍了文本分类问题。当时我们将整个字典储存起来作为词汇表。但实际上这种做法效率不高。更高效的做法是设定一个常用词汇表，只存储一定量的常用单词。但若遇到词汇表之外的生词，该怎么办呢？

首先，我们分析一下遇到生词会导致什么问题。回顾垃圾邮件分类过程：假设你完成了 CS229 课程并做了出色的研究项目，决定在 20xx 年 6 月将作品投稿到 NeurIPS 会议（机器学习领域的顶级会议，投稿截止日期通常在六月底至七月初）。你通过邮件讨论了该会议，随后开始收到包含 "neurips" 单词的邮件。然而，这是你的第一篇 NeurIPS 投稿，此前从未收到过包含 "neurips" 的邮件；更重要的是，"neurips" 这个词从未出现在你的垃圾邮件 / 正常邮件训练集中。假设 "neurips" 是词汇表中的第 35000 个词，那么朴素贝叶斯分类器对该参数 ${\varphi }_{35000|y}$ 的最大似然估计结果如下：

$$\begin{array}{rl}{\varphi }_{35000|y=1}& =\frac{\sum _{i=1}^{m}1\{x_{35000}^{(i)}=1\wedge y^{(i)}=1\}}{\sum _{i=1}^{m}1\{y^{(i)}=1\}}=0\\ {\varphi }_{35000|y=0}& =\frac{\sum _{i=1}^{m}1\{x_{35000}^{(i)}=1\wedge y^{(i)}=0\}}{\sum _{i=1}^{m}1\{y^{(i)}=0\}}=0\end{array}$$

由于分类器从未在垃圾邮件或正常邮件的训练样本中见过 "neurips" 这个词，它认为该词出现在两类邮件中的概率均为 $0$。因此，当需要判断一封包含 "neurips" 的邮件是否为垃圾邮件时，算法计算后验概率得到：

$$\begin{array}{rl}p(y=1|x)& =\frac{\prod _{i=1}^{n}p(x_i|y=1)p(y=1)}{\prod _{i=1}^{n}p(x_i|y=1)p(y=1)+\prod _{i=1}^{n}p(x_i|y=0)p(y=0)}\\ & =\frac{0}{0}\end{array}$$

问题在于 $\prod _{i=1}^{n}p(x_i|y)$ 中包含了 $p(x_{35000}|y)=0$，导致整个乘积为 $0$。因此算法得到 $\frac{0}{0}$，无法做出预测。

根本原因在于统计学中常将未观测到的事件的概率估计为 $0$，从而导致了 $\frac{0}{0}$ 的情况。为避免此问题，我们引入拉普拉斯平滑 (Laplace smoothing)，用一个小概率值替代零概率。具体来说，假设要估计一个在 $\{1,...,k\}$ 范围内取值的多项式随机变量 $z$ 的参数 ${\varphi }_i=p(z=i)$。给定 $m$ 个独立观测样本 $\{z^{(1)},...,z^{(m)}\}$，最大似然估计经拉普拉斯平滑后变为：

$${\varphi }_j=\frac{\sum _{i=1}^{m}1\{z^{(i)}=j\}+1}{m+k}$$

此处，分子加 $1$，分母加 $k$。需注意 $\sum _{j=1}^k{\varphi }_j=1$ 仍然成立（这是概率估计的必要性质）。同时，所有 ${\varphi }_j$ 都不为零，从而解决了零概率问题。在某些条件下，拉普拉斯平滑可被证明能给出参数 ${\varphi }_j$ 的良好估计。

回到朴素贝叶斯分类器，应用拉普拉斯平滑后，参数估计公式修正如下：

$$\begin{array}{rl}{\varphi }_{j|y=1}& =\frac{\sum _{i=1}^{m}1\{x_j^{(i)}=1\wedge y^{(i)}=1\}+1}{\sum _{i=1}^{m}1\{y^{(i)}=1\}+2}\\ {\varphi }_{j|y=0}& =\frac{\sum _{i=1}^{m}1\{x_j^{(i)}=1\wedge y^{(i)}=0\}+1}{\sum _{i=1}^{m}1\{y^{(i)}=0\}+2}\end{array}$$

（实践中，通常无需对 ${\varphi }_y$ 进行拉普拉斯平滑，因为垃圾邮件与非垃圾邮件的比例通常是合理可估计的，${\varphi }_y$ 作为 $p(y=1)$ 的估计值通常不会接近零。）

文本分类的事件模型（Event Models for Text Classification）

接下来介绍文本分类的另一种模型。朴素贝叶斯算法已能解决许多分类问题，但还有一种相关算法在文本分类上表现更优。

在之前针对文本分类的朴素贝叶斯方法中，我们使用的是多元伯努利事件模型（Multi-Variate Bernoulli Event Model）。在该模型中，假设邮件是否发送由随机过程决定（先验概率 $p(y)$）。然后，发件人（无论是否垃圾邮件发送者）独立地遍历词汇表，依据概率分布 $p(x_i=1|y)={\varphi }_{i|y}$ 决定是否将每个词 $i$ 包含在邮件中。因此，收到一封垃圾邮件的概率为：$p(y)\prod _{i=1}^{n}p(x_i|y)$。

另一种模型称为多项式事件模型（Multinomial Event Model）。为描述此模型，需使用不同的特征表示方法：令 $x_i$ 表示邮件中的第 $i$ 个单词。因此，$x_i$ 是一个整数，取值范围为 $\{1,...,|V|\}$，其中 $|V|$ 是词汇表的大小。一封包含 $n$ 个单词的邮件可表示为一个长度为 $n$ 的向量 $(x_1,x_2,...,x_n)$；注意，不同邮件的 $n$ 值可以不同。例如，邮件开头是 "A NIPS ..."，则 $x_1=1$ ("a" 是词汇表第一个词)，$x_2=35000$ (假设 "nips" 是词汇表第 35000 个词)。

在多项式事件模型中，假设邮件生成过程如下：首先确定是否为垃圾邮件（依据 $p(y)$，与前模型相同）。接着，发件人依据多项式分布 $p(x_1|y)$ 生成第一个词 $x_1$。然后，独立于 $x_1$ 地依据相同的多项式分布生成 $x_2$，再生成 $x_3$、$x_4$，依此类推，直至生成邮件所有词。因此，邮件的整体概率为 $p(y)\prod _{i=1}^{n}p(x_i|y)$。虽然此公式形式与多元伯努利模型相似，但含义截然不同：此处的 $x_i|y$ 服从多项式分布，而非伯努利分布。

新模型的参数仍然是 ${\varphi }_y=p(y)$（与前相同），以及 ${\varphi }_{k|y=1}=p(x_j=k|y=1)$ 和 ${\varphi }_{k|y=0}=p(x_j=k|y=0)$（对任意位置 $j$）。注意，我们假设 $p(x_j|y)$ 的值与位置 $j$ 无关，即单词的生成分布不依赖于其在邮件中的位置（词袋模型假设的一种体现）。

给定训练集 $\{(x^{(i)},y^{(i)});i=1,...,m\}$，其中 $x^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_{n_i}^{(i)})$（$n_i$ 是第 $i$ 个样本的单词数），数据的似然函数为：

$$\begin{array}{rl}\mathcal{L}({\varphi }_y,{\varphi }_{k|y=0},{\varphi }_{k|y=1})& =\prod _{i=1}^{m}p(x^{(i)},y^{(i)})\\ & =\prod _{i=1}^m(\prod _{j=1}^{n_i}p(x_j^{(i)}|y^{(i)};{\varphi }_{k|y=0},{\varphi }_{k|y=1}))p(y^{(i)};{\varphi }_y)\end{array}$$

最大化该似然函数得到参数的最大似然估计：

$$\begin{array}{rl}{\varphi }_{k|y=1}& =\frac{\sum _{i=1}^m\sum _{j=1}^{n_i}1\{x_j^{(i)}=k\wedge y^{(i)}=1\}}{\sum _{i=1}^{m}1\{y^{(i)}=1\}{n}_i}\\ {\varphi }_{k|y=0}& =\frac{\sum _{i=1}^m\sum _{j=1}^{n_i}1\{x_j^{(i)}=k\wedge y^{(i)}=0\}}{\sum _{i=1}^{m}1\{y^{(i)}=0\}{n}_i}\\ {\varphi }_y& =\frac{\sum _{i=1}^{m}1\{y^{(i)}=1\}}{m}\end{array}$$

若应用拉普拉斯平滑（实践中用于提升性能）估计 ${\varphi }_{k|y=0}$ 和 ${\varphi }_{k|y=1}$，在分子加 $1$，分母加 $|V|$，得到：

$$\begin{array}{rl}{\varphi }_{k|y=1}& =\frac{\sum _{i=1}^m\sum _{j=1}^{n_i}1\{x_j^{(i)}=k\wedge y^{(i)}=1\}+1}{\sum _{i=1}^{m}1\{y^{(i)}=1\}{n}_i+|V|}\\ {\varphi }_{k|y=0}& =\frac{\sum _{i=1}^m\sum _{j=1}^{n_i}1\{x_j^{(i)}=k\wedge y^{(i)}=0\}+1}{\sum _{i=1}^{m}1\{y^{(i)}=0\}{n}_i+|V|}\end{array}$$

当然，这未必是最优的分类算法，但朴素贝叶斯分类器在实践中往往表现优异。因此，它因其简单、易于实现而成为一个很好的首选方案。