SVM解读(1)

​ 支持向量机(SVM)是机器学习中获得关注最多的算法。它是我们除了集成算法之外，接触的第一个强学习器。从学术的角度看，SVM是最接近深度学习的机器学习方法。

sklearn中的支持向量机

注意，除了特别表明是线性的两个类LinearSVC和LinearSVR之外，其他的所有类都是同时支持线性和非线性的。NuSVC和NuSVC可以手动调节支持向量的数目，其他参数都与最常用的SVC和SVR一致。注意OneClassSVM是无监督的类。
除了本身所带的类之外，sklearn还提供了直接调用libsvm库的几个函数。libsvm是一个简单、易于使用和快速有效的英文的SVM库。

SVM原理解读

支持向量机原理的三层理解：

第一层理解

支持向量机所做的事情其实非常容易理解，看下图：

上图是一组两种标签的数据，两种标签分别用圆和方块代表。支持向量机的分类方法，是在这组分布中找出一个超平面作为决策边界，使模型在数据上的分类误差尽量接近于小，尤其是在位置数据集上的分类误差(泛化误差)尽量小。

关键概念：

​ 超平面：在几何中，超平面是一个空间的子空间，它是维度比所在空间小一维的空间。 如果数据空间本身是三维的， 则其超平面是二维平面，而如果数据空间本身是二维的，则其超平面是一维的直线。

​ 决策边界：在二分类问题中，如果一个超平面能够将数据划分为两个集合，其中每个集合中包含单独的一个类别，我们就 说这个超平面是数据的“决策边界”。

决策边界一侧的所有点在分类为属于一个类，而另一个类的所有店分类属于另一个类。比如上面的数据集，我们很容易的在方块和圆的中间画一条线并让所有落在直线左边的样本被分类为方块，在直线右边的样本被分类为圆。如果把数据当作我们的训练集，只要直线的一边只有一种类型的数据，就没有分类错误，我们的训练误差就会为0。 所以，对于一个数据集来说，让训练误差为0的决策边界可以有无数条。

但在此基础上，我们无法保证这条决策边界在未知数据集（测试集）上的表现也会优秀。对于现有的数据集来说， 我们有B1和B2两条可能的决策边界。我们可以把决策边界B1向两边平移，直到碰到离这条决策边界最近的方块和圆圈后停下，形成两个新的超平面，分别是b11和b12，并且我们将原始的决策边界移动到b11和b12的中间，确保B1到b11和b12的距离相等。在b11和b12中间的距离，叫做 这条决策边界的边际(margin)，通常记作d。对B2也执行同样的操作，然后我们来对比一下两个决策边界。现在两条决策边界右边的数据都被判断为圆，左边的数据都被判断为方块，两条决策边界在现在的数据集上的训练误差都是0，没有一个样本被分错。

接着我们引入和原本的数据集相同分布的测试样本（红色所示），平面中的样本变多了，此时我们可以发现，对于B1而言，依然没有一个样本被分错，这条决策边界上的泛化误差也是0。但是对于B2而言，却有三个方块被误认成了圆，有两个圆被误分类成了方块，这条决策边界上的泛化误差就远远大于B1了。这个例子表现出，拥有更大边际的决策边界在分类中的泛化误差更小，这一点可以由结构风险最小化定律来证明（SRM）。如果边际很小，则任何轻微扰动都会对决策边界的分类产生很大的影响。边际很小的情况，是一种模型在训练集上表现很好，却在测试集上表现糟糕的情况，所以会“过拟合”。所以我们在找寻决策边界的时候，希望边际越大越好。

结论：支持向量机，就是通过找出边际最多的决策边界，来对数据进行分类的分类器。

我们让所有紫色点的标签为1，红色点的标签为-1。我们要在这个数据集上寻找一个决策边界，在二维平面上，决 策边界（超平面）就是一条直线。二维平面上的任意一条线可以被表示为：

我们将此表达式变换一下：

其中[a, -1]就是我们的参数向量 ， 就是我们的特征向量， 是我们的截距。

我们要求解参数向量w和截距b 。如果在决策边界上任意取两个点Xa，Xb，并带入决策边界的表达式，则有：

将两式相减，得：

Xa和Xb是一条直线上的两个点，相减后的得到的向量方向是由Xb指向Xa，所以Xa-Xb的方向是平行于他们所在的直线——我们的决策边界的。而w与Xa-Xb相互垂直，所以参数向量w方向必然是垂直于我们的决策边界。

此时，我们有了我们得决策边界，任意一个紫色得点Xp就可以表示为：

由于紫色的点所代表的标签y是1，所以我们规定，p>0。

同样的，对于任意一个红色的点Xr而言，我们可以将它表示为：

由于红色点所表示的标签y是-1，所以我们规定，r<0

