12.2初级支持向量机

12.2 初级支持向量机

基于点到超平面的距离概念，我们现在可以讨论支持向量机了。对于一个线性可分的数据集\{(\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_N,y_N)\}，我们有无数个候选超平面（参考图12.3），因此也有无数个分类器，它们可以在没有任何（训练）错误的情况下解决我们的分类问题。为了找到一个唯一解，一个想法是选择分隔超平面，该超平面最大化正例和反例之间的间隔。换句话说，我们希望正例和反例被一个较大的间隔分开（第12.2.1节）。接下来，我们计算一个样本与超平面之间的距离，以推导出这个间隔。回想一下，给定点（样本x_n）到超平面上最近点的距离是通过正交投影获得的（第3.8节）。

12.2.1 间隔的概念

间隔的概念直观上很简单：在假设数据集是线性可分的情况下，它是分隔超平面到数据集中最近样本的距离。然而，在尝试将这个距离形式化时，可能会遇到一个技术上的难题。这个技术难题在于我们需要定义一个测量距离的尺度。一个潜在的尺度是考虑数据的尺度，即x_n的原始值。但这存在问题，因为我们可以改变x_n的测量单位，从而改变x_n中的值，进而改变到超平面的距离。正如我们稍后将看到的，我们将基于超平面方程(12.3)本身来定义这个尺度。

考虑一个超平面\langle w,x\rangle+b和一个样本x_\alpha，如图12.4所示。不失一般性，我们可以考虑样本x_{\alpha}位于超平面的正面，即\langle w,x_a\rangle+b>0。我们想要计算x_a到超平面的距离r>0。我们通过考虑x_a到超平面的正交投影（第3.8节）来实现这一点，我们将其表示为x_a^{\prime}。由于w与超平面正交，我们知道距离r只是这个向量w的一个缩放。如果知道w的长度，那么我们可以使用这个缩放因子r来计算x_\alpha和x_\alpha^{\prime}之间的绝对距离。为了方便起见，我们选择使用单位长度的向量（其范数为1），并通过将w除以其范数\frac{w}{\|w\|}来获得。使用向量加法（第2.4节），我们得到

(12.8)

另一种思考r的方式是，它是x_{\alpha}在由w/\|w\|跨越的子空间中的坐标。现在我们已经将x_{\alpha}到超平面的距离表示为r，如果我们选择x_\alpha为最接近超平面的点，那么这个距离r就是间隔。

回想一下，我们希望正样本距离超平面超过r，负样本距离超平面（在负方向上）超过距离r。类似于将(12.5)和(12.6)组合成(12.7)，我们将这个目标表述为

(12.9)

换句话说，我们将样本至少距离超平面r（在正方向和负方向上）的要求合并为一个不等式。由于我们只关心方向，我们在模型中增加了一个假设，即参数向量w的单位长度为1，即\|\boldsymbol w\|=1，其中我们使用 Euclid 范数\|w\|=\sqrt{w^\top w}（第3.1节）。这个假设也使得对距离r（12.8）的解释更加直观，因为它是长度为1的向量的缩放因子。

备注。熟悉其他间隔表示法的读者会注意到，如果支持向量机（SVM）是由Schölkopf和Smola（2002） et al.提供的，那么我们对\|w\|=1的定义与标准表示法不同。在第12.2.3节中，我们将展示这两种方法的等价性。

将这三个要求合并为一个带约束的优化问题，我们得到目标函数

(12.10)

这表示我们想要最大化间隔r，同时确保数据位于超平面的正确一侧。

备注。间隔的概念在机器学习中非常普遍。Vladimir Vapnik和Alexey Chervonenkis使用这个概念来表明，当间隔较大时，函数类的“复杂性”较低，因此学习是可能的（Vapnik，2000）。事实证明，这个概念对于从理论上分析泛化误差的各种不同方法非常有用（Steinwart和Christmann，2008；Shalev-Shwartz和Ben-David，2014）。

12.2.2 间隔的传统推导

在上一节中，我们通过观察到我们只关心w的方向而不是其长度，从而得出了（12.10），并假设了\|w\|=1。在本节中，我们将通过不同的假设来推导间隔最大化问题。我们不是选择参数向量进行归一化，而是选择数据的比例尺。我们选择这个比例尺，使得预测器\langle\boldsymbol w,\boldsymbol x\rangle+b在最接近的样本上的值为1。我们还将数据集中最接近超平面的样本表示为x_a。

图12.5与图12.4相同，但现在我们重新调整了坐标轴的比例，使得样本x_a正好位于间隔上，即\langle w,x_a\rangle+b=1。由于x_a^\prime是x_a在超平面上的正交投影，根据定义，它必须位于超平面上，即

