大白话SVM支持向量机：三天从入门到入坟(史上最详细推导)

支持向量机

支持向量机（SVM）是一种用于解决二分类问题的模型，与之前所有的模型相比，它要复杂得多。原因在于它涉及到的理论涵盖凸优化理论、对偶理论与核技巧等。最初，SVM适用于线性可分的数据集，但是引入了核函数后，它也能被用于线性不可分的情形。本质上，SVM是一个二次规划问题，现有的许多软件都可以用于求解，但考虑到效率问题，实际求解过程中运用的是John Platt提出的SMO算法。在深度学习出现之前，SVM被认为是效果最好、最强大的模型。

 

SVM的核心思想

       SVM的目标还是在于寻找一个超平面，将两种不同类别的数据分开。但SVM与其他模型不同的是，样本的正例和负例分别用1和-1标记，而不是1和0，这种标记方式是SVM比较特殊的地方，对于推导过程至关重要。我们需要解决如下一个二分类的问题。

这个数据集是线性可分的，在二维空间中超平面退化为1条直线。我们给出了2种能将数据分开的超平面，如下。

       显然，能够将这个数据集分开的超平面有无限多个，那么我们自然就要问一个问题：在这些超平面中，是否存在一个最好的超平面？SVM解决的正是这个问题，它能够在所有超平面中求解出一个最好的超平面。我们如何定义一个超平面有多“好”呢？好的超平面需要具备一定的鲁棒性。

       实线代表分割超平面，圈出来的2个数据点就是支持向量。SVM认为，分割超平面应能将数据尽可能的分开，也就是数据点要离超平面足够远（两条虚线与分割超平面之间的距离），这样就能容忍更多的离群点，提高模型的鲁棒性。

 

硬间隔SVM

分割超平面可以写为 ，我们在分割超平面两边新增加两个超平面（图中的虚线）用以度量分割的间隔。它们总是可以写为 和 。我们不妨假设分割超平面为 ，上下平移后 后，得到 和 ，这三个平面两边同时除以 得到：

 

再令

就得到：

我们的目标是让这三个超平面之间的间隔尽可能大，同时要保证没有数据点落在间隔之间。我们定义 与 的间隔为 ，则 与 的间隔也为 。因此我们只需要最大化 ，同时保证所有数据点距离 的距离大于 即可。

如上图所示

位于 与 上，且向量 与 的法向量 平行，即 与 之间的夹角为0。则它们的内积为：

同时

其中， )， )，则

这样就得到了需要优化的目标——间隔。我们需要最大化间隔 ，并且确保所有的数据点距离超平面的距离大于这个间隔。因此，需要加上这一约束条件。

由点到平面的距离公式可得，某一数据点 距离超平面的距离为：

因此，可以得到约束条件 ，即：

       其次，由我们模型的定义可知，当 时， ， 时， ，则 等价于 ，上述约束条件转化为 。至此，我们得到了SVM的数学描述。

当然，我们可以把上述模型转化为一个等价的最小化问题。

软间隔SVM

       以上数学模型被称之为硬间隔的SVM，因为它严格约束了所有的样本点必须位于间隔之外。不难发现，SVM起决定作用的是支持向量，它们是离分割超平面最近的样本点。如果有离群点距离分割超平面更近，则这些样本会成为新的支持向量，最大间隔也会改变。其次，对于下面的数据集来说，硬间隔的SVM是无解的。

为了进一步提升模型的鲁棒性，我们为每个样本引入一个松弛变量 ，并将约束条件改为 。当 时，意味着允许样本点落在最大间隔内。当 时，意味着允许样本被错误分类。

       显然，只要 足够大，模型总是有解的，即使所有的样本都被分错，我们不允许这种情况发生，因此要在我们的目标函数中加入惩罚项，防止 过大。如此就能得到软间隔的SVM。

 

       其中 为超参数，越大时越不能容忍异常点。当 趋于正无穷时，等价于硬间隔SVM，当C为0时，模型总是有解的，可以容忍任何异常点和错分类点。因此，软间隔的SVM更具有一般性。

SVM的对偶形式

1、原始问题

       软间隔SVM的目标函数时一个凸函数，约束条件是仿射函数，因此，这是一个不等式约束的凸优化问题。对于一个凸优化问题

其中 是定义在 上的连续可微函数，可以引入拉格朗日函数

 

这里 ， ， ， 和 是拉格朗日乘子， 。考虑 的函数：

       下标 表示原始问题。假设给定某个 ，它违反了原始问题的约束条件，即存在某个 使得 或 ,那么就有

       因为若某个 使约束 ，则可令 趋于 。若某个 使 ，则可令 使 趋于 ，而将其余 ， 均取为0。

       相反地，如果 满足约束条件，即 和 ，则有