由上面得知：如果我们有新的测试数据Xt，则Xt的标签就可以根据以下式子来判定：

注意：p和r的符号是我们人为规定的

两类数据中距离我们的决策边界 最近的点，这些点就被称为支持向量。

紫色类的点为Xp ，红色类的点为Xr，则我们可以得到：

两个式子相减，得：

如下图所示： (Xp-Xr)可表示为两点之间的连线，而我们的边际d是平行于w的，所以我们现在，相当于是得到 了三角型中的斜边，并且知道一条直角边的方向。在线性代数中，向量有这样的性质：向量a除以向量b的模长||b|| ，可以得到向量a在向量b的方向上的投影的长度。所以，我们另上述式子两边同时除以||w||，则可以得到

最大边界所对应的决策边界，那问题就简单了，要最大化d，就求解w的最小值。极值问题可以相互转化，我们可以把求解w的最小值转化为，求解以下函数的最小值：

之所以要在模长上加上平方，是因为模长的本质是一个距离，所以它是一个带根号的存在，我们对它取平方，是为了消除根号。

我们得到我们SVM的损失函数：

至此，SVM的第一层理解就完成了。

关键概念：函数间隔与几何间隔

对于给定的数据集T和超平面(ω,b),定义超平面(ω,b)关于样本点(x_i,y_i)的函数间隔为：

这其实是我们的虚线超平面的表达式整理过后得到的式子。函数间隔可以表示分类预测的正确性以及确信度。再在这个函数间隔的基础上除以ω的模长||ω||来得到几何间隔：

几何间隔的本质其实是点x_i到超平面(ω,b)，即到我们的决策边界的带符号的距离(signed distance)。

第二层理解

用拉格朗日对偶函数求解线性SVM

有了我们的损失函数以后，我们就需要对损失函数进行求解。我们之前得到了线性SVM损失函数的最初形态。

这个损失函数分为两部分：需要最小化的函数，以及参数求解后必须满足的约束条件。这是一个最优化问题。

为什么要进行转换？

我们的目标是求解让损失函数最小化的ω,但其实很容易看的出来，如果||ω||为0，f(ω)必然最小了。但是，||ω||=0其实是一个无效的值，原因很简单：首先，我们的决策边界是ωx+b=0，如果ω为0，则这个向量的所有元素都为0，那就有b=0这个唯一值。如果b和ω都为0，决策边界就不在是一条直线了，函数间隔y_i(ω\x_i+b)就会为0，条件中的y(ω*x_i+b)>=1就不可能实现，所有ω不可以是一个0向量。可见，单纯让f(ω)为0，是不能求解出合理的ω的。我们希望能够能够找出一种方式，能够让我们的条件y_i(ω*x_i+b)>=1在计算中也被纳入考虑，其中一种方法就是使用拉格朗日乘数法。

为什么可以进行转换？

我们的损失函数是二次的(quadratic)，并且我们损失函数中的约束条件在参数ω和b下是线性的，求解这样的损失函数被称为“凸优化问题”(convex optimization problem)。拉格朗日乘数法正好可以用来解决凸优化问题，这种方法也是业界常用的，用来解决带约束条件，尤其是带有不等式的约束条件的函数的数学方法。首先第一步，我们需要使用拉格朗日乘数来将损失函数改写为考虑了约束条件的形式：

上面被称为拉格朗日函数。其中α_i就叫做拉格朗日乘数。此时此刻，我们要求解的就不只有参数向量ω和截距b了，我们也要求拉格朗日乘数α，而我们的x_i和y_i都是我们已知的特征矩阵和标签。

怎么进行转换？

拉格朗日函数也分为两部分。第一部分和我们原始的损失函数一样，第二部分呈现了我们带有不等式的约束条件。我们希望，L(ω,b,α)不仅能够代表我们原有的损失函数f(ω)和约束条件。还能够表示我们想要最小化损失函数来求解ω和b的意图，所以我们要先以α为参数，L(ω,b,α)的最大值，再以ω和b为参数，求解L(ω,b,α)的最小值。因此，我们的目标可以写作：

首先，我们先执行max，即最大化L(ω,b,α)，那就有两种情况：

若把函数第二部分当作一个惩罚项来看待，则y_i(ω*x_i+b)大于1时函数没有收到惩罚。而y_i(ω*x_i+b)小于1时函数受到极致的惩罚，即加上一个正无穷项，函数整体永远不可能渠道最小值。所以第二部，我们执行min的命令，求解函数整体的最小值，我们就永远不能让α必须取到正无穷的状况出现，即是说永远不让y_i(ω*x_i+b)<1的状况出现。从而实现了求解最小值的同时让约束条件满足。现在，L(ω,b,α)就是我们新的损失函数。我们的目标时通过先最大化，再最小化它来求解参数向量ω和截距b的值。

拉格朗日函数转换为拉格朗日对偶函数

