五、支持向量机 - 背后机制 - 《Sklearn 与 TensorFlow 机器学习实用指南》

背后机制

这个章节从线性 SVM 分类器开始，将解释 SVM 是如何做预测的并且算法是如何工作的。如果你是刚接触机器学习，你可以跳过这个章节，直接进入本章末尾的练习。等到你想深入了解 SVM，再回头研究这部分内容。

首先，关于符号的约定：在第 4 章，我们将所有模型参数放在一个矢量θ里，包括偏置项θ0，θ1到θn的输入特征权重，和增加一个偏差输入x0 = 1到所有样本。在本章中，我们将使用一个不同的符号约定，在处理 SVM 上，这更方便，也更常见：偏置项被命名为b，特征权重向量被称为w，在输入特征向量中不再添加偏置特征。

决策函数和预测

线性 SVM 分类器通过简单地计算决策函数 $w \cdot x+b = w_1 x_1 + ... + w_n x_n + b$ 来预测新样本的类别：如果结果是正的，预测类别ŷ是正类，为 1，否则他就是负类，为 0。见公式 5-2

图 5-12 显示了和图 5-4 右边图模型相对应的决策函数：因为这个数据集有两个特征（花瓣的宽度和花瓣的长度），所以是个二维的平面。决策边界是决策函数等于 0 的点的集合，图中两个平面的交叉处，即一条直线（图中的实线）

虚线表示的是那些决策函数等于 1 或 -1 的点：它们平行，且到决策边界的距离相等，形成一个间隔。训练线性 SVM 分类器意味着找到w值和b值使得这一个间隔尽可能大，同时避免间隔违规（硬间隔）或限制它们（软间隔）

训练目标

看下决策函数的斜率：它等于权重向量的范数 $\|w\|$ 。如果我们把这个斜率除于 2，决策函数等于 ±1 的点将会离决策边界原来的两倍大。换句话，即斜率除于 2，那么间隔将增加两倍。在图 5-13 中，2D 形式比较容易可视化。权重向量w越小，间隔越大。

所以我们的目标是最小化 $\|w\|$ ，从而获得大的间隔。然而，如果我们想要避免间隔违规（硬间隔），对于正的训练样本，我们需要决策函数大于 1，对于负训练样本，小于 -1。若我们对负样本（即 $y^{(i)} = 0$ ）定义 $t^{(i)}=-1$ ，对正样本（即 $y^{(i)} = 1$ ）定义 $t^{(i)}=1$ ，那么我们可以对所有的样本表示为 $t^{(i)} (w^T x^{(i)} + b) \ge 1$ 。

因此，我们可以将硬间隔线性 SVM 分类器表示为公式 5-3 中的约束优化问题

注

等于 $1/2 \|w\|^2$ ，我们最小化，而不是最小化 $\|w\|$ 。这会给我们相同的结果（因为最小化w值和b值，也是最小化该值一半的平方），但是 $1/2 \|w\|^2$ 有很好又简单的导数（只有w）， $\|w\|$ 在w=0处是不可微的。优化算法在可微函数表现得更好。

为了获得软间隔的目标，我们需要对每个样本应用一个松弛变量（slack variable） $\zeta^{(i)} \ge 0$ 。 $\zeta^{(i)}$ 表示了第i个样本允许违规间隔的程度。我们现在有两个不一致的目标：一个是使松弛变量尽可能的小，从而减小间隔违规，另一个是使1/2 w·w尽量小，从而增大间隔。这时C超参数发挥作用：它允许我们在两个目标之间权衡。我们得到了公式 5-4 的约束优化问题。

二次规划

硬间隔和软间隔都是线性约束的凸二次规划优化问题。这些问题被称之为二次规划（QP）问题。现在有许多解决方案可以使用各种技术来处理 QP 问题，但这超出了本书的范围。一般问题的公式在公式 5-5 给出。

注意到表达式Ap ≤ b实际上定义了约束： $p^T a^{(i)} \le b^{(i)}, for i = 1, 2, ..., n$ ， $a^{(i)}$ 是个包含了A的第i行元素的向量， $b^{(i)}$ 是b的第i个元素。

可以很容易地看到，如果你用以下的方式设置 QP 的参数，你将获得硬间隔线性 SVM 分类器的目标：

，n表示特征的数量（+1 是偏置项）
，m表示训练样本数量
H是 $n_p \times n_p$ 单位矩阵，除了左上角为 0（忽略偏置项）
f = 0，一个全为 0 的维向量
，一个全为 1 的维向量
$a^{(i)} = –t^{(i)} \dot{x}^{(i)}$ ， $\dot{x}^{(i)}$ 等于 $x^{(i)}$ 带一个额外的偏置特征 $\dot{x}_0=1$ ！

所以训练硬间隔线性 SVM 分类器的一种方式是使用现有的 QP 解决方案，即上述的参数。由此产生的向量p将包含偏置项和特征权重。同样的，你可以使用 QP 解决方案来解决软间隔问题（见本章最后的练习）

然而，使用核技巧我们将会看到一个不同的约束优化问题。

对偶问题

