机器学习算法之支持向量机SVM

来源： https://www.biaodianfu.com

什么是支持向量机（SVM）？

支持向量机（support vector machines, SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机学习方法包括构建由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case），线性支持向量机（linear support vector machine）及非线性支持向量机（non-linear support vector machine）。简单的模型是复杂模型的基础，也是复杂模型的特殊情况。当训练数据线性可分时，通过硬间隔最大化（hard margin maximization），学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。

当输入空间为欧式空间或离散集合、特征空间为希尔贝特空间时，核函数（kernel function）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。核方法（kernel method）是比支持向量机更为一般的机器学习方法。

以上定义来自《统计学习方法》上的定义。简单的讲支持向量机(Support vector machines, SVM)是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，他的学习策略就是间隔最大化，同时该方法可以形式化为一个求解图二次规划。

支持向量机可分为三类:

• 线性可分支持向量机、硬间隔（hard-margin svm)
• 线性支持向量机、软间隔(soft-margin svm)
• 非线性支持向量机、Kernel SVM

支持向量机模型中存在三宝：

• 间隔
• 对偶
• 核技巧

支持向量机和感知机在某些方面很相似，其相同点:

• 都是二分类模型
• 都是通过一个分离超平面对特征进行分类

不同点：

• SVM 是特殊的感知机
• 感知机是用误分类最小的策略，求得分离超平面，这时存在无穷个解，感知机利用间隔最大化求得最优分离超平面。

简单点讲，SVM就是一种二类分类模型，他的基本模型是的定义在特征空间上的间隔最大的线性分类器，SVM的学习策略就是间隔最大化。我们先来看看下面这个图:

图中有分别属于两类的一些二维数据点和三条直线。如果三条直线分别代表三个分类器的话，请问哪一个分类器比较好？我们凭直观感受应该觉得答案是H3。首先H1不能把类别分开，这个分类器肯定是不行的；H2可以，但分割线与最近的数据点只有很小的间隔，如果测试数据有一些噪声的话可能就会被H2错误分类(即对噪声敏感、泛化能力弱)。H3以较大间隔将它们分开，这样就能容忍测试数据的一些噪声而正确分类，是一个泛化能力不错的分类器。对于支持向量机来说，数据点若是p维向量，我们用p-1维的超平面来分开这些点。但是可能有许多超平面可以把数据分类。最佳超平面的一个合理选择就是以最大间隔把两个类分开的超平面。因此，SVM选择能够使离超平面最近的数据点的到超平面距离最大的超平面。

支持向量机原理

线性可分支持向量机与硬间隔最大化

首先给出一个非常简单的分类问题（线性可分），我们要用一条直线，将下图中黑色的点和白色的点分开，很显然，图上的这条直线就是我们要求的直线之一（可以有无数条这样的直线）

假如说，我们令黑色的点=-1，白色的点=+1，直线

f(x)=w⋅x+b

，这儿的x、w是向量，其实等价f(x)=w1x1+w2x2+…+wnxn+b

, 当向量x的维度=2的时候，f(x)

表示二维空间中的一条直线，当x的维度=3的时候，f(x)

表示3维空间中的一个平面，当x的维度n>3的时候，表示n维空间中的n-1维超平面。我们令黑色白色两类的点分别为+1, -1，所以当有一个新的点x需要预测属于哪个分类的时候，我们用sgn(f(x))

就可以预测了，sgn

表示符号函数，当f(x)>0

的时候，sgn(f(x))=+1

, 当f(x)<0

的时候sgn(f(x))=–1

。但是，我们怎样才能取得一个最优的划分直线f(x)

呢？下图的直线表示几条可能的f(x)

：

一个很直观的感受是让这条直线到给定样本中最近的点最远，下面给出几个图，来说明一下。

第一种分法：

第二种分法：

这两种分法哪种更好呢？从直观上来说，就是分割的间隙越大越好，把两个类别的点分得越开越好。选择使得间隙最大的函数作为分割平面是由很多道理的，比如说从概率的角度上来说，就是使得置信度最小的点置信度最大，从实践的角度来说，这样的效果非常好。

