概述

SVM&＃xff08;支持向量机&＃xff09;是一个二分类的模型&＃xff0c;它的主要思想就是间隔最大化&＃xff0c;那么问题来了&＃xff0c;什么是间隔最大化&＃xff0c;老规矩&＃xff0c;没图说个JB&＃xff0c;所以喽&＃xff0c;首先先来了解下分类的概念&＃xff0c;如图&＃xff1a;

图中&＃xff0c;每个点是一个样本&＃xff0c;黑色的点属于一类&＃xff0c;用1表示&＃xff1b;白色的点属于一类&＃xff0c;用-1表示。我们现在目的就是找得一条线可以将这两类分开&＃xff0c;这条直线具体又是怎么完成分类呢&＃xff0c;假设我们现在有了这条直线方程了&＃xff0c;那么根据我们高中学过的数学知识可以知道&＃xff0c;将黑色的点的坐标带入直线方程&＃xff0c;它得到的值都大于0的&＃xff0c;同理&＃xff0c;白色的点都小于0&＃xff0c;那么我们岂不是就完成了分类目的了。。。
下面在来看第二张图&＃xff1a;

从刚才的分析中我们可以总结出&＃xff1a;我们的目的就是找到那条可以使样本分开的直线&＃xff0c;但是如上图所示我们可以看到有无数条直线都可以将样本分开&＃xff0c;你是否又产生了疑问&＃xff1a;“那种可以分开的直线有很多条哇&＃xff0c;该选哪一条呢&＃xff1f;”现在就可以回归刚刚的问题啦&＃xff0c;通过最大间隔求得最优的那条&＃xff0c;当然还是看图喽&＃xff1a;

图中黄色区域就是间隔喽&＃xff0c;从我们直观感受可以看出&＃xff1a;间隔的大小是由距离直线最近的那些点&＃xff08;也就是图中蓝色和红色圈出的点&＃xff09;所决定&＃xff0c;这些点在这里有个名字——支持向量&＃xff0c;哦吼&＃xff0c;估计你现在对支持向量机这个名字有点认识了&＃xff0c;当这些支持向量距离直线的距离达到最大时&＃xff0c;间隔也就达到了最大&＃xff0c;而这条直线也正是我们要找的。。。

以上就是SVM的基本思想&＃xff0c;是不是还挺简单的哈。。。哦&＃xff0c;对了还有一点哦&＃xff0c;以上都是2维的样本&＃xff0c;当样本是3维时&＃xff0c;我们就要将那条直线升级为一个平面了&＃xff1b;当>3维时&＃xff0c;那条直线就是一个超平面&＃xff0c;什么是超平面&＃xff1f;问得好&＃xff0c;我也不知道哦&＃xff0c;哈哈&＃xff0c;不过把它理解为一个类似三维的平面就可以了&＃xff0c;初学千万别花太多时间去想多维是个什么情形&＃xff0c;那样会把自己整死。。。

支持向量机的模型有简单到复杂可以分为&＃xff1a;线性可分支持向量机、线性支持向量机、非线性支持向量机。下面就分别讲解一下这三种模型&＃xff0c;什么鬼&＃xff0c;怎么那么多&＃xff0c;别紧张&＃xff0c;好好看懂线性可分支持向量机就ok了&＃xff0c;其他两种只是它的稍微变形。。。

1、线性可分支持向量机

1.1、函数间隔和几何间隔

先来看一些基本字母表示和定义&＃xff1a;
以下全是基于多维的情况&＃xff0c;一个样本表示为&＃xff08;xi&＃xff0c;yi&＃xff09;&＃xff0c;其中x是特征&＃xff08;n维&＃xff09;&＃xff0c;y代表了标签&＃xff08;由-1,1组成&＃xff09;&＃xff0c;i代表了第i个样本。超平面也就是&＃xff1a;wTx&＃43;b&＃61;0&＃xff0c;其中w是超平面的法向量。

1.1.1 函数间隔

