SVM 的“核”武器
一、上一次我们讲到关于SVM通过拉格朗日乘子法去求解的部分，引入乘子\alpha 得到下面的式子：
我们令
当所有的约束条件满足时，我们得到的
，而之前的优化目标就是最小化
，所以跟我们要求的目标函数就转化为：
将最大化和最小化交换之后便可以得到我们的对偶问题：
这里肯定会有很多读者疑问，为什么要用对偶解法？就是线性可分条件下引入支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。当然，交换以后的问题不再等价于原问题，这个新问题的最优值用d^* 来表示。并且，我们有d^* \le p^* ，这在直观上也不难理解，最大值中最小的一个总也比最小值中最大的一个要大吧！ 总之，第二个问题的最优值d^* 在这里提供了一个第一个问题的最优值p^* 的一个下界，在满足某些条件的情况下，这两者相等，这个时候我们就可以通过求解第二个问题来间接地求解第一个问题。这里说的某些条件就是KKT，就不再过多证明。
然后关于对偶算式的解法：首先固定\alpha ，要让 L 关于 w 和 b 最小化，我们分别对w，b求偏导数，即令 ∂L/∂w 和 ∂L/∂b 等于零。然后求对\alpha 的极大，即是关于对偶问题的最优化问题，经过上面第一个步骤的求w和b，得到的拉格朗日函数式子已经没有了变量w，b，只有\alpha ，而反过来，求得的\alpha 将能导出w，b的解，最终得出分离超平面和分类决策函数。即可得到我们的SVM的数学式的求解答案。
二、非线性情况的SVM求解
对于一个数据点 x 进行分类，实际上是通过把 x 带入到
算出结果然后根据其正负号来进行类别划分的。而前面的推导中我们得到：
因此分类函数可以写为：
这里的形式的有趣之处在于，对于新点 x的预测，只需要计算它与训练数据点的内积即可（<,>表示向量内积），这一点至关重要，是之后使用 Kernel 进行非线性推广的基本前提。此外，所谓 Supporting Vector 也在这里显示出来——事实上，所有非Supporting Vector 所对应的系数\alpha 都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。
核函数表示特征空间的隐式映射：在上文中，我们已经了解到了SVM处理线性可分求解的情况，而对于非线性的情况，SVM 的处理方法是选择一个核函数 κ(⋅,⋅) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。由于核函数的优良品质，这样的非线性扩展在计算量上并没有比原来复杂多少，这一点是非常难得的。当然，这要归功于核方法——除了 SVM 之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。
核函数通过把数据映射到高维空间来增加第一节所述的线性学习器的能力，使得线性学习器对偶空间的表达方式让分类操作更具灵活性和可操作性。因为训练样例一般是不会独立出现的，它们总是以成对样例的内积形式出现，而用对偶形式表示学习器的优势在为在该表示中可调参数的个数不依赖输入属性的个数，通过使用恰当的核函数来替代内积，可以隐式得将非线性的训练数据映射到高维空间，而不增加可调参数的个数(当然，前提是核函数能够计算对应着两个输入特征向量的内积)。
具体说来：考虑的假设集是这种类型的函数：
这里ϕ：X->F是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：
- 首先使用一个非线性映射将数据变换到一个特征空间F，
- 然后在特征空间使用线性学习器分类。
在上文我提到过对偶形式，而这个对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：
如果有一种方式可以在特征空间中直接计算内积〈φ(xi · φ(x)〉，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，这样直接计算法的方法称为核函数方法。这里直接给出一个定义：核是一个函数K，对所有x，z，满足
，这里φ是从X到内积特征空间F的映射。
对于下图来说：
事实上，上图所述的这个数据集，是用两个半径不同的圆圈加上了少量的噪音生成得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用 X1 和 X2来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：
注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为X21Z1=X1, Z2=X21, Z3=X2, Z4=X22, Z5=X1X2那么显然，上面的方程在新的坐标系下可以写作：
关于新的坐标 Z ，这正是一个 hyper plane 的方程！也就是说，如果我们做一个映射 ϕ:R2→R5 ，将 X 按照上面的规则映射为 Z ，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。
再进一步描述 Kernel 的细节之前，不妨再来看看这个例子映射过后的直观例子。当然，你我可能无法把 5 维空间画出来，不过由于我这里生成数据的时候就是用了特殊的情形，具体来说，我这里的超平面实际的方程是这个样子（圆心在 X2 轴上的一个正圆）：
因此我只需要把它映射到
这样一个三维空间中即可，下图即是映射之后的结果，将坐标轴经过适当的旋转，就可以很明显地看出，数据是可以通过一个平面来分开的。
关于拉格朗日乘子参数在核函数方法中的求解，其实是与之前是一致的，因为核函数能简化映射空间中的内积运算——刚好“碰巧”的是，在我们的 SVM 里需要计算的地方数据向量总是以内积的形式出现的。这样一来，核函数方法避开了映射高维空间的计算的复杂度和维度爆炸。我们的优化目标函数如下：
还有些可能并不是因为数据本身是非线性结构的，而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为 outlier ，在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 support vector 组成的，如果这些 support vector 里又存在 outlier 的话，其影响就很大了。例如下图：
用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。
为了处理这种情况，SVM 允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该 outlier 偏离的距离，如果把它移动回来，就刚好落在原来的超平面上，而不会使得超平面发生变形了。
现在考虑到outlier问题，约束条件变成了：
其中\xi_{i} \ge 0 为松弛变量，优化目标变为：
其中 C 是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。注意，其中 \xi 是需要优化的变量（之一），而 C是一个事先确定好的常量。完整地写出来是这个样子：
用同样的拉格朗日乘子法求解出来唯一的区别就是现在 dual variable \alpha 多了一个上限C 。而 Kernel 化的非线性形式也是一样的，只要把换成即可。这样一来，一个完整的，可以处理线性和非线性并能容忍噪音和 outliers 的支持向量机才终于介绍完毕了。
下次我们将用实例来介绍SVM的应用。敬请期待！
参考文献：（支持向量机通俗导论-july）http://blog.csdn.net/macyang/article/details/38782399
《统计学习方法》- 李航
免责声明：本文系网络转载。版权归原作者所有。如涉及版权，请联系删除！