机器学习之支持向量机的详细版_支持向量机如何训练

目录

一、函数间隔与几何间隔

在正式介绍SVM的模型和损失函数之前，我们还需要先了解下函数间隔和几何间隔的知识。

在分离超平面固定为
的时候，
表示点X到超平面的距离，通过观察
和y是否同号，我们判断分类是否正确，这些知识在感知机模型里有。这里我们引入函数间隔的概念，定义函数间隔r为：

可以看到，它就是感知机模型里面的误分类点到超平面距离的分子。对于训练集中m个样本点对应的m个函数间隔的最小值，就是整个训练集的函数间隔。

函数间隔并不能正常反应点到超平面的距离，在感知机模型里我们也提到，当分子成比例的增长时，分母也是成倍增长。为了统一度量，我们需要对法向量w加上约束条件，这样我们就得到了几何间隔r,定义为：

几何间隔才是点到超平面的真正距离，感知机模型里用到的距离就是几何距离。

二、支持向量

在感知机模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都离超平面远。但是实际上离超平面很远的点已经被正确分类，我们让它离超平面更远并没有意义。反而我们最关心是那些离超平面很近的点，这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面，那么我们的分类效果会好有一些。SVM的思想起源正起于此。

如下图所示，分离超平面为w^{T}x+b=0，如果所有的样本不光可以被超平面分开，还和超平面保持一定的函数距离（下图函数距离为1），那么这样的分类超平面是比感知机的分类超平面优的。可以证明，这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。

支持向量到超平面的距离为L:

,两个支持向量之间的距离为2L。

三、SVM模型目标函数与优化

SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为：

对于这个式子，我们从SVM的思想入手，找到离超平面最近的点，使它的几何间隔最大，即：

在数学上，我们总可以通过等比例的缩放w,b，来使得函数间隔:

则有目标函数：

约束条件：

建立新的目标函数：

首先我们来求L(w,b,α)基于w和b的极小值，这个极值我们可以通过对w和b分别求偏导数得到：

从上两式子可以看出，我们已经求得了w和α的关系，只要我们后面接着能够求出优化函数极大化对应的α，就可以求出我们的w了，至于b，由于上两式已经没有b，所以最后的b可以有多个。

带入优化函数L(w,b,α)消去w了。我们定义:

现在我们来看将w替换为α的表达式以后的优化函数L(w,b,a)的表达式：

（9）式到(10)式使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法运算法则

  从上面可以看出，通过对w,b极小化以后，我们的优化函数L(w,b,a))仅仅只有α向量做参数。只要我们能够极大化L(w,b,a)，就可以求出此时对应的α，进而求出w,b.
1

对L(w,b,a)求极大化的数学表达式如下：

