从原理到代码实现4万字一步一步带你入门支持向量机

引言

各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。

如果有人问到说机器学习中最经典的算法是什么，那一定就是非支持向量机（Support Vector Machine, SVM）莫属了。之所以称之为经典是因为支持向量机的背后有着完美的数学推导与证明作为支撑。当然，也正是因为这个原因使得SVM有着较高的学习门槛，很多初学者在学习SVM时都会被它的数学证明所难倒。因此，在接下来的内容中，掌柜将会尽可能以最通俗的表达来介绍 SVM 中的相关原理。

本文总计约4万余字，全方面地阐述了SVM从思想、原理、sklearn中的使用示例到数学证明再到代码实现的所有内容，希望能够帮助各位初学者一步一步买入支持向量机的大门。

以下为全文目录，大家可以根据需要索引。

第9章 支持向量机 9.1 SVM思想 9.2 SVM原理 9.2.1超平面的表达 9.2.2函数间隔 9.2.3几何间隔 9.2.4最大间隔分类器 9.2.5函数间隔的性质 9.2.6小结 9.3 SVM示例代码与线性不可分 9.3.1线性SVM示例代码 9.3.2从线性不可分谈起 9.3.3将低维特征映射到高维空间 9.3.4 SVM中的核技巧 9.3.5从高维到无穷维 9.3.6常见核函数 9.3.7小结 9.4 SVM中的软间隔 9.4.1软间隔定义 9.4.2最大化软间隔 9.4.3 SVM软间隔示例代码 9.4.4 小结 9.5拉格朗日乘数法 9.5.1条件极值 9.5.2求解条件极值 9.5.3小结 9.6对偶性与KKT条件 9.6.1广义拉格朗日乘数法 9.6.2原始优化问题 9.6.3对偶优化问题 9.6.4 KKT条件 9.6.5计算示例 9.6.6小结 9.7 SVM优化问题 9.7.1构造硬间隔广义拉格朗日函数 9.7.2硬间隔求解计算示例 9.7.3构造软间隔广义拉格朗日函数 9.7.4软间隔中的支持向量 9.7.5小结 9.8 SMO算法 9.8.1坐标上升算法 9.8.2 SMO算法思想 9.8.3 SMO算法原理 9.8.4偏置 求解 9.8.5 SVM算法求解示例 9.8.6小结 9.9 从零实现支持向量机 9.9.1 常见核函数实现 9.9.2 SMO求解过程实现 9.9.3 SVM二分类代码实现 9.9.4 SVM多分类代码实现 9.9.5 小结

9 支持向量机

9.1 SVM思想

什么是支持向量机呢？初学者刚接触到这个算法时基本上都会被这个名字所困扰，到底什么叫“向量机”，听起来总觉得怪怪的。因此首先需要明白的是，支持向量机其实和“机”一点关系也没有，算法的关键在于“支持向量”。如图9-1所示为4种不同模型对同一个数据集分类后的决策边界图。可以看到尽管每个模型都能准确地将数据集分成两类，但是从各自的决策边界到两边样本点的距离来看却有着很大的区别。

为了能更加清楚的进行观察，下面将4个决策边界放到一张图中，如图9-2所示。

如图9-2所示，图中左边从上到下分别为模型(d)(a)(b)(c)在数据集上的决策边界。可以发现模型(c)的泛化能力应该会是最差的，因为从数据的分布位置来看真实的决策面应该是一条左高右低倾斜的直线。其次是模型(b)的泛化能力，因为从图2可以看出模型(b)的决策面太过于偏向方块形的样本点。因为在评估分类决策面优劣的一个原则就是，当没有明确的先验知识告诉我们决策面应该偏向于哪边时，最好的做法应该是居于中间位置，也就是类似于模型(a)和模型(d)的决策面。那么模型(a)和模型(d)谁又更胜一筹呢？进一步，可以将(a)和(d)这两个模型各自到两侧样本点距离可视化出来，如图9-3所示。

