1. 基本概念

SVM，全称是Support Vector Machine，中文名叫支持向量机。SVM的基本模型是在特征空间上找到最佳的分离超平面，使得训练集上正负样本间隔(Margin)最大。SVM是用来解决二分类问题的有监督学习算法，在引入了核方法之后SVM也可以用来解决非线性问题。

SVM一般有下面三种：

硬间隔支持向量机（线性可分支持向量机）：当训练数据线性可分时，可通过硬间隔最大化，学习一个线性的分类器。

软间隔支持向量机（线性支持向量机）：当训练数据近似线性可分时，可通过软间隔最大化，也学习一个线性的分类器。

非线性支持向量机：当训练数据线性不可分时，可通过核方法以及软间隔最大化，学习非线性支持向量机。

2. 硬间隔支持向量机

现有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是-1 ，另一边所对应的y全是1。 

图1

这个超平面可以用分类函数 f(x) = wx + b表示，当f(x) 等于0的时候，x便是位于超平面上的点，而f(x)大于0的点对应 y=1 的数据点，f(x)小于0的点对应y=-1的点，如下图所示：

从直观上而言，这个超平面应该是最适合分开两类数据的直线。而判定“最适合”的标准就是这条直线离直线两边的数据的间隔最大。所以，得寻找有着最大间隔的超平面。SVM的核心之一就是想办法将“间隔”最大化！

最大间隔推导过程

通过数学公式推导发现：两类样本距离最大的因素仅仅和最佳超平面的法向量有关！ 要找到具有“最大间隔”（maximum margin）的最佳超平面，就是找到以下的条件约束满足式。

满足条件约束的最大间隔超平面（SVM基本型）

这就是SVM的基本型，现在我们已经推导知道了。因为现在的目标函数是二次的，约束条件是线性的，所以它是一个凸二次规划问题。这个问题可以用现成的QP (Quadratic Programming) 优化包进行求解。一言以蔽之：在一定的约束条件下，目标最优，损失最小。

此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

2.1 拉格朗日对偶问题

引入拉格朗日乘子，则SVM的基本型问题的拉格朗日函数可写为

该问题的拉格朗日函数

引入拉格朗日乘子推导过程

以上推导结论是：我们并不关心单个样本是如何的，我们只关心样本间两两的乘积，这也为后面核方法提供了很大的便利。 

SVM决策模型

2.2 SVM问题的KKT条件

SVM的基本型有不等式约束，因此上述过程满足库恩-塔克尔条件(Kuhn-Tucker condition KKT)条件：

库恩-塔克尔条件(Kuhn-Tucker condition)

训练完成之后，大部分的训练样本都不需要保留，最终的模型仅与支持向量有关。 如何求解α呢？很明显这是一个二次规划问题，可使用通用的二次规划算法来求解，但是SVM的算法复杂度是O(n*n)，在实际问题中这种开销太大了。为了有效求解该二次规划问题，人们通过利用问题本身的特性，提出了很多高效算法，Sequential Minimal Optimization(SMO)就是一个常用的高效算法。在利用SMO算法进行求解的时候就需要用到上面的KKT条件。

3. 软间隔支持向量机

在现实任务中很难找到一个超平面将不同类别的样本完全划分开，即很难找到合适的核函数使得训练样本在特征空间中线性可分。退一步说，即使找到了一个可以使训练集在特征空间中完全分开的核函数，也很难确定这个线性可分的结果是不是由于过拟合导致的。解决该问题的办法是在一定程度上运行SVM在一些样本上出错，为此引入了“软间隔”（soft margin）的概念。

Soft Margin

具体来说，硬间隔支持向量机要求所有的样本均被最佳超平面正确划分，而软间隔支持向量机允许某些样本点不满足间隔大于等于1的条件。当然在最大化间隔的时候也要限制不满足间隔大于等于1的样本的个数使之尽可能的少。于是我们引入一个惩罚系数C>0 ，并对每个样本点(xi→,yi)引入一个松弛变量（slack variables）ξ≥0 此时

软间隔SVM推导过程

对比软间隔支持向量机的对偶问题和硬间隔支持向量机的对偶问题可发现二者的唯一差别就在于对偶变量的约束不同，软间隔支持向量机对对偶变量的约束是0≤αi≤C，硬间隔支持向量机对对偶变量的约束是0≤αi，于是可采用和硬间隔支持向量机相同的解法求解式。

对于软间隔支持向量机，KKT条件要求：

软间隔支持向量机KKT

软间隔支持向量机的最终模型仅与支持向量有关。

4. 非线性支持向量机

现实任务中原始的样本空间D中很可能并不存在一个能正确划分两类样本的超平面。对于这样的问题可以通过将样本从原始空间映射到特征空间使得样本在映射后的特征空间里线性可分。

特征变换

在上文中我们提到其实我们根本不关心单个样本的表现，只关心特征空间中样本间两两的乘积，因此我们没有必要把原始空间的样本一个个地映射到特征空间中，只需要想法办求解出样本对应到特征空间中样本间两两的乘积即可。为了解决该问题可设想存在核函数：

这给求解带来很大的方便。于是可写为：

同样的我们只关心在高维空间中样本之间两两点乘的结果而不关心样本是如何变换到高维空间中去的。求解后即可得到：

剩余的问题同样是求解αi，然后求解w和b即可得到最佳超平面。

5.支持向量回归

支持向量机不仅可以用来解决分类问题还可以用来解决回归问题，称为支持向量回归（Support Vector Regression，SVR）。

6.常用核函数

7. SVM的优缺点

优点：SVM在中小量样本规模的时候容易得到数据和特征之间的非线性关系，可以避免使用神经网络结构选择和局部极小值问题，可解释性强，可以解决高维问题。

缺点：SVM对缺失数据敏感，对非线性问题没有通用的解决方案，核函数的正确选择不容易，计算复杂度高，主流的算法可以达到O(n*n)的复杂度，这对大规模的数据是吃不消的。

8. 参考文献

周志华. 机器学习 [D]. 清华大学出版社，2016. 

华校专、王正林. Python大战机器学习 [D]. 电子工业出版社，2017. 

Peter Flach著、段菲译. 机器学习 [D]. 人民邮电出版社，2016. 

SVM：https://blog.csdn.net/liugan528/article/details/79448379

支持向量机通俗导论（理解SVM的三层境界）https://blog.csdn.net/v_july_v/article/details/7624837