机器学习算法复习之SVM
由ypyu创建，最终由ypyu 被浏览 10 用户
支持向量机最初也是用于分类任务，基本思路和logistic回归非常类似。但它一般比logistic回归的表现得好，而且可以解决非线性分类问题。
通俗理解
关于分类任务，可以看作在特征空间中，找到一个超平面（hyperplane，在二维特征空间就是一条分割线，三维就是一个面），将不同类的样本分隔开。能把不同类训练样本分隔开的超平面可能有很多个，一个超平面对应一个预测函数，所以找到合适参数的预测函数，也就是找到了合适的超平面。
那么怎么找这个合适的参数/预测函数/超平面呢？在logistic回归中，我们通过计算选择能让平方差损失函数最小化的那些参数作为这个合适的参数。虽然logistic回归已经不错了，但在很多情况下它表现得不好，这时可以考虑SVM。
SVM之所以会表现得更好，关键在于它要求超平面（预测函数）不仅完成样本分类，而且还要满足最大间隔条件，也就是说，参数/预测函数/超平面的选择标准比原来多加了一个条件，更严格，是优中选优。
所以SVM又叫最大间隔分类器（large margin classifier），至于为什么叫支持向量机，因为求最大间隔，需要用到作为支持向量的那些点（封面图）。
——这里所谓表现的更好，不一定仅是准确率提升，还有robust的提升，泛化能力的提升等等。
数学原理
一个超平面对应一个预测函数，所以可以从这两个角度来看SVM的原理。
1、最大间隔条件的数学表达
如何将二维、三维图像上很直观的最大间隔条件，在数学表达式中表示出来，并求解？
首先，在数学上，超平面可以用方程表示：
$w^{T}x+w_{0}=0$
w是超平面的法向量（垂直于平面，决定平面的方向），一系列w值也就是预测函数的参数，因为一个超平面对应一个预测函数。w0是位移项，决定超平面到原点的距离。
知识点1：线性代数中，任意一个点x到超平面的距离，等于点x和超平面上某点x*组成的向量在超平面的法向量方向上的投影（图中绿线）。
而由投影的公式（project=
$\frac{u^{T}v}{||u||}$
，即乘以被投向量的单位向量。||u||是向量的范数，又叫向量的模，也即向量的长度）
这里：distance=
$|\frac{w^{T}(x-x*)}{||w||}|$
投影是有方向（正负）的，所以取绝对值，又因为x*是超平面上的某点，满足超平面表达式：
$w^{T}x+w_{0}=0$
所以上式变成：
distance=
$|\frac{w^{T}x+w_{0}}{||w||}|$
这也就是我们要最大化的间隔，但要注意，这里不是用随便一个点到超平面的距离，而是用离超平面最近的那个（些）点到超平面的距离，只有这样才能起到辅助分类的作用。
2、从超平面选择和最大间隔条件到带约束条件的最优化问题
现在从预测函数和最优化问题角度考虑。选择带最大间隔条件的最优超平面等价于求解带约束条件的最优化问题。
为使其体现间隔的要求，需重新定义预测函数：
因为是二分类问题，如果预测函数能够正确分类，则满足x为正例时，y值为1；x为负例时，y值为-1（而不是logistic回归中的1和0）
预测函数：
$f(x)=w^{T}x+w_{0}$
结合上面的定义，就是：
$f(x^{(i)})>0\Leftrightarrow y^{(i)}=1$
$f(x^{(i)})<0\Leftrightarrow y^{(i)}=-1$
也即：
$f(x^{(i)})y^{(i)}>0$
我们要体现间隔的这个条件，需要再强加一个假设（不是随便加的，后面会有代价：多了约束条件），将上式变为：
$f(x^{(i)})y^{(i)}\geq1$
——即大于1时对应1，小于-1时对应-1
体现在图上更直观：
上式恒为正，所以之前的间隔公式可以去掉绝对值号：
$|\frac{w^{T}x+w_{0}}{||w||}|=\frac{y^{(i)}(w^{T}x+w_{0})}{||w||}$
(因为y只能取1或-1，所以它只起到转换正负的作用，但不影响大小)
前面又说了，SVM是使得离超平面最近的那个（些）点到超平面的距离最大。
首先我们要找到最近的那个（些）样本点i：（这里取1，因为只取一边，其实两边一样）
$min_{i}\frac{1}{||w||}(y^{(i)}f(x^{(i)}))$
然后找到那些令这个（些）点到超平面的距离最大的参数w：
$max_{w}[min_{i}\frac{1}{||w||}(y^{(i)}f(x^{(i)}))]$
只要找到一系列w，解决上式这个最优化问题，也就是找到了最佳参数。
因为，
$f(x^{(i)})y^{(i)}\geq1$
，那么可以看作其最小值为1，代入上面的最优化问题，就变成了：
$max_{w}(\frac{1}{||w||})\Leftrightarrow min_{w}(\frac{1}{2}||w||^{2})$
s.t.
$y^{(i)}(w^{T}x^{(i)}+w_{0})\geq1$
，i=1,2,...m
（因为前面用了一个假设，后面就得付出代价：多了一个约束条件）
（为什么是平方，因为模是开根号的，为去掉根号计算方便）
SVM求解最佳参数最终变成一个带约束条件的最优化问题。
3、用拉格朗日乘子法转换带约束条件的最优化问题
例如：
$minf_{0}(x)$
subject to
$f_{i}(x)\leq0$
,i=1,2,...m
可以转换为：
$minL(x,\lambda)=f_{0}(x)+\sum_{i=1}^{m}{\lambda_{i}f_{i}(x)}$
SVM的最优化问题也可转换为：
$minL(w,\alpha)=\frac{1}{2}||w||^{2}-\sum_{i=1}^{m}{\alpha^{(i)}(y^{(i)}f(x^{(i)})}-1)$
少了约束条件，但多了一系列未知变量α（≥0），一个样本点i对应一个α。α取能令上式最大的值。
所以又变成先求最大后求最小的形式。
不过，我们可以根据拉格朗日对偶性进行一个转换：
$min_{w}max_{\alpha}L(w,\alpha)->max_{\alpha}min_{w}L(w,\alpha)$
先解决最小化问题：
$min_{w}L(w,\alpha)$
令关于w的偏导为0，得到：
$w=\sum_{i=1}^{n}{a^{(i)}y^{(i)}x^{(i)}}$
$\sum_{i=1}^{m}{\alpha^{(i)}y^{(i)}}=0$
将上面w的表达式和等式再代回
$L(w,\alpha)$
，即可转换成一个只有未知量α的目标函数L(α)，第二个等式变成约束条件。
再解决最大化问题：
$max_{\alpha}L(\alpha)$
s.t.
$\sum_{i=1}^{m}{\alpha^{(i)}y^{(i)}}=0$
,
$\alpha^{(i)}\geq0$
将这个最大化问题再转换为最小化问题（加负号），求出一系列α（这种形式似乎又要用拉格朗日乘子法，但这里可以用下面的更高效的方法求解），将求出的α再代回w的表达式，即可求得参数w。将参数代入预测方程，即可得到针对此数据集的SVM模型。
注意：求α的过程中，最重要的计算是将α对应的样本点在特征空间中所表示向量的内积两两相乘，这一点也与后面理解kernel相关。
扩展：KKT条件、互不松弛特性、支持向量
在求解包含不等式约束条件的最优化问题时，需要满足KKT条件，对于一般的任意问题而言，KKT条件是使一组解成为最优解的必要条件，当原问题是凸问题的时候，KKT条件也是充分条件。具体到本题中就是：
$y^{(i)}(w^{T}x^{(i)}+w_{0})\geq1$
$\alpha^{(i)}(y^{(i)}f(x^{(i)})-1)=0$
$\alpha^{(i)}\geq0$
其中第二式，叫做互补松弛特性（complementary slackness），即它要成立，要么α=0，要么
$y^{(i)}f(x^{(i)})=1$
。
而我们又知道，一个样本点xi对应一个αi值：
如果α为0，那么后面两个式子就没用了，α也不会影响第一个式子，所以这些α对应的点，对模型就没有影响。
如果α不为0，那么
$y^{(i)}f(x^{(i)})=1$
就要成立，这些点都在边界点上，对模型有影响。所以所谓支持向量是指那些对应的α≠0的那些点，也就是边界点，这些边界点才是决定最大间隔的那些点。
（其实强加的假设并没有消去
$min_{i}\frac{1}{||w||}(y^{(i)}f(x^{(i)}))$
这个最优化问题，而只是将其转换成了
$max_{\alpha}L(\alpha)$
问题，所以才会有一个样本点对应一个α值这个情况）
所以说，只要支持向量不变，那么在数据集内无论再增添多少个点，都对模型没有影响。
也就是说，对于SVM来说，训练过程完成后，大部分数据都不需保留，最终模型只与支持向量有关，所以数据量增多不一定提高SVM性能（反而可能拖慢训练速度）。
4、SMO（Sequential Minimal Optimization，序列最小最优化算法）
上述关于α的最优化问题是一个二次规划问题，可以用二次规划的解法求解，但考虑该问题的规模正比于样本数，计算量太大，所以开发出了一些更高效的算法，比如SMO。
基本思路：先固定αi以外的其他参数（即将其他α暂时看作已知常数），然后求αi的极值。
这样αi可以由其他α表示，又因为满足
$\sum_{i=1}^{m}{\alpha^{(i)}y^{(i)}}=0$
条件，所以有了αi，也就相当于表示了两个参数：αi和αj
SMO不断重复以下过程直至收敛：
（1）选取两个待求的α；
（2）固定其他参数，然后求解
$max_{\alpha}L(\alpha)$
这个最优化问题获得这两个α。
5、soft margin（软间隔）与参数C：解决噪音问题
对于有异常值或离群点的数据集，需要SVM对其的敏感性降低一些，即不要那么严格，放松一下，允许犯一点错。
前面我们强加了一个假设是
$f(x^{(i)})y^{(i)}\geq1$
，而本来应该是
$f(x^{(i)})y^{(i)}>0$
这个强加的假设太严格了，引入松弛变量就是：
$f(x^{(i)})y^{(i)}\geq1-\xi^{(i)}$
构造一个新的目标函数：
$min(\frac{1}{2}||w||^{2}+C\sum_{i=1}^{m}{\xi^{(i)}})$
引入的C是一个超参数，它和正则化系数由类似功能，控制模型是否过拟合。
当C很大时，ξ必须很小，极端情况下小到0相当于没加松弛，所以C越大越严格，越敏感，越容易过拟合。
当C很小时，同理，越放松，越不敏感，有更大的错误容忍，但越容易欠拟合。
**扩展：**可以将参数C类比做正则化过程中的正则化系数，只不过与其成反比，C越大正则化效果越低。
6、核函数/核变换与参数 kernel：从低维到高维，从线性可分到非线性可分
$f(x)=w^{T}\phi(x)+w_{0}$
如何从低维到高维，从线性到非线性，就是用一个中间转换函数Φ(x)，增加新的一系列特征。
这里注意：当数据映射到高维后，如果在高维进行计算内积，其计算难度会大大增加，所以我们直接在低维计算，然后将内积的值转换到高维，代入前面的式子。（并不将数据真正映射，而是将计算后的值映射）
sklearn常用的核函数：
poly：多项式核函数（polynomial）
rbf：径向基函数（radial basis function），高斯核函数是最常用的径向基函数。
扩展：选用rbf kernel（高斯核）时，数据已经被映射到了无穷维的空间，从而保证数据一定是线性可分的。
**知识点：**Kernel提供了一种在 不写出具体映射表达式的情况下，计算数据内积的方法。 原则上说，但凡是需要计算内积的算法，都可以使用kernel trick，而不仅仅局限于svm。
算法评价
优点：
1、可以在样本数量较小或适中，特征数量较多的情况下表现出色（需要的是有限的点-支持向量，所以不需要很多的数据、稀疏的样本也能表现得好）
2、可以用不同的核函数应对比较复杂的情况（相当于logistic回归）
3、无局部最优问题（相对于神经网络等）
缺点：
1、SVM的处理速度相对较慢，尤其是数据量较多时（涉及大量计算）
2、对噪声（异常值）比较敏感，可能出现类重叠问题导致过拟合
解决：调参C松弛一下；换成贝叶斯
3、特征数比样本数多很多时也是容易过拟合的
解决：不带核函数；进行正则化；换成logistic回归
4、需要调参（尤其是C和kernel）
5、数学原理比较复杂，不易解释，也不易进行可视化展示（相对于决策树）。
应用
也可以用于回归，但主要是二分类，比如文本和超文本的分类、图像识别、手写体识别等，近年来很多领域被神经网络所取代。