针对文本分类的事件模型

接下里用一个文本分类方面的模型来对生成学习算法进行收尾，之前说的朴素贝叶斯方法已经可以解决很多分类问题了，不过还有另外一个算法在针对文本的分类效果要更好

在文本分类的特定上下文中，朴素贝叶斯使用了所谓的 多变量伯努利事件模型。在这个模型中，我们假设生成电子邮件的方式是首先随机确定(根据类先验$p(y)$) 邮件是垃圾邮件还是非垃圾邮件，然后发送邮件的人通过字典根据概率$p(x_i = 1 \mid y)$ 独立决定是否包括邮件中的每个单词。因此，邮件的概率由

给出。

这里有个不同的模型，称为多项事件模型。为了描述这个模型，我们将使用不同的表示法和一组特征来表示电子邮件。我们令 $x_i$ 表示电子邮件中第 $i$ 个单词的标识。因此，$x_i$ 现在是一个整数，取值为 ${1, \dots, |V|}$，其中 $|V|$ 是我们词汇量的大小（字典）。$n$ 个单词的电子邮件现在由长度为 $n$ 的向量 $(x_1, x_2, \dots, x_n)$ 表示；请注意，$n$ 可能因不同文档而异。例如，如果电子邮件以 “A NIPS …” 开头，那么 $x_1 = 1$（“a” 是字典中的第 1 个单词），$x_2 = 35000$（如果 “nips” 是字典中的第 35000 个单词）。

在多项事件模型中，我们假设生成电子邮件的方式是通过如下随机过程：首先确定邮件是垃圾邮件/非垃圾邮件（根据 $p(y)$）。然后，电子邮件的发件人首先从某个多项分布生成 $x_1$（$p(x_1 \mid y)$）。接下来，第二个单词 $x_2$ 独立于 $x_1$ 且从相同的多项分布中选择，并且类似地对于 $x_3, x_4$ 等等，直到已经生成了电子邮件的所有 $n$ 个单词。因此，邮件的总概率由

给出。请注意，此公式看起来与我们之前在多变量伯努利事件模型下的邮件概率公式类似，但公式中的项现在意味着非常不同的事物。特别是 $x_j \mid y$ 现在服从多项分布，而不是伯努利分布。

我们的新模型的参数如前所述是 $\phi_y = p(y)$，$\phi_{k \mid y=1} = p(x_j = k \mid y = 1)$（对于任何 $j$），以及 $\phi_{k \mid y=0} = p(x_j = k \mid y = 0)$。注意，我们假设 $p(x_j \mid y)$ 对于 $j$ 的所有值是相同的（即，生成单词的分布不依赖于其在电子邮件中的位置 $j$）。

如果给定训练集 ${(x^{(i)}, y^{(i)}); i = 1, \dots, m}$，其中\(x^{(i)} = (x^{(i)}_1, x^{(i)}_2, \dots, x^{(i)}_{n_i})\)（这里，$n_i$ 是第 $i$ 个训练样本的单词数），数据的似然性由下式给出：

最大化上式会产生参数的最大似然估计：

如果我们在估计 $\phi_{k \mid y=1}$ 和 $\phi_{k \mid y=0}$ 时应用拉普拉斯平滑，我们对分子加 1，对分母加 $|V|$，并得到：

虽然不一定是最好的分类算法，但朴素贝叶斯分类器通常效果非常好。考虑到它的简单性和易于实现，它通常也非常适合作为第一个尝试。

支持向量机

这一章节主要讲的是支持向量机(SVM)学习算法，SVM是现成的最好的监督学习算法。为了讲述SVM，我们首先需要讨论间隔以及将数据以大的“间隔”分开的想法。接下来，我们将讨论最优间隔分类器，这将引导我们对拉格朗日对偶的讨论。我们还将看到核方法，它提供了一种在非常高维（例如无限维）特征空间中有效应用SVM的方法，最后，我们会使用SMO算法结束这章，该方法可以有效地实现支持向量机

