支持向量机 | Support Vector Machine (SVM)
1、SVM算法思想
SVM算法的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。什么意思呢？往下看
线性可分SVM（硬间隔）
现在有两种类别的数据需要分类, 如下图:
要想将这两类数据分开, 可以说是轻而易举, 只需要这样:
但是这样分类的方式(线条)有很多, 而支持向量机这个算法是追求完美的, 他想要的效果不仅仅是将数据分开, 还要找到一个最佳的分类'位置'进行黄金分割, 就像这样:
每一个可能把数据集正确分开的方向都有一个最优决策面（有些方向无论如何移动决策面的位置也不可能将两类样本完全分开），而不同方向的最优决策面的分类间隔通常是不同的，那个具有“最大间隔”的决策面就是SVM要寻找的最优解。
这是无数条可以分类的直线当中最完美的，因为它恰好在两个类的中间，距离两个类的点都一样远, 同时他还是这两个类别之间间隔最大的线性分类器; 换句话说: 这个分类器对每个类别最近的元素距离最远.
线性SVM（软间隔）
上面这种能将数据集完全正确划分的SVM，我们称为——线性可分SVM（硬间隔），但在实际应用中，完全线性可分的样本是很少的，我们会遇到不能够完全线性可分的样本，于是我们就有了线性SVM（软间隔），相比于硬间隔的苛刻条件，我们允许个别样本点出现在间隔带里面，即允许少量样本不满足约束，比如：
非线性SVM
事实上，大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在。
在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。
以上就是SVM的三种应用情况，可以总结为：
- 当训练数据线性可分时，通过硬间隔(hard margin)最大化可以学习得到一个线性分类器，即硬间隔SVM。
- 当训练数据不能线性可分但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以学习到一个线性分类器，即软间隔SVM。
- 当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以学习到一个非线性SVM。
2、SVM算法原理
首先，牢记：SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。
但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。而在经过漫长的公式推导后，你最终会发现，其实与线性决策面的方向和位置直接相关的参数都会被约减掉，最终结果只取决于样本点的选择结果。
线性可分SVM—硬间隔
目标函数(类别之间的间隔)
如图所示：
我们先在数据内找到另个类别的支持向量（可以理解为靠近另一个类别的一些点），支持向量决定了支持边界，两个类别的支持边界是平行的，二我们要找的最优超平面就在这两个支持边界正中间，这样就保证了找出来的最优超平面到两个类别的距离是最远的。所以我们在推导SVM时可以先将两个支持边界之间的间隔表示出来，找到最大间隔就可以了。
我们给出样本, 类别标签为
在上图中, 向量是决策面的法向量, 那么决策面的方程就能表示成: ；可以规定法向量指向的一侧为正类,另一侧为负类，则：
正例满足：
负例满足：
此时两个类别的边界分别为和，求两个支持边界之间的距离有很多种方式：
用点到直线的距离求间隔
知道了决策面的表达式后, 我们就可以根据点到直线的距离公式：
求出其中一个支持边界到决策面的距离：
这里 是向量的模，表示在空间中向量的长度；支持向量所在的直线 或 , 而无论是-1还是1, 绝对值之后都是1 , 所以:
这只是其中一类到决策面的距离, 因此, 总间隔为
用向量投影求间隔
如图：
我们要分类的向量到决策边界的距离可以用该向量在决策边界的法向量上面的正交投影来衡量,所以我们如果想要求两个类别之间的间隔, 可以用两个支持边界(决策边界两边的那两条线)上的支持向量在决策边界的法向量上的正交投影相减即可( 在 上的投影减去 在 上的投影)：
当然上图中的 并没有在支持边界上, 我们假设他们都在决策边界上, 这时我们就可以用向量的正交投影的公式：
所以间隔为：
还可以用两条平行线兼得距离公式求得间隔表达式；
得出目标函数
间隔求出来了, 而我们的SVM要求的是两类之间的最大间隔：
等价于：
等价于：
之所以要加上平方和1/2的系数，是为了以后进行最优化的过程中对目标函数求导时比较方便，但这绝不影响最优化问题最后的解。
同时也不要忘了有一些约束条件：
将这个式子精简一下：
至此我们的目标函数就出来了：
这里n是样本点的总个数，缩写s. t. 表示“Subject to”，是“服从某某条件”的意思。这是一个典型的不等式约束条件下的二次型函数优化问题
某些条件下，把原始的约束问题通过拉格朗日函数转化为无约束问题，如果原始问题求解棘手，在满足KKT的条件下用求解对偶问题来代替求解原始问题，使得问题求解更加容易。
拉格朗日乘子法
上一节我们求出了目标函数, 但这是一个带约束的优化问题, 此时我们可以用拉格朗日乘子法构造一个拉格朗日函数, 将原来的有约束的优化问题转换为没有约束的优化问题。
拉格朗日乘子法的基本思想是把约束条件转化为新的目标函数的一部分，从而使有约束优化问题变成我们习惯的无约束优化问题。
拉格朗日乘子法扩展
①: 当约束条件为等式时：
原函数：
拉格朗日函数：
②: 当约束条件为不等式时：
原函数：
拉格朗日函数：
并且不等式约束转换之后需要满足**KKT(Karush-Kuhn-Tucker)**条件, 即：
KKT条件是对最优解的约束，而原始问题中的约束条件是对可行解的约束
回到我们得原始问题上来，
我们用拉格朗日乘子法对我们得原函数进行转换：
假设找到了最佳参数使得目标函数取得了最小值 。即 。而根据 ， 可知 ，因此 ，为了找到最优的参数 ，使得 接近 ，故问题转换为出 。
但我们最终得目的是求原函数关于 和 的最小值, 也就是拉格朗日函数关于 和 的最小值，
所以我们将问题转换为：
拉格朗日对偶函数
拉格朗日函数的对偶问题为：
对偶问题
假设有个函数 我们有：
也就是说，最大的里面挑出来的最小的也要比最小的里面挑出来的最大的要大。这关系实际上就是弱对偶关系，而强对偶关系是当等号成立时，即：
如果 是凸优化问题，强对偶性成立。而我们之前求的 KKT 条件是强对偶性的充要条件。
回到我们的问题中, 我们现在的目标是先求出：
我们分别令函数 对 求偏导，并使其等于0。
得到 :
将我们得到的结果带入 ：
求出来之后我们就可以求 了, 也就是:
不难发现这是一个二次规划问题，有现成的通用的算法来求解。
二次规划（SMO算法）
二次规划
一个有n个变数与m个限制的二次规划问题可以用以下的形式描述。首先给定：
- 一个n 维的向量 c
- 一个n × n 维的对称矩阵Q
- 一个m × n 维的矩阵A
- 一个m 维的向量 b
则此二次规划问题的目标即是在限制条件为
的条件下，找一个n 维的向量 x ，使得
为最小。
其中是的转置。
根据不同的参数特性，可以得到对问题不同的结论
- 如果Q是半正定矩阵，那么f(x)是一个凸函数。相应的二次规划为凸二次规划问题；此时若约束条件定义的可行域不为空，且目标函数在此可行域有下界，则该问题有全局最小值。
- 如果Q是正定矩阵，则该问题有唯一的全局最小值。
- 若Q为非正定矩阵，则目标函数是有多个平稳点和局部极小点的NP难问题
根据优化理论，一个点x成为全局最小值的必要条件是满足KKT。当f(x)是凸函数时，KKT条件也是充分条件。
对于二次规划问题, 我们常用 SMO(Sequential Minimal Optimization) 算法求解。SMO序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。
我们刚说了 SMO 算法每次只优化一个参数，但我们的优化目标有约束条件： 没法一次只变动一个参数。所以我们选择了一次选择两个参数。
这里的SMO算法就不展开说了，可以参考：SMO详解 - SVM中的SMO算法 我们通过 SMO 求得最优解
假设我们现在求得了 的最优解 ，则根据式 可求得最优 ：
我们知道所有 对应的点都是支持向量，我们可以随便找个支持向量，然后带入： 求出 b 即可:
此处s代表该点是支持向量,
为了更具鲁棒性，我们可以求得支持向量的均值：
最终我们的决策函数为:
最最后,加上一个阶跃函数:
阶跃函数sing()
线性不可分SVM—软间隔
我们允许部分样本点不满足约束条件：
为了度量这个间隔软到何种程度，我们为每个样本引入一个松弛变量 ，令 ，且
引入松弛变量后, 我们的目标函数就可以重新写为:
其中 C 是一个大于 0 的常数，可以理解为错误样本的惩罚程度，若 C 为无穷大， 必然无穷小，如此一来线性 SVM 就又变成了线性可分 SVM；当 C 为有限值的时候，才会允许部分样本不遵循约束条件。
构造拉格朗日函数:
其中 和 是拉格朗日乘子， 和 是主问题参数。
根据强对偶性，对偶问题为：
分别对主问题参数、b 和 求偏导数，并令偏导数为 0，得出如下关系：
将这些关系带入拉格朗日函数中，得到：
所以:
我们可以看到这个和硬间隔的一样，只是多了个约束条件。
然后我们利用 SMO 算法求解得到拉格朗日乘子。
将最佳乘子带入即得:
超平面函数为:
这边要注意一个问题，在间隔内的那部分样本点是不是支持向量
我们可以由求参数 w 的那个式子可看出，只要 的点都能够影响我们的超平面，因此都是支持向量。
非线性SVM—核函数
如下图所示，核技巧的基本思路分为两步:
- 使用一个变换将原空间的数据映射到新空间(例如更高维甚至无穷维的空间)；
- 然后在新空间里用线性方法从训练数据中学习得到模型。
我们用 x 表示原来的样本点，用 表示 x 映射到特征新的特征空间后到新向量。那么分割超平面可以表示为:
则非线性得SVM的对偶问题就变成:
核函数得定义
设 是输入空间(欧式空间的子集或离散集合)，又设 是特征空间(希尔伯特空间)，如果存在一个 到 的映射
使得对所有 ，函数满足条件
则称 为核函数， 为映射函数，式中 为 和 的內积。
因为低维空间映射到高维空间后维度可能会很大，如果将全部样本的点乘全部计算好，这样的计算量太大了。
有了核函数之后, 我们可以通过计算原始空间的核函数, 就可以得到特征空间内 和 的点积, 岂不美哉?
而我们常见的核函数有:
(1): 线性核函数
(2): 多项式核函数
(3): 高斯核函数
其他核函数：核函数详解
选择核函数的方法：
- 如果特征的数量大到和样本数量差不多，则选用LR或者线性核的SVM；
- 如果特征的数量小，样本的数量正常，则选用SVM+高斯核函数；
- 如果特征的数量小，而样本的数量很大，则需要手工添加一些特征从而变成第一种情况。
3、SVM优缺点
优点
- 有严格的数学理论支持，可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题；
- 由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
- 能找出对任务至关重要的关键样本（即：支持向量）；
- 采用核技巧之后，可以处理非线性分类/回归任务；
- 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
缺点
- 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为 ，其中 N 为训练样本的数量；
- 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 ；
- 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。
4、SVM调参
主要参考: Hsu C W, Chang C C, Lin C J. A practical guide to support vector classification[J]. 2003.
- 将原始数据转换为SVM算法期待的格式；
- 将数据进行scaling(很重要)；
- 一般考虑用高斯核RBF(如果特征维度太高，建议直接用线性SVM)；
- 交叉验证寻找最优的RBF的参数以及参数 CC ;
- 用上面找到的最优参数在整个训练集上训练；
参考文章:
同时推荐刘建平老师的文章: