ML1-10 朴素贝叶斯

1. 引入 Naive Bayes

在 GDA 中，特征向量 $x$ 是连续的实值向量（$x_j$ 取连续实数，因为选择了多元高斯分布进行建模）。我们接下来要讨论一个不同的学习算法，其中 $x_j$ 是离散的。

引用

我们考虑使用机器学习构建电子邮件垃圾邮件过滤器的例子。这里，我们希望根据邮件是未经请求的商业邮件（垃圾邮件）还是非垃圾邮件来分类消息。在学习到这一点之后，我们可以让邮件阅读器自动过滤掉垃圾邮件，也许将它们放在一个单独的邮件文件夹中。

假设我们有一个训练集（即一组打好标签的电子邮件，分为垃圾邮件或者非垃圾邮件），我们通过指定用于表示电子邮件的特征 $x_j$ 来构建过滤器。

我们通过特征向量 $x$ 来表示一封电子邮件，该向量的长度等于字典中的单词数量。具体地，如果一封电子邮件包含字典中的第 $j$ 个单词，那么设 $x_j=1$ ，否则 $x_j=0$。例如：

$$x = \begin{bmatrix}1 \\ 0 \\ 0 \\ \vdots \\ 1 \\ \vdots \\ 0\end{bmatrix} \begin{matrix}\text{a} \\ \text{aardvark} \\ \text{aardwolf} \\ \vdots \\ \text{buy} \\ \vdots \\ \text{zygmurgy}\end{matrix}$$

用于表示一封包含单词"a"和"buy"但不包含"aardvark"、"aardwolf"或"zygmurgy"的电子邮件。编码进特征向量中的单词集合称为词汇表（vocabulary），所以向量的维度跟词汇表的大小是一致的。

选择了特征向量之后，现在我们想要去构建一个生成模型。因此，我们需要对 $p(x|y)$ 进行建模。但是，若我们有一个包含 50000 个词汇的 vocabulary 的话，那么 $x \in \{0, 1\}^{50000}$ （$x$ 是一个 50000 维的 01 向量）。如果不对各个特征之间的关系作任何结构假设，而直接显式建模整个 $p(x|y)$，由于 $x \in \{0, 1\}^{50000}$，那么 $x$ 共 $2^{50000}$ 种可能，这显然是无法建模的。

为了对 $p(x|y)$ 建模，我们将做出一个非常强的假设，称为朴素贝叶斯 NB 假设（NB assumption）：在给定 $y$ 下，$x_i$ 是条件独立的。 由该假设得到的算法称为朴素贝叶斯分类器。例如，我们知道某个特定的邮件其 $y = 1$ （代表它是一个垃圾邮件），"buy"是第 2087 个单词，"price"是第 39831 个单词。那么，知道 $x_{2087}$ 不会影响我们对 $x_{39831}$ 的信念（知道"buy"是否出现在消息中不影响我们对"price"是否出现的信念），即：

$$p(x_{2087} | y) = p(x_{2087} | y, x_{39831})$$

注意，这与说 $x_{2087}$ 与 $x_{39831}$ 独立不同，后者应该写为 $p(x_{2087}) = p(x_{2087} | x_{39831})$ 。

现在我们就可以得到：

$$\begin{aligned}p(x_1, \ldots, x_{50000} | y) &= p(x_1|y) p(x_2|y, x_1) p(x_3|y, x_1, x_2) \cdots p(x_{50000}|y, x_1, \ldots, x_{49999}) \\&= p(x_1|y) p(x_2|y) p(x_3|y) \cdots p(x_{50000}|y) \\&= \prod_{j=1}^{d} p(x_j | y)\end{aligned}$$

第一个等式简单地来自概率的通常性质，第二个等式使用了 NB 假设。我们注意到，尽管朴素贝叶斯假设是一个极强的假设，但得到的算法在许多问题上效果很好。

提示

为了构建生成模型，GDA 和 NB 方法都尝试对 $p(x|y)$ 进行建模。

• GDA 假设 $p(x|y)$ 服从多元高斯分布
• NB 假设各个 $x_j$ 在给定 $y$ 后条件独立，即 $p(x|y) = \prod_{j=1}^{d} p(x_j | y)$