边界：直觉

我们将通过讨论间隔来开始我们关于SVM的讨论。本节将给出关于间隔和我们预测的“信心”的直觉；这些想法将在第3节中正式提出。

考虑logistic回归，其中概率 $p(y = 1 \mid x; \theta)$ 由 $h_\theta(x) = g(\theta^T x)$ 建模。然后，当且仅当 $h_\theta(x) \ge 0.5$ 时，我们才会预测输入 $x$ 为“1”，或者等价的，当且仅当 $\theta^T x \ge 0$。

考虑一个正训练样本 $(y = 1)$。$\theta^T x$ 越大，$h_\theta(x) = p(y = 1 \mid x; w, b)$ 也越大，因此标记为1的“置信度”也越高。因此，非正式地，我们可以对 $y = 1$ 进行非常自信的预测，如果 $\theta^T x \gg 0$。类似地，我们将logistic回归视为对 $y = 0$ 进行非常自信的预测，如果 $\theta^T x \ll 0$。

给定一个训练集，再次非正式地看起来我们已经找到了一个对训练数据很好的拟合，如果我们可以找到 $\theta$，以便每当 $y^{(i)} = 1$ 时，$\theta^T x^{(i)} \gg 0$，并且每当 $y^{(i)} = 0$ 时，$\theta^T x^{(i)} \ll 0$，因为这将反映所有训练样本的非常有信心（和正确）的分类。这似乎是一个很好的目标，我们很快就会使用函数间隔的概念来形式化这个想法。

对于不同的直觉，请考虑下图，其中 x 代表正训练样本，o 代表负训练样本。决策边界（这是由等式 $\theta^T x = 0$ 给出的线，也称为分离超平面）也在图中，并且三个点也被标记为 A、B 和 C。

注意到A点离决策边界很远。如果我们被要求在A处对 $y$ 的值进行预测，那么我们应该非常确信 $y = 1$。相反，C点非常接近决策边界，虽然它位于我们预测 $y = 1$ 的决策边界的一侧，但似乎只是对决策边界的一个小变化很容易导致我们的预测改变为 $y = 0$。因此，我们对A处的预测比对C的预测更有信心。B点位于这两种情况之间，更广泛地说，我们看到如果一点远离分离超平面，那么我们对预测可能会更有信心。

同样，非正式地，我们认为，如果给定一个训练集，我们设法找到一个决策边界，使我们能够在训练样例上做出所有正确和自信（意味着远离决策边界）的预测，那将是非常好的。我们稍后将使用几何间隔的概念将其形式化。

符号

为了使我们对SVM的讨论更容易，我们首先需要引入一个新的符号来讨论分类。我们将考虑用于解决带有标签 $y$ 和特征 $x$ 的二元分类问题的线性分类器。从现在开始，我们将使用 $y \in {-1, 1}$（而不是 ${0, 1}$）来表示类标签。此外，我们将使用参数 $w, b$，而不是使用向量 $\theta$ 来参数化我们的线性分类器，并将分类器改写为

这里，如果 $z \ge 0$，则 $g(z) = 1$，否则 $g(z) = -1$。这个 “$w, b$” 表示法允许我们明确地将截距项 $b$ 与其他参数分开处理。（我们也放弃了以前让 $x_0 = 1$ 成为输入特征向量中的额外坐标的约定。）因此，$b$ 扮演以前 $\theta_0$ 的角色，$w$ 扮演 $(\theta_1, \dots, \theta_n)^T$ 的角色。

还要注意，根据我们上面对 $g$ 的定义，我们的分类器将直接预测 $1$ 或 $-1$（参见感知机算法），而不是首先进行估计 $y$ 为 $1$ 的概率的中间步骤（这是 logistic 回归所做的）。

函数和几何间隔

