从超平面到SVM（二）

源 | 小象    文 | 数据挖掘机

各位读者好，上期的文章已经讲解了《从超平面到SVM（一）》的内容，主要讲解了超平面和函数间隔最大化，本期将继续讲解《从超平面到SVM》的数学推理和核函数部分，这部分涉及到的数学知识较多，对于较难理解的部分会尽力讲清，但是仍需部分数学基础，涉及到的知识点读者可以翻阅之前的数学课本，后期若有时间我也会对机器学习中的数学知识进行盘点和总结，往继续关注本公众号的后期文章。

间隔边界与对偶算法

上期在讲函数间隔最大化那一部分时经过推理后已经得到了如下一个优化函数：

上面这个优化函数是一个优化问题，这部分涉及的知识非常的多，其中凸优化是所有优化问题里面较为简单的一种，只要一个问题经过转化后可以转化为凸优化问题，则可以认为该问题就可解了。

如上图，在线性可分的情况下，训练数据集的样本点中与分离超平面最近的样本点的实例称为支持向量，支持向量是使约束条件等号成立的带点，即：

对于yi=+1的正例点，支持向量在超平面H1上的对应方程为：

对于yi=-1的负例点，支持向量在超平面H2上的对应方程为：

                                     

如上图，蓝色的直线y=x-0.5，是划分蓝色的圆点和红色的红叉的超平面，其中红色的直线y=x和绿色的直线y=x-1是支持向量（1，1），（2，2）和（2，1），（3，2）所在的直线，可以看到红色的直线和绿色的直线之间没有其他样本点落在其中，且分离超平面位于两条直线的中央。长带的宽度，即H1与H2之间的距离称之为间隔（margin）。上期的优化函数化简后如下：

从上述函数可以看出，最大化H1和H2间隔就等同于最大化1/||w0||，为了后期求导的方便，可以写成2/||w0||，H1和H2可以称为间隔边界。在决定分离超平面时只有支持向量起到了作用，如果支持向量变化会影响到解，而移动支持向量以外的点并不会影响最终解。

为了求解上述优化函数，还需要进一步转化为数学计算问题，上面是一个比较典型的有限制条件的求多元函数极值的问题，以前在高等数学中最常见的多元函数条件极值中条件极值都是等式，此处变成了不等式，如何求解呢？下面先开始复习下条件等式下的求极值是如何求得：

上面这个函数存在极值的话，可以假设此极值点为(x0,y0)，当然，极值点未必只有一个，因为此处的限制条件为f(x,y)=0的形式，为了方便求导和带入原方程，可以将限制条件转化为y=f(x)的形式，此处就涉及到隐函数存在定理，定理如下：

看懂上述定理后，则下面简单证明下等式条件下拉格朗日乘子法的来历：

所以上述问题就转化为了一个一元函数求极值的问题，可依据求极值的条件如下：

拉格朗日乘子法：函数Z=f(x,y)在附加条件ϕ(x,y)=0下可能的极值点，可以先做拉格朗日函数：

好了，上面已经讲清了拉格朗日乘子法的原理，但是此时仍旧解决不了上面的约束问题，因为该问题约束条件是不等式，下面将逐步解决此问题。

对于约束条件是不等式约束的情况，此时不光需要引入拉格朗日乘子，还需要引入一个KKT条件，所有的不等式约束问题可以如下的表示：

其中，不同的m和n代表的是约束条件的个数，此处默认只有一个即可，然后依然构造拉格朗日函数，然后解决办法如下：

上面的求解优化方法中前两个KKT条件和之前的拉格朗日乘子法是一致的，但是后面一个就比较难懂了，可以如下去理解：

搞懂了上面的不等式优化问题后，就可以依据之前的优化问题构建对应的拉格朗日函数，其中，对每一个不等式约束引进拉格朗日乘子αi≥0,i=1,2,3,...,N，定义如下的拉格朗日函数：

为了更好的求解上述问题，此时又要引入一个新的概念，即对偶问题，可以认为是原问题的等价问题，对偶问题变换后更易求解且后期方便引入核函数，原问题的对偶问题就是极大极小问题：

于是为了得到问题的解，就变成了先求L对w、b的极小，再求对α的极大。

所以，可以总结下线性可分支持向量机的算法：