当所有 均取为0时，上式可取等号，此时 。若再进一步考虑极小化问题

则它是与原始问题

等价的，因此它们有相同的解。这样一来，就把原始最优化问题表示为拉格朗日函数的极小极大问题。为了方便，定义原始问题的最优值

 

 

 

2、对偶问题

       原始问题时一个极大极小问题，即先对拉格朗日函数 求关于的极大值，再求关于 的极小值。我们可以再定义一个极小极大问题，即先对拉格朗日函数 求关于 的极小值，再求关于 的极大值。定义

再考虑极大化 ，即

       可以将这一极大极小化问题表示为有约束的最优化问题

如此定义的一个优化问题称为原始问题的对偶问题。定义对偶问题的最优解

3、原始问题与对偶问题的关系

       根据原始问题和对偶问题的定义，可以得到

即

取任何值时，上式总是成立的，因此，当原始问题和对偶问题都取最优值时，上式依然成立，即

原始问题的最优解是对偶问题最优解的一个上界，它们之间的差 称为对偶间隙。当满足某些条件时，对偶间隙为0，原始问题和对偶问题的最优解相等。此时，可以通过求解对偶问题得到原始问题的最优解。下面叙述这些条件。

       对于原始问题

假设 和 是凸函数， 是仿射函数，且不等式约束是严格可行的，则* 分别是原始问题和对偶问题的最优解的充分必要条件是 满足下面的Karush-Kuhn-Tucker(KKT)条件：

       特别指出 被称为互补松弛条件，由此条件可知：若 ，则 ，若 ，则 。下面我们证明KKT条件的充要性

必要性：

假设，即，则原始问题和对偶问题取得最值的必要条件是

同时，还需要满足约束条件 

因此，我们需要证明的只剩下互补松弛条件

由于，因此有

 

第一个等号是因为原问题的最优值等价于极大极小化拉格朗日函数，第二个等号根据拉格朗日函数的定义和对偶间隙为0，第三个不等号是因为函数值必定大于等于函数的最小值，最后一个不等号是因为满足约束条件和  。

因此中间的不等号可以全部变为等号，得到

充分性

假设 满足KKT条件，那么由凸函数的定义可知

以及仿射函数的定义，可知

 

又由KKT条件 ，可知

当x、x* 满足约束条件时，可知

可得

带入 可得

因此 是最小值点，得证。

 

 

我们回顾软间隔SVM需要求解的问题：

显然，目标函数是凸函数，且不等式约束也是凸函数，因此这个问题可以被转换为对偶问题来求解。定义拉格朗日函数

。对偶问题是拉格朗日函数的极大极小问题。首先求 对 的极小值，由

得

将其带入拉格朗日函数 得到

再对 求 的极大，即得到对偶问题：

进一步，由 可知 ，又由于 ，因此得到 ，问题变换为：

通过求解这一对偶问题，可以得到原始问题的最优解。

核技巧

       上述的SVM是线性模型，适用于线性可分的情形，但是，很多时候分类问题是非线性的，无法使用超平面将不同类别分开。这时可以使用非线性支持向量机，其与线性支持向量机唯一的区别在于利用了核技巧。当然，核技巧不仅可以应用于支持向量机，而且可以应用于其他统计学习问题。

       一个非线性的分类问题类似于下图的数据集 。 表示样本的类别， 代表正例， 代表负例。

显然，这个数据集无法用直线（线性模型）将不同类别的样本能正确分开，但是可以利用一条圆形曲线将它正确分开。非线性问题往往不好求解，所以我们希望能用解线性分类的方法解决这个问题，这里所采取的方法就是对数据集进行一个非线性变换，将变换后的数据集转换为一个线性问题，如此就可以用线性模型来解决了。

       具体来说，我们可以定义一个非线性映射 。将映射 作用到所有样本点上，则原数据集经过非线性变换后的结果如下。

此时，经过非线性变换后的数据可以利用线性SVM正确分类了。由于特征 通过非线性变换后变成了 ，因此线性SVM变为

这个例子说明，用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类方法从变换后的训练数据中学习分类模型。核技巧就属于这样的方法。

留意到，目标函数中 是 的向量内积，在高维空间中，内积运算是比较慢的，因此我们希望引入一个函数，当给定 和 时，函数 。如此，就能用函数 来代替内积运算，提高运算效率。能满足这一条件的函数，就是核函数。

       例如，我们可以定义核函数

容易验证， 。

       常用的核函数有：多项式核函数

它会将特征 从原来的空间变换到 维的空间中，对应的支持向量机是一个 次多项式分类器。

 

高斯核函数

它会将特征 从原来的空间变换到无限维的空间中，对应的支持向量机是高斯径向基函数分类器。