函数间隔被定义为&＃xff1a;
γ^&＃61;y(i)(wTx(i)&＃43;b)
为何这么定义&＃xff0c;我们再回忆一下直线方程&＃xff0c;我们高中时老师就教给我们&＃xff0c;要想知道某个点在直线的上方和下方&＃xff0c;只需将这个点带入到直线方程&＃xff0c;看得到的值大于0还是小于0即可。同理推理到超平面&＃xff0c;我们将第i个样本点带入就得到函数值wTx(i)&＃43;b&＃xff0c;但是这个函数值有正有负&＃xff0c;而函数间隔在我们日常表达中都是正的&＃xff0c;因此我们需要在刚刚的函数值之前乘上一个标签y(i)&＃xff0c;因为y取1对应于样本在超平面的上方&＃xff08;函数值为正&＃xff09;而y取-1对应于样本在超平面的下方&＃xff08;函数值为负&＃xff09;&＃xff0c;所以上式中的γ^实际上就是|wTx(i)&＃43;b|。
总结&＃xff1a;这样定义的好处是不管是正例还是反例&＃xff0c;当求得的γ^较大时就说明距离超平面的距离越远&＃xff0c;反之亦然。。。

1.1.2 几何间隔

先来看个图&＃xff1a;

如图所示&＃xff1a;B点是A点在超平面上的投影&＃xff0c;样本A表示为&＃xff08;xi&＃xff0c;yi&＃xff09;&＃xff0c;A点到超平面的几个间隔为γ(i)&＃xff0c;向量BA的方向和法向量w一致&＃xff0c;这个方向的单位向量表示为&＃xff1a;w||w||&＃xff0c;因此BA向量可以表示为&＃xff1a;γ(i)w||w||&＃xff0c;根据向量&＃xff08;矢量&＃xff09;的加减可知B点是&＃xff1a;xi−γ(i)w||w||&＃xff0c;将B点带入超平面wTx&＃43;b&＃61;0可得&＃xff1a;

经过移位和简单变换&＃xff0c;求解出γ(i)&＃xff0c;上式变为&＃xff1a;

同样的给它乘上标签y&＃xff0c;那么最终完美的γ(i)写成了&＃xff1a;

为什么说它很完美呢&＃xff0c;因为你有没有发现&＃xff0c;当||w||&＃61;1时&＃xff0c;几何间隔就变成了函数间隔。我们反过来再看函数间隔&＃xff0c;对于超平面wTx&＃43;b&＃61;0&＃xff0c;当w和b都同时增大或减小相同倍数时&＃xff0c;我们发现对这个超平面的位置没有影响&＃xff08;可以约掉放大的倍数&＃xff09;&＃xff0c;所以这样就会没有唯一解&＃xff0c;所以我们要对函数间隔归一化&＃xff0c;归一化后正好就是我们刚刚求得的几何间隔&＃xff0c;这时不禁要第一次感慨一下数学家的睿智&＃xff0c;之所以要说是第一次&＃xff0c;因为看到后面你会继续被数学家所折服。说了那么多你可能会问&＃xff0c;干嘛整出来什么函数间隔&＃xff0c;直接用我们平时地几何间隔不就完了吗&＃xff0c;哈哈&＃xff0c;提出这个当然是有用的喽&＃xff0c;不然数学家干吗费这个脑子哟&＃xff0c;这个问题我会在接下来的一小节中讲解。。。

总结函数间隔和几何间隔的关系是&＃xff1a;
γ&＃61;γ^||w||

1.2、 最大间隔分类器

现在再次回到我们的初始目标&＃xff1a;寻找最优一个超平面&＃xff0c;使得距离它最近的点&＃xff08;支持向量&＃xff09;到它的距离最大&＃xff0c;也就是所谓的间隔最大化&＃xff0c;将其用公式表示如下&＃xff1a;

这里加上了约束||w||&＃61;1&＃xff0c;这样就使得y(i)(wTx(i)&＃43;b)是几何间隔了&＃xff0c;但是||w||&＃61;1是非凸的不易求解&＃xff08;可以经过贪婪或非贪婪的方式求解&＃xff09;&＃xff0c;所以我们刚才提出的问题答案就在这里了&＃xff0c;我们这时就要用到函数间隔这个概念了&＃xff0c;我们将模型改为如下形式&＃xff1a;

