理解支持向量机

SIGAI学习与实践平台

发布于 2019-10-08 16:22:15

6540

发布于 2019-10-08 16:22:15

支持向量机是机器学习中最不易理解的算法之一，它对数学有较高的要求。之前SIGAI微信公众号已经发过“用一张图理解SVM脉络”，“理解SVM的核函数和参数”这两篇文章，今天重启此话题，对SVM的推导做一个清晰而透彻的介绍，帮助大家真正理解SVM，掌握其精髓。市面上有不少讲解支持向量机的文章和书籍，但真正结构清晰、触达精髓的讲解非常少见。

为什么要掌握SVM？

在2012年深度学习火了之后，SVM用得越来越少了，目前在机器视觉领域CNN是标配，NLP中通常也使用RNN/LSTM和CNN，语音识别中大量使用RNN/LSTM。为什么还要学SVM？原因有3：

1.保证机器学习知识的系统性、完整性。SVM作为历史上出现的最重要的有监督学习算法之一，其思想、原理（包括核技巧）是机器学习的重要组成部分。如果不学它，你对机器学习的理解是不完整的。对于做学术，很多东西是一脉相承的，新的方法和理论有不少是借鉴于或扩展于已有的方法和思想。

2.面试时经常会问到，尤其是应届生校招面试。SVM、logistic回归、决策树、EM算法之类的知识点，很多时候在面试官眼里是检验应聘者机器学习水平的试金石，如果你不想因为它而导致面试挂掉，那就一定要啃下这个硬骨头。

3.在某些问题上，可能还会使用此算法。在某些结构化数据预测（分类与回归问题）上，SVM有很好的效果，核函数是很强悍的，可以解决非线性问题；在小样本的情况下，SVM也可以训练出高精度、泛化性能好的模型，而且核函数可以规避维数灾难问题。

数学知识

要理解支持向量机，下面的数学知识是必不可少的：

1.解析几何中点到平面距离的计算公式

2.拉格朗日对偶，包括强对偶条件、Slater条件

3.KKT条件

4.凸优化，Hessian矩阵

在推导和证明中将会大量使用这些知识，如果对它们还不清楚，一定要沉下心来仔细学习理解。本文不对这些数学知识做专门的介绍。

整体推导思路

在之前的公众号文章“用一句话总结常用的机器学习算法”中对SVM的一句话解释是：最大化分类间隔的线性分类器（不考虑核函数）。这一总结可谓精准，指出了SVM的本质。SVM的推导过程冗长而复杂，为了让大家不至于迷路，只知细节而无法把握整体，我们总结了整个推导过程中的关键步骤和要点，画出了下面的图：

这是之前的公众号文章“用一张图理解SVM脉络”的升级版。下面我们以此图为主线，介绍SVM的推导过程和核心的点。

线性分类器

SVM起源于线性分类器，如果不使用费线性核函数，它就是线性分类器。因此要理解SVM首先要真正理解线性分类器的原理。

线性分类器是n维空间中的分类超平面，它将空间切分成两部分，对应于正样本和负样本所在的区域。对于二维空间，线性分类器是一条直线；对于三维空间，它是一个平面；超平面是在更高维空间的推广。

线性分类器所依赖的超平面方程为

其中x为输入向量（样本特征向量）；w是权重向量，b是偏置项（标量），这两组参数通过训练得到。一个样本如果满足

则被判定为正样本，否则被判定为负样本。下图是线性分类器对空间进行分割的示意图，在这里是二维平面

令很多初学者困惑的是，到底在直线哪一边的样本是正样本，哪一边的样本是负样本？其实无论哪一边，都是可以做到的。因为只要将超平面方程乘以一个负数，即可实现上面不等式的反号。下面用一个例子说明，如下图

在上图中，正样本有一个样本点(5, 5)，以红色表示。负样本有一个样本点(1, 1)，用蓝色表示。分类超平面即图中的直线的方程为

将正样本的点代入上面的方程，计算出的值为正。将负样本的点代入，计算出来的结果为负。但如果我们将方程两边同乘以-1，得到如下的方程

此方程所表示的还是同一条直线，但将正样本代入方程之后，计算出的结果为负，负样本则为正。因此我们可以控制权重向量w和偏置项b的值使得正样本的预测值一定为正。

最大化分类间隔

一般情况下，给定一组训练样本可以得到不止一个可行的线性分类器将两类样本正确分类，如下图的例子

问题来了：在所有可行的线性分类器中，什么样的分类器是好的？为了得到好的泛化性能，分类平面应该不偏向于任何一类，并且离两个类的样本都尽可能的远。这样，落在直线两边这个间隔内的样本都能被正确分类。这种最大化分类间隔的目标就是SVM的基本思想。