上图被红色和蓝色的线圈出来的点就是所谓的支持向量(support vector)。

Classifier Boundary就是f(x)，红色和蓝色的线（plus plane与minus plane）就是support vector所在的面，红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙。

这里直接给出M的式子：

M=2‖w‖

SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。如下图所示，

w⋅x+b=0

即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。

在推导之前，先给出一些定义。假设给定一个特征空间上的训练数据集：

T=(x1,y1),(x2,y2),…,(xN,yN)

。其中，xi∈Rn

，yi∈{+1,−1},i=1,2,…N

，xi

为第i个特征向量，yi

为类标记，当它等于+1时为正例；为-1时为负例。再假设训练数据集是线性可分的。

几何间隔

对于给定的数据集

T

和超平面wx+b=0

，定义超平面关于样本点(xi,yi)

的几何间隔为：γi=yi(w‖w‖⋅xi+b‖w‖)

。超平面关于所有样本点的几何间隔的最小值为：γ=mini=1,2…,Nγi

。实际上这个距离就是我们所谓的支持向量到超平面的距离。

根据以上定义，SVM模型的求解最大分割超平面问题可以表示为以下约束最优化问题：

maxw,bγ

s.t.yi(w‖w‖⋅xi+b‖w‖)≥γ,i=1,2,…,N

s.t的意思是subject to，也就是限制条件的意思。将约束条件两边同时除以

γ

得到：yi(w‖w‖γ⋅xi+b‖w‖γ)≥1

因为

‖w‖

，γ

都是标量，所以为了表达式简洁，令：w=w‖w‖γ

，b=b‖w‖γ

得到：yi(w⋅xi+b)≥1,i=1,2,…,N

又因为最大化

γ

，等价于最大化1‖w‖

，也就等价于最小化12‖w‖2

，因此SVM模型的求解最大分割超平面问题又可以表示为以下约束最优化问题：

minw,b12‖w‖2

s.t.yi(w⋅xi+b)≥1,i=1,2,…,N

对偶算法

为了求解线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，这就是线性可分支持向量机的对偶算法（dual algorithm）。这样做的优点，一是对偶问题往往更容易求解；二是引入自然核函数，进而推广到非线性分类问题。

首先构建拉格朗日函数（Lagrange function）。为此，对每一个不等式约束引进拉格朗日乘子（Lagrange multiplier）

αi≥0,i=1,2,…,N

，定义拉格朗日函数：

L(w,b,α)=12wTw+∑i=1Nαi(1−yi(wTxi+b))=12wTw−∑i=1Nαiyi(wTxi+b)+∑i=1Nαi

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

maxαminw,bL(w,b,α)

。所以，为了得到对偶问题的解，需要先求L(w,b,α)

对w,b的极小，再求对α

的极大。

1、求

minw,bL(w,b,α)

将拉格朗日函数

L(w,b,α)

分别对 w,b求偏导，并令其值为0。

∂L∂w=w–∑i=1Nαiyixi=0⇒w=∑i=1Nαiyixi

∂Lb=−∑i=1Nαiyi=0⇒∑i=1Nαiyi=0

将上式代入拉格朗日函数，即得：

minw,bL(w,b,α)=12(∑i=1Nαiyixi)T∑i=1Nαiyixi−∑i=1Nαiyi((∑i=1Nαiyixi)Txi+b)+∑i=1Nαi=12∑i=1N∑j=1NαiyiαjyjxiTxj−∑i=1N∑j=1NαiyiαjyjxjTxi+∑i=1Nαi=−12∑i=1N∑j=1NαiyiαjyjxiTxj+∑i=1Nαi

2、求

minw,bL(w,b,α)

对α

的极大值，即对偶问题：

maxα−12∑i=1N∑j=1NαiyiαjyjxiTxj+∑i=1Nαis.t.∑i=1Nαiyi=0αi≥0,i=1,2…N