为什么要进行转换？

要求极值，最简单的方法还是对参数求导后让一阶导数等于0。我们先来试试看对拉格朗日函数求极值，在这里我
们对参数向量ω和截距b分别求偏导并且让他们等于0。 求导过程如下：

由于两个求偏导结果中都带有未知的拉格朗日乘数α_i，因此我们还是无法求解出ω和b，我们必须想出一种方法来求解拉格朗日乘数α_i。幸运地是，拉格朗日函数可以被转换成一种只带有α_i，而不带有ω和b的形式，这种形式被称为拉格朗日对偶函数。在对偶函数下，我们就可以求解出拉格朗日乘数α_i，然后带入到上面推导出的(1)和(2)式中来求解ω和b。

为什么能够进行转换？

对于任何一个拉格朗日函数，都存在一个与它对于的对偶函数g(α)，只带有拉格朗日乘数α作为唯一的参数。如果L(x,a)的最优解存在并可以表示为min L(x,a)，并且对偶函数的最优解也存在并可以表示为max g(α)，则可以定义对偶差异。即拉格朗日函数的最优解与其对偶函数的最优解之间的差值：

如果$\Delta$=0，则称L(x,α)与其对偶函数之间存在强对偶关系(strong duality property)，此时我们就可以通过求解其对偶函数的最优解来替代求解原始函数的最优解。 那强对偶关系上面时候存在呢？那就是这个拉格朗日函数必须满足KTT(Karush-Kuhn-Tucker)条件：

这里的条件其实都比较好理解。首先是所有参数的一阶导数必须为0，然后约束条件中的函数本身需要小于等于0，拉格朗日乘数需要大于等于0，以及约束条件乘以拉格朗日乘数必须等于0，即不同i的取值下，两者之中至少有一个为0。当所有限制都被满足，则拉格朗日函数L(x,α)的最优解与其对偶函数的最优解相等，我们就可以将原始的最优化问题转换成为对偶函数的最优化问题。而不难注意到，对于我们的损失函数L(α,b,α)而言，KTT条件都是可以操作的。如果我们能够人为让KTT条件全部成立，我们就可以求解出L(ω,b,α)的对偶函数来解出α。

之前我们已经让拉格朗日函数上对参数ω和b的求导为0，得到了式子：

并且在我们的函数中，我们通过先求解最大值再求解最小值的方法使得函数天然满足：

接下来，我们只需要再满足一个条件：

这个条件其实很容易满足，能够让y_i(ω*x_i+b)-1=0的就是落在虚线的超平面上的样本点，即我们的支持向量。所有不是支持向量的样本点则必须满足α_i=0。满足这个式子说明了，我们求解的参数ω和b以及求解的超平面的存在，只与支持向量相关，与其他样本点无关。五个条件满足后，就可以使用L(ω,b,α)的对偶函数来求解α了。

怎么进行转换？

首先让拉格朗日函数对参数ω和b求导后的结果为0，本质时再探索拉格朗日函数的最小值。然后：

这个L_d就是我们的对偶函数。对所有存在对偶函数的拉格朗日函数我们有对偶差异如下：

则对于我们的L(ω,b,α)和L_d，我们则有：

我们推到L_d的第一步是对L(ω,b,α)求偏导并让偏导数都为0。所有我们求解对偶函数的过程其实是在求解L(ω,b,α)的最小值。所以我们又可以把公式写成：

如此，我们只需要求解对偶函数的最大值，就可以求出α了。最终，我们的目标函数变化为：

求解拉格朗日对偶函数

到了这一步，我们就需要使用梯度下降，smo或者二次规划(QP，quadratic programming)来求解α。由于数学太难且我的数学也是太差，我不看了也就不讲了，头都要秃了。大家只需要知道，一但我们求得了α值，我们就可以使用求导后得到的(1)式求解ω，并可以使用(1)式子和决策边界的表达式结合，得到下面的式子来求解b：

当求得特征向量ω和b，我们就得到了我们的决策边界的表达式。也就可以利用决策边界和其有关的超平面来进行分类，我们的决策函数就可以写作：

其中x_test是任意测试样本，sign(h)是h>0时返回-1的符号函数。到这里，我们也就完成了对SVM的第二层理解的大部分内容，我们了解了线性SVM的四种相关函数：损失函数的初始形态、拉格朗日函数、拉格朗日对偶函数以及最后的决策函数。

第三层理解

熟练以上的推导过程，就是我们的第三层理解。

线性SVM决策过程的可视化

我们可以使用sklearn的式子来可视化我们的决策边界、支持向量、以及决策边界平行的两个超平面。

画决策边界的函数：contour