这两种假设都能很好地用有限参数描述 $p(x|y)$。

根据 NB 假设，使用以下参数来参数化我们的模型：

$\phi_{j|y=1} = p(x_j = 1 | y = 1)$、$\phi_{j|y=0} = p(x_j = 1 | y = 0)$ 以及 $\phi_y = p(y = 1)$

和之前一样，我们给定训练集 $\{(x^{(i)}, y^{(i)}); i = 1, \ldots, n\}$，可以写出数据的联合似然：

$$L(\phi_y, \phi_{j|y=0}, \phi_{j|y=1}) = \prod_{i=1}^n p(x^{(i)}, y^{(i)})$$

部分推导：

$$\mathcal{L}=\prod_{i=1}^{n}p(x^{(i)},y^{(i)})=\prod_{i=1}^{n}p(y^{(i)})p(x^{(i)}\mid y^{(i)})=\prod_{i=1}^{n}p(y^{(i)})\prod_{j=1}^{d}p(x_j^{(i)}\mid y^{(i)})=\prod_{i=1}^{n}\left[\phi_y^{y^{(i)}}(1-\phi_y)^{1-y^{(i)}}\prod_{j=1}^{d}\left(\phi_{j\mid y=1}^{x_j^{(i)}}(1-\phi_{j\mid y=1})^{1-x_j^{(i)}}\right)^{y^{(i)}}\left(\phi_{j\mid y=0}^{x_j^{(i)}}(1-\phi_{j\mid y=0})^{1-x_j^{(i)}}\right)^{1-y^{(i)}}\right]$$

（p.s. 单个 $x_j|y$ 满足伯努利分布）

直接给出关于 $\phi_y$ 、$\phi_{j|y=0}$ 以及 $\phi_{j|y=1}$ 在取得最大似然估计时的取值：

$$\phi_{j|y=1} = \frac{\sum_{i=1}^n 1\{x_j^{(i)} = 1 \land y^{(i)} = 1\}}{\sum_{i=1}^n 1\{y^{(i)} = 1\}}$$

$$\phi_{j|y=0} = \frac{\sum_{i=1}^n 1\{x_j^{(i)} = 1 \land y^{(i)} = 0\}}{\sum_{i=1}^n 1\{y^{(i)} = 0\}}$$

$$\phi_y = \frac{\sum_{i=1}^n 1\{y^{(i)} = 1\}}{n}$$

这些参数具有非常自然的解释。例如，$\phi_{j|y=1}$ 正好是含单词 $j$ 的垃圾邮件占总垃圾邮件数的比例。

在拟合了所有这些参数之后，要对一个具有特征 $x$ 的新样本进行预测，我们只需计算：

$$p(y=1|x) = \frac{p(x|y=1)p(y=1)}{p(x)} = \frac{(\prod_{j=1}^d p(x_j|y=1)) p(y=1)}{(\prod_{j=1}^d p(x_j|y=1)) p(y=1) + (\prod_{j=1}^d p(x_j|y=0)) p(y=0)}$$

并选择后验概率较大的类别（此处是二分类，只有 $y$ 取 0,1 的两种情况）。

最后，我们注意到，虽然我们主要针对特征 $x_j$ 是二值的情况探讨了朴素贝叶斯算法，但推广到 $x_j$ 可以取 $\{1, 2, \ldots, k_j\}$ 中的值也是直接的。这里，我们只需将 $p(x_j|y)$ 建模为多项分布而非伯努利分布。实际上，即使某些原始输入属性（比如我们之前例子中房屋的居住面积）是连续的，通常的做法是将其离散化——即将其转化为一组小的离散值——然后应用朴素贝叶斯。例如，如果我们使用某个特征 $x_j$ 来表示居住面积，我们可以将连续值离散化如下：

因此，对于一栋居住面积为 890 平方英尺的房子，我们会将相应特征 $x_j$ 的值设为 3。然后我们可以应用朴素贝叶斯算法，并使用多项分布对 $p(x_j|y)$ 建模。当原始的连续值属性不能很好地用多元正态分布建模时，离散化特征并使用朴素贝叶斯（而不是 GDA）通常会产生更好的分类器。