等价的极小化问题如下(整理目标函数，添加负号）：

只要我们可以求出上式极小化时对应的α向量就可以求出w和b了。具体怎么极小化上式得到对应的α，一般需要用到SMO算法，这个算法比较复杂，后面来讲。在这里，我们假设通过SMO算法，我们得到了对应的α的值α∗。

那么我们根据：
既可以求出对应的w的值。
求b则稍微麻烦一点。注意到，对于任意支持向量(x,y)，都有

假设我们有S个支持向量，则对应我们求出S个b∗,理论上这些b∗都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的b_{s}^{*}，然后将其平均值作为最后的结果。注意到对于严格线性可分的SVM，b的值是有唯一解的，也就是这里求出的所有b∗都是一样的，这里我们仍然这么写是为了和后面加入软间隔后的SVM的算法描述一致。

怎么得到支持向量呢？根据KKT条件中的对偶互补条件

如果αi>0则有
即点在支持向量上，否则如果αi=0则有
上式>=1,则样本在支持向量上或者已经被正确分类。

四、线性可分支持向量机学习算法过程

计算：

求得分离超平面：

分类决策函数：

举例：
如下图所示：

给定三个数据点：正例点X1=(3,3)T，X2=（4，3）T ，负例点X3=（1，1）T，求线性可支持向量机。
1、目标函数：

2、将约束带入目标函数，化简计算：

分离超平面：

五、线性SVM的软间隔最大化

线性可分SVM的学习方法对于非线性的数据集是没有办法使用的， 有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分， 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢？

如何解决这些问题呢？SVM引入了软间隔最大化的方法来解决。

回顾下硬间隔最大化的条件：

SVM对训练集里面的每个样本(xi,yi)引入了一个松弛变量ξi≥0,使函数间隔加上松弛变量大于等于1，也就是说(注意：这里的ξi本身就是一个函数间隔)：

对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量ξi, 对应了一个代价ξi，这个就得到了我们的软间隔最大化的SVM学习条件如下：

约束条件：

目标函数：
线性SVM的目标函数：

这里,C>0为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。

     也就是说，我们希望尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。
1

六、线性SVM软间隔最大化目标函数的优化

和线性可分SVM的优化方式类似，我们首先将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题如下：
对w,b,ξ求偏导：

好了，我们可以利用上面的三个式子去消除w和b了。

仔细观察可以发现，这个式子和我们上面线性可分SVM的一样。唯一不一样的是约束条件。现在我们看看我们的优化目标的数学形式：

最终得到目标函数：

整理，得到对偶问题：

就是软间隔最大化时的线性可分SVM的优化目标形式，和上面的硬间隔最大化的线性可分SVM相比，我们仅仅是多了一个约束条件0≤αi≤C。我们依然可以通过SMO算法来求上式极小化时对应的α向量就可以求出w和b了。

七、软间隔最大化时的支持向量

计算：

注意：

计算b时，需要使用满足条件的0<@<C 的向量
实践中往往取支持向量的所有值取平均数，作为b

求得超平面:
分类决策函数：

八、合页损失函数

损失函数分析：

Code:

核函数的引入

上一节我们讲到线性不可分的低维特征数据，我们可以将其映射到高维，就能线性可分。现在我们将它运用到我们的SVM的算法上。回顾线性可分SVM的优化目标函数：

注意到上式低维特征仅仅以内积x_{i}\cdot x_{j}的形式出现，如果我们定义一个低维特征空间到高维特征空间的映射ϕ（比如上面的例子就是从2维到5维的映射），将所有特征映射到一个更高的维度，让数据线性可分，我们就可以继续按前面的方法来优化目标函数，求出分离超平面和分类决策函数了。也就是说现在的SVM的优化目标函数变成：

       可以看到，和线性可分SVM的优化目标函数的区别仅仅是将内积x_{i}\cdot x_{j}替换为\phi (x_{i})\cdot \phi (x_{j})。

    看起来似乎这样我们就已经完美解决了线性不可分SVM的问题了，但是事实是不是这样呢？我们看看，假如是一个2维特征的数据，我们可以将其映射到5维来做特征的内积，如果原始空间是三维，可以映射到到19维空间，似乎还可以处理。但是如果我们的低维特征是100个维度，1000个维度呢？那么我们要将其映射到超级高的维度来计算特征的内积。这时候映射成的高维维度是爆炸性增长的，这个计算量实在是太大了，而且如果遇到无穷维的情况，就根本无从计算了。
1
2
3

好吧，核函数该隆重出场了！

假设ϕ是一个从低维的输入空间χ（欧式空间的子集或者离散集合）到高维的希尔伯特空间的H映射。那么如果存在函数K(x,z)，对于任意x,z∈χ，都有：K(x,z)=ϕ(x)∙ϕ(z),我们就称K(x,z)为核函数。

核函数的理解：

从上面的式子乍一看还是不明白核函数怎么帮我们解决线性不可分的问题的。仔细观察上式可以发现，K(x,z)的计算是在低维特征空间来计算的，它避免了在刚才我们提到了在高维维度空间计算内积的恐怖计算量。也就是说，我们可以好好享受在高维特征空间线性可分的结果，却避免了高维特征空间恐怖的内积计算量。

我们遇到线性不可分的样例时，常用做法是把样例特征映射到高维空间中去(如上面的多项式回归）但是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到令人恐怖的。此时，核函数就体现出它的价值了，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数好在它在低维上进行计算，而将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM线性不可分的问题。

核函数的定理有一个复杂的数学推导过程，这里不做过多的叙述，感兴趣的可以参考下李航老师的《统计学习方法》。

下面我们来看看常见的核函数, 选择这几个核函数介绍是因为scikit-learn中默认可选的就是下面几个核函数。

线性核函数

线性核函数（Linear Kernel）其实就是我们前面的线性可分SVM，表达式为：

也就是说，线性可分SVM我们可以和线性不可分SVM归为一类，区别仅仅在于线性可分SVM用的是线性核函数。

多项式核函数

多项式核函数（Polynomial Kernel）是线性不可分SVM常用的核函数之一，表达式为：

高斯核函数RBF:

高斯核函数（Gaussian Kernel），在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是非线性分类SVM最主流的核函数。libsvm默认的核函数就是它。表达式为：
Sigmoid函数：

Sigmoid核函数（Sigmoid Kernel）也是线性不可分SVM常用的核函数之一，表达式为：

核函数映射：

高斯核：

1、粗线时分割超“平面”
2、其他线时y的等高线
3、绿色圈点时支持向量点

高斯核的分类效果：

code

def kernel(x1,x2):
	n = len(x2) - 1
	s = 0
	if kn ==0 ：
		for i in range(n):
			s += x1[i] * x2[i]
		return s
	for i in range(n):
		s += （x1[i] - x2[i]）**2
	k = math.exp(-s/(2*sigma**2))
	return k
1
2
3
4
5
6
7
8
9
10
11

SVM的中的系数的求解：SMO

1、序列最小最优化
考察目标函数，假设a1和a2是变量，其他是定值。


二变量优化问题：

SMO的迭代公式：

退出条件：

九、SVM总结

1、SVM的空间消耗主要是存储训练样本和核矩阵。

2、时间消耗《A Tutorial on Support Vector Machines for Pattern Recognition》 1998KluwerAcademicPublishers,Boston，训练计算复杂度在O(Nsv^3+LNsv2+dLNsv)和O(d*L^2)之间，其中Nsv是支持向量的个数，L是训练集样本的个数，d是每个样本的维数(原始的维数，没有经过向高维空间映射之前的维数)

优点：

1、使用核函数可以向高维空间进行映射
2、使用核函数可以解决非线性的分类
3、分类思想很简单，就是将样本与决策面的间隔最大化
4、分类效果较好

缺点：

1、
SVM算法对大规模训练样本难以实施，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。

针对这个问题的主要改进有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM

2、 用SVM解决多分类问题存在困难，法直接支持多分类，但是可以使用间接的方法来做

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有：

一对多组合模式、一对一组合模式和SVM决策树；通过构造多个分类器的组合来解决。

其他观点：SVM在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目前最常用，效果最好的分类器之一，在于其优秀的泛化能力，这是是因为其本身的优化目标是结构化风险最小，而不是经验风险最小，因此，通过margin的概念，得到对数据分布的结构化描述，因此减低了对数据规模和数据分布的要求。SVM也并不是在任何场景都比其他算法好，对于每种应用，最好尝试多种算法，然后评估结果。如SVM在邮件分类上，还不如逻辑回归、KNN、bayes的效果好。

最后感谢读者给小编一点❤❤❤