contour是专门用来画等高线的函数。等高线，本质上是在二维图像表现三维图像的一种形式，其中两维X和Y是两条坐标轴上的取值，而Z表示高度。Contour就是将由X和Y构成平面上的所有点中，高度一致的点连接成线段的函数，在同一条等高线上的点一定具有相同的Z值。我们可以利用这个性质来绘制我们的决策边界。

回忆一下，我们的决策边界是ω*x+b=0，并在决策边界的两边找出两个超平面，使得超平面到决策边界的相对距离为1。那其实，我们只需要在我们的样本构成的平面上，把所有到决策边界的距离为0的点相连，就是我们的决策边界，而把所有到决策边界的相对距离为1的点相连，就是我们的两个平行于决策边界的超平面了。此时，我们的Z就是平面上的任意点到达超平面的距离。
那首先，我们需要获取样本构成的平面，作为一个对象。

from sklearn.datasets import make_blobs
from sklearn.svm import SVC
import matplotlib.pyplot as plt
import numpy as np
X,y = make_blobs(n_samples=50, centers=2, random_state=0,cluster_std=0.6)
plt.scatter(X[:,0],X[:,1],c=y,s=50,cmap="rainbow")
plt.xticks([])
plt.yticks([])
#制作数据的散点图
plt.show()
def plot_svc_decision_function(model,ax=None):
#获取当前的子图，如果没有，就创建    
    if ax is None:
        ax = plt.gca()
#获取x轴的最小最大值
    xlim = ax.get_xlim()
#获取y轴的最小最大值
    ylim = ax.get_ylim()
#在两个最小最大值间生成30个值
    x = np.linspace(xlim[0],xlim[1],30)
    y = np.linspace(ylim[0],ylim[1],30)
#使用meshgrid函数将两个一维向量转换为特征矩阵
    Y,X = np.meshgrid(y,x)
#列合并numpy 
    xy = np.vstack([X.ravel(), Y.ravel()]).T
#decision_function是一个重要接口，返回每个输入的样本所对应到决策边界的距离，
#P的本质是输入的样本到决策边界的距离，而contour函数中的level其实是输入了这个距离
    P = model.decision_function(xy).reshape(X.shape)
    ax.contour(X, Y, P,colors="k",levels=[-1,0,1],alpha=0.5,linestyles=["--","-","--"])
    ax.set_xlim(xlim)
    ax.set_ylim(ylim)
    plt.show()
clf = SVC(kernel = "linear").fit(X,y)
plt.scatter(X[:,0],X[:,1],c=y,s=50,cmap="rainbow")
plot_svc_decision_function(clf)
print("预测值：",clf.predict(X))
print("准确度：",clf.score(X,y))
print("返回支持向量：",clf.support_vectors_)
print("返回每个类中支持向量的个数：",clf.n_support_)

那如果推广到非线性数据上呢，比如环形数据

from sklearn.datasets import make_circles
X,y = make_circles(100, factor=0.1, noise=.1)
plt.scatter(X[:,0],X[:,1],c=y,s=50,cmap="rainbow")
plt.show()
clf = SVC(kernel = "linear").fit(X,y)
plt.scatter(X[:,0],X[:,1],c=y,s=50,cmap="rainbow")
plot_svc_decision_function(clf)

运行代码后看效果图，很明显，现在线性SVM已经不适合于我们的状况了，我们无法找出一条直线来划分我们的数据集，让直线的两边分别是两种类别。这个时候，如果我们能够在原本的X和y的基础上，添加一个维度r，变成三维，我们可视化这个数据，来看看添加维度让我们的数据如何变化。

#即使下面的代码没有看出来用了这个模块，但是必须要引入
from mpl_toolkits import mplot3d
#定义一个绘制三维图像的函数
#elev表示上下旋转的角度
#azim表示平行旋转的角度
def plot_3D(elev=30,azim=30,X=X,y=y):
    ax = plt.subplot(projection="3d")
    ax.scatter3D(X[:,0],X[:,1],r,c=y,s=50,cmap='rainbow')
    ax.view_init(elev=elev,azim=azim)
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.set_zlabel("r")
    plt.show()
plot_3D()

可以看见，此时此刻我们的数据明显是线性可分的了：我们可以使用一个平面来将数据完全分开，并使平面的上方的所有数据点为一类，平面下方的所有数据点为另一类。此时我们的数据在三维空间中，我们的超平面就是一个二维平面。明显我们可以用一个平面将两类数据隔开，这个平面就是我们的决策边界了。我们刚才做的，计算r，并将r作为数据的第三维度来将数据升维的过程，被称为“核变换”，即是将数据投影到高维空间中，以寻找能够将数据完美分割的超平面，即是说寻找能够让数据线性可分的高维空间。为了详细解释这个过程，我们需要引入SVM中的核心概念：核函数

后续内容请看SVM解读(2)](https://brickexperts.github.io/2019/09/15/SVM%E8%A7%A3%E8%AF%BB(2)/#more/#more)