2. 拉普拉斯平滑

我们描述的朴素贝叶斯算法在许多问题上效果相当好，但有一个简单的修改可以使其工作得更好，特别是对于文本分类问题。让我们简要讨论当前形式算法的一个问题，然后讨论如何修复它。

引用

考虑垃圾邮件/电子邮件分类，假设在公元 20xx 年，完成 CS229 并在项目中做了出色工作后，你决定在 20xx 年 5 月左右将你的工作提交给 NeurIPS 会议发表。因为你最终在电子邮件中讨论了这个会议，你也开始收到包含单词"neurips"的消息。但这是你的第一篇 NeurIPS 论文，在此之前，你从未见过任何包含"neurips"的电子邮件；特别是"neurips"从未出现在你的训练集（垃圾/非垃圾邮件）中。

假设"neurips"是字典中的第 35000 个单词，你的朴素贝叶斯垃圾邮件过滤器对参数 $\phi_{35000|y}$ 的最大似然估计为：

$$\phi_{35000|y=1} = \frac{\sum_{i=1}^n 1\{x_{35000}^{(i)} = 1 \land y^{(i)} = 1\}}{\sum_{i=1}^n 1\{y^{(i)} = 1\}} = 0$$

$$\phi_{35000|y=0} = \frac{\sum_{i=1}^n 1\{x_{35000}^{(i)} = 1 \land y^{(i)} = 0\}}{\sum_{i=1}^n 1\{y^{(i)} = 0\}} = 0$$

也就是说，因为在垃圾邮件或非垃圾邮件的训练样本中从未见过"neurips"，它认为在任何类型的邮件中看到它的概率都为零。因此，当尝试判断包含"neurips"的消息是否为垃圾邮件时，它计算类别后验概率，得到：

$$p(y=1|x) = \frac{\prod_{j=1}^d p(x_j|y=1)p(y=1)}{\prod_{j=1}^d p(x_j|y=1)p(y=1) + \prod_{j=1}^d p(x_j|y=0)p(y=0)} = \frac{0}{0}$$

这是因为每一项 $\prod_{j=1}^d p(x_j|y)$ 都包含一个因子 $p(x_{35000}|y) = 0$。因此，我们的算法得到 0/0，不知道如何进行预测。

更广泛地说，仅仅因为你在有限的训练集中没有见过某个事件，就将其概率估计为零，这在统计上是一个坏主意。考虑估计一个取值为 $\{1, \ldots, k\}$ 的多项随机变量 $z$ 的均值问题。我们可以用 $\phi_j = p(z = j)$ 来参数化多项分布。给定一组 $n$ 个独立观测 $\{z^{(1)}, \ldots, z^{(n)}\}$，最大似然估计由下式给出：

$$\phi_j = \frac{\sum_{i=1}^n 1\{z^{(i)} = j\}}{n}$$

正如我们之前看到的，如果使用这些最大似然估计，某些 $\phi_j$ 可能最终为零，这就成了一个问题。为了避免这种情况，我们可以使用拉普拉斯平滑（Laplace smoothing），它将上述估计替换为：

$$\phi_j = \frac{1 + \sum_{i=1}^n 1\{z^{(i)} = j\}}{k + n}$$

这里，我们在分子中加 $1$，在分母中加 $k$。为了解释上述式子，我们来引入下述视角。

2.1 从 MLE 到 MAP 的视角

我们在之前的文章中已经提到 MLE 和 MAP 方法。MAP 即 Maximum A Posteriori，最大后验概率。为了引入该视角，这里再次重新介绍一下。

• MLE paradigm：找到参数，使得在参数下所呈现的数据是最似然的
• MAP paradigm：找到参数，使得在给定的数据下是最可能的参数值

MLE 的一个缺点是，它只能最好地解释我们已经看到的数据，并不会尝试去推广到没见过的数据。而在 MAP 里，我们会把我们对于参数的先验信念加进去，然后根据已经看到的数据，来更新我们对参数的后验信念。

