支持向量机（SVM）

数据分类是机器学习中的一项常见任务。 假设某些给定的数据点各自属于两个类别之一，而目标是确定新的数据点属于哪个类别。对于支持向量机来说，数据点被视为  维向量，而我们想知道是否可以用  维度的超平面来分开这些点。这就是所谓的线性分类器。可能会有许多超平面可以用来分类这些数据。一个合理的最佳超平面的选择是以最大间隔把两个类别分开的超平面。因此，我们要选择能够让到每一侧最近的数据点的距离最大化的超平面。如果存在这样的超平面，则称为最大间隔超平面，而其定义的线性分类器被称为最大间隔分类器，或者叫做最稳定的感知器。

更正式地说，支持向量机在高维度或无限维度空间中构造一个或一组超平面，这些超平面可用于分类、回归或其他任务，如孤立点检测。^[3] 直观上来说，好的间隔，是与超平面距离最近的任何类别的训练数据点与该超平面的距离越大越好(所谓的功能型间隔)。因为通常间距越大，分类器的泛化误差越小。^[4]

虽然最初的问题可以在有限维空间中解决，但用于区分的集合在该空间中往往不是线性可分的。为此，有人提出将原来的有限维空间映射到维数高得多的空间中，这样在该空间中进行分离可能会更容易。为了保持计算负荷的合理性，人们选择适合该问题的核函数   来定义支持向量机使用的映射，以确保原空间中的变量可以很容易的进行成对的向量输入值的点积计算。^[3] 高维空间中的超平面被定义为与该空间中的向量的点积是常数的点的集合，这样的一组向量是该超平面的正交（并因此最小）向量集。定义超平面的向量可以选择在数据基中出现的特征向量   的图像的参数   的线性组合。通过选择超平面，被映射到超平面上的特征空间中的点集   可以定义为：   。需要注意的是，如果随着  逐渐远离  ，  会变小，则求和中的每一项都是在衡量测试点  与对应的数据基点  的接近程度。这样，上述内核的总和可以用于衡量每个测试点相对于待分离的集合中的数据点的相对接近程度。这样一组点  映射到任何超平面上都可能会有非常复杂的结果，从而允许原本在原空间中完全不凸显的集合之间进行更复杂的区分。

支持向量机可以用来解决各种实际问题:

• 支持向量机有助于文本和超文本分类。用于标准归纳和转导推理中，都可以显著减少所需要的有标签分类的样本数。浅层语义分析的一些方法就是基于支持向量机的。^[6]
• 图像分类也可以使用支持向量机。实验结果表明，只需三到四轮相关反馈，支持向量机实现了比传统查询细化方案更高的搜索精度。对于图像分割系统也是如此，包括那些根据瓦普尼克 (Vapnik)的建议，使用修改版的特权方法的支持向量机。^[7][8]
• 可以用支持向量机识别手写字体。^[9]
• 支持向量机算法已广泛应用于生物和其他科学。 它被用于蛋白质分类，高达90%的化合物能够被正确分类。基于支持向量机权重的置换检验已被建议作为解释支持向量机模型的一种机制。^[10][11] 支持向量机权重也可以被用来解释过去的支持向量机模型。^[12] 支持向量机模型的事后解释用于通过模型特征识别来进行预测，是一个相对较新的研究领域，在生物科学中有着特殊的意义。

最初的支持向量机算法是由弗拉基米尔·瓦普尼克(Vladimir N. Vapnik)和Alexey Ya. Chervonenkis于1963年发明的。1992年，Bernhard E. Boser、Isabelle M. Guyon和弗拉基米尔·瓦普尼克(Vladimir N. Vapnik)提出了一种通过将核技巧应用于最大间隔超平面来创建非线性分类器的方法。^[13] 当前标准的前身(软间隔)由Corinna Cortes和瓦普尼克 (Vapnik)于1993年提出，并于1995年发布。^[1]

一个  个点的训练数据集可以描述成：

