机器学习十大经典算法之支持向量机

支持向量机Support Vector Machines

在分类问题中，除了线性的逻辑回归模型和非线性的深度神经网络外，我们还可以应用一种被广泛应用于工业界和学术界的模型——支持向量机（SVM），与逻辑回归和神经网络相比，支持向量机在学习复杂的非线性方程时提供了一种更为清晰，更加强大的方式。支持向量机相对于神经网络和逻辑回归，特别擅长于特征维数多于样本数的情况，而小样本学习至今仍是深度学习的一大难题。

SVM简介

支持向量机的数学定义：

支持向量机损失函数如下：

经过进一步简化，我们可以得到SVM中的损失函数：

这里

，去除了

，并不影响

这个目标的达成。

大间距的直观理解

有时候，人们会将把SVM叫做大间距分类器。我们先回顾一下支持向量机的模型定义：

我们的目标是最小化这个方程，下面我们结合图像说明最小化的过程：

参数C很大时

这里我们假设参数C很大，此时最小化方程式的重点放在左半部分，而可以"忽略"右边的

所以我们的优化目标主要放在让左边式子为0上。

• 1、当样本为正,y = 1,则根据

的函数图像，我们希望

,因为此时：

，我们可以使得方程最小化。

• 2、当样本为负时，即y = 0,则根据

函数图像，此时，我们希望

,因为此时：

不过，我们注意到，如果一个样本满足y = 1时，

即可使模型能将其准确分类，对于负样本y = 0同样只需要

即可。那么支持向量机里，追求的最优化方程究竟会带来什么？

我们将样本点x在坐标系中向量化表示,即x是一条从原点开始，指向(x1,x2)的矢量，x的模长 = x1^2 + x2^2，则我们可以得到一系列样本点坐标图，如下：

追求最优化方程究竟会带来什么？

会带来一条支持向量机的超平面，在二维方程中，超平面即一条直线，我们会得到一条直线，将样本点分割开来，且这条直线满足

即将这个表达式的值取到最小：

这里，在样本点中，我们可以划出一条满足支持向量机方程的直线：黑色线。这条划分样本点的线在SVM中也叫决策边界(SVM Decision Boundary)。这条黑线不仅满足数学表达式上的最小属性，从图像上看，黑色线也能满足和样本间的最大距离，这里的最大是指总体最大，这也是支持向量机被称为大间距分类器(Large margin classifier)的缘由。

当然，当样本上升到3维、4维、N维时，支持向量机就表示一个平面、多维超平面，而不仅仅是一条线。但是同样会满足大间距分类器这样的含义。即保持到样本点间的最大距离。

• 这里需要说明的是：决策边界可以划出n条，如图中的粉色、绿色、黑色.....但满足最小化方程式的值的边界只有一条，这条边界被称为支持向量机。

参数C较小时

当然，我们上面都是基于假设参数C很大时的情况，那如果C不是很大时，我们就不仅仅要考虑方程式中左边的项，还需要同步考虑右边项了。

下面我们再看一个例子：

当C很大时，我们的支持向量机画出了一条决策边界：

此时，又新增一个样本点(位于图中左下角靠近原点)，那么为了继续满足支持向量机方程式的定义，我们的决策边界变更了，如图中的粉线：

但是，需要注意，仅仅由一个样本点导致的决策边界发生大幅改变，是不明智的。此时我可以将原本很大的C变小，这样，我们考虑的就不仅仅是左边的。

因为C很小的化，这个式子的乘积就会变得较小，对于整个方程式的最小化影响会降低，这时，支持向量机的决策边界就会忽略掉一些异常点影响，即决策界还是会保持在黑线上，而不会划出粉线。因为支持向量机要保证的是总体方程式最小化。

关于参数C

回顾之前的表达式可知，参数_C = 1/λ_ 当C较大时，对应λ较小，即正则化参数较小，可能会导致过拟合，和支持向量机的高方差；当C较小时，对应λ较大，可能导致欠拟合(拟合不够)，和支持向量机的高偏差。

大间距的数学原理

向量内积

为了方便举例，此处以二维向量举例。u、v都是二维向量，它们的内积：

内积的含义在哪里？图中我们可以用投影和范数(在欧几里得范数中即 = 模长)来表示：

用文字表示：u和v的内积 = 向量v在向量u上的投影乘以向量向量u的范数（或者反过来表示也一样）

这里需要注意，如图中的第二个图所展示的：当向量u和v角度>90°时，p值为负。

SVM的数学原理

之前支持向量机的方程，写作：

在数学里面[s.t.]是subject to 的缩写，意为：使得...满足。

