硬间隔最大化SVM
- SVM
-
- 介绍
- SVM转化为最优解问题
- KKT
-
- KKT图解
- KKT定理
- KKT例子
- 求解SVM最优化问题
- 拉格朗日对偶
-
- 拉格朗日对偶例子
- 用拉格朗日对偶解决问题
- KKT在SVM中的意义
- 测试
SVM
介绍
SVM是一种分类手段，就是找出一个超平面，将给定的数据集{(x1，y1),(x1，y2),…,(xn，yn)}分类(xi为特征向量，yi为类别，这边分为两类y=0或1)。这种超平面很多，但SVM分类是找到那个最优的超平面，即下图中的蓝色平面-------要求是margin（分隔间距）最大。
margin（分隔间距）最大：通俗理解就是这个平面向垂直于它的方向上下平移，所碰到的第一个点（上下都有）离它的距离和最大。
所以说SVM的目标就是如何去找到这个能使得margin最大的分类蓝色超平面。
SVM转化为最优解问题
我们先设超平面的方程为：wTx+b =0，两侧margin/2距离的平面方程设为：wTx+b =±c，为了方便起见c选为1：wTx+b =±1。
(为了理解方便，可设x为二维特征，式子就变成：w1 * x1+w2 * x2+b=0，可以看出w就是这个平面的法向量，b为截距）
所以呢，我们只要求出w向量和 b值 ，就可解得超平面方程。
从上图中可以看到，凡是在虚平面wTx+b =-1下方的样本xi，wTx+b <=-1 都属于y = -1类，在虚平面wTx+b =1上方的样本xi，wTx+b >=1 都属于y = 1类。
即if：wTx+b <=-1 则 y = -1
if：wTx+b >= 1 则 y = 1 ==》 y(wTx+b) >= 1 限制条件
现在算margin ：margin是 wTx+b =0和wTx+b =1 距离的两倍。
（假设x二维，可参考两直线的距离公式： w1x1+w2x2=0-b，w1x1+w2x2+b=1-b
d = |0-b-1+b| / (根号(w1的平方+w2的平方)) ）提升到高维距离距离就是1/||w||。
所以 margin = 2/||w||
我们期望的是距离最大即margin最大 ，也就是||w|| = wTw 最小。为了方便起见前面加个1/2.。
于是就成了个最优化问题 （注：限制条件是N组不等式 x是N维的）
KKT
对于求解不等式约束条件的优化问题，必须满足KKT条件
KKT图解
上图所示图中
f是目标函数 ，求其最小值。
g1(x)<=0,g2(x)<=0,g3(x)<=0为限制函数 。
▽则表示为梯度，梯度方向为函数增加最快的方向。
通过 反梯度方向及g(x) = 0 ,我们可以判断出阴影部分三个函数都<=0，是x的取值范围。
进一步的通过分析，不难确定x的取值应该是g1=0， g2=0的交点处。
似乎有没有g3(x)<=0 这个限制条件x取值都一样，此时我们称 g1，g2条件是活跃的，g3是不活跃的。
且 ▽f 可以被活跃的两个限制函数的梯度▽g1，▽g2表示出来。
▽f =α1 (-▽g1)+α2 (-▽g2) 且从图中梯度方向不难看出 α1，α2都应该大于0。
为了整齐起见，不活跃的g3我们也加上去，只是系数α3设为0
于是式子就变成▽f =α1 (-▽g1)+α2 (-▽g2)+α3 (-▽g3)
整理可得 ===》▽f +α1 (▽g1)+α2 (▽g2)+α3 (▽g3) = 0
(其中活跃限制条件系数>0,不活跃限制条件系数=0,总的来说α>=0）
KKT定理
以上就是KKT引导，下面给出KKT定理：
概括如下： 目标函数： f(x)
限制条件 (分两类，一类是等式限制条件，一类是不等式)：
h(x) = 0, g(x)<=0(不等式都写成<=形式)
KKT条件：
1.：▽f +α(▽g)+λ(▽h)=0
其中等式h(x)前的λ没有限制就像正常的拉格朗日乘子法一样。
2.不等式g(x)前的系数α则要大于等于0。(这个就是上面的α推导)
3.最后解读 αTg(x) = 0 :
写开就是: α1 (g1)+α2 (g2)+α3 (g3)+…+αn (gn)=0
因为α>=0 g<=0，他们两都不等于0，相乘结果一定是负。要满足αTg(x) = 0，如果α不等于0，g就必须等于0，反之也是。
这个结论和刚刚那张图推导结果是一致的，即g(x) = 0,说明他是活跃的，α>0，g(x) < 0,说明不活跃，α=0。
KKT例子
怎么是横的
如果实在不懂，可以看这篇文。
https://www.cnblogs.com/xinchen1111/p/8804858.html
求解SVM最优化问题
刚刚我们已经将SVM转化为一个最优化问题。
为了满足KKT条件，这边的g(x)取: 1-y(wTx+b) <=0 ,α>=0
列出拉格朗日方程
所以对w，b求偏导等于0。
很多时候在现空间中是找不到一个线性超平面来区分样本的所以引入核技巧，映射到高维空间中进行分类。
将样本用核技巧进行处理后：
考虑到维度可能太高，所以用拉格拉日对偶解决问题
拉格朗日对偶
也没研究过拉格朗日对偶，书上怎么说，咱就怎么做：
拉格朗日对偶例子
用拉格朗日对偶解决问题
求min 1/2wTw ,就是求max W(α)=L(w(α),b,α)(推导我不会)
我们需要把wTw，wTφxi，b化成关于α的式子
现在的问题就变成了这个：
下面证明W(α)有最大值，是一个半负定二次型，开口向下有最大值。
所以可求出W(α)的最大值时 的α值（这个计算有一种简单的SMO算法）
知道α即可通过
求出w。
在通过：
求出b。
KKT在SVM中的意义
KKT条件在物理意义上对应的SVM含义
KKT的条件之一为αTg(x) = 0 ，α >=0, 其中 g(x) = 1-y(wTx+b) 。
可以在图中看到凡是在wT+b=-1下方 或者 wT+b=1上方的样本都有y(wTx+b) > 1
通过上述条件可得：此时α必定为0。
只有在虚线上的的点 1-y(wTx+b)=0 此时α>0
而w是关于α的函数，α为0时，对应的样本毫无意义，只有在虚线上的点 α>0才真正起了作用。
所以真正参加运算的只有边缘那些点，这些点就叫支持向量
测试
代码：https://blog.csdn.net/jirong5206/article/details/106032636
将测试样本核化后代入超平面方程，大于0 ，小于0 分类。