SVM 的原理和目标

几个基本概念

线性可分SVM——线性 SVM——非线性 SVM

1、线性可分SVM，表示可以用一根线非常清晰的划分两个区域；线到支持向量的距离 d 就是最小的。

2、线性 SVM，表示用一根线划分区域后，可能存在误判点，但还是线性的；线到支持向量的距离不一定是最小的，但忽略其他非规则的支持向量。

3、非线性 SVM，表示使用核函数之后，把低维的非线性转换为高维线性

复习下函数和向量

假如有个方程

image

y=x/2-1可以变化为 -x+2y+2=0

f(x,y)=-x+2y+2,其中红色的就是他的法向量

写成向量的形式：

image

改写下

image

前面的系数项可以令其为

image

x，y 的那一项，其实可以演变为 n行，所以可以简化为

image

后面的2是常数项，用 b 代替

这样处理完，我们的式子可以修改为

image

其中 w 就是我们的法线方向，x 是我们的参数，b 是截距项。

此时如果有个

image

带入式子得到是正值，那么就在法线的同方向；否则在法线的逆方向。如果等于0，那么该点就在线上。

f(x1，x2)代表一个线，f(x1,x2,x3)代表一个面，如果是 n 维的，那么给他一个牛逼的名称“超平面”，由于这个名字太牛逼，所以低维的也叫超平面。

计算过程和算法步骤

接入给定一个特征空间上的训练数据集，

image

其中

image

image

这里为什么 y 取值+1和-1？

因为这样取值方便后面的推导，如果非要把+1和-1换为+3和-8什么的，其实没有什么不同。后面推导不受影响。

写成+1和-1的话，那么我们的

image

,那么

image

，两边同时乘以 yj，得到

image

，这样我们就可以很方便的得到两个标记相乘等于两个标记相除。如果选择不同的值，就得不到上面的式子。

推导目标函数

分割平面：

image

训练集：x1，x2，x3......

目标集：y1，y2,y3...... y属于1和-1的集合

新数据的分类：sign(y(x))

根据题设

image

其中

image

就是一个映射，

image

就是原封不动一阶映射，二阶映射的例子如下：

{1，x1，x2,x3}==>{1,x1,x2,x3,x12,x22,x3^2,x1x2,x2x3,x1x3}把原来的四维转换成10维。

接下来就有

image

其中：y(x)为预测值，y 为真实值，他们互为推导。最终他们的乘积大于0.

从而可以得到下面的公式（其实是点到直线的距离）

image

我们的目标函数：

image

解释：对于所有的样本到平面的距离求最近，也就是最小值，然后得到的这些平面里面根据 w 和 b再求 最大值。

如何优化

转换等价问题，直接来解决的确棘手。先来看

线性可分的这个图

image

可以看出，有3个支持向量。

上虚线五角星的那个点到红线的距离是一个值，而且是最近的一个距离，假如该距离为 d=3，那么也就是

image

两边同时除以3

image

也就是范数 w 乘以3，但是对整个方程来说位置是不发生变化的。（其实 w 是我们要求的，可以随便设置，总能得到右边为1）

打个比方，假如有个方程 f(x,y)=ax+by+c=0,有个点到该线的距离为d，那么我们可以除以 d，使得到改线的距离为1，可以认为是距离归一处理。那么同理我们总能得到一个 w，使得五角星那个点到红线的距离为1，就得有个约束条件就是

image

，好了，现在这个值要求取最小值，而且又是大于等于1，那么就直接取1就是最小值。

那么新的目标函数就变化为

image

一个数的倒数求最大，也就是这个数求最小，也就是求这个数的平方最小，也就是求这个数平方的一半最小，好了，公式继续演变为：

image

这个就是我们需要求解的目标，假如 n=10000（n 是样本个数），也就是有1万个下面的约束条件下求上式子的最小值，对于这个目标函数如何来求呢？带有约束条件的求极值问题，就想到拉格朗日乘子法。

拉格朗日乘子法和KKT条件

其实拉格朗日乘子法的约束条件是要求等于某个条件，而这里是不等于，也可以这么做。

image

这个式子的暂且放一边，我们来梳理下拉格朗日乘子法。

假设有个函数要求最小值，min f(x)，其中有两部分要求，第一部分是不等式部分：

image

image

image

这里所有条件的方向可以修改为

image

，因为可以增加负号来改变方向，不是什么大问题。

最终也就是

image

第二部分是等式部分，记为

image

本科阶段的拉格朗日乘子法只有等式部分，现在这里增加了不等式部分，针对不等式部分，做如下操作。

先设置一系列的

image

，构造一个新的函数

image

这个就是拉格朗日函数。对于这个函数来说，以

image

w为变量，对其求导数，可得系数为

image

,在二维坐标上就是一条线，同理

image

image

等。

将他们画在一张坐标系里面，

image

对于这3个线段求取每个 x 点的最小值，得到的是红色的这个区域的线，同理，n 条这样的线也可以得到这样一个凹函数，凹函数必有最大值，并且是全局最大。

