支持向量机：抽象难懂？看这里就明白了！

今天给大家分享的知识是关于支持向量机的内容，支持向量机算法是目前学习到的机器学习算法中最抽象、最难以理解的内容，不过支持向量机算法在实际使用过程中还是比较常见，无论是在医学研究还是经济研究中都能看到身影，所有，这一块内容还是非常重要的，而且很多面试中对这一部分的基础知识还是会考察，所以大家还是需要掌握理解。

支持向量机（support vector machines，SVM）是一种二类分类模型，但是和一般的二分类模型例如逻辑回归模型在分类结果上还是有区别，支持向量机的二分类是正类和负类的划分。其基本模型定义是在特征空间上的间隔最大的线性分类器，熟悉感知机的都知道，感知机只注重是否能够正确分类样本，因此，感知机模型是存在多个模型，支持向量机在正确分类样本的基础上还强调正确分类样本的可信度，要求分离超平面距离支持向量的距离最大。支持向量机模型由简单到复杂主要包括：线性可分支持向量机、线性支持向量机以及非线形支持向量机。当训练数据线形可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机，从而也被称为硬间隔支持向量机；当训练数据近似线形可分时，通过软间隔最大化，学习一个线形的分类器，即线性支持向量机，又被称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

一、线性可分支持向量机

当我们有一个线性可分的数据集，我们肯定能够找得到一个甚至多个超平面讲数据集完全分类正确，如图中随时，在两类不同点之间，我们总是可以找到一个或者多个直线将两类点分开，这也是感知机的原理，只需要注重分类正确即可，但是支持向量机强调在在保证分类正确的基础上，我们还要要求距离分离超平面的点与超平面的间隔越大，越大表示在现有的分类下，分类正确的可信度越高，在这种情况下，我们只能求得唯一的超平面。

在线性可分训练数据集的情况下，通过间隔最大化得到的最优分离超平面我们假设为 $w^{*}\cdot x+b^{*}=0$ 对应的决策函数 $f(x) = sign(w^{*}\cdot x+b^{*})$ 称为线性可分支持向量机。在讲解关于支持向量机相关的知识之前，我们先做一点准备和铺垫工作，关于函数间隔和几何间隔，一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度，在数据可分的情况下，同时我们已经得到能够将数据正确分类的超平面，对于距离超平面远的点，我们都不会对其分类正确性存疑，但是距离超平面近点点，我们会担心是不是被误分类，在 $w\cdot x+b = 0$ 确定的情况下, $|w\cdot x+b|$ 能够相对地表示点x距离超平面的远近，而 $w\cdot x+b$ 的符号与类标记y的符号是否一致能够表示分类是否正确，所有可以使用 $y(w\cdot x+b)$ 来表示分类的正确性及确信度，这就是函数间隔的概念，记为 $\hat{\gamma _{i}} = y_{i}(w\cdot x_{i}+b)$ ,定义最小函数间隔为 $\hat{\gamma }=min\hat{\gamma _{i}}$ ，函数间隔可以表示分类预测的正确性话置信度，但是只要我们成比例低改变超平面的参数w和b,例如 $\lambda w$ 和 $\lambda b$ ，超平面并没有变化，但是函数间隔却变成了之前的 $\lambda$ 倍，从而，我们引入了几何间隔 $\gamma _{i}=y_{i}(\frac{w}{||w||}\cdot x_{i}+\frac{b}{||w||})$ ,大家可以看出，几何间隔相当于在函数间隔上做了一个单位化的操作，最小几何间隔定义为 $\gamma =min\gamma _{i}$ ,从几何间隔和函数间隔的公式得出，他们关系如下： $\gamma _{i}=\frac{\hat{\gamma _{i}}}{||w||}$ , $\gamma = \frac{\hat{\gamma }}{||w||}$ 。

在讲完上面的基础知识之后，我们正式讲解关于支持向量机的内容，支持向量机的核心就是最大化间隔，我们可以将其转换成约束最优化问题：

我们的主问题是最大化几何间隔 $\gamma$ ，约束条件是所有的点几何间隔都必须大于等于 $\gamma$ ，考虑函数间隔和几何间隔的关系，我们将其转换为：

函数间隔 $\hat{\gamma }$ 的值并不会影响最优问题的解，当我们将w和b按比例改变， $\hat{\gamma }$ 也会按照相应的比例改变，因此， $\hat{\gamma }$ 的取值不会对最终结果产生影响，我们为了方便将其取值为1，同时由于最大化 $\frac{1}{||w||}$ 和最小化 $\frac{1}{2}||w||^{2}$ 等价，进一步地，我们求解的模型为：