正式地说，对于独立同分布 $i.i.d.$ 随机变量 $X_1, X_2, \dots, X_n$：

$$\begin{aligned} \theta_{\text{MAP}} &= \mathop{\arg\max}_{\theta} f(\theta \mid X_1,X_2,\dots,X_n) \\ &= \mathop{\arg\max}_{\theta} \frac{f(X_1,X_2,\dots,X_n \mid \theta)\,g(\theta)}{h(X_1,X_2,\dots,X_n)} \end{aligned}$$

注意两点：第一，假设数据是独立同分布的，所以我们可以分解给定 $\theta$ 时数据的密度。第二，分母相对于 $\theta$ 是一个常数。因此，它的值不影响 $arg max$，我们可以把那一项去掉。用数学表示如下，之后可以使用对数法进行求解：

$$\begin{aligned} \theta_{\text{MAP}} &= \mathop{\arg\max}_{\theta} \frac{\prod_{i=1}^{n} f(X_i \mid \theta)\,g(\theta)}{h(X_1,X_2,\dots,X_n)} \qquad \text{Since the samples are IID}\\ &= \mathop{\arg\max}_{\theta} \prod_{i=1}^{n} f(X_i \mid \theta)\,g(\theta) \qquad \text{Since } h \text{ is constant with respect to } \theta \end{aligned}$$

即

$$\theta_{\text{MAP}} = \mathop{\arg\max}_{\theta} \left( \log(g(\theta)) + \sum_{i=1}^{n} \log(f(X_i \mid \theta)) \right)$$

用贝叶斯术语来说，MAP 估计就是 $\theta$ 的后验分布的众数（mode，即分布取最大值的位置）。如果你把这个方程和 MLE 方程并排放在一起看，你会发现 MAP 就是完全相同的那个函数再加上一个先验对数的项之后，取 $arg max$。

为了进行 MAP 估计，我们需要为每个不同的参数找到合理的分布。比如说，如果你要预测一个泊松分布，那么 $\lambda$ 的先验应该用什么样的随机变量类型才合适呢？

对于先验分布，有一个理想的要求是：得到的后验分布和先验分布具有相同的函数形式。我们把这样的先验叫作共轭先验（相关概念可以参见指数族相关章节）。在需要反复更新信念很多次的情况下，共轭先验会让数学公式的编程实现容易得多。

下面是一份不同参数及其先验最常用分布的列表：

这里介绍对于多项分布参数 $p_i$，采用狄利克雷分布先验的场景。一个服从狄利克雷分布的随机变量 $X$ ，满足 $X \sim Dir(a_1, a_2, \dots, a_m)$。这个分布的概率密度函数如下，其中 $K$ 是一个归一化常数。

$$f(X_1 = x_1,X_2 = x_2,\dots,X_m = x_m) = K \prod_{i=1}^{m} x_i^{a_i-1}$$

如何理解狄利克雷分布的超参数：想象我们在看到真实数据之前，已经看到了 $\sum^m_{i=1}a_i - m$ 次虚拟试验。在这些试验中，得到了 $(a_i-1)$ 次值为 $i$ 的结果。

举个例子，考虑估计一个六面偏斜骰子（每一面图案不同）掷出不同数字的概率。我们将通过反复掷这个骰子 $n$ 次来估计每一面被掷出的概率。这会产生 $n$ 个独立同分布的样本。对于 MAP 范式，我们需要对每个参数 $p_1, \dots, p_6$ 的信念设定一个先验。我们想表达的是，我们略微相信每一次投掷的可能性是相等的。

在开始掷骰子之前，我们先想象一下：假设已经掷了六次骰子，而且每个面都出现了一次。这样一来，先验分布就是 $Dir(2,2,2,2,2,2)$。在观察到 $n_1 + n_2 + \dots + n_6$次新的试验、其中结果 $i$ 出现了 $n_i$ 次之后，通过贝叶斯更新，得到后验分布为 $Dir(2 + n_1,\dots,2 + n_6)$。

用一个先验来表示对每个结果的一次想象观测，这种做法也叫做“拉普拉斯平滑”，它能保证你的概率不会出现 0 或 1 。