那么

image

到底是什么？

继续看下

image

image

因为

image

而

image

，所以

image

因为

image

，所以无论 lambda 取什么值，

image

,这就是说 G(x)是一个 f(x)加上一个负数，那么也就是说 G(x)的最大也就是 f(x)了。

image

，那么要求 minf(x)也就是求

image

可以找到他的对偶函数

image

再回到我们原来的式子，

image

这个式子比上面的理论要简单点，没有等式约束。那么他的原始极小极大问题

image

他的对偶问题为极大极小问题

image

为了求最小值，我们需要对w 和 b 分别求导，并且使之为0，

其中

image

最终得到

image

也就是

image

接下来，对 b 求偏导数，得到

image

w 不就是法向量嘛，其中包含的 alpha=0的点不是支撑向量，而 alpha 不为0 的才是 SV。pha(x）就是核函数，所有的这些在这里可以体现出来了。

归纳下：

image

继续推导。。。带入 w 和 b，剩下 alpha 的式子。

image

最后得到求 alpha 的式子

image

使用某种方法（SMO）求得 alpha，带入 w 和 b 就可以求得 w。

SMO 算法，由条件可知，

[图片上传失败...(image-ab4eb3-1526290967990)]

我们需要调节2个 alpha 参数，一大一小，使得为0，满足条件后求得 alpha 较大值，然后慢慢调节，再得到一个较大值，这样的按照序列求得最大的优化方法叫 SMO

掉个方向，得到

image

举个例子看的明白些：

给定3个数据点，正例点x1=(3,3)T,x2=(4,3)T,反例点 x3=(1,1)T,  求解线性可分的SVM。

image

解：目标函数是

image

[图片上传失败...(image-fbc4d6-1526290967990)]

根据

image

可得

image

其中正例就是 x1=(3,3,1) x2=(4,3,1);负例x3=(1,1,-1)

最后是表示 y 的值。x1对应的系数 alpha1，x2对应的系数是 alpha2，x3对应的系数是 alpha3.

将 alpha3=alpha1+alpha2带入式子计算得到关羽 alpha1和 alpha2 的han 函数

image

对 alpha1和 alpha2求偏导令他为0，得到在（1.5，-1）这个点取到极值，但是改点不满足 alpha2>0这个条件，所以最小值在边界上没有达到。

令 alpha1=0，最小值 s（0，2/13）=-2/13=-0.1538

令 alpha2=0，最小值 s（1/4，0）=-1/4=-0.25

所以得到s(alpha1,alpha2)在1/4,0处达到最小，此时 alpha3=alpha1+alpha2=0.25

所以 alpha1=alpha3=0.25对应点 x1和 x3构成支持向量。

带入公式：

image

这里 fai(xi)就是 xi

得到 w1=w2=0.5 b=-2

所以超平面为

image

图形

image

x1的系数和x3的系数是0.25，而x2的系数是0，也就是说 x2没有参与支持向量的构建，不是支持向量。

以上是线性可分，那么线性不一定可分的咋办呢？

如图

image

按照可分那就是实线，貌似虚线应该更好。

若线性不可分，需要加入松弛因子[图片上传失败...(image-8be0f1-1526290967990)]>=0，

此时约束条件变成：

image

当

image

=0就是线性可分。

目标函数：

image

这个式子中，当 C 趋向无穷大的时候，

image

只能取0才能保证能取最小值。C 可以认为是允许犯错误的容忍程度，C 太大，表示对错误完全不能容忍，必须要线性可分。从另外角度来说，C 太大，那么不允许犯错误，那么过渡带就会窄。C 小些的话，过渡带会宽些，也就是泛化能力较强。

归纳下：

image

对应的拉格朗日函数（注意符号，ξ>=0的变化）

image

然后对其求偏导数

image

将三个式子带入

image

把 μ消掉了

对上式子求关羽 α 的极大，得到

image

上式右下角的条件限制了α的取值范围是缩小了的。

进一步整理得到对偶问题

image

再进一步构造最优化问题

image

求解得 a^*

然后计算出w 和 b

image

注意：计算 b 的时候需要满足α在（0，C）之间

最终求得超平面：

image

损失函数分析

image

圆圈的点：他们的α=C，他们是有损失的，并且哪些红色线段表示损失值；虽然他们分的是对的。但是已经进入敏感地带。

方块的星：他们的0 < α < C,是支持向量

其他点：α = 0

损失值=1-d；d 是点到超平面的距离，那么过渡带之外的损失值为0，于是得到 SVM 损失函数图(Hindge损失）

image

也就是

image

但得到这个最小的时候，求得新的 w 和 b。

我们再看下

[图片上传失败...(image-faff7c-1526290967990)]

这里出现了损失函数，经过变换得到新的损失函数

image

后面一项是 L2正则

作者：breezedancer

链接：https://www.jianshu.com/p/7d5693d9e2fe

來源：简书

简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。