SVM算法

7.20
：：：：：：：硬间隔最大化（线性可分）

二分类问题 找到超平面 且是最优超平面（最大间距的超平面
凸二次规划 局部最优=全局最优
优重点是这个优化过程————————对偶的到对偶变量 的带更好的求最解的情况
应用拉格朗日对偶性，通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一是对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

：：：：：：对偶优化？？？
约束极值 ————用朗格朗日————求a————wb
其实很多的αi都是0，也就是说w只是一些少量样本的线性加权值

：：：：：：：软间隔
离群点 松弛变量4 放松限制条件 重新调整目标函数 对离群点处罚 c是离群点权重 C越大代表对目标影响越大 ——————C尽量小
（原文）

松弛变量与惩罚因子

引入非负参数 后（称为松弛变量），就允许某些样本点的函数间隔小于1，即在最大间隔区间里面，或者函数间隔是负数，即样本点在对方的区域中。而放松限制条件后，我们需要重新调整目标函数，以对离群点进行处罚，目标函数后面加上的 就表示离群点越多，目标函数值越大，而我们要求的是尽可能小的目标函数值。这里的C是离群点的权重，C越大表明离群点对目标函数影响越大，也就是越不希望看到离群点。我们看到，目标函数控制了离群点的数目和程度，使大部分样本点仍然遵守限制条件。

（不一定用到，出现非线性）
：：：：：：：：核函数
SVM对线性可分数据有效，对不可分的有何应对良策呢？是核方法（kernel trick）大展身手的时候
原始样本点通过一个变换，变换到另一个特征空间，在这个特征空间上是线性可分的，那么上面的SVM就可以轻易工作了。

也就是说，对于不可分的数据，现在我们要做两个工作：

1）首先使用一个非线性映射Φ(x)将全部原始数据x变换到另一个特征空间，在这个空间中，样本变得线性可分了；————————&x*&y样本x与y的内积就是分类决策的计算 如果对应到高维的话，就可以用核函数 ，而且避免在高维运算

2）然后在特征空间中使用SVM进行学习分类。

因为大多a=0，只需要将少数的a与新来的样本进行核函数即可

到这里，忍不住要感叹几声。为什么“碰巧”SVM里需要计算的地方数据向量总是以内积的形式出现？为什么“碰巧”存在能简化映射空间中的内积运算的核函数？为什么“碰巧”大部分的样本对决策边界的贡献为0？…该感谢上帝，还是感谢广大和伟大的科研工作者啊！让我等凡夫俗子可以瞥见如此精妙和无与伦比的数学之美！

：：：：：：：
总的来说，SVM决策过程就是输入样本与支持向量进行核函数的相对比较
即通过非线性变化将样本映射到高维度空间，并在这个空间进行计算求得最大间隔超平面。映射即为核函数
:::::::::::::::::::::可从损失函数和优化算法角度看SVM，

：：：：：多分类
一对一
一对多
详情看：https://blog.csdn.net/zouxy09/article/details/17291805

：：：：：：KKT (有不等式约束）朗格朗日 等式约束
a = c————在间隔内
0<a<c————在最大间隔平面
a=0————在间隔外
第三个式子表明如果0<αi<C，那么该样本一定落在分隔线上（这点很重要，b就是拿这些落在分隔线上的点来求的，因为在分割线上wTx+b=1或者-1嘛，才是等式，在其他地方，都是不等式，求解不了b）

：：：：：：：：SMO
1.坐标梯度下降 求Min
上升求max
核心是一次迭代：固定其他变量ai，只对一个变量a1进行优化

（核心算法 ，求a)
2.smo
核心是一次迭代：有多个变量ai,固定两个以外的其他变量
总结下来是：

重复下面过程直到收敛{

（1）选择两个拉格朗日乘子αi和αj；

（2）固定其他拉格朗日乘子αk(k不等于i和j)，只对αi和αj优化w(α);

（3）根据优化后的αi和αj，更新截距b的值；

}

SVM小结

引入了核函数后，我们的SVM算法才算是比较完整了。现在我们对分类SVM的算法过程做一个总结。不再区别是否线性可分。

输入是m个样本(x1,y1),(x2,y2),...,(xm,ym),,其中x为n维特征向量。y为二元输出，值为1，或者-1.

输出是分离超平面的参数和w∗和b∗和分类决策函数。

算法过程

1）选择适当的核函数K(x,z)和一个惩罚系数C>0, 构造约束优化问题

image

2）用SMO算法求出上式最小时对应的α向量的值α∗向量.

3) 得到

image

4) 找出所有的S个支持向量,即满足0<αs<C对应的样本(xs,ys)，计算出每个支持向量(xs,ys)对应的偏置b，最终的偏置项为所有值的平均

image

最终的分类超平面为

image

最终的分类决策函数为

image

至此，我们的分类SVM算是总结完毕。