(12.11)

将（12.8）代入（12.11），我们得到

(12.12)

利用内积的双线性性质（见第3.2节），我们得到

(12.13)

根据我们设定的比例尺，第一项为1，即\langle w,x_a\rangle+b=1。从第3.1节的（3.16）中，我们知道\langle w,w\rangle=\|\boldsymbol{w}\|^2。因此，第二项简化为r\|w\|。使用这些简化，我们得到

(12.14)

这意味着我们根据超平面的法向量w推导出了距离r。乍一看，这个方程似乎有些反直觉，因为我们似乎是用向量w的长度来表示了到超平面的距离，但我们还不知道这个向量。一种思考方式是将距离r视为一个临时变量，我们仅在此推导中使用它。因此，在本节的其余部分，我们将到超平面的距离表示为 \frac{1}{\|w\|} 。在第12.2.3节中，我们将看到选择间隔等于1与我们在第12.2.1节中的假设 \|\boldsymbol{w}\|=1 是等价的。

类似于获得（12.9）的论证，我们希望正样本和负样本都至少距离超平面1个单位，这产生了条件

(12.15)

将间隔最大化与样本需要根据其标签位于超平面的正确一侧这一事实相结合，我们得到

(12.16)

(12.17)

而不是像（12.16）那样最大化范数的倒数，我们通常最小化范数的平方。我们还经常包含一个常数\frac12，它不会影响最优的w,b，但在我们计算梯度时会得到一个更整洁的形式。然后，我们的目标变为

(12.18)

受约束于 y_n( \langle \boldsymbol{w}, \boldsymbol{x}_n\rangle + b) \geqslant 1 对所有 n= 1, \ldots , N 成立。 (12.19)

方程（12.18）被称为硬间隔SVM。“硬”这个表达的原因是因为该公式不允许间隔条件有任何违反。我们将在第12.2.4节中看到，如果数据不是线性可分的，这个“硬”条件可以放宽以容纳违反情况。

12.2.3 为什么我们可以将间隔设置为1

在12.2.1节中，我们论证了希望最大化某个值r，它代表最接近超平面的样本点的距离。在12.2.2节中，我们对数据进行了缩放，使得最接近超平面的样本点到超平面的距离为1。在本节中，我们将这两个推导联系起来，并证明它们是等价的。

定理12.1. 最大化间隔r，其中我们考虑如(12.10)所示的规范化权重，

(12.20)

这等价于对数据进行缩放，使得间隔为1：

(12.21)

证明：考虑(12.20)。由于平方是对于非负参数的严格单调变换，如果我们在目标函数中考虑r^2，则最大值保持不变。由于\|w\|=1，我们可以使用新的权重向量w^{\prime}（不显式地进行规范化）来重新参数化方程，即使用\frac{w^{\prime}}{\|w^{\prime}\|}。我们得到

(12.22)

方程(12.22)明确指出距离r是正数。因此，我们可以将第一个约束条件除以r，得到

(12.23)

将参数重命名为w^{\prime\prime}和b^{\prime\prime}。由于w^{\prime\prime}=\frac{w^{\prime}}{\|w^{\prime}\|_r}，重新排列得到

(12.24)

将这个结果代入(12.23)，我们得到

(12.25)

最后一步是观察到，最大化\frac1{\|w^{\prime\prime}\|^2}与最小化\frac12\|w^{\prime\prime}\|^2得到相同的解，这完成了定理12.1的证明。

12.2.4 软间隔支持向量机：几何视角

当数据不是线性可分的情况下，我们可能希望允许一些样本落在间隔区域内，甚至落在超平面的错误一侧，如图12.6所示。允许一定分类错误的模型被称为软间隔支持向量机（soft margin SVM）。在本节中，我们将使用几何论证来推导出相应的优化问题。在12.2.5节中，我们将使用损失函数的思想推导出等价的优化问题。利用Lagrangre 乘子（第7.2节），我们将在12.3节中推导出SVM的对偶优化问题。这个对偶优化问题使我们能够观察到SVM的第三种解释：作为平分正样本和负样本凸包之间连线的超平面（12.3.2节）。

关键的几何思想是引入一个松弛变量\xi_n，对应于每个样本-标签对(x_n,y_n)，允许特定样本位于间隔内甚至超平面的错误一侧（参考图12.7）。我们从间隔中减去\xi_n的值，并约束\xi_n为非负。为了鼓励样本的正确分类，我们将\xi_n添加到目标函数中：