其中  要么是1要么是-1，表明点  所属的类别。每个  都是一个  维实向量。我们所需要的是将  的点集与  的点集分开的“最大间隔超平面”，从而使超平面与最近的点  之间的距离最大化。为此，从每一组点来看，超平面和最近点之间的距离，来自任一组的最大化。

任何超平面都可以描述成满足下面方程的点集  ，

其中   是超平面的法线向量(不一定归一化)。除了   不一定需要是单位向量以外，就和海赛范式一样。参数   确定从原点沿法向量  到超平面的偏移量。

5.1 硬间隔

如果这些训练数据是线性可分的，可以选择两个平行超平面来分离这两个类别的数据，使得它们之间的间距尽可能大。在这两个超平面范围内的区域称为“间隔”，最大间隔超平面是位于它们正中间的超平面。这些超平面可以由方程：

  (这个边界上或者上方区域的任何东西都属于一类，标签为1)

和

  (这个边界上或者下方区域的任何东西都属于另一类，标记为 -1)。

从几何上来看，这两个超平面之间的距离为  ^[1]。因此为了最大化两平面间的距离，我们想要最小化  。该距离可以使用从点到平面的距离的方程来计算。为了使得样本数据点都在超平面的间隔区以外，我们需要保证对于所有的  满足其中的一个条件：

 时，  

或者

 时，  。

这些约束表明每个数据点都必须位于间隔的正确一侧。

这可以重新描述为：

  （1）

即: “对于  ，在满足  的条件时，  为最小化 。"

这个问题的解  和  决定了我们分类器  。

该几何描述的一个显而易见却重要的结果是，最大间隔超平面完全是由最靠近它的那些  确定的。这些  叫做支持向量。

5.2 软间隔

为了将支持向量机扩展到数据线性不可分的情况，我们引入了铰链损失函数，

其中   是第 i 个目标(在这种情况下，1或 -1)，以及当前输出为  。

当约束条件(1)满足，即  位于间隔的正确一侧时，该函数为零。对于间隔的错误一侧的数据，该函数的值与距间隔的距离成正比。然后我们希望最小化

其中参数   用来权衡增加间隔大小与确保  位于间隔的正确一侧之间的关系。因此，对于足够小的  值，如果输入数据是可以线性分类的，则软间隔支持向量机与硬间隔支持向量机将表现相同，但即使是不可线性分类，仍能学习出可行的分类规则。

瓦普尼克 (Vapnik)在1963年提出的原始最大间隔超平面算法构造了一个线性分类器。然而，在1992年，Bernhard E. Boser、Isabelle M. Guyon和弗拉基米尔·瓦普尼克(Vladimir N. Vapnik)提出了一种通过将核技巧(最初由Aizerman 等人 ^[15]提出)用于最大间隔超平面来创建非线性分类器的方法。^[13] 除了每一个点积都被一个非线性核函数代替之外，所得到的算法在形式上是类似的。这允许算法在转换后的特征空间中拟合最大间隔超平面。这个转换可以是非线性的且转换后的空间是高维度的。虽然这个分类器是一个转换后的特征空间中的超平面，但在原始输入空间中可能是非线性的。

值得注意的是，在高维度特征空间中计算，会增加支持向量机的泛化误差，但是如果给定足够的样本，该算法仍然可以表现很好。^[16]

一些常用的核函数包括:

• 齐次多项式:  。
• 非齐次多项式:  。
• 高斯径向基函数:   ，其中  。有时参数化使用  。
• 双曲正切:   其中一些(不是所有)  和  。

根据等式  ，核函数与转换相关   。转换空间中也有w的值，即  。与w的点积也可以用核技巧计算，即  。

计算(软间隔)支持向量机分类器相当于使下面表达式最小化

如上所述，由于我们关注的是软间隔分类器，   选择足够小的值就能得到可线性分类的输入数据的硬间隔分类器。下面会详细介绍将(2)简化为二次规划问题的经典方法，之后会讨论一些最近才出现的方法，如次梯度下降法和坐标下降法。

7.1 原型

最小化(2)可以用以下方式重写为具有目标函数可微的约束优化问题。