从图9-3中一眼便可以看出，模型(d)的决策面要更居于“中间”（事实上就是在中间），而模型(a)的决策面也是略微偏向于方块形的样本点。因此在这4个模型中，模型(d)的泛化能力通常情况下都会是最强的。此时有读者可能就会问，假如把模型(a)中的决策面向上平移一点，使得其也居于两条虚线之间，那么此时应该选择谁呢？答案当然依旧是模型(d)，原因在于模型(d)的决策面还满足另外一个条件，到两条虚线的距离最大。换句话说也就是，模型(d)中两条虚线之间的距离要大于模型(a)中两条虚线之间的距离。

说到这里，相信各位读者已经猜到，模型(d)对应的就是支持向量机模型，同时虚线上的两个样本点就被称为支持向量。可以发现，最终对决策面其决定性作用的也只有这两个样本点，说得通俗点就是仅根据这两个点就能训练得到模型(d)。

因此，这里可以得出的结论就是，通过支持向量机我们便能够得到一个最优超平面，该超平面满足到左右两侧最近样本点的间隔相同，且离左右最近样本点的间隔最大。不过那又该如何来找到这个超平面呢？

9.2 SVM原理

9.2.1超平面的表达

在正式定义距离之前，这里先回顾一下超平面的表达式

其中$w$$w$表示权重参数（系数），$b$$b$表示截距，$x$$x$表示样本点。同时需要说明的是，在SVM中，用$y=+1,y=-1$$y=+1,y=-1$分别来表示正样本和负样本。

从上述表达式可知，当通过某种方法找到参数$w,b$$w,b$后，也就代表确立了超平面。不过对于SVM建模来说，应该从哪个地方入手呢？ 答案是从SVM的核心思想：最大化间隔（Gap） 入手。

9.2.2函数间隔

上面说到SVM的核心思想就是最大化间隔，既然是最大化间隔那总得有个度量间隔的方法才行。根据中学知识可知，当超平面$w^{T}x+b=0$${{w}^{T}}x+b=0$确定后，可以通过$|w^{T}x+b|$$|{{w}^{T}}x+b|$来表示每个样本点到超平面的相对距离，也就是说虽然实际距离不是$|w^{T}x+b|$$|{{w}^{T}}x+b|$这么多，但是它依旧遵循绝对值大的离超平面更远的原则，如图9-4所示。

如图9-4所示，其中直线方程为$x_1+x_2-3=0$$x_1+x_2-3=0$，且$A,B$$A,B$分别为正负两个样本点，即$y^A=+1,y^B=-1$$y^A=+1,y^B=-1$，则此时有点$A$$A$到直线的相对距离为$|w^{T}x+b|=|2+3-3|=2$$|{{w}^{T}}x+b|=|2+3-3|=2$，点$B$$B$到直线的相对距离为$|w^{T}x+b|=|1+1-3|=1$$|w^Tx+b|=|1+1-3|=1$。

同时还可以注意到，只要分类正确，$y^{(i)}(w^{T}x+b)>0$${{y}^{(i)}}({{w}^{T}}x+b)>0$就成立；或者说如果$y^{(i)}(w^{T}x+b)>0$${{y}^{(i)}}({{w}^{T}}x+b)>0$成立，则这就意味着分类正确。并且其值越大说明其分类正确的可信度就越高，而这也是$y$$y$为什么取$\pm 1$$\pm1$的原因。所以此时可以将训练集中所有样本点到超平面的函数间隔（Functional Margin）定义为[1]

且定义训练集中样本点到超平面的函数间隔中的最小值为

但是此时可以发现，如果在式$(9.1)$$(9.1)$的两边同时乘以$k(k\ne 0)$$k(k\neq0)$，虽然此时超平面并没有发生改变，但是相对距离却变成了之前的$k$$k$倍。所以仅有函数间隔显然不能够唯一确定这一距离，还需要引入另外一种度量方式——几何间隔。

9.2.3 几何间隔

所谓几何间隔（Geometric Margin），就是样本点到直线实实在在的距离。只要直线不发生改变，那么间隔就不会发生任何改变，这样就避免了在函数间隔中所存在的问题。那么应该如何来表示几何间隔呢？如图9-5所示，线段$AB$$AB$就表示样本点$A$$A$到直线的真实距离。