可以看到模型中&＃xff0c;目标函数由原来的几何间隔变成了函数间隔除以||w||&＃xff0c;因为γ&＃61;γ^||w||&＃xff0c;所以目标函数还是几何间隔&＃xff0c;但是约束里就没有了||w||&＃61;1这一项。解决了约束问题&＃xff0c;但是目标函数中还是含有非凸的||w||项&＃xff0c;这怎么办呢&＃xff0c;当然不是凉拌炒鸡蛋&＃xff0c;这里首先将γ^&＃61;1&＃xff0c;也就是将支持向量到超平面的距离定义为1&＃xff0c;目标函数就变成了1||w||&＃xff0c;最大化这个目标函数&＃xff0c;也就相当于最小化12||w||2&＃xff0c;为什么这么写&＃xff0c;因为这样它就是一个凸函数了哇&＃xff0c;就容易求解喽&＃xff0c;最终模型如下&＃xff1a;

通过上述模型我们能够求解出最优w和b&＃xff0c;也就求得了最大间隔超平面了&＃xff0c;求得超平面后&＃xff0c;我们将要测试的样本点带入&＃xff0c;当求得的函数值>0时归为正例一类&＃xff0c;将函数值<0的归为负例一类。到这里就结束了吗&＃xff0c;当然没有&＃xff0c;还记得我说的被数学家的睿智所彻底折服吗&＃xff0c;这里就需要你来膜拜了。。。

当然在进行下面的推导之前你需要看下一对偶问题的求解&＃xff0c;要是只是想会用SVM不看也没关系&＃xff0c;你可以直接跳过标有红色字体的理解&＃xff0c;单纯的记住需要这样就ok啦。

为什么需要求解对偶问题呢&＃xff1f;问的好&＃xff0c;优点&＃xff1a;1.对偶问题更容易求解&＃xff1b;2.方便我们之后进入核函数&＃xff0c;这是后话&＃xff0c;到讲到核函数时&＃xff0c;你就是茅塞顿开啦。

我们先将约束进行改写为&＃xff1a;

接着构造拉格朗日函数为&＃xff1a;

根据KKT条件可知&＃xff1a;只有支持向量前面的系数α>0&＃xff0c;其他样本点前的系数α&＃61;0。当满足KKT条件时&＃xff0c;原问题和对偶问题是等价的&＃xff0c;所以我们可以将原模型改变为如下公式的对偶问题。

也就是说我们现在的目的就变成了解决上式。。首先先求内部&＃xff0c;固定α&＃xff0c;对w和b求偏导如下&＃xff1a;

整理上式可得&＃xff1a;

将求偏导后的结果带入化简后得到如下&＃xff1a;

我们再将向量内积换一种表示形式为&＃xff1a;。

我们可以看出上式只和α有关了&＃xff0c;也就比较好求解了&＃xff0c;我们需要求出α&＃xff0c;然后就可以得到w和b了&＃xff0c;现在我们要求解外层了&＃xff0c;将上述求出的内层结果带入&＃xff0c;相当于求解下式&＃xff1a;

对于上式模型的求解&＃xff0c;做经典的就是使用SMO&＃xff08;Sequential minimal optimization&＃xff09;算法了&＃xff0c;具体的思想请移步&＃xff1a;欲知详情请点我哦&＃xff01;

好啦&＃xff0c;现在我们经过SMO算法更新迭代求得了最优的α了&＃xff0c;那么根据公式&＃xff0c;我们就可以求出法向量最优w&＃xff0c;在这里我们可以看到求解w时&＃xff0c;对所有样本做运算&＃xff0c;这岂不是要耗时很多哇&＃xff0c;给这个算法差评&＃xff0c;哈哈&＃xff0c;当然不是&＃xff0c;这里就再次体现了支持向量的优势之处了&＃xff0c;还记得我们前面说过的只有支持向量的系数α>0&＃xff0c;其他样本的系数α都等于0吗&＃xff0c;这样我们不难发现实际上只是那几个少数的支持向量参与了运算&＃xff0c;计算量是不是就很小了哇&＃xff0c;然后再根据公式&＃xff1a;

求得最优的b&＃xff0c;知道了最优的w和b&＃xff0c;那么很自然的含有最大间隔的超平面也就相应地可以求得啦&＃xff0c;这就完成了我们最终的目的喽&＃xff0c;求解出了线性可分支持向量机&＃xff0c;第一部分到这里完全结束啦。

2. 线性支持向量机

上一节我们讲了线性可分支持向量机&＃xff0c;为什么起的是这个名字呢&＃xff0c;因为它的所有样本是线性可分的&＃xff0c;但是当存在离群点时&＃xff0c;什么是离群点呢&＃xff0c;如下图所示&＃xff1a;