将式中的目标函数由求极大转换成求极小，就得到下面与之等价的对偶最优化问题：

minα12∑i=1N∑j=1NαiyiαjyjxiTxj−∑i=1Nαis.t.∑i=1Nαiyi=0αi≥0,i=1,2…N

对线性可分训练数据集，假设对偶最优化问题对

α

的解为α∗=(α1∗,α2∗,…,αN∗)T

，可以由α∗

求得原始最优化问题的解w∗,b∗

。有下面的定理：

设

α∗=(α1∗,α2∗,…,αN∗)T

是对偶最优化问题的解，则存在下标j，使得αj∗>0

，并可按下式求得原始最优化问题的解w∗,b∗

：

w∗=∑i=1Nαi∗yixi

b∗=yj−∑i=1Nαi∗yi(xiTxj)

证明：根据定理，KKT条件成立，即得：

∂L(w∗,b∗,α∗)∂w=w∗−∑i=1Nαi∗yixi=0∂L(w∗,b∗,α∗)∂b=−∑i=1Nαi∗yi=0∂L(w∗,b∗,α∗)∂α=0αi(1−yi(wTxi+b))=0αi≥0,i=1,2,…,N1−yi(wTxi+b)≤0,i=1,2,…,N

由此得

w∗=∑i=1Nαi∗yixi

，其中至少有一个αj∗>0

（用反正法，假设αj∗=0

，由式可知w∗=0

，而w∗=0

不是原始最优化问题的解，产生矛盾），由此对j有：

yj(w∗⋅xj+b∗)–1=0

将式代入并注意到

yj2=1

，即得：

b∗=yj–w∗xj=yj–∑i=1Nαi∗yi(xixj)

由此定理可知，分离超平面可以写成：

∑i=1Nαi∗yi(x⋅xi)+b∗=0

分类决策函数可以写成：

f(x)=sign(∑i=1Nαi∗yi(x⋅xi)+b∗)

这就是说，分类决策函数只依赖于输入x和训练样本输入得内积。上式称为线性可分支持向量机得对偶形式。

综上所述，对于给定得线性可分训练数据集，可以首先求对偶we难题的解

α∗

；再利用公式求得原始问题的解w∗,b∗

；从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。

线性支持向量机与软间隔最大化

接下来谈谈线性不可分的情况，因为线性可分这种假设实在是太有局限性了。下图就是一个典型的线性不可分的分类图，我们没有办法用一条直线去将其分成两个区域，每个区域只包含一种颜色的点。

要想在这种情况下的分类器，有两种方式，一种是用曲线去将其完全分开，曲线就是一种非线性的情况，跟之后将谈到的核函数有一定的关系：

另外一种还是用直线，不过不用去保证可分性，就是包容那些分错的情况，不过我们得加入惩罚函数，使得点分错的情况越合理越好。对一个分错的点的惩罚函数就是这个点到其正确位置的距离：

在上图中，蓝色、红色的直线分别为支持向量所在的边界，绿色的线为决策函数，那些紫色的线表示分错的点到其相应的决策面的距离，这样我们可以在原函数上面加上一个惩罚函数，并且带上其限制条件为：

min12‖w‖2+C∑i=1Rεi,s.t.,yi(wTxi+b)≥1−εi,εi≥0

公式为在线性可分问题的基础上加上的惩罚函数部分，当

xi

在正确一边的时候，ε=0

，R为全部的点的数目，C是一个由用户去指定的系数，表示对分错的点加入多少的惩罚，当C很大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重，当C很小的时候，分错的点可能会很多，不过可能由此得到的模型也会不太正确，所以如何选择C是有很多学问的，不过在大部分情况下就是通过经验尝试得到的。

接下来就是同样的，求解一个拉格朗日对偶问题，得到一个原问题的对偶问题的表达式：

maxα∑i=1nαi−12∑i,j=1nαiαjyiyjxiTxj s.t. ,C≥αi≥0,i=1,⋯,n∑i=1nαiyi=0