SVM的目标是寻找一个分类超平面，不仅能正确的分类每一个样本，且要使得每一类样本中距离超平面最近的样本到超平面的距离尽可能远。假设训练样本集有l个样本，特征向量是n维向量，类别标签取值为+1或者-1，分别对应正样本和负样本。SVM为这些样本寻找一个最优分类超平面

首先要保证每个样本都被正确分类。对于正样本有

对于负样本有

由于正样本的的类别标签为+1，负样本的类别标签为-1，可统一写成如下不等式约束

第二个要求是超平面离两类样本的距离要尽可能大。根据解析几何中点到平面的距离公式，每个样本离分类超平面的距离为

其中

是向量的L2范数。显然上面的超平面方程有冗余，将方程两边都乘以不等于0的常数，还是同一个超平面，利用这个特点可以简化求解的问题。可以对w和b加上如下约束

消掉此冗余，同时简化点到超平面距离计算公式。对分类超平面的约束变成

这是上面那个不等式约束的加强版。分类超平面与两类样本之间的间隔为

目标是使得这个间隔最大化，等价于最小化下面的目标函数

加上前面定义的约束条件之后，求解的优化问题可以写成：

可以证明这个问题是凸优化问题，且满足Slater条件。一个被证明为凸优化问题，意义是重大的，它意味着我们可以用通行的数值优化算法得到全局最优解。而满足Slater条件则意味着我们可以用拉格朗日对偶将其转化为对偶问题求解，对偶问题的求解难度远小于求解原问题。具体的证明与推导可以阅读参考文献[1]。

对偶问题

上面的优化问题带有大量不等式约束，因此不容易求解，可以用拉格朗日对偶将其转化成对偶问题。经过推导，得到对偶问题为

这里的α是拉格朗日乘子变量，在对偶问题中，它们是优化变量。具体的推导过程可以阅读文献[1]。需要强调的是，不是什么问题都可以用拉格朗日对偶转化为对偶问题求解，它需要满足强对偶条件，此时原问题与对偶问题有相同的最优解。强对偶成立的一种判据是Slater条件。

在推导过程中可以解出w的值，由此得到SVM的预测函数为

不为0的α对应的训练样本称为支持向量，这就是支持向量机这一名字的来历。下图是支持向量的示意图

另外可以证明对偶问题同样为凸优化问题，在文献[1]中有详细的证明过程。限于篇幅，本文不对推导和证明和推导的细节进行过多的介绍。

松弛变量与惩罚因子

线性可分的支持向量机不具有太多的实用价值，因为在现实应用中样本一般都不是线性可分的，接下来对它进行扩展，得到能够处理线性不可分问题的支持向量机。通过使用松弛变量和惩罚因子对违反不等式约束的样本进行惩罚，可以得到如下最优化问题

其中

是松弛变量，如果它不为0，表示样本违反了不等式约束条件。C为惩罚因子，是人工设定的大于0的参数，用来对违反不等式约束条件的样本进行惩罚。

同样可以证明此问题是凸优化问题，且满足Slater条件，因此可以用拉格朗日对偶转化为对偶问题求解。

上面的原问题中还是带有大量的不等式约束，不易求解，通过拉格朗日对偶，将其转化为如下的对偶问题

和线性可分的对偶问题相比，唯一的区别是多了

不等式约束，这是乘子变量的上界。将w的值代入超平面方程，得到分类决策函数为：

这和线性可分时是一样的。这个预测函数是线性函数，因此这种SVM还是一个线性分类器。同样可以证明，此时的对偶问题是凸优化问题。

KKT条件的使用

在最优点处必须满足KKT条件，将其应用于原问题，可以得到，在最优点处所有的样本都必须要满足下面的条件

上面第一种情况对应的是自由变量即非支持向量，第二种情况对应的是支持向量，第三种情况对应的是违反不等式约束的样本。在后面的SMO算法中，会应用此条件来选择优化变量，以及判定算法是否收敛。

核映射与核函数

虽然加入松弛变量和惩罚因子之后可以处理线性不可分问题，但支持向量机还是一个线性分类器，只是允许错分样本的存在，这从前面给出的预测函数可以看出。本节要介绍的核映射使得支持向量机成为非线性分类器，决策边界不再是线性的超平面，而可以是形状非常复杂的曲面。

如果样本线性不可分，可以对特征向量进行映射将它转化到更高维的空间，使得在该空间中线性可分，这种方法在机器学习中被称为核技巧。核映射

将特征向量变换到更高维的空间

在对偶问题中计算的是两个样本向量之间的内积，映射后的向量在对偶问题中为

直接计算这个映射效率太低，而且不容易构造映射函数。如果映射函数选取得当，存在函数K，使得下面等式成立

这样只需先对向量做内积然后用函数进行变换，这等价于先对向量做核映射然后再做内积，这将能有效的简化问题的求解。在这里我们看到了求解对偶问题的另外一个好处，对偶问题中出现的是样本特征向量之间的内积，而核函数刚好作用于这种内积，替代对特征向量的核映射。满足上面条件的函数称为核函数，常用的核函数有以下几种