(12.26a) (12.26b) (12.26c)

对于n=1,\ldots,N。与硬间隔SVM的优化问题（12.18）相比，这被称为软间隔SVM。参数C>0用于权衡间隔大小和总松弛量。这个参数被称为正则化参数，因为正如我们将在下一节看到的那样，目标函数（12.26a）中的间隔项是一个正则化项。间隔项\|w\|^2被称为正则化器，在许多数值优化书籍中，正则化参数会乘以这个项（第8.2.3节）。这与我们在本节中的表述不同。在这里，C的较大值意味着较低的正则化，因为我们给松弛变量更大的权重，因此更优先考虑不在间隔正确一侧的样本。

备注：在软间隔SVM的表述（12.26a）中，\boldsymbol{w}被正则化，但b没有被正则化。我们可以通过观察正则化项不包含b来看到这一点。未正则化的项b使理论分析复杂化（Steinwart和Christmann，2008，第1章），并降低了计算效率（Fan等，2008）。

12.2.5 软间隔支持向量机：损失函数视角

让我们考虑一种不同的方法来推导支持向量机（SVM），遵循经验风险最小化原则（第8.2节）。对于SVM，我们选择超平面作为假设类，即

(12.27)

我们将在本节中看到，间隔对应于正则化项。剩下的问题是，损失函数是什么？与第9章考虑回归问题（预测器的输出是实数）不同，本章我们考虑二分类问题（预测器的输出是两个标签之一\{+1, -1\}）。因此，每个样本-标签对的误差/损失函数需要适用于二分类。例如，用于回归的平方损失（9.10b）不适用于二分类。

备注：二进制标签之间的理想损失函数是计算预测与标签之间不匹配的数量。这意味着对于应用于样本x_n的预测器f，我们将输出f(x_n)与标签y_n进行比较。如果它们匹配，我们定义损失为零；如果不匹配，则损失为一。这表示为1_{(f(x_n)\neq y_n)}，并称为零一损失。不幸的是，零一损失导致了一个组合优化问题，用于寻找最佳参数w,b。组合优化问题（与第7章中讨论的连续优化问题相比）通常更难解决。

\diamondsuit

SVM对应的损失函数是什么？考虑预测器f(x_n)的输出与标签y_n之间的误差。损失描述了训练数据上的误差。推导（12.26a）的等效方法是使用合页损失（hinge loss）

(12.28)

如果f(\boldsymbol x)位于超平面的正确一侧（基于相应的标签y），并且距离大于1，这意味着t\geqslant1，并且合页损失返回零。如果f(x)位于正确一侧但太接近超平面（0<t<1），则样本x位于间隔内，并且合页损失返回一个正值。当样本位于超平面的错误一侧（t<0）时，合页损失返回一个更大的值，该值线性增加。换句话说，一旦我们比间隔更接近超平面，即使预测是正确的，我们也会受到惩罚，并且该惩罚线性增加。合页损失的另一种表示方法是将其视为两个线性部分

(12.29)

如图12.8所示。硬间隔对应的损失定义为

(12.30)

这种损失可以理解为绝不允许任何样本位于间隔内部。

对于给定的训练集\{(x_1,y_1),\ldots,(x_N,y_N)\}，我们寻求最小化总损失，同时使用\ell_2正则化（见第8.2.3节）对目标进行正则化。使用合页损失（12.28），我们得到了无约束优化问题

(12.31)

(12.31)中的第一项称为正则化项或正则器（见第8.2.3节），第二项称为损失项或误差项。回想第12.2.4节，\frac12\left\|w\right\|^{2}这一项直接来源于间隔。换句话说，最大化间隔可以解释为正则化。

原则上，(12.31)中的无约束优化问题可以直接用第7.1节中描述的（子）梯度下降法求解。为了看到(12.31)和(12.26a)是等价的，请注意合页损失（12.28）本质上由两部分线性函数组成，如(12.29)所示。考虑单个样本-标签对的合页损失（12.28）。我们可以等价地将t上的合页损失最小化替换为带有两个约束的松弛变量\xi的最小化。以方程形式表示，

(12.32)

等价于

(12.33)

将此表达式代入(12.31)并重新排列其中一个约束，我们正好得到软间隔SVM（12.26a）。

备注：让我们将本节中选择的损失函数与第9章中线性回归的损失函数进行对比。回想第9.2.1节，为了找到最大似然估计量，我们通常最小化负对数似然。此外，由于带有高斯噪声的线性回归的似然项是高斯分布，因此每个样本的负对数似然是一个平方误差函数。平方误差函数是在寻找最大似然解时最小化的“损失函数”。