让我们形式化函数间隔和几何间隔的概念。给定一个训练样本 $(x^{(i)}, y^{(i)})$，我们根据训练样本定义 $(w,b)$ 的函数间隔为

注意，如果 $y^{(i)} = 1$，那么为了使函数间隔变大（即，为了使我们的预测有信心和正确），我们需要 $w^T x^{(i)} + b$ 为大的正数。相反，如果 $y^{(i)} = -1$，那么为了使函数间隔变大，我们需要 $w^T x^{(i)} + b$ 为（绝对值）大的负数。此外，如果 $y^{(i)} (w^T x^{(i)} + b) > 0$，那么我们对这个例子的预测是正确的。因此，大的函数间隔代表了自信和正确的预测。

对于上面给出的线性分类器 $g$（取 ${-1,1}$ 中的值），函数间隔的一个属性使得它不是一个非常好的置信度量。给定我们的选择 $g$，我们注意到如果我们用 $2w$ 代替 $w$，用 $2b$ 代替 $b$，那么因为

所以这根本不会改变 $h_{w,b}(x)$。即，$g$，因此也是 $h_{w,b}(x)$，仅取决于 $w^T x + b$ 的符号，而不取决于其模长。然而，用 $(2w, 2b)$ 代替 $(w, b)$ 也会导致我们的函数间隔乘以 2。因此，通过利用对 $w$ 和 $b$ 的缩放，我们可以使函数间隔任意大，但实际上没有改变任何有意义的事情，因此强制某种归一化条件可能是有意义的，例如 $|w|_2 = 1$；也就是说，我们可以用 $(w/|w|_2, b/|w|_2)$ 代替 $(w, b)$，然后考虑 $(w/|w|_2, b/|w|_2)$ 的函数间隔。

给定训练集

我们还将 $(w,b)$ 关于 $S$ 的函数间隔定义为训练样本中最小的函数间隔，用 $\hat{\gamma}$ 表示，因此可以写成：

接下来，我们来谈谈几何间隔。请看下图：

上图展示了对应于 $(w,b)$ 的决策边界以及向量 $w$。注意，$w$ 与分离超平面正交。考虑 A 处的点，它代表某个训练样本 $x^{(i)}$，标签为 $y^{(i)} = 1$，它与决策边界的距离为 $\gamma^{(i)}$，由线段 $AB$ 给出。

我们怎样才能得到 $\gamma^{(i)}$ 的值？注意到 $w/|w|$ 是和 $w$ 同向的单位长度向量。由于 A 代表 $x^{(i)}$，因此我们发现点 $B$ 由

给出。但这一点在决策边界上，决策边界上的所有点 $x$ 都满足方程 $w^T x + b = 0$。因此，

解出 $\gamma^{(i)}$ 得到

这是针对图中 A 处的正训练样本的情况得到的，其中处于决策边界的“正”侧是好的。更一般地，我们定义 $(w,b)$ 相对于训练样本 $(x^{(i)}, y^{(i)})$ 的几何间隔为

请注意，如果 $|w| = 1$，那么函数间隔等于几何间隔——这就为我们提供了一种方法来联系这两种不同的间隔概念。此外，几何间隔对于重新缩放参数是不变的；即，如果我们用 $2w$ 代替 $w$，用 $2b$ 代替 $b$，则几何间隔不会改变。事实上，这将在以后派上用场。具体来说，由于这种参数缩放的不变性，当试图将 $w$ 和 $b$ 拟合到训练数据时，我们可以对 $w$ 施加任意缩放约束而不改变任何重要的东西；例如，我们可以要求 $|w| = 1$，或 $|w|_1 = 5$，或 $|w_1 + b| + |w_2| = 2$，只需重新调整 $w$ 和 $b$ 即可满足其中任何一个。

给定训练集

我们还将 $(w,b)$ 关于 $S$ 的几何间隔定义为训练样本中最小的几何间隔，用 $\gamma$ 表示，因此可以写成：