这是一个凸优化问题，存在唯一解，我们最终可以得到一个最优的超平面 $w^{*}\cdot x+b^{*}=0$

总结一下，线性可分支持向量机算法如下：

尽管我们在上面提出了支持向量机的原始问题以及求解，但是实际并不好做，因此，我们引入对偶问题求解，将对偶问题引入有以下优点：一、算法求解会相对容易；二、可以引入核函数，进而推广到非线形分类问题。我们根据前面的目标函数和约束构建拉格朗日函数，如下：

$L(w,b,a)=\frac{1}{2}||w||^{2}-\sum_{i=1}^{N}a_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i=1}^{N}a_{i}$

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

为了得到对偶问题的解，我们需要先对目标函数求极小值，再求极大值，求 $minL(w,b,a)$ ，对 L(w,b,a)分别关于w,b求一阶导数并令其为0，得到如下结果：

这一块知识需要使用到矩阵求导到知识，大家如果需要自行学习，难度不大，根据等式结果我们得到

$w=\sum_{i=1}^{N}a_{i}y_{i}x_{i}$

$\sum_{i=1}^{N}a_{i}y_{i}=0$

将上面结果带入原拉格朗日函数，我们可以得到如下结果：

再得到以上结果之后，我们再针对极小函数再求极大结果，如下：

最终我们可以得到对偶问题的最优解 $\alpha ^{*}$ ，根据我们之前的一阶求导公式我们可以得到

$w^{*}=\sum_{i=1}^{N}\alpha _{i}^{*}y_{i}x_{i}$

$b^{*} = y_{j}-\sum_{i=1}^{N}\alpha _{i}^{*}y_{i}(x_{i}*x_{j})$

分离超平面为：

$\sum_{i=1}^{N}\alpha _{i}^{*}y_{i}(x_{i}*x_{j})+b^{*} =0$

分类决策函数为：

$f(x) = sign(\sum_{i=1}^{N}\alpha _{i}^{*}y_{i}(x_{i}*x_{j})+b^{*})$

最后总结一下线性可分支持向量机的算法如下：

二、线性支持向量机

在我们上面讲述的线性可分支持向量机的基本要求是数据线性可分，即我们能够找到一个甚至多个超平面将数据完全分类正确，但是我们在实际过程中不一定能够满足这种严格的条件，总是会存在一些特异点，导致数据线性不可分，我们将这些特异点去掉之后，剩下的大部分样本点的组合是线性可分的。线性不可分意味着函数间隔不能大于等于1的约束条件，因此，我们就放松了这个约束，引入了一个松弛变量 $\varepsilon _{i}\geq 0$ ，使得函数间隔加上松弛变量大于等于1，约束条件变为

$y_{i}(w\cdot x_{i}+b)\geq 1-\varepsilon _{i}$

我们的目标函数针对每个松弛变量 $\varepsilon _{i}$ ，都会支付一个代价 $\varepsilon _{i}$ ，类似于lasso回归和Ridge回归限制模型复杂度的思想，从而，我们的目标函数变成了

$\frac{1}{2}||w||^{2}+C\sum_{i=1}^{N}\varepsilon _{i}$

这里，C>0称为惩罚参数，C值越大对误分类的惩罚增大，C值小时对误分类的惩罚减小。从我们的目标函数可以看出要使整个目标函数最小化，需要使得两部分内容都要小，前面部分尽量小使得我们的间隔尽量大，参考前面最大化间隔定义，后面部分尽量小要求误分类的点个数要尽量少。

因此我们完整的最优化问题为：

同样地，原始问题的最优解不好求，我们还是采用求解对偶问题得到最优解，构建拉格朗日函数为：

分别针对 $w$ 、 $b$ 和 $\varepsilon _{i}$ 求一阶导数

得到：

将以上结果带入拉格朗日函数中得

再对 $\alpha$ 求极大，即得到对偶问题：

最终我们的分离超平面为：

$\sum_{i=1}^{N}\alpha _{i}^{*}y_{i}(x\cdot x_{i})+b^{*} =0$

分类决策函数为：

$f(x) = sign(\sum_{i=1}^{N}\alpha _{i}^{*}y_{i}(x\cdot x_{i})+b^{*} )$

总结一下，线性支持向量机算法如下：

三、非线形支持向量机

对于线性分类问题，线性分类支持向量机是一种非常有有效的方法但是，有时分类问题不是线性的，例如下图所示，我们在原始的二维空间中无法找到一条直线进行分类，但是我们可以将数据中映射到三维或者更高维的空间，从而，在高纬空间中找到一个可以分类的超平面，实现这个操作我们需要使用到核技巧，至于核技巧是什么我们不过多讲述，可以实现将数据映射到高纬领域，同时可以在低纬空间进行运算。