《Python大规模机器学习》 —3.2支持向量机

3.2支持向量机

支持向量机(SVM)是一套实现分类和回归的监督学习技术（也用于异常值检测），具有非常好的通用性，因为它有特殊函数——核函数，因而可以同时适合线性和非线性模型。核函数的特点是能够使用有限的计算量将输入特征映射到一个新且更复杂的特征向量。核函数可以非线性地重组原始特征，使得以非常复杂的函数来映射响应成为可能。从这个意义上说，SVM与神经网络相当，就像通用逼近器一样，因此在许多问题上具有类似的预测能力。与前一章的线性模型相反，SVM最初用于解决分类问题，而不是回归问题。上世纪90年代SVM由AT&T实验室的数学家Vladimir Vapnik和计算机科学家Corinna Cortes提出（很多Vapnik的合作者也参与了该算法）。本质上，SVM试图通过寻找特定的超平面来分离特征空间中各类，从而解决分类问题，这种特定超平面必须被描述为在这些类的边界间具有最大分离边界的那个面（边界将被作为间隙，即类自身之间的空间）。

这意味着两个结果：

 根据经验，SVM通过在刚好位于被观察类中间的训练集中寻找解决方法来最小化测试误差，显然该方法可计算得到（这是一种基于二次规划的优化，请参考https://en.wikipedia.org/wiki/Quadratic_programming）

 由于解决方法仅取决于由相邻示例（称为支持向量）支撑的类边界，因此其他示例均可忽略，这样使得该技术对异常值不敏感，并且比基于诸如线性模型这样的矩阵求逆方法耗费内存更少。有了对该算法这样的基本概述，我们将花费几个页面介绍表征SVM的关键内容。虽然不对该方法做完整而详细的解释，但描述其工作方式确实有助于读者弄清楚技术背后发生了什么，并为了解如何将它扩展到大数据奠定基础。

历史上，SVM就像感知器一样被认为是硬边界分类器。实际上，最初SVM被设置为试图找到两个超平面，它们能将相互距离可能最大的类分开。这种方法可以很好处理线性可分的合成数据。无论如何，在硬边界版本中，SVM面对非线性可分数据时只能使用特征非线性变换才能成功。但是，当误分类错误是由数据中噪声而不是非线性造成时，其分类效果不甚满意。

出于这个原因，以能够考虑错误严重程度(硬边界发生错误才跟踪边界)的成本函数的方式引入了软边界，因此允许误分类案例有一定的容忍度，但不能太大，因为它们位于分离的超平面边界的旁边。

自从引入软边界以来，SVM也变得能够承受由噪音引起的不可分离性。软边界的引入过程是围绕近似等于误分类示例数的松弛变量来建立成本函数，该松弛变量也称为经验风险（从训练数据的角度看误分类的风险）。

在数学公式中，给定矩阵数据集X，其中包含n个示例和m个特征，以及一个表示类别+1（归属）和-1（不属于）属性的响应向量，二分类SVM尽力使成本函数最小化：

在上面函数中，w是表示分离超平面的向量系数，b表示偏离原点的偏差，还有正则化参数λ（λ≥0）。

为更好理解成本函数的工作原理，有必要将其分成两部分。第一部分为正则化项：

当假设值很高时，正则化项与向量值w的最小化过程形成鲜明对比。第二项称为损失项或松弛变量，实际上是SVM最小化过程的核心：

损失项输出误分类错误的近似值，事实上，求和运算常常会增加每个分类错误的单位值，其总数除以示例数量n得到分类错误的近似比例。

通常，就像在Scikit-learn实现中一样，从正则化项中删除lambda并由误分类参数C乘以损失项来代替:

前一个参数lambda和新C之间的关系如下：

这只是一个约定问题，因为优化公式中从参数lambda变到C并不意味着有不同结果。成本项受超参数C影响。高的C值对错误施加高惩罚,从而迫使SVM尽量对所有训练示例正确分类。因此，较大的C值趋向于用更少的支持向量，导致边界更严格，边界减少意味着偏差增加和方差减小。

这能让我们找到观察样本之间的相互作用，实际上，我们很有信心将那些被误分类或未分类的示例定义为支持向量，因为它们在边界内（嘈杂样本观察不可能分类）。如果只考虑这种情况，优化示例确实使SVM成为一种节省内存的技术，如图3-1所示。

图3-1SVM通过优化示例节省内存

在上图中，二维特征空间内有两组投影点（蓝色和白色），尽管边界两侧都存在一些误分类，但将超参数C设置为1.0的SVM方法能轻松找到分界线（由图中实线表示）。另外，边界也能被可视化（由两条虚线定义），由各自类别的支持向量决定。图中用虚圆表示支持向量，你可能注意到某些支持向量在边界外侧；由于它们属于误分类,SVM必须跟踪它们以进行优化，原因在于其错误已包括在损失项内，如图3-2所示。