对于每一个   我们引入了一个变量  。其中  为满足  条件的最小的非负数。

因此，我们可以将优化问题重写如下，即原型问题。

对于所有 i，满足  条件时，  达到最小化

7.2 对偶型

通过求解上述问题的拉格朗日对偶，可以得到一个简化的问题，称为对偶型问题。即：

对于所有i，满足  条件时，  达到最大化。

因为对偶最大化问题是在线性约束下的二次函数  ，它可以通过二次规划算法有效地求解。

这里，变量   被定义为  。

此外， 当  位于间隔的正确一侧时，可以确定  。并且当  位于间隔的边界上时，  。由此可见   可以写成支持向量的线性组合。

偏移量  可以通过查找一个在间隔的边界上的   来求解，

  (由于  ，所以   )

7.3 核技巧

假设现在我们想要学习一个非线性分类规则，它对应于转换数据点的线性分类规则   此外，还给出了一个满足  的核函数  。

我们知道向量  的分类在转换空间中满足

其中  通过优化问题求解获得

对于所有i，满足  条件时，  达到最大化。

其中系数  可以像以前一样用二次规划求解。同样，我们可以找到一些索引  使得  。从而  位于转换空间的间隔的边界上，然后求解

最后，新的点可以通过计算进行分类

7.4 现代方法

最近用于查找支持向量机分类器的算法包括: 次梯度下降和坐标下降。这两种方法在处理大型稀疏数据集时都被证明具有比传统方法更显著的优势。在有许多训练样本的情况下，次梯度方法会特别有效，而在特征空间维数较高的情况下，坐标下降特别有效。

次梯度下降

用于支持向量机的次梯度下降算法可以直接使用以下表达式

其中  是  和  的凸函数。因此，可以使用修正后的传统的梯度下降(或SGD)方法，即不是在函数梯度的方向上进行，而是在从次梯度函数中选择的向量的方向上进行。这种方法的优点是，对于某些实现方法，迭代的次数不随数据点的数量  而变化。^[17]

坐标下降法

从对偶问题看用于支持向量机的坐标下降法算法

对于所有i，满足  条件时，  达到最大化。

对于迭代每一个  ，系数  会被调整到  方向。然后，系数   的结果向量会投影到满足给定约束系数的最近的向量上。(通常会使用欧式距离)。然后重复该过程，直到获得近优向量。最终的算法在实践中速度极快，尽管几乎没有性能保证被运用。^[18]

上述软间隔支持向量机是用于铰链损失的经验风险最小化的算法的示例。以这种方式看，支持向量机属于统计推理的自然算法，它的许多独特特征都是来自于铰链损失的行为。这种观点可以帮助进一步深入的了解支持向量机的工作原理和方式，并使我们能够更好地分析它们的统计特性。

8.1 风险最小化

在监督学习中，我们会得到一组有标签  的训练样本  。并希望通过  预测   。为此，我们形成一个假设  。即  是一个很好的  的近似值。好的近似值通常借助于损失函数，  表示对于  的预测会有多差的  值。然后我们想选择一个假设 来最小化预期风险:

在大多数情况下，我们不知道  的联合分布情况。所以一种常见的策略是选择一个假设条件来最小化经验风险:

在某些关于随机变量  的序列的假设下 (例如，它们是由有限马尔可夫过程产生)，如果所考虑的假设集合足够的小，则经验风险的最小值将近似于期望风险的最小值，因为   变的很大。这种方法被称为经验风险最小化(ERM)。

8.2 正规化和稳定性

为了使最小化问题有一个明确的解决方案，我们必须对被考虑到的假设的集合  施加约束。如果  是一个赋范空间(由于使用支持向量机)，一种特别有效的技术是只考虑满足  的那些假设  。这相当于强加一个正规化惩罚  ，并解决新的优化问题

这种方法被称为吉洪诺夫正则化方法。

更直接地说，  可以用于衡量这个假设条件  的复杂性，因此更简单的假设会更好。

8.3 支持向量机和铰链损失