给出一个约束优化问题，即原始问题（primal problem），它可能表示不同但是和另一个问题紧密相连，称为对偶问题（Dual Problem）。对偶问题的解通常是对原始问题的解给出一个下界约束，但在某些条件下，它们可以获得相同解。幸运的是，SVM 问题恰好满足这些条件，所以你可以选择解决原始问题或者对偶问题，两者将会有相同解。公式 5-6 表示了线性 SVM 的对偶形式（如果你对怎么从原始问题获得对偶问题感兴趣，可以看下附录 C）

一旦你找到最小化公式的向量α（使用 QP 解决方案），你可以通过使用公式 5-7 的方法计算w和b，从而使原始问题最小化。

当训练样本的数量比特征数量小的时候，对偶问题比原始问题要快得多。更重要的是，它让核技巧成为可能，而原始问题则不然。那么这个核技巧是怎么样的呢？

核化支持向量机

假设你想把一个 2 次多项式变换应用到二维空间的训练集（例如卫星数据集），然后在变换后的训练集上训练一个线性SVM分类器。公式 5-8 显示了你想应用的 2 次多项式映射函数ϕ。

注意到转换后的向量是 3 维的而不是 2 维。如果我们应用这个 2 次多项式映射，然后计算转换后向量的点积（见公式 5-9），让我们看下两个 2 维向量a和b会发生什么。

转换后向量的点积等于原始向量点积的平方： $\phi(a)^T \phi(b) = (a^T b)^2$

关键点是：如果你应用转换ϕ到所有训练样本，那么对偶问题（见公式 5-6）将会包含点积 $\phi(x^{(i)})^T \phi(x^{(j)})$ 。但如果ϕ像在公式 5-8 定义的 2 次多项式转换，那么你可以将这个转换后的向量点积替换成 $(x^{(i)T} x^{(j)})^2$ 。所以实际上你根本不需要对训练样本进行转换：仅仅需要在公式 5-6 中，将点积替换成它点积的平方。结果将会和你经过麻烦的训练集转换并拟合出线性 SVM 算法得出的结果一样，但是这个技巧使得整个过程在计算上面更有效率。这就是核技巧的精髓。

函数被称为二次多项式核（polynomial kernel）。在机器学习，核函数是一个能计算点积的函数，并只基于原始向量a和b，不需要计算（甚至知道）转换ϕ。公式 5-10 列举了一些最常用的核函数。

Mercer 定理

根据 Mercer 定理，如果函数K(a, b)满足一些 Mercer 条件的数学条件(K函数在参数内必须是连续，对称，即K(a, b)=K(b, a)，等)，那么存在函数ϕ，将a和b映射到另一个空间（可能有更高的维度），有 $K(a, b) = \phi(a)^T ϕ(b)$ 。所以你可以用K作为核函数，即使你不知道ϕ是什么。使用高斯核（Gaussian RBF kernel）情况下，它实际是将每个训练样本映射到无限维空间，所以你不需要知道是怎么执行映射的也是一件好事。

注意一些常用核函数（例如 Sigmoid 核函数）并不满足所有的 Mercer 条件，然而在实践中通常表现得很好。

我们还有一个问题要解决。公式 5-7 展示了线性 SVM 分类器如何从对偶解到原始解，如果你应用了核技巧那么得到的公式会包含 $\phi(x^{(i)})$ 。事实上，w必须和 $\phi(x^{(i)})$ 有同样的维度，可能是巨大的维度或者无限的维度，所以你很难计算它。但怎么在不知道w的情况下做出预测？好消息是你可以将公式 5-7 的w代入到新的样本 $x^{(n)}$ 的决策函数中，你会得到一个在输入向量之间只有点积的方程式。这时，核技巧将派上用场，见公式 5-11

注意到支持向量才满足α(i)≠0，做出预测只涉及计算为支持向量部分的输入样本 $x^{(n)}$ 的点积，而不是全部的训练样本。当然，你同样也需要使用同样的技巧来计算偏置项b，见公式 5-12

如果你开始感到头痛，这很正常：因为这是核技巧一个不幸的副作用

在线支持向量机

在结束这一章之前，我们快速地了解一下在线 SVM 分类器（回想一下，在线学习意味着增量地学习，不断有新实例）。对于线性SVM分类器，一种方式是使用梯度下降（例如使用SGDClassifire）最小化代价函数，如从原始问题推导出的公式 5-13。不幸的是，它比基于 QP 方式收敛慢得多。

代价函数第一个和会使模型有一个小的权重向量w，从而获得一个更大的间隔。第二个和计算所有间隔违规的总数。如果样本位于“街道”上和正确的一边，或它与“街道”正确一边的距离成比例，则间隔违规等于 0。最小化保证了模型的间隔违规尽可能小并且少。

Hinge 损失

函数max(0, 1–t)被称为 Hinge 损失函数（如下）。当t≥1时，Hinge 值为 0。如果t<1,它的导数（斜率）为 -1，若t>1，则等于0。在t=1处，它是不可微的，但就像套索回归（Lasso Regression）（参见 130 页套索回归）一样，你仍然可以在t=0时使用梯度下降法（即 -1 到 0 之间任何值）

我们也可以实现在线核化的 SVM。例如使用“增量和递减 SVM 学习”或者“在线和主动的快速核分类器”。但是，这些都是用 Matlab 和 C++ 实现的。对于大规模的非线性问题，你可能需要考虑使用神经网络（见第二部分）