上图中左边的图形是线性可分的情况下的描述&＃xff0c;右图的最上方那个圆圈样本就是离群点&＃xff0c;当这种样本存在时&＃xff0c;我们发现超平面的位置改变了&＃xff0c;它使原来的最大间隔变小了&＃xff0c;这是我们特别不希望的&＃xff0c;再有更糟糕的情况&＃xff0c;就是离群点完全在另一类中了&＃xff0c;如下图所示&＃xff1a;

这种糟糕的情况就变成了线性不可分的情况&＃xff0c;也许你会说我们找到一个曲线&＃xff08;如图中所示&＃xff09;区分不就行了&＃xff0c;但是这样会产生严重的过拟合&＃xff08;对训练样本表现极好&＃xff0c;对测试样本表现不好&＃xff0c;泛化能力差&＃xff09;&＃xff0c;所以我们需要将上一节中的模型进行改进&＃xff0c;改进结果如下&＃xff1a;

在上式中我们可以看到&＃xff1a;增加了一个松弛因子ξi&＃xff0c;它的作用就是允许离群点存在&＃xff08;离群点到超平面的距离小于1&＃xff09;&＃xff0c;在目标函数中我们又对那些离群点乘了一个C&＃xff08;惩罚项&＃xff09;&＃xff0c;C就是为了让这些离群点对最大间隔超平面的影响变小&＃xff0c;C值越大对离群点的惩罚增大&＃xff0c;C值越小对离群点的惩罚减小。

对于上式的求解和化简&＃xff0c;类似于上一节中对模型的计算&＃xff0c;首先将其化为拉格朗日函数&＃xff0c;然后根据对偶函数求解化简&＃xff0c;最终得到下式&＃xff1a;

首先看一下这个推导化简后的式子&＃xff0c;ξi不见了&＃xff0c;在我们推导的过程被约去了&＃xff0c;再仔细看这个式子&＃xff0c;有没有似曾相识的赶脚&＃xff0c;是的&＃xff0c;你没看错&＃xff0c;就和上一节的线性可分支持向量机的最终模型是差不多的&＃xff0c;所不同的就是对α的约束这里不同了&＃xff0c;此时有没有感觉到提出SVM的研究者的思想之高深。。。

对于上式模型的求解&＃xff0c;当然还是用到了SMO&＃xff08;Sequential minimal optimization&＃xff09;算法&＃xff0c;首先迭代求解出最优的α&＃xff0c;然后根据α和对应的样本&＃xff0c;求出最大间隔超平面就ok啦&＃xff01;第二部分就结束了&＃xff0c;下面让我们来看看非线性支持向量机。

3. 非线性支持向量机

上一节我们讲了线性不可分的情况&＃xff0c;当离群点特别多&＃xff0c;多到如下图那样时&＃xff0c;我们就需要再改进一个新模型来解决了&＃xff1a;

这是一个二维空间的例子&＃xff0c;我们可以看到两类样本完全无法分开&＃xff0c;我们这样想&＃xff0c;将这些样本映射到高维空间是什么情形了&＃xff0c;看如下的一种映射&＃xff1a;

我们将刚刚二维空间的样本映射到三维&＃xff0c;是不是显而易见就变成了线性可分的啦&＃xff0c;此时我就就能又能解决分类问题啦&＃xff0c;当然喽&＃xff0c;此时你需要补充的就是核函数这个概念了&＃xff08;点我了解核函数&＃xff09;。。。

现在你已经看完了核函数&＃xff0c;没看也没关系&＃xff0c;你只要记住&＃xff1a;我们的模型改进是在上一节的模型中将样本内积换成核函数就ok了&＃xff0c;核函数的值代表了样本在高维空间的内积&＃xff08;千万别认为核函数是将低维空间的样本映射到高维空间&＃xff0c;然后做的内积&＃xff0c;因为它没有映射这个过程&＃xff09;&＃xff0c;改进后的最终模型如下&＃xff1a;

大家和上一节中的最终模型对比&＃xff0c;可以看到只有内积换成了核函数&＃xff0c;其他的都没有变&＃xff0c;也是一样的&＃xff0c;通过SMO算法求得最优的α&＃xff0c;然后再求出最终的最大间隔超平面&＃xff0c;就可以进行分类啦。。。

对于SVM的理论介绍就讲到这里了&＃xff0c;也许有些地方的理解不到位&＃xff0c;欢迎留言&＃xff0c;共同进步&＃xff01;