9.2 朴素贝叶斯 (Naive Bayes)
我们将用一个机器学习算法的具体例子来激发我们对机器学习的讨论。让我们考虑构建垃圾邮件过滤器的常见问题，该过滤器将邮件分类为垃圾邮件（不需要的邮件）或非垃圾邮件（想要的邮件）。这样的问题被称为分类问题 (classification problem)——给定各种数据点（在这种情况下，每封电子邮件都是一个数据点），我们的目标是将它们归入两个或更多类别 (classes) 中的一个。对于分类问题，我们会得到一组训练数据点以及它们相应的标签 (labels)，这些标签通常是几个离散值之一。
我们的目标是使用这些训练数据（电子邮件，以及每封邮件的垃圾邮件/非垃圾邮件标签）来学习某种关系，我们可以利用这种关系对以前未见过的电子邮件进行预测。在本节中，我们将描述如何构建一种用于解决分类问题的模型，称为朴素贝叶斯分类器 (Naive Bayes Classifier)。
为了训练一个模型将电子邮件分类为垃圾邮件或非垃圾邮件，我们需要一些由预先分类的电子邮件组成的训练数据，我们可以从中学习。然而，电子邮件只是文本字符串，为了学到任何有用的东西，我们需要从每封邮件中提取某些属性，称为特征 (features)。特征可以是任何东西，从特定的单词计数到文本模式（例如，单词是否全大写），再到你能想象到的数据的几乎任何其他属性。
为训练提取的具体特征通常取决于你试图解决的具体问题，你决定选择哪些特征会极大地影响模型的性能。决定使用哪些特征被称为特征工程 (feature engineering)，这是机器学习的基础，但为了本课程的目的，你可以假设对于任何给定的数据集，你总是会得到提取好的特征。在这篇笔记中，f(x) 指的是在将所有输入 x 放入模型之前应用于它们的特征函数。
现在假设你有一个包含 \(n\) 个单词的字典，并且从每封电子邮件中，你提取一个特征向量 \(F \in \mathbb{R}^{n}\)，其中 \(F\) 中的第 \(i\) 个条目是一个随机变量 \(F_i\)，它可以取值 \(0\) 或 \(1\)，取决于字典中的第 \(i\) 个单词是否出现在正在考虑的电子邮件中。例如，如果 \(F_{200}\) 是单词 free 的特征，如果 free 出现在电子邮件中，我们将有 \(F_{200} = 1\)，如果没有出现，则为 \(0\)。
有了这些定义，我们可以更具体地定义如何预测一封电子邮件是垃圾邮件还是非垃圾邮件——如果我们能在每个 \(F_i\) 和标签 \(Y\) 之间生成一个联合概率表，我们就可以计算任何正在考虑的电子邮件在给定其特征向量的情况下是垃圾邮件或非垃圾邮件的概率。具体来说，我们可以计算
\[P(Y = \text{spam} | F_1 = f_1, \dots, F_n = f_n)\] \[P(Y = \text{ham} | F_1 = f_1, \dots, F_n = f_n)\]并简单地根据两个概率中哪个更高来标记电子邮件。
不幸的是，由于我们有 \(n\) 个特征和 1 个标签，每个都可以取 2 个不同的值，对应于此分布的联合概率表需要一个大小随 \(n\) 指数增长的表，有 \(2^{n+1}\) 个条目——非常不切实际！这个问题通过用贝叶斯网络对联合概率表建模来解决，做出关键的简化假设，即给定类标签，每个特征 \(F_i\) 独立于所有其他特征。
这是一个非常强的建模假设（也是朴素贝叶斯被称为_朴素_的原因），但它简化了推理，并且通常在实践中效果很好。它导致以下贝叶斯网络来表示我们期望的联合概率分布。
\(d\)-分离规则清楚地表明，在这个贝叶斯网络中，给定 \(Y\)，每个 \(F_i\) 条件独立于所有其他特征。现在我们有一个包含 2 个条目的 \(P(Y)\) 表，以及每个 \(P(F_i | Y)\) 的 \(n\) 个表，每个表有 \(2^2 = 4\) 个条目，总共有 \(4n + 2\) 个条目——与 \(n\) 成线性关系！这个简化假设突出了由统计效率 (statistical efficiency) 概念引起的权衡；有时我们需要牺牲模型的复杂性以保持在计算限制内。
确实，在特征数量足够少的情况下，通常会对特征之间的关系做出更多假设以生成更好的模型（对应于向贝叶斯网络添加边）。使用此模型，对未知数据点进行预测相当于在我们的贝叶斯网络上运行推理。我们观察到了 \(F_1, \dots, F_n\) 的值，并希望选择在这些特征条件下具有最高概率的 \(Y\) 值：
\[\text{prediction}(f_1, \cdots, f_n) = \underset{y}{\text{argmax}}~P(Y=y \mid F_1=f_1, \ldots, F_N = f_n) \\ = \underset{y}{\text{argmax}}~P(Y=y, F_1=f_1, \ldots, F_N = f_n) \\ = \underset{y}{\text{argmax}}~P(Y=y) \prod_{i=1}^n P(F_i = f_i \mid Y=y)\]第一步是因为最高概率类别在归一化或未归一化分布中是相同的，第二步直接来自朴素贝叶斯的独立性假设，即给定类标签，特征是独立的（如在图模型结构中所见）。
从垃圾邮件过滤器推广开来，假设现在有 \(k\) 个类标签（\(Y\) 的可能值）。此外，在注意到我们期望的概率——给定我们的特征，每个标签 \(y_i\) 的概率 \(P(Y = y_i | F_1 = f_1, \dots, F_n = f_n)\)——与联合概率 \(P(Y = y_i, F_1 = f_1, \dots, F_n = f_n)\) 成正比后，我们可以计算：
\(P(Y, F_1 = f_1, \dots, F_n = f_n) = \begin{bmatrix} P(Y = y_1, F_1 = f_1, \dots, F_n = f_n) \\ P(Y = y_2, F_1 = f_1, \dots, F_n = f_n) \\ \vdots \\ P(Y = y_k, F_1 = f_1, \dots, F_n = f_n) \end{bmatrix}\) \(= \begin{bmatrix} P(Y = y_1)\prod_i P(F_i = f_i | Y = y_1) \\ P(Y = y_2)\prod_i P(F_i = f_i | Y = y_2) \\ \vdots \\ P(Y = y_k)\prod_i P(F_i = f_i | Y = y_k) \end{bmatrix}\)
我们对对应于特征向量 \(F\) 的类标签的预测仅仅是对应于上述计算向量中最大值的标签：
\[\text{prediction}(F) = \underset{y_i}{\text{argmax}}~P(Y = y_i)\prod_j P(F_j = f_j | Y = y_i)\]我们现在已经了解了朴素贝叶斯分类器建模假设背后的基本理论以及如何使用它进行预测，但还没有触及我们究竟如何从输入数据中学习贝叶斯网络中使用的条件概率表。这必须等待我们的下一个讨论主题，参数估计 (parameter estimation)。
9.2.1 参数估计 (Parameter Estimation)
假设你有一组样本点 (sample points) 或观测值 (observations)，\(x_1, \ldots, x_N\)，并且你相信这些数据是从一个由未知值 \(\theta\) 参数化 (parametrized) 的分布中抽取的。换句话说，你相信每个观测值的概率 \(P_{\theta}(x_i)\) 是 \(\theta\) 的函数。例如，我们可能正在抛一枚硬币，它有 \(\theta\) 的概率正面朝上。
给定你的样本，你如何“学习” \(\theta\) 最可能的值？例如，如果我们抛了 10 次硬币，看到其中 7 次是正面，我们应该为 \(\theta\) 选择什么值？这个问题的一个答案是推断 \(\theta\) 等于最大化从你假设的概率分布中选择样本 \(x_1, \ldots, x_N\) 的概率的值。机器学习中一种常用且基本的方法，称为最大似然估计 (maximum likelihood estimation) (MLE)，正是这样做的。
最大似然估计通常做出以下简化假设：
- 每个样本都是从相同的分布中抽取的。换句话说，每个 \(x_i\) 是同分布的 (identically distributed)。在我们的抛硬币例子中，每次抛硬币都有相同的机会 \(\theta\) 正面朝上。
- 给定我们分布的参数，每个样本 \(x_i\) 条件独立 (independent) 于其他样本。这是一个很强的假设，但正如我们将看到的，它极大地有助于简化最大似然估计问题，并且通常在实践中效果很好。在抛硬币的例子中，一次抛掷的结果不会影响任何其他抛掷。
- 在我们看到任何数据之前，\(\theta\) 的所有可能值都是同样可能的（这被称为均匀先验 (uniform prior)）。
上述前两个假设通常被称为独立同分布 (independent, identically distributed) (i.i.d.)。上述第三个假设使 MLE 方法成为最大后验 (MAP) 方法的一个特例，后者允许非均匀先验。
现在让我们定义我们样本的似然 (likelihood) \(\mathcal{L}(\theta)\)，这是一个表示从我们的分布中抽取样本的概率的函数。对于固定样本 \(x_1, \ldots, x_N\)，似然只是 \(\theta\) 的函数：
\[\mathcal{L}(\theta) = P_{\theta}(x_1, \ldots, x_N)\]使用我们的简化假设，即样本 \(x_i\) 是 i.i.d.，似然函数可以重新表达如下：
\[\mathcal{L}(\theta) = \prod_{i=1}^N P_{\theta}(x_i)\]我们如何找到最大化这个函数的 \(\theta\) 值？这将是最好地解释我们所见数据的 \(\theta\) 值。回想微积分，在实现函数最大值和最小值的点处，其关于每个输入的如一阶导数（也称为函数的梯度 (gradient)）必须等于零。因此，\(\theta\) 的最大似然估计是满足以下方程的值：
\[\frac{\partial}{\partial\theta} \mathcal{L}(\theta) = 0\]让我们通过一个例子来使这个概念更具体。假设你有一个装满红球和蓝球的袋子，不知道每种有多少个。你通过从袋子中取出一个球，记下颜色，然后把球放回去（有放回采样）来抽取样本。从这个袋子中抽取三个球的样本得到 红，红，蓝。这似乎意味着我们应该推断袋子中 \(\frac{2}{3}\) 的球是红色的，\(\frac{1}{3}\) 的球是蓝色的。我们将假设从袋子中取出的每个球是红色的概率为 \(\theta\)，是蓝色的概率为 \(1 - \theta\)，对于我们想要估计的某个值 \(\theta\)（这被称为伯努利分布）：
我们样本的似然是：
\[\mathcal{L}(\theta) = \prod_{i=1}^3 P_{\theta}(x_i) = P_{\theta}(x_1 = \text{red}) \cdot P_{\theta}(x_2 = \text{red}) \cdot P_{\theta}(x_3 = \text{blue}) = \theta^2 \cdot (1 - \theta)\]最后一步是将似然的导数设为 \(0\) 并求解 \(\theta\)：
\[\frac{\partial}{\partial\theta} \mathcal{L}(\theta) = \frac{\partial}{\partial\theta} \left( \theta^2 \cdot (1 - \theta) \right) = \theta (2 - 3\theta) = 0\]求解这个方程得到 \(\theta = \frac{2}{3}\)，这在直觉上是有道理的！（还有一个解，\(\theta = 0\) ——但这对应于似然函数的最小值，因为 \(\mathcal{L}(0) = 0 < \mathcal{L}(\frac{2}{3}) = \frac{4}{27}\)。）
9.2.2 朴素贝叶斯的最大似然 (Maximum Likelihood for Naive Bayes)
现在让我们回到推断垃圾邮件分类器的条件概率表的问题，首先回顾一下我们知道的变量：
- \(n\) - 我们字典中的单词数。
- \(N\) - 你用于训练的观测值（电子邮件）的数量。对于我们接下来的讨论，让我们也定义 \(N_h\) 为标记为非垃圾邮件的训练样本数，\(N_s\) 为标记为垃圾邮件的训练样本数。注意 \(N_h + N_s = N\)。
- \(F_i\) - 一个随机变量，如果第 \(i\) 个字典单词出现在正在考虑的电子邮件中，则为 \(1\)，否则为 \(0\)。
- \(Y\) - 一个随机变量，取决于相应电子邮件的标签，是
spam或ham。 - \(f_i^{(j)}\) - 这引用了训练集中第 \(j\) 个项目中随机变量 \(F_i\) 的解析值。换句话说，如果单词 \(i\) 出现在第 \(j\) 封正在考虑的电子邮件中，则每个 \(f_i^{(j)}\) 为 \(1\)，否则为 \(0\)。这是我们第一次看到这个符号，但在接下来的推导中它会派上用场。
免责声明：随意跳过下面的数学推导。对于 CS 188，你只需要知道本节末尾段落中总结的推导结果。
现在在每个条件概率表 \(P(F_i | Y)\) 中，注意我们有两个不同的伯努利分布：\(P(F_i | Y = ham)\) 和 \(P(F_i | Y = spam)\)。为了简单起见，让我们专门考虑 \(P(F_i | Y = ham)\) 并尝试找到参数 \(\theta = P(F_i = 1 | Y = ham)\) 的最大似然估计，即我们字典中的第 \(i\) 个单词出现在非垃圾邮件中的概率。由于我们在训练集中有 \(N_h\) 封非垃圾邮件，我们有 \(N_h\) 个关于单词 \(i\) 是否出现在非垃圾邮件中的观测值。因为我们的模型假设给定标签的每个单词的出现服从伯努利分布，我们可以如下制定我们的似然函数：
\[\mathcal{L}(\theta) = \prod_{j=1}^{N_h}P(F_i = f_i^{(j)}| Y = ham) = \prod_{j=1}^{N_h}\theta^{f_i^{(j)}}(1 - \theta)^{1 - f_i^{(j)}}\]
第二步来自一个小小的数学技巧：如果 \(f_i^{(j)} = 1\) 那么
\[P(F_i = f_i^{(j)}| Y = ham) = \theta^1(1 - \theta)^0 = \theta\]同样如果 \(f_i^{(j)} = 0\) 那么
\[P(F_i = f_i^{(j)}| Y = ham) = \theta^0(1 - \theta)^1 = (1 - \theta)\]为了计算 \(\theta\) 的最大似然估计，回想一下下一步是计算 \(\mathcal{L}(\theta)\) 的导数并将其设为 \(0\)。尝试这样做证明是相当困难的，因为隔离和求解 \(\theta\) 不是一件简单的任务。相反，我们将采用一个在最大似然推导中非常常见的技巧，那就是找到最大化似然函数的 \(\log\) 的 \(\theta\) 值。因为 \(\log(x)\) 是一个严格递增的函数（有时被称为单调变换 (monotonic transformation)），找到一个最大化 \(\log \mathcal{L}(\theta)\) 的值也将最大化 \(\mathcal{L}(\theta)\)。\(\log{\mathcal{L}(\theta)}\) 的展开如下：
\[\log{\mathcal{L}(\theta)} = \log\bigg(\prod_{j=1}^{N_h}\theta^{f_i^{(j)}}(1 - \theta)^{1 - f_i^{(j)}}\bigg)\] \[= \sum_{j=1}^{N_h}\log\big(\theta^{f_i^{(j)}}(1 - \theta)^{1 - f_i^{(j)}}\big)\] \[= \sum_{j=1}^{N_h}\log\big(\theta^{f_i^{(j)}}\big) + \sum_{j=1}^{N_h}\log\big((1 - \theta)^{1 - f_i^{(j)}}\big)\] \[= \log(\theta)\sum_{j=1}^{N_h}f_i^{(j)} + \log(1 - \theta)\sum_{j=1}^{N_h}(1 - f_i^{(j)})\]注意在上面的推导中，我们使用了对数函数的属性 \(\log(a^c) = c \cdot \log(a)\) 和 \(\log(ab) = \log(a) + \log(b)\)。现在我们将似然函数的对数的导数设为 \(0\) 并求解 \(\theta\)：
\[\frac{\partial}{\partial\theta}\bigg(\log(\theta)\sum_{j=1}^{N_h}f_i^{(j)} + \log(1 - \theta)\sum_{j=1}^{N_h}(1 - f_i^{(j)})\bigg) = 0\] \[\frac{1}{\theta}\sum_{j=1}^{N_h}f_i^{(j)} - \frac{1}{(1 - \theta)}\sum_{j=1}^{N_h}(1 - f_i^{(j)}) = 0\] \[\frac{1}{\theta}\sum_{j=1}^{N_h}f_i^{(j)} = \frac{1}{(1 - \theta)}\sum_{j=1}^{N_h}(1 - f_i^{(j)})\] \[(1 - \theta)\sum_{j=1}^{N_h}f_i^{(j)} = \theta\sum_{j=1}^{N_h}(1 - f_i^{(j)})\] \[\sum_{j=1}^{N_h}f_i^{(j)} - \theta\sum_{j=1}^{N_h}f_i^{(j)} = \theta\sum_{j=1}^{N_h}1 - \theta\sum_{j=1}^{N_h}f_i^{(j)}\] \[\sum_{j=1}^{N_h}f_i^{(j)} = \theta \cdot N_h\] \[\theta = \frac{1}{N_h}\sum_{j=1}^{N_h}f_i^{(j)}\]
我们得到了一个非常简单的最终结果！根据我们上面的公式，\(\theta\) 的最大似然估计（记住，它是 \(P(F_i = 1 | Y = ham)\) 的概率）对应于计算单词 \(i\) 出现的非垃圾邮件的数量，并将其除以非垃圾邮件的总数。你可能认为为了一个直观的结果做了很多工作（确实如此），但推导和技术对于比我们在这里为每个特征使用的简单伯努利分布更复杂的分布将是有用的。总而言之，在这个具有伯努利特征分布的朴素贝叶斯模型中，在任何给定类别内，任何结果概率的最大似然估计对应于结果的计数除以给定类别的样本总数。上述推导可以推广到我们有两个以上类别和每个特征有两个以上结果的情况，尽管这里没有提供这种推导。
9.2.3 平滑 (Smoothing)
虽然最大似然估计是一种非常强大的参数估计方法，但糟糕的训练数据往往会导致不幸的后果。例如，如果每次单词“minute”出现在我们训练集的电子邮件中时，该电子邮件都被归类为垃圾邮件，我们的训练模型将学习到
\[P(F_{minute} = 1 | Y = ham) = 0\]因此在未见过的电子邮件中，如果单词 minute 出现，
所以你的模型永远不会将任何包含单词 minute 的电子邮件归类为非垃圾邮件。这是过拟合 (overfitting) 的一个典型例子，或者是构建了一个不能很好地泛化到以前未见过的数据的模型。仅仅因为一个特定的单词没有出现在你的训练数据的电子邮件中，并不意味着它不会出现在你的测试数据或现实世界的电子邮件中。
朴素贝叶斯分类器的过拟合可以通过拉普拉斯平滑 (Laplace smoothing) 来缓解。从概念上讲，强度为 \(k\) 的拉普拉斯平滑假设已经看到了每个结果的 \(k\) 个额外实例。因此，如果在给定样本中，对于可以从大小为 \(N\) 的样本中取 \(|X|\) 个不同值的结果 \(x\)，你的最大似然估计是
\[P_{MLE}(x) = \frac{count(x)}{N}\]
那么强度为 \(k\) 的拉普拉斯估计是
\[P_{LAP, k}(x) = \frac{count(x) + k}{N + k|X|}\]
这个方程说明了什么？我们假设看到了每个结果的 \(k\) 个额外实例，因此表现得好像我们已经看到了 \(count(x) + k\) 而不是 \(count(x)\) 个 \(x\) 的实例。同样，如果我们看到 \(|X|\) 个类别中每一个的 \(k\) 个额外实例，那么我们必须将 \(k|X|\) 加到我们的原始样本数 \(N\) 中。这两个陈述共同得出了上述公式。类似的结果适用于计算条件的拉普拉斯估计（这对计算不同类别的结果的拉普拉斯估计很有用）：
\[P_{LAP, k}(x|y) = \frac{count(x, y) + k}{count(y) + k|X|}\]
拉普拉斯平滑有两个特别值得注意的情况。第一种是当 \(k = 0\) 时，那么
\[P_{LAP, 0}(x) = P_{MLE}(x)\]第二种是 \(k = \infty\) 的情况。观察到每个结果的非常大的、无限的数量使你的实际样本结果变得无关紧要，因此你的拉普拉斯估计意味着每个结果都是同样可能的。确实：
\[P_{LAP, \infty}(x) = \frac{1}{|X|}\]在你的模型中使用的合适的 \(k\) 的具体值通常由试错法确定。\(k\) 是你模型中的一个超参数，这意味着你可以将其设置为任何你想要的值，并查看哪个值在你的验证数据上产生最佳的预测准确性/性能。