机器学习-SVM学习笔记
非原创，许多图是搬运其他博主，底下有链接，我只是把不同人做的好的东西做了一个融合并加入少许个人看法而已
如有侵权请立刻与我联系
参考博客链接：
https://www.cnblogs.com/liaohuiqiang/p/7805954.html
https://www.cnblogs.com/pinard/p/6111471.html
http://www.cnblogs.com/pinard/p/6126077.html
文章结构：
1.SVM定义
2.对偶问题
3.KKT
4.核函数简介
5.SMO简介
6.调参技巧
1.SVM定义
假设对于一个线性可分的问题，存在分割面y=wx+b，若总能分类正确，则有y(wx+b)>0
我们需要使得分隔所有样本到分隔平面的距离最大，即函数间隔
但如果w，b同时扩大两倍，间隔会扩大，但是分割面实际没变，于是用几何间隔代替函数间隔（点到直线的公式）
只考虑距离分割面最近的点（support vector），即距离为1的点，得到
等价于
2.对偶问题
原始问题是在限定的范围内求极值，不易直接求解。
构造拉格朗日函数表示原始问题
其中alpha>=0
当等式只有前面这一项即为原始问题。
对偶问题即为
极大值中的最小一个也要比极小值中的最大一个大
当函数满足强对偶条件的时候可以取等号。满足的条件是slater条件，而满足KKT则满足。即凸优化问题，在一点x使得所有等式约束满足条件，不等式约束严格成立。
3.KKT
对于考虑凸优化问题，拆解问题
假设只有等式约束，画出等高线
当画出不同位置的梯度的时候有
我们发现，当取得极值的时候，约束条件和函数的法向量是同向的
即可构造拉格朗日函数
考虑存在不等式约束的时候，分两种情况
极小值点落在可行域内（不包含边界）：这个时候可行域的限制不起作用，相当于没有约束，直接f(x)的梯度等于0求解，这个时候g(x极小值点)<0（因为落在可行域内）。
极小值点落在可行域外（包含边界）：可行域的限制起作用，极小值点应该落在可行域边界上即g(x)=0，类似于等值约束，此时有g(x)的梯度和f(x)的负梯度同向。
来自 <https://www.cnblogs.com/liaohuiqiang/p/7805954.html>
KKT可总结为原始问题构造拉格朗日函数后
4.核函数简介
定义
假设X是输入空间，H是特征空间，存在一个映射ϕ使得X中的点x能够计算得到H空间中的点h(x)=ϕ(x)
对于所有的X中的点都成立，x，z是X空间中的点。函数k(x,z)满足条件k(x,z)=ϕ(x)⋅ϕ(z)都成立，则称k为核函数，而ϕ为映射函数。
核矩阵
必须是对称半正定
常用核函数
5.求解以及SMO坐标下降
利用偏导=0将原始问题转化为求解alpha以后使用SMO算法
上面这个优化式子比较复杂，里面有m个变量组成的向量alpha需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量，将其他的变量都视为常数。两个变量的关系有限定条件确定。
来自 <https://www.cnblogs.com/pinard/p/6111471.html>
6.调参技巧
C表示松弛变量的系数，C越大越表明我们不愿意放弃比较远的离群点，使得模型加入更多的支持向量，更加复杂，也更容易过拟合。默认scikit-learn中C=1
gamma表示RBF核函数中单个样本对整个分类平面的影响，当gamma较大的时候，单个样本对超平面的选取影响更大，更容易成为支持向量。
对于SVM的RBF核，我们主要的调参方法都是交叉验证。具体在scikit-learn中，主要是使用网格搜索