核函数的精妙之处在于不用真的对特征向量做核映射，而是直接对特征向量的内积进行变换，而这种变换却等价于先对特征向量做核映射然后做内积。

需要注意的是，并不是任何函数都可以用来做核函数，必须满足一定的条件-即Mercer条件。

为向量加上核映射后，要求解的对偶问题变为

根据核函数必须满足的等式条件，它等价于下面的问题

最后得到的分类判别函数为：

如果核函数K是非线性函数，此时的预测函数是非线性的，因此SVM是非线性的。与不用核映射相比，只是求解的目标函数、最后的判定函数对特征向量的内积做了核函数变换。预测时的时间复杂度为

，当训练样本很多、支持向量的个数很大的时候，速度是一个问题。

了简化表述，定义矩阵Q，其元素为

对偶问题可以写成矩阵和向量形式

其中e是分量全为1的向量，y是样本的类别标签向量。

SMO算法

前面给出了支持向量机的对偶问题，但并没有说明怎么求解此问题。由于矩阵的规模和样本数相等，当训练样本数很大的时候，这个矩阵的规模很大，求解二次规划问题的经典算法将会面临性能问题。本节将介绍高效的求解算法-经典的SMO算法。

前面已经推导出加上松弛变量和核函数后的对偶问题：

矩阵Q为对称半正定矩阵，其元素为

根据核函数的定义有

Q矩阵半正定由核函数的性质保证。

为了表述方便，定义下面的核矩阵：

它和矩阵Q的关系为

定义变量

之前推导过，原问题的KKT条件为

在极小值点处必须满足该条件，由于对偶问题是凸优化问题，KKT条件是取得极值的充分条件。在后面的求解过程中将使用这一结论。

求解子问题

SMO算法由Platt等人提出，是求解支持向量机对偶问题的高效算法。算法的核心思想是每次在优化变量中挑出两个分量进行优化，让其他分量固定，这样能保证满足等式约束条件，这是一种分治法的思想。

下面先给出这两个变量的优化问题（称为子问题）的求解方法。假设选取的两个分量为和，其他分量都固定即当成常数。由于

对这两个变量的目标函数可以写成

现在的核心问题是求解两个变量的二次函数的极值。约束条件为线性约束与常数不等式约束。这个问题可以得到公式解。利用等式约束可以消掉一个变量，转化为一元函数函数在区间上的极值问题，只要学过初中数学，都可以推导，无非是过程较为繁琐而已。详细的推导可以阅读文献[1]。

优化变量的选择

上面已经解决了两个变量问题的求解，接下来说明怎么选择这两个变量，在这里使用了启发式规则。第一个变量的选择方法是在训练样本中选取违反KKT条件最严重的那个样本。在最优点处训练样本是否满足KKT条件的判据是

其中

定义为：

首先遍历所有满足约束条件

的样本点，检查它们是否满足KKT条件。如果都满足KKT条件，则遍历整个训练样本集，判断它们是否满足KKT条件，直到找到一个违反KKT条件的变量

。找到这个变量之后，接下来寻找

，选择的标准是

使得有足够大的变化。根据前面的推导，

依赖于

。因此选择使得

最大的

。由于

已经确定，因此

已知。如果

，则选择最小的

；否则选择最大的

。

多分类问题

前面讲述的支持向量机只能解决二分类问题。对于多分类问题，可以用这种二分类器的组合来解决，常用的是如下两种方案：

1对剩余方案。对于有K个类的分类问题，训练k个二分类器。训练时第i个分类器的正样本是第i类样本，负样本是除第i类之外其他类型的样本，这个分类器的作用是判断样本是否属于第i类。在进行分类时，对于待预测样本，用每个分类器计算输出值，取输出值最大那个作为预测结果。

1对1方案。如果有k个类，训练

个二分类器，即这些类两两组合。训练时将第类作为正样本，其他各个类依次作为负样本，总共有k(k-1)/2种组合。每个分类器的作用是判断样本是属于第i类还是第j类。对样本进行分类时采用投票的方法，依次用每个二分类器进行预测，如果判定为第m类，则m类的投票数加1，得票最多的那个类作为最终的判定结果。

下面用一个简单的例子来进行说明，我们要对3个类进行分类。如果采用1对剩余方案，则训练3个分类器：

第1个分类器在训练时以第1类样本作为正样本，另外两类作为负样本；第2个分类器在训练时以第2类样本作为正样本，另外两类作为负样本；第3个分类器在训练时以第3类样本作为正样本，另外两类作为负样本。在预测时，输入样本特征向量，计算每个模型的预测函数值，将样本判别为预测值最大的那个类。这种方案如下图所示，黑色的样本为待预测样本。