如图9-5所示，直线方程为$w^{T}x+b=0$${{w}^{T}}x+b=0$，$A$$A$为数据集中任意一个点$x^{(i)}$${{x}^{(i)}}$，${\gamma }^{(i)}$${{\gamma }^{(i)}}$为$A$$A$到直线的距离，可以看成是向量$\overrightarrow{BA}$$\vec{BA}$的模；$W$$W$为垂直于$w^{T}x+b=0$$w^Tx+b=0$的法向量。此时便可以得到点$B$$B$的坐标为

又因为$B$$B$点在直线上，所以满足

因此可以通过化简等式$(9.5)$$(9.5)$来得到几何距离的计算公式。不过此时的问题在于$W$$W$该怎么得到？

现在，假设有一直线$w^{T}x+b=0$${{w}^{T}}x+b=0$,$w={(w_1,w_2)}^T$$w={{({{w}_{1}},{{w}_{2}})}^{T}}$，即$w_1{x}_1+w_2{x}_2+b=0$$w_1x_1+w_2x_2+b=0$，那么该直线的斜率便为$k_1=-w_1/w_2$$k_1=-w_1/w_2$。又因为$W$$W$垂直于该直线，所以$W$$W$的斜率为$k_2=w_2/w_1$$k_2=w_2/w_1$。因此$W$$W$的一个方向向量为$(1,k_2)$$(1,k_2)$。进一步再同时乘以$w_1$$w_1$即可得到$W=(w_1,w_2)=w$$W=(w_1,w_2)=w$，即$W$$W$其实就是$w$$w$。也就是说，如果直线$w^{T}x+b=0$${{w}^{T}}x+b=0$，那么$w$$w$就是该直线的其中一条法向量。

所以根据式$(9.5)$$(9.5)$有

因此几何距离计算公式为

当然，这只是当样本$A$$A$为正样本，即$y_A=+1$${{y}_{A}}=+1$时的情况，更一般地几何距离的计算公式为

故，根据图9-4可知，样本点$A,B$$A,B$到直线$x_1+x_2-3=0$$x_1+x_2-3=0$的距离分别为

此时可以发现，同函数间隔类似只要在分类正确的情况下几何间隔也都满足条件$y^{(i)}\cdot {\gamma }^{(i)}>0$${{y}^{(i)}}\cdot {{\gamma }^{(i)}}>0$。进一步，定义训练集中样本点到超平面的几何间隔中最小值为

同时，函数间隔与几何间隔存在以下关系

可以发现，几何间隔其实就是在函数间隔的基础上施加了一个约束限制。此时我们已经有了对于间隔度量的方式，所以下一步自然就是最大化这个间隔来求得分类超平面。

9.2.4 最大间隔分类器

什么是最大间隔分类器（Maximum Margin Classifiers） 呢？上面说到，有了间隔的度量方式后，接着就是最大化这一间隔，然后求得超平面$w^{T}x+b=0$${{w}^{T}}x+b=0$。最后通过函数$g(w^{T}x+b)$$g({{w}^{T}}x+b)$将所有样本点输出只含$\{-1,+1\}$$\{-1,+1\}$的值，以此来完成对数据集样本的分类任务。由于$g(w^{T}x+b)$$g({{w}^{T}}x+b)$就是一个分类器，又因为它是通过最大化几何间隔得来的，故将其称之为最大间隔分类器。

因为在式$(9.10)$$(9.10)$中已经得到了几何间隔的表达式，所以再对其最大化即可

其中$s.t.$$s.t.$表示服从于约束条件。同时，式$(9.12)$$(9.12)$的含义就是找到参数$w,b$$w,b$，使得满足以下条件：

① $\gamma$$\gamma$尽可能大，因为目的就是最大化$\gamma$$\gamma$;

② 同时要使得样本中所有的几何距离都大于$\gamma$$\gamma$，因为由式$(9.10)$$(9.10)$可知$\gamma$$\gamma$是所有间隔中的最小值；

所以，进一步由式$(9.11)$$(9.11)$中函数间隔与几何间隔的关系，可以将式$(9.12)$$(9.12)$中的优化问题转化为