图3-2超参数C=100.0时SVM的优化情况

随着C值增长，考虑到SVM优化过程中的支持向量越少边界就会越紧，因此分界线斜率也会发生变化。

相反，较小的C值会放宽边界，这样会增加方差。极小的C值甚至可能导致SVM考虑边界内的所有示例点，当存在很多错误点时，C值取最小不失为好办法。这样的设置迫使SVM忽略边界定义中的许多误分类示例（错误权重较小，在搜索最大边距时能容忍更多错误），如图3-3所示。

图3-3C值极小时SVM的优化情况

继续前面的可视化示例，如果我们减少超参数C，由于支持向量数量增加，边界实际上会扩大。因此，边界不同则SVM解析为不同分割问题。在测试数据之前，没有C值可被认为是正确的，必须通过交叉验证以经验方式找到正确的值。到目前为止，C是SVM中最重要的超参数，需要在选择核函数后对其进行设置。

核函数通过以非线性方式对其进行组合，来将原始特征映射到更高维空间。通过这种方式，原始特征空间中明显不可分离的组可以在更高维数表示中变得可分离。尽管将原始特征值明确地转换为新特征值的过程在投影到高维数时可能会在特征数量上产生潜在爆炸，但这种投影不需要太复杂的计算。核函数可被简单插入到决策函数中，而不必进行如此烦琐的计算，从而替换特征和系数向量之间的原始点积，并获得与显式映射本身相同的优化结果（这种插件称为核技巧，因为实际上是一种数学技巧）。

标准核函数是线性函数（无变换）、多项式函数、径向基函数（RBF）和S形函数。为了便于理解，RBF函数可以表示如下：

基本上，RBF和其他核函数只是直接将其自身插入到以前见过的要最小化的函数的某个变体中。以前见过的优化函数称为原始公式，而类似的重新表达称为对偶公式：

虽然在没有数学演示的情况下将原始公式转换到对偶公式非常具有挑战性，但掌握核心技巧很重要。假如有一个核函数示例，只需要进行有限数量的计算就能将其展开到无限维的特征空间，这种核技巧致使该算法在处理诸如图像识别或文本分类等非常复杂的问题方面特别有效（与神经网络相当），如图3-4所示。

图3-4用sigmoid核实现的SVM解决方案

例如，有了sigmoid核函数，上面的SVM方法变为可能，下面给出一个基于RBF的SVM方法示例，如图3-5所示。

图3-5基于RBF的SVM解决方案

从视觉效果不难看出，RBF核函数允许相当复杂的边界定义，甚至可将其分成多个部分（上面示例中，“飞地”很明显）。

RBF核函数公式如下：

Gamma是定义先验项的超参数，核转换会在支持向量周围创建某种分类气泡，因此可以通过合并气泡本身来定义非常复杂的边界形状。

sigmoid核函数公式如下：

这里除Gamma外，还应该选择r来获取最佳结果。

显然，基于sigmoid、RBF和多项式(隐含后面内容将讨论的多项式展开)的核函数方法与方差估计差异很大，因此决定采用时要求严格验证。尽管SVM能抵抗过拟合，但对其并不一定免疫。

支持向量回归与支持向量分类相关，只有符号（更类似于线性回归，使用β而不是系数向量w）和损失函数不同:

值得注意的是，唯一重要的区别是损失函数Lε，如果示例在距回归超平面的某个距离ε内，它就对误差不敏感（因此不计算它），这种最小化成本函数优化了回归问题的结果，将输出值而不是类。

3.2.1hinge loss及其变形

总结SVM的内基本要点，请记住其算法核心的成本函数为hinge loss：

如前面所述，y^表示为X与系数向量w的点积与偏差b之和：

回想感知器，这种损失函数以线性方式惩罚错误，当示例被分类在边界错误一侧时表示错误，与其边界本身的距离成正比。尽管为凸形，但缺点是到处都不可微，它有时会被可区分的变量所替换，例如平方hinge loss（也称L2损失，而L1损失是hinge loss）：

另一个变形是Huber loss，当误差等于或低于某个阈值h时，它是二次函数，否则是线性函数。该方法根据误差将hinge loss的L1和L2混合变形，是对异常值非常有抵抗力的替代方法，并且由于较大误差值非平方级，因此需要通过SVM学习进行更小的调整。Huber loss也是逻辑损失（线性模型）的替代方法，因为其计算速度更快并且能提供对类概率的估计（hinge loss不具备这种能力）。

从实际的角度来看，没有特别的报道说Huber loss或L2 hinge loss始终比hinge loss效果好。最后，选择成本函数可归结为针对每个不同的学习问题测试其可用函数（根据无免费午餐定理，机器学习中没有适合所有问题的解决方法）。