支持向量机SVM原理

【数之道】支持向量机SVM是什么，八分钟直觉理解其本质_哔哩哔哩_bilibili

SVM是由Vapnik等人于1995年提出的，在之后的20多年里它都是最具影响力的机器学习算法之一。SVM不仅可以用于分类问题，还可以用于回归问题。在深度学习出现之前，基于高斯核的SVM在很多问题上一度取得了最好的效果。

SVM也因为具有较好的泛化性能，适合小样本等优点，被广泛应用于各种实际问题。

为了更好地理解下文，我们首先由简至繁地梳理一下支持向量机学习方法：

线性可分SVM：当训练数据线性可分时，通过硬间隔(hard margin，什么是硬、软间隔下面会讲)最大化得到一个线性分类器，即硬间隔SVM。
线性SVM：当训练数据非线性可分，但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以得到一个线性分类器，即软间隔SVM。
非线性SVM：当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以得到非线性SVM。

SVM原理

SVM原理的数学推导过程冗长而复杂，后文我们一一拆解，首先简要总结如下：

简单的SVM可以从线性分类器推导出来，根据最大化分类间隔的优化目标，线性可分问题中的SVM是可以求解的。
SVM优化问题是一个凸优化问题，并且满足Slater条件，因此强对偶成立，通过拉格朗日对偶可以将其转化成对偶问题求解。
通过加入松弛变量和惩罚因子，可以将SVM推广到线性不可分的情况，具体做法是对违反约束条件的训练样本进行惩罚，得到线性不可分问题的SVM优化训练。
通过核函数，可以将支持向量机转化成非线性模型，此时的对偶问题也是凸优化问题。
支持向量机的求解，常用方法是SMO算法，它是一种分治法，每次选择两个变量进行优化。两变量优化问题是一个带等式和不等式约束条件的二次函数极值问题，可以求出解析解。并且这个问题也是凸优化问题，优化变量的选择通过KKT条件来确定。

从线性分类器说起

SVM起源于线性分类器，如果不使用非线性核函数，SVM就是线性分类器。线性分类器是维空间中的分类超平面，它将空间切分成两部分，分别对应于正样本和负样本所在的区域。对于二维空间，线性分类器是一条直线；对于三维空间，它是一个平面；超平面是在更高维空间的推广。

SVM的目标是最大化分类间隔

一般情况下，给定一组训练样本可以得到不止一个可行的线性分类器，如下图的例子。那么在所有可行的线性分类器中，什么样的分类器是好的呢？为了得到好的泛化性能，分类平面应该不偏向于任何一类，并且离两个类的样本都尽可能的远。这样，落在直线两边这个间隔内的样本都能被正确分类。这种最大化分类间隔的目标就是SVM的基本思想。SVM算法认为下图中的分类器A在性能上优于分类器B，其依据是A的分类间隔比B要大。

SVM的目标是寻找一个分类超平面，不仅能正确的分类每一个样本，且要使得每一类样本中距离超平面最近的样本到超平面的距离尽可能的远。根据解析几何中点到平面的距离公式，每个样本离分类超平面的距离为：

上式即支持向量机SVM的基本型，或者说是线性SVM最优化问题的数学描述。这是一个凸二次规划（convex quadratic programming）问题。

接下来，就要讨论如何利用最优化技术求解上述公式描述的问题。相信到这里的SVM并不难，不过接下来就会出现一些令人望而生畏的数学术语了，凸二次优化、拉格朗日对偶、KKT条件、Slater条件等等

转化为对偶问题求解

这里我们先复习一下求解最优化问题的方法，根据待优化问题是否有约束，以及约束的类型，可以把求解方式分为以下三种：

无约束优化问题：直接求导、最速下降法、共轭梯度法、牛顿法等；
等式约束优化问题：拉格朗日（Lagrange）乘子法；
不等式约束优化问题：KKT条件（Karush–Kuhn–Tucker这三个人名字的缩写）。

大家应该发现了，SVM的优化问题就是带有大量不等式约束的优化问题，属于最不容易求解的哪一类，那么如何求解呢？先说答案，可以用拉格朗日对偶将原问题（primal problem）转化成对偶问题（dual problem）来求解。之所以可以这么求解，还需要满足一些条件。

首先得是可以转化：因为SVM的优化问题问题是凸优化问题，且满足Slater条件，因此可以转为对偶问题。

是凸优化问题，意味着可以用通行的数值优化算法得到全局最优解。
凸规划指的是目标函数为凸函数，不等式约束函数也为凸函数，等式约束函数是仿射的（理解成是线性的也行）。
满足Slater条件，意味着可以用拉格朗日对偶将其转化为对偶问题求解，对偶问题的求解难度远小于求解原问题（求解更高效）。
Slater条件告诉我们，在什么样的条件下凸优化问题与其Lagrange对偶问题是强对偶的，也就是什么条件下我们可以将原问题进行转化。所幸的是，这个条件告诉我们，一般情况下强对偶是成立的，因为该条件很弱。
Slater条件是指，如果满足原问题是凸优化问题，并且至少存在绝对一个绝对可行点，什么叫绝对可行点，就是一个可以让所有不等式约束都不取等号的可行点，那么就具有强对偶性。

其次是转化的条件：KKT条件是不等式约束的最优解的必要条件（对于凸规划，KKT条件就是充要条件了）。KKT条件将拉格朗日乘子法所处理的等式约束优化问题推广至不等式。在实际应用上，KKT条件（方程组）一般不存在解析解，有数值计算可供选用。
最后是转化的方法：拉格朗日乘子法的基本思想是把原始目标函数约束条件转化为新的目标函数的一部分，从而使有约束优化问题变成我们习惯的无约束优化问题。

总结一下，待解的SVM优化原问题是凸优化，且满足Slater条件，因此加上KKT条件，就可以用拉格朗日乘子法把它转化为对偶问题求解了。