此时可以发现，约束条件由几何间隔变成了函数间隔，准确说应该既是函数间隔同样也是几何间隔。因此，既然可以看作函数间隔，那么令$\hat{\gamma }=1$$\hat{\gamma}=1$自然也不会影响最终的优化结果。

所以，式$(9.13)$$(9.13)$中的优化问题便可以再次转化为如下形式

但是对于$(9.14)$$(9.14)$这样一个优化问题还是无法直接解决。不过，对于$f(x)>0$$f(x)>0$来说$max1/f(x)$$\max 1/f(x)$就等价于$minf(x)$$\min f(x)$，进一步也就等价于$min{(f(x))}^2$$\min {{(f(x))}^{2}}$，这三者求解出的$x$$x$都相同。所以进一步式$(9.14)$$(9.14)$可以将式化简为

之所以要进行这样的处理，是因为这样可以将其转换为一个典型的凸优化问题，并用现有的方法进行求解；而在前面乘以$1/2$$1/2$是为了后面求导时方便，同时这也不会影响优化结果。到这一步，我们就算是搞清楚了SVM的基本思想，以及它需要求解的优化问题。

9.2.5 函数间隔的性质

在9.2.1节优化问题的化简过程中掌柜直接将函数间隔设置为了1，不过相信对于不少读者来说在这一点上仍旧比较疑惑。当然，这也是一个在学习SVM中最典型的问题，因此接下来就这点进行一个简要的说明。

假设现在有如下函数间隔

那么对等式$(9.16)$$(9.16)$两边同时除以$\hat{\gamma }$$\hat{\gamma}$便有

此时令$W=\frac{w}{\hat{\gamma }},B=\frac{b}{\hat{\gamma }}$$W=\frac{w}{{\hat{\gamma }}},B=\frac{b}{{\hat{\gamma }}}$，便可以将$(9.17)$$(9.17)$转化为

接着再把式$(9.18)$$(9.18)$中的$W,B$$W,B$换成$w,b$$w,b$即可得到

不过需要明白的是，式$(9.16)$$(9.16)$和式$(9.19)$$(9.19)$中的$w,b$$w,b$并不是同一个。

例如现有如下平面方程

某正样本$y^{(k)}=+1$${{y}^{(k)}}=+1$的函数间隔为${\hat{\gamma }}^{(k)}=2$${{\hat{\gamma }}^{(k)}}=2$，所以有

进一步在等式$(9.21)$$(9.21)$两边同时除以2有

虽然此时的$w,b$$w,b$同时都缩小了两倍，函数间隔变成了$1$$1$，但是$2x_1+4x_2-8=0$$2x_1+4x_2-8=0$与$x_1+2x_2-4=0$$x_1+2x_2-4=0$所表示的依旧是同一个平面。所以此时可知，$w^T{x}^{(i)}+b=0$${{w}^{T}}{{x}^{(i)}}+b=0$与$W^T{x}^{(i)}+B=0$${{W}^{T}}{{x}^{(i)}}+B=0$代表的是同一个平面，故可以直接由式$(9.16)$$(9.16)$得到式$(9.19)$$(9.19)$，也就是说同一个平面与用什么字母表示无关。因此可以将函数间隔直接设为1（实质是同时除以了函数间隔）。

9.2.6 小结

在本节中，掌柜首先通过一个引例介绍了支持向量机的核心思想；接着介绍了支持向量机中衡量间隔的两种度量方式，即函数间隔和几何间隔；然后介绍了如何通过结合函数间隔与几何间隔来建模支持向量机的优化问题；最后还介绍了SVM中的一个经典问题，函数间隔为什么可以设为1。

9.3 SVM示例代码与线性不可分

在前面两节内容中，掌柜介绍了支持向量机的基本思想以及对应的数学原理。不过说一千道一万，还是不如自己亲手来做一做。在接下来的内容中，掌柜将首先介绍如何通过sklearn来搭建相应的SVM分类模型，然后将接着介绍如何处理SVM中的线性不可分问题。

由于文章篇幅过长排版不便，大家可以回复SVM获取本文高清PDF下载链接与教学PPT！

代码仓库见：https://github.com/moon-hotel/MachineLearningWithMe

本次内容就到此结束，感谢您的阅读！青山不改，绿水长流，我们月来客栈见！