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什么的，其实没有什么不同。后面推导不受影响。
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个支持向量。
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正则
网友评论