对于一个多项随机变量，拉普拉斯估计是

$$p_i=\frac{X_i+1}{n+m}$$

其中 $i = 1,\dots,m$ ，而 $n$ 是你实际实验中的试验次数。分子 $+1$ 可理解为对某类情况的“虚拟观测”，分母 $+m$ 可理解为共有 $m$ 类情况，每类都被“虚拟观测“一次。我们可以与 MLE 估计进行对比：

$$p_i = \frac{X_i}{n}$$

2.2 平滑后的 NB

回到应用拉普拉斯平滑后的 $\phi_j$：

$$\phi_j = \frac{1 + \sum_{i=1}^n 1\{z^{(i)} = j\}}{k + n}$$

注意 $\sum_{j=1}^k \phi_j = 1$ 仍然成立，这是一个理想的性质，因为 $\phi_j$ 是必须总和为 1 的概率估计。同时，对于所有 $j$ ，已经有 $\phi_j \neq 0$ ，这解决了概率被估计为零的问题。在某些（可以说相当强的）条件下，可以证明拉普拉斯平滑实际上给出了 $\phi_j$ 的最优估计。

回到朴素贝叶斯分类器，同样使用拉普拉斯平滑，我们还得到以下参数估计：

$$\phi_{j|y=1} = \frac{1 + \sum_{i=1}^n 1\{x_j^{(i)} = 1 \land y^{(i)} = 1\}}{2 + \sum_{i=1}^n 1\{y^{(i)} = 1\}}$$

$$\phi_{j|y=0} = \frac{1 + \sum_{i=1}^n 1\{x_j^{(i)} = 1 \land y^{(i)} = 0\}}{2 + \sum_{i=1}^n 1\{y^{(i)} = 0\}}$$

在实践中，是否对 $\phi_j$ 应用拉普拉斯平滑通常并不重要，因为我们通常有相当比例的垃圾邮件和非垃圾邮件，所以 $\phi_j$ 将是 $p(y=1)$ 的合理估计，而且距离 0 很远。

3. 文本分类的事件模型

为了结束我们对生成学习算法的讨论，我们再谈一个专门用于文本分类的模型。虽然我们前面介绍过的朴素贝叶斯在许多分类问题上都表现不错，但在文本分类方面，有一个相关的模型表现得更好。

3.1 Bernoulli event model

在文本分类的具体情境下，我们之前引入的朴素贝叶斯使用所谓的伯努利事件模型（有时称为多变量伯努利事件模型）。这个模型主要看邮件中的某词有没有出现。我们假设一个电子邮件是这样生成的：

1. 随机决定（根据类先验概率 $p(y)$）下一个给你发消息的是垃圾邮件发送者还是非垃圾邮件发送者，即确定类别 $y$。
2. 开始遍历整个词典。假设词典有 $d$ 个词，对第 $j$ 个词，判断它是否出现在该邮件中。$x_j \in \{0,1\}$ ，1 表示出现，0 表示没出现。出现的概率由类别决定，即 $p(x_j=1|y) = \phi_{j|y}$ 。
3. 根据 NB 假设，给定 $y$ 以后，各个词是否出现是彼此独立的。所以有 $p(x, y) = p(y) \prod_{j=1}^d p(x_j|y)$

注意，在该事件模型下，一篇文本表示成一个固定长度的 0/1 向量，即

$$\boldsymbol{x} = (x_1,\dots,x_V), \quad x_j \in \{0,1\}$$

$x_j$ 表示词表中的第 $j$ 个词在文本中有没有出现。

3.2 Multinomial event model

另一种事件模型，称为多项事件模型。在多项事件模型中，我们假设电子邮件是通过一个随机过程生成的：

1. 首先（与之前一样）根据 $p(y)$ 决定是垃圾邮件/非垃圾邮件，确定类别 $y$。
2. 开始按照位置生成单词。假设邮件一共有 $d$ 个词，从某个关于单词的多项分布（ $p(x_1|y)$ ）中生成 $x_1$。接下来，第二个单词 $x_2$ 与 $x_1$ 独立，但从相同的多项分布中选择，类似地生成后续单词，直到直到电子邮件的所有 $d$ 个词都被生成。
3. 根据 NB 假设，给定 $y$ 以后，$x_j$ 彼此独立。所以有 $p(x, y) = p(y) \prod_{j=1}^d p(x_j|y)$