记得软间隔支持向量机分类器   可以被用来最小化以下表达式:

根据上面的讨论，我们看到，支持向量机技术等同于使用吉洪诺夫正则化最小化经验风险。在这种情况下，损失函数是铰链损失：

从这个角度来看，支持向量机与其他基本的分类算法密切相关。如正则化最小二乘法和逻辑回归。

这三者之间的区别在于损失函数的选择不同：正则化最小二乘法的损失函数等同于有平方损失的经验风险最小化的损失函数，即  ，也等同于采用对数损失的逻辑回归的损失函数，即  

目标函数

铰链损失和这些其他损失函数之间的差异最好用目标函数来表示，即对给定的成对的随机变量  的最小化预期风险的函数。

特别是，让   表示以  为条件的  。在分类设置中，我们有:

因此，最佳分类器是:

对于平方损失，目标函数是条件期望函数，即  。对于逻辑损失，是优势对数函数，即  。虽然这两个目标函数都产生了正确的分类器，如  。它们给了我们足够的信息来完成对  的描述。

另一方面，可以为铰链损失检查目标函数的是  。因此，在足够丰富的假设的空间(或等价的)中，对于适当选择的核函数(支持向量机分类器将根据  收敛到最简单的函数)，对数据进行正确分类。对于线性分类，这扩展了对支持向量机的几何学解释，经验风险通过任何间隔位于支持向量之间的函数达到最小化，其中最简单的是最大间隔分类器。^[19]

支持向量机属于广义线性分类器，可以解释为是感知器的扩展。它们也可以被认为是吉洪诺夫正则化的特例。一个特殊的属性是它们同时最小化了经验分类误差并且最大化了几何间隔。因此，它们也被称为最大间隔分类器。

Meyer、Leisch和Hornik将支持向量机分类器与其他分类器进行了比较。^[20]

9.1 参数选择

支持向量机的有效性取决于核函数、核参数和软间隔参数C 的选择。 通常会选只有一个参数  的高斯核函数。C 和  的最佳组合通常通过具有C 和  的指数增长序列的网格搜索来选择。例如，  且  。通常情况下，使用交叉验证来检查参数选择的每一个组合，并选择具有最佳交叉验证精度的参数。或者，最近在贝叶斯优化中的工作可以用于选择 C 和   ，通常需要评估比网格搜索少得多的参数组合。然后，使用所选择的参数在整个训练集上训练用于测试和分类新数据的最终模型^。[21]

9.2 问题

支持向量机的潜在缺点包括以下几个方面:

• 输入数据需要的完整的分类标签。
• 未校准的类成员概率，支持向量机来源于瓦普尼克 (Vapnik)的理论，该理论避免了对有限数据的概率估计。
• 支持向量机只可直接用于两种类别的任务。因此，必须应用将多种类别的任务简化为几个二进制问题的算法。
• 解出的模型的参数很难理解。

10.1 支持向量聚类(SVC)

支持向量聚类是一种与建立在核函数的基础上的类似的方法，但其适用于无监督学习模型。它被认为是数据科学中的一种基本方法。

10.2 多元分类支持向量机

多元分类支持向量机，是通过从多元有限集合提取标签，对实例进行标签分类的支持向量机。

这样做的主要方法是将单个多元分类问题简化为多个二进制分类问题。^[22] 这种简化的常用方法包括:^[22][23]

• 构建用于区分一个标签和其他标签(一对多)或者每对类别(一对一)之间的二进制分类器。一对多情况下，使用赢者通吃的策略对新的实例进行分类，其中功能的输出值为最高的分类器负责分配该类别(重要的是功能的输出值要经过校准以产生可比较的分数)。对于一对一的方法，采用最多投票策略进行分类。其中每个分类器将实例分配给两个类别中的一个，然后分配的类别的投票增加一票，最后投票最多的类别确定为该实例分类。
• 有向无环图支持向量机^[24]
• 纠错输出编码^[25]

Crammer和Singer提出了一种多元分类支持向量机的方法，将多元分类问题转化为单个优化问题，而不是将其分解为多个二进制分类问题。^[26]  