在线性不可分情况下得到的对偶问题，不同的地方就是α的范围从[0, +∞)，变为了[0, C]，增加的惩罚

ε

没有为对偶问题增加什么复杂度。

非线性支持向量机与核函数

在这之前我们都假设样本空间是线性可分的，然而在很多现实任务中，原始样本可能并不存在一个能正确分类的线性超平面。那怎么办呢？对于这样的问题，我们可以将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分，然后再运用SVM求解。

下图是一个典型的线性不可分的情况：

但是当我们把这两个类似于椭圆形的点映射到一个高维空间后，映射函数为：

z1=x12,z2=x22,z3=x2

用这个函数可以将上图的平面中的点映射到一个三维空间（

z1,z2,z3

)，并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。

回忆刚刚得到的对偶问题表达式：

maxα∑i=1nαi−12∑i,j=1nαiαjyiyjxiTxj s.t. ,C≥αi≥0,i=1,⋯,n∑i=1nαiyi=0

我们可以进行改造，令：

xiTxj=κ(xi,xj)

。这个式子所做的事情就是将线性的空间映射到高维的空间，κ(xi,xj)

有很多种，下面是比较典型的两种：

κ(xi,xj)=(xi⋅xj+1)d

κ(xi,xj)=exp⁡(−(xi−xj)22σ2)

上面这个核称为多项式核，下面这个核称为高斯核，高斯核甚至是将原始空间映射为无穷维空间，另外核函数有一些比较好的性质，比如说不会比线性条件下增加多少额外的计算量，等等，这里也不再深入。一般对于一个问题，不同的核函数可能会带来不同的结果，一般是需要尝试来得到的。

SVM优缺点总结

SVM优点

• 由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
• 不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
• 拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，这在某种意义上避免了“维数灾难”。
• 理论基础比较完善(例如神经网络就更像一个黑盒子)。
• 解决小样本下机器学习问题
• 无需依赖整个数据
• 泛化能力比较强

SVM缺点：

• 二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)
• 只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)
• 当观测样本很多时，效率并不是很高
• 对非线性问题没有通用解决方案，有时候很难找到一个合适的核函数
• 对于核函数的高维映射解释力不强，尤其是径向基函数
• 对缺失数据敏感

如何在 Python中使用 SVM？

Scikit-learn里对SVM的算法实现都包在sklearn.svm下面，其中SVC类是用来进行进行分类的任务，SVR是用来进行数值回归任务的。不同的核函数需要指定不同的参数。针对线性函数，只需要指定参数C，它表示对不符合最大间距规则的样本的惩罚力度。针对多项式核函数，除了参数C外，还需要指定degree，它表示多项式的阶数。针对高斯核函数，除了参数C外，还需要指定gamma值，这个值对应的是高斯函数公式中的

12σ2

的值。

使用线性核函数

import matplotlib.pyplot as plt

from sklearn import svm, datasets

iris = datasets.load_iris()

X = iris.data[:, :2]  # we only take the first two features. We could

svc = svm.SVC(kernel='linear', C=1).fit(X, y)

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1

y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1

h = (x_max / x_min) / 100

xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])

plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)

plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)

plt.xlabel('Sepal length')

plt.ylabel('Sepal width')

plt.xlim(xx.min(), xx.max())

plt.title('SVC with linear kernel')

使用rbf核函数（高斯核函数）

svc = svm.SVC(kernel='rbf', C=1).fit(X, y)

gamma 值越大，SVM 就会倾向于越准确的划分每一个训练集里的数据，这会导致泛化误差较大和过拟合问题。

C: 错误项的惩罚参数 C。它还控制平滑决策边界和正确分类训练点之间的权衡。

多项式核函数

svc = svm.SVC(kernel='poly', degree=4).fit(X, y)

参考链接：

• 支持向量机（SVM）
• https://www.cnblogs.com/leftnoteasy/archive/2011/05/02/basic-of-svm.html
• https://tangshusen.me/2018/10/27/SVM/