支持向量机

动机

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

定义

更正式地来说，支持向量机在高维或无限维空间中构造超平面或超平面集合，其可以用于分类、回归或其他任务。直观来说，分类边界距离最近的训练数据点越远越好，因为这样可以缩小分类器的泛化误差。
尽管原始问题可能是在有限维空间中陈述的，但用于区分的集合在该空间中往往线性不可分。为此，有人提出将原有限维空间映射到维数高得多的空间中，在该空间中进行分离可能会更容易。为了保持计算负荷合理，人们选择适合该问题的核函数  来定义SVM方案使用的映射，以确保用原始空间中的变量可以很容易计算点积。 高维空间中的超平面定义为与该空间中的某向量的点积是常数的点的集合。定义超平面的向量可以选择在数据基中出现的特征向量 的图像的参数 的线性组合。通过选择超平面，被映射到超平面上的特征空间中的点集 由以下关系定义：  注意，如果随着 逐渐远离， 变小，则求和中的每一项都是在衡量测试点 与对应的数据基点 的接近程度。这样，上述内核的总和可以用于衡量每个测试点相对于待分离的集合中的数据点的相对接近度。

历史

原始SVM算法是由弗拉基米尔·万普尼克和亚历克塞·泽范兰杰斯于1963年发明的。1992年，Bernhard E. Boser、Isabelle M. Guyon和弗拉基米尔·万普尼克提出了一种通过将核技巧应用于最大间隔超平面来创建非线性分类器的方法。 当前标准的前身（软间隔）由Corinna Cortes和Vapnik于1993年提出，并于1995年发表。

软间隔

为了将SVM扩展到数据线性不可分的情况，我们引入铰链损失函数，
当约束条件(1) 满足时（也就是如果 位于边距的正确一侧）此函数为零。对于间隔的错误一侧的数据，该函数的值与距间隔的距离成正比。
然后我们希望最小化
其中参数 用来权衡增加间隔大小与确保 位于间隔的正确一侧之间的关系。因此，对于足够小的 值，如果输入数据是可以线性分类的，则软间隔SVM与硬间隔SVM将表现相同，但即使不可线性分类，仍能学习出可行的分类规则。

计算SVM分类器

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

原型

最小化(2)可以用下面的方式改写为目标函数可微的约束优化问题。
对所有 我们引入变量。注意到 是满足 的最小非负数。

因此，我们可以将优化问题叙述如下
 
这就叫做原型问题。

对偶型

通过求解上述问题的拉格朗日对偶，得到简化的问题
这就叫做对偶问题。由于对偶最小化问题是受线性约束的 的二次函数，所以它可以通过二次规划算法高效地解出。
这里，变量  定义为满足
. 
此外，当  恰好在间隔的正确一侧时，且当 位于间隔的边界时。因此， 可以写为支持向量的线性组合。
可以通过在间隔的边界上找到一个 并求解
得到偏移量。（注意由于 因而 。）

核技巧

假设我们要学习与变换后数据点 的线性分类规则对应的非线性分类规则。此外，我们有一个满足 的核函数。

我们知道变换空间中的分类向量 满足
其中  可以通过求解优化问题
得到。与前面一样，可以使用二次规划来求解系数。同样，我们可以找到让 的索引，使得  位于变换空间中间隔的边界上，然后求解
最后，可以通过计算下式来分类新点

现代方法

用于找到SVM分类器的最近的算法包括次梯度下降和坐标下降。当处理大的稀疏数据集时，这两种技术已经被证明有着显著的优点——当存在许多训练实例时次梯度法是特别有效的，并且当特征空间的维度高时，坐标下降特别有效。

次梯度下降

SVM的次梯度下降算法直接用表达式
注意  是  与  的凸函数。因此，可以采用传统的梯度下降（或SGD）方法，其中不是在函数梯度的方向上前进，而是在从函数的次梯度中选出的向量的方向上前进。该方法的优点在于，对于某些实现，迭代次数不随着数据点的数量 而增加或减少。

坐标下降

SVM的坐标下降算法基于对偶问题
对所有 进行迭代，使系数 的方向与 一致。然后，将所得的系数向量 投影到满足给定约束的最接近的系数向量。（通常使用欧氏距离。）然后重复该过程，直到获得接近最佳的系数向量。所得的算法在实践中运行非常快，尽管已经证明的性能保证很少。

性质

SVM属于广义线性分类器的一族，并且可以解释为感知器的延伸。它们也可以被认为是吉洪诺夫正则化的特例。它们有一个特别的性质，就是可以同时最小化经验误差和最大化几何边缘区; 因此它们也被称为最大间隔分类器。
Meyer、Leisch和Hornik对SVM与其他分类器进行了比较。

参数选择

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

实现

最大间隔超平面的参数是通过求解优化得到的。有几种专门的算法可用于快速解决由SVM产生的QP问题，它们主要依靠启发式算法将问题分解成更小、更易于处理的子问题。
另一种方法是使用内点法，其使用类似牛顿法的迭代找到卡罗需－库恩－塔克条件下原型和对偶型的解。
这种方法不是去解决一系列分解问题，而是直接完全解决该问题。为了避免求解核矩阵很大的线性系统，在核技巧中经常使用矩阵的低秩近似。
另一个常见的方法是普莱特的序列最小优化算法（SMO），它把问题分成了若干个可以解析求解的二维子问题，这样就可以避免使用数值优化算法和矩阵存储。
线性支持向量机的特殊情况可以通过用于优化其类似问题逻辑回归的同类算法更高效求解；这类算法包括次梯度下降法（如PEGASOS）和坐标下降法（如LIBLINEAR）。LIBLINEAR有一些引人注目的训练时间上的特性。每次收敛迭代花费在读取训练数据上的时间是线性的，而且这些迭代还具有Q-线性收敛特性，使得算法非常快。
一般的核SVM也可以用次梯度下降法（P-packSVM）更快求解，在允许并行化时求解速度尤其快。
许多机器学习工具包都可以使用核SVM，有LIBSVM、MATLAB、SAS、SVMlight、kernlab、scikit-learn、Shogun、Weka、Shark、JKernelMachines、OpenCV等。