10.3 转导支持向量机

转导支持向量机扩展了支持向量机，在半监督学习中，它们也可以通过遵循转导原理来处理部分标记的数据。这里，除了训练集  之外，学习者还会有一套要分类的测试样本  。

理论上，转导支持向量机由以下最初的优化问题来定义:^[2]

即  ，且当   和  时，如果满足  和  的条件，

在  中，  会达到最小化。

转导支持向量机由弗拉基米尔·瓦普尼克(Vladimir N. Vapnik)于1998年提出。

10.4 结构化支持向量机

支持向量机已经被推广为结构化支持向量机，其中标记空间是结构化的且可能具有无限的大小。

10.5 回归

弗拉基米尔·瓦普尼克(Vladimir N. Vapnik)、Harris Drucker、Christopher J. C. Burges、Linda Kaufman和Alexander J. Smola在1996年提出了回归的支持向量机版本。^[30] 这种方法被称为支持向量回归(SVR)。通过支持向量分类而建立的模型仅依赖于训练数据的子集，因为用于构建该模型的成本函数并不关心超出间隔的训练点。类似地，通过支持向量回归建立的模型也只依赖于训练数据的子集，因为用于建立该模型的成本函数忽略了任何接近模型预测的训练数据。另一个被称为最小二乘支持向量机(LS-SVM)的支持向量机版本是由Suykens和Vandewalle提出的。^[31]

训练原始的支持向量回归机意味着解决^[3]

满足  的条件时，  达到最小化。

其中  是具有目标值  的训练样本。内积加截距  是对该训练样本的预测。  是作为阈值的自由参数，即所有预测都必须在真实预测的范围  内。并通常会使用一个松弛变量，以允许误差并在上面的方法不可行的情况下允许使用近似值。

10.6 贝叶斯支持向量机

2011年，Polson和Scott证明，支持向量机通过数据增强技术承认了贝叶斯解释。^[33] 在这种方法中，支持向量机被视为一个图形模型(其中参数通过概率分布连接)。这种扩展视图允许将贝叶斯技术用于支持向量机，例如灵活的特征建模、自动超参数调整和预测不确定性量化。最近，贝叶斯支持向量机的可扩展版本由Wenzel等人开发，使得其能够应用于大数据。^[34]

最大间隔超平面的参数是通过求解优化得到的。有几种专门的算法用于快速解决由支持向量机产生的二次规划(QP)问题，主要依靠启发式算法将问题分解成更小、更易于处理的子问题。

另一种方法是使用内点法，该方法使用类似牛顿法的迭代来找库恩塔克条件(K-T条件)下原型和对偶型的解。^[35] 这种方法不是去解决一系列分解问题，而是直接完全解决该问题。为了避免求解核矩阵很大的线性系统，在核技巧中经常使用矩阵的低秩近似。

另一种常见的方法是Platt的序列最小优化算法(SMO)，它将问题分成若干个可以解析求解的二维子问题，这样可以避免使用数值优化算法和矩阵存储。该算法概念简单，易于实现，通常速度更快，并且对于困难的支持向量机问题具有更好的可扩展特性。^[36]

线性支持向量机的特殊用例可以通过用于优化其类似问题逻辑回归算法更高效的求解。这类算法包括次梯度下降法(如PEGASOS^[37])和坐标下降法(如LIBLINEAR^[38])。LIBLINEAR有一些引人注目的训练时间上的特性。每次收敛迭代花费在读取训练数据上的时间是线性的，并且迭代还具有Q-线性收敛特性，使得算法速度非常快。

一般使用核函数的支持向量机也可以使用次梯度下降法(如P-packSVM^[39])更有效地求解，当允许并行化时，求解速度尤其快。

许多机器学习工具包中都有可以使用核函数的支持向量机，包括LIBSVM、MATLAB、SAS、SVMlight、 kernlab、scikit-learn、Shogun、Weka、 Shark、 JKernelMachines、OpenCV以及其他。