注意，上面的公式看起来与伯努利事件模型下一封消息的概率公式相同，但公式中的项现在意味着非常不同的东西。特别是，$x_j|y$ 现在是多项分布，而不是伯努利分布。

在该事件模型下，一篇长度为 $d$ 的文本表示成一个长度为 $d$ 的向量 $(x_1, x_2, \ldots, x_d)$ 表示：

$$\boldsymbol{x} = (x_1,\dots,x_d),\quad x_j \in \{1,\dots,V\}$$

注意不同文本的 $d$ 可以是不同的。$x_j$ 表示电子邮件中第 $j$ 个位置的词的身份，其值表示是词表中的哪个词。

我们新模型的参数与之前一样：

$\phi_y = p(y)$
$\phi_{k|y=1} = p(x_j = k | y = 1)$
$\phi_{k|y=0} = p(x_j = k | y = 0)$

注意，我们假设 $p(x_j|y)$ 对所有 $j$ 都相同（即，生成单词的分布不依赖于其在电子邮件中的位置 $j$ ）。

如果我们有一个训练集 $\{(x^{(i)}, y^{(i)}); i = 1, \ldots, n\}$，其中 $x^{(i)} = (x_1^{(i)}, x_2^{(i)}, \ldots, x_{d_i}^{(i)})$ （这里 $d_i$ 是第 $i$ 个训练样本中的单词数量），数据的似然由下式给出：

$$L(\phi_y, \phi_{k|y=0}, \phi_{k|y=1}) = \prod_{i=1}^n p(x^{(i)}, y^{(i)}) = \prod_{i=1}^n \left( \prod_{j=1}^{d_i} p(x_j^{(i)} | y; \phi_{k|y=0}, \phi_{k|y=1}) \right) p(y^{(i)}; \phi_y)$$

最大化这个似然得到参数的最大似然估计：

$\phi_{k|y=1} = \frac{\sum_{i=1}^n \sum_{j=1}^{d_i} 1\{x_j^{(i)} = k \land y^{(i)} = 1\}}{\sum_{i=1}^n 1\{y^{(i)} = 1\} d_i}$
$\phi_{k|y=0} = \frac{\sum_{i=1}^n \sum_{j=1}^{d_i} 1\{x_j^{(i)} = k \land y^{(i)} = 0\}}{\sum_{i=1}^n 1\{y^{(i)} = 0\} d_i}$
$\phi_y = \frac{\sum_{i=1}^n 1\{y^{(i)} = 1\}}{n}$

如果我们在估计 $\phi_{k|y=0}$ 和 $\phi_{k|y=1}$ 时应用拉普拉斯平滑（在实际中为了良好性能需要这样做），我们在分子中加 1，在分母中加 $|V|$，得到：

$\phi_{k|y=1} = \frac{1 + \sum_{i=1}^n \sum_{j=1}^{d_i} 1\{x_j^{(i)} = k \land y^{(i)} = 1\}}{|V| + \sum_{i=1}^n 1\{y^{(i)} = 1\} d_i}$
$\phi_{k|y=0} = \frac{1 + \sum_{i=1}^n \sum_{j=1}^{d_i} 1\{x_j^{(i)} = k \land y^{(i)} = 0\}}{|V| + \sum_{i=1}^n 1\{y^{(i)} = 0\} d_i}$

虽然不一定是绝对最好的分类算法，但朴素贝叶斯分类器通常工作得出奇地好。

参考

1. CS229 课程讲义

   https://cs229.stanford.edu/main_notes.pdf

2. Amann's Algorithm • CS229 • Native Bayes

   https://aman.ai/cs229/naive-bayes/

3. https://web.stanford.edu/class/archive/cs/cs109/cs109.1212/lectureNotes/LN22_map.pdf
4. https://web.stanford.edu/class/archive/cs/cs109/cs109.1212/lectureNotes/LN24_naive_bayes.pdf