输入：给定线性可分训练集T={(x1,y1),(x2,y2),...,(xN,yN)},其中xi∈X=Rn，yi∈Y={+1,-1}，i=1,2,3,...,N

输出：分离超平面和分类决策函数

(1)构造并求解约束最优化问题

2)计算解w和b

(3)求得分离超平面

(4)分类决策函数

从上面公式中可以看出w*,b*仅仅依赖于训练数据中对应α*j>0的样本点，与其他样本点无关，其实这部分就是前面所讲的离超平面最近的向量，可以称之为支持向量，即α*j>0>0对应的那部分向量即是支持向量。

间线性不可分与核技巧

对于线性分类问题可以使用上面的线性分类支持向量机来解决，即在N维坐标空间中可以用N维的变量组合来构建一个超平面划分正例点和负例点，如果正例点和负例点的分布无法用一个超平面去划分就需要用到支持向量机非线性分类器了，当然，一般解决这种问题不可能再从头到尾重新研究一种算法，而是想办法来将非线性分类问题转化为线性分类问题，此时就需要引入一种新的办法，核技巧。

如上图，在二维空间中，x和o无法找到一条直线将其分开，但是将这些点映射到三维空间中就可以用一个平面去划分了，就实现了线性可分，所以，可以考虑通过对低维空间的样本点进行映射到高维空间，然后再在高维空间里面找到一个超平面进行划分就实现了将线性不可分转化为线性可分的问题了。

上面这种方法就是通过将样本点映射到高维特征空间然后在高维特征空间进行分类的方法，公式描述如下：

这样的方法主要分两步：

(1)      首先使用一个非线性映射将样本变换到高纬特征空间

(2)      然后在特征空间里面用线性分类器进行分类

根据分类平面的解可知，原始分类函数可以如下表示：

如果要映射为高维空间函数则需要做一次映射，表示如下：

但是如果每次都需要对每个样本做这类映射计算，然后再在高维空间做线性分类则显得很麻烦，为了解决这个问题，可以考虑进行合二为一，引入一个核变换的函数，直接将计算部分计算出来，然后直接用线性分类其分类就好了，所以，下面介绍下核函数。

核函数：设X是输入空间，H为特征空间，如果存在一个从X到H的映射：

使得对于所有的x,z∈X，函数K(x,z)满足条件：

则称K(x,z)为核函数，Φ(x)为映射函数，Φ(x)•Φ(z)为二者的内积。

于是，引入核函数以后，可以进行如下的变换：

这样，就可以把计算的问题交给核函数了，每次只需在低维空间里面进行计算，就直接完成了映射过程，然后用线性分类器就可以分类了，不过有个问题就是，如果核函数不能保证映射后的数据线性可分怎么办，这个问题也是现实中存在的，不过，经过推理和证明，总结了一些常用的核函数，这些函数多数在映射后都是可分得，对于及其特殊的情况，可以通过选择不同的核函数进行调试。

对于上面的理论基本都是抽象的推理，为了更直观去理解这部分，可以举一个很简单的例子，比如最常见的二维空间不可分的异或问题：

这样，上面两个圆圈的坐标别为(0,0)、(1,1),三角坐标为(0,1)、(1,0)，很明显，无法在二维直角坐标系找到一条直线将圆圈和三角划分开，于是可以做如下变换：

这样，上面两个圆圈的坐标别为(0,0)、(1,1),三角坐标为(0,1)、(1,0)，很明显，无法在二维直角坐标系找到一条直线将圆圈和三角划分开，于是可以做如下变换：

所以坐标就变成了(0,0,0)、(1,1,1)、(0,0,1)、(1,0,0)，此时该映射到三维空间中的四个点就可分了，其中黄色的三角确定的屏幕即是超平面：

到现在为止，已经从间隔边界和对偶算法一直讲到了核技巧，《从超平面到SVM》的理论部分就暂时讲完了，不过SVM远比我们想的要复杂些，虽然理论上已经梳理了一遍，但是它在程序中的实现也是很大的一个问题，因为SVM涉及到很多样本空间的计算，这个过程及其耗费时间，如果按照上面理论讲的来实现会发现，随着数据量的增长SVM算法会越来越慢，为了解决这一问题，后面还有一部分关于SVM实现的算法称为SMO算法，下期本文将继续讲解SVM的第三部分SMO算法。

-END-