这里，为了方便说明，简化一下令

。此时

此时

、

可以看作是向量

的两个分量，则有：

对于

和

可以将其看作是

和

的内积，P表示

在

上的投影，则向量关系示意图如下：

整个表达式可以转化为如下形式：

7.png

这时再看一个例子：

左图种的绿线是支持向量机的一种决策边界，我们称为A，右图的绿线是另一种决策边界B，支持向量机会更倾向于选择哪种决策边界呢？答案是B。

因为根据公式，支持向量机需要最小化θ的范数，即

取到最小。

为了满足

的条件，当||θ||取值越小时，向量机希望

越大，即

在

上的投影越大。且

和绿色的决策边界垂直，很明显可以看出，当决策边界为B时，投影越大，即

足够大，我们可以取到更小的

。

核函数

回顾我们之前讨论过可以使用高级数的多项式模型来解决无法用直线进行分隔的分类问题:

为了获取上图中的决策边界，我们的假设函数可能是：

的形式，为了方便，我们可以用一系列新的特征值来替换模型中的每一项，譬如：

则假设函数便可以转化为：

这种方法即通过多项式模型的方式构造新特征

，那么有没有其他方式来构造新特征？有，通过核函数即可完成。

为了构造新的特征

我们引入地标（landmark)

,我们可以通过判断样本x和地标间的近似程度来选取新的特征

如上图所示，特征

都可以用similarity(x,l)函数来获取，这里的similarity(x,l)函数即被称为—核函数（kernel function）,在本例中我们用核函数中的一种—高斯核函数来举例，即：

地标的作用是什么 ？如果一个样本x距离地标距离接近/等于0，则

,否则 = 0，于是我们利用样本和地标间的关系来得出了特征f的值。

landmark和𝜎

l和

会对模型和特征f有什么影响？我们看一个例子：

这里取地标为固定向量，三组不同的

看图，可以总结出几点：

• 1、红色顶点处，即向量

和向量地标向量

重合处，即距离= 0，故此时

。

• 2、可以看见

越大，图像越宽，同样的x样本向量，譬如

这个样本在图1中就会被判定为

，而在图3中则可能被判定为

，即

会影响到最终特征值f的判断。即随着𝑥的改变𝑓值改变的速率受到𝜎的控制。

决策边界

假定：假设函数值>=0时预测y = 1,否则y = 0，则通过上面的高斯核函数我们可以算出每个样本点x距离地标l的距离，从而算出每个特征f，从而求出每个样本点的预测值y，即可以正确给每个样本分类，从而得到一条决策边界。

屏幕快照 2019-07-22 23.16.26.png

例如：

对于红色点x，由于其距离地标l1较近，故f1 = 1,同时其距离l2和l3较远，故f2 = f3 = 0，假设函数值= -0.5+1 = 0.5>0故预测其y = 1；

对于绿色点x,f2 = 1 ,假设函数值 = -0.5+0+1+0 =0.5故其预测也为1

可以看出此例中存在一条决策边界，如红线划出的范围，在边界以内的样本都是预测y = 1，边界外的都是y = 0。

核函数2

上一个例子，比较简单地说明了核函数的应用，但是实际情况下，核函数怎么使用呢？landmark又如何选取？

实际情况下，我们会选取和样本点数量同样多的且值相同的landmark？

和之前的一样，如果我们有m个样本，就能得到m+1个特征矩阵f(加了一项f0作为bias)

得到新的特征后，我们可以写出代价函数的表达式：

这里可以看到

替代了原来的

,因为f是计算出来的用于模拟x的特征值。最后一项

实际上的n-可以替换成m，因为这里特征值只有m个。然后，在实际计算的时候，

我们会在之间加一个矩阵M，不同的核函数，M不同，目的在于优化计算和迭代速度。所以最终，正则化项应该是：

在此，我们不介绍最小化支持向量机的代价函数的方法，你可以使用现有的软件包(如liblinear,libsvm 等)。在使用这些软件包最小化我们的代价函数之前，我们通常需要编写核函数，并且如果我们使用高斯核函数，那么在使用之前进行特征缩放是非常必要的。

另外，支持向量机也可以不使用核函数，不使用核函数又称为线性核函数(linear kernel)， 当我们不采用非常复杂的函数，或者我们的训练集特征非常多而实例非常少的时候，可以采用这种不带核函数的支持向量机。

代码实现

下面代码是用SVM支持向量机对Minist进行分类：

https://github.com/ksopyla/svm_mnist_digit_classification

参考文献

《机器学习》周志华

https://zhuanlan.zhihu.com/p/74764135