[关闭]
@Duanxx 2016-07-31T09:01:56.000000Z 字数 36240 阅读 7539

支持向量机(SVM)

监督学习


@author : duanxxnj@163.com
@time : 2016-07-31


在看这篇文章之间,建议先看一下感知机,这样可以更好的看懂SVM。



一、最大间隔分类器

在之前的文章感知机中提到过,感知机模型对应于特征空间中将实例划分为正负两类的分离超平面,但是,感知机的解却不止一个。对同一个数据集而言,可以计算得到很多的感知机模型,不同的感知机的 训练误差 都是一样的,都为0。

那么,这些训练误差都为0的感知机模型中,如何针对当前数据集,选择一个最好的感知机模型呢?现在就需要考虑模型的 泛化误差 了。即,在所有训练误差为0的感知机中,选择泛化误差最小的那个感知机,这就是SVM算法最初的目的。

基本的SVM(最大间隔分类器)是一种二分类模型,它是定义在特征空间上的间隔最大的线性分类器,间隔最大是SVM和感知机不同的地方,间隔最大化对应于泛化误差最小。


1.1 决策面

面对一个线性可分的二分类问题,将正负样本分开的超平面,称为决策面。

线性回归 模型一样,这里一般会使用一些特征函数,将输入空间映射到新的特征空间中,再进行计算。

这里 叫做激活函数,是线性模型的系数,一般被叫做偏置:

这里输出的取值为 ,即正负样本。这里的 仅仅是一个标号,代表正负样本,并不是具体的数值。如果感觉不喜欢,可以和Logistics Regression一样,使用也行。而且,可以使用主要也是因为这里是二分类问题,遇到多分类问题的时候,还得考虑其他的标号方式。

如果感觉这种表述方式不太习惯,可以考虑所有的,这样就和一般的书上的公式一致了。这种表达仅仅是我个人的喜好,式主要是为了强调,在实际问题中,输入空间一般不会作为模型的输入,而是要将输入空间通过一定的特征转换算法,转换到特征空间,最后在特征空间中做算法学习。而且,在实际问题中,各种算法基本上都是死的,但是,特征变换的这个过程却是活的,很多时候,决定一个实际问题能不能很好的解决,起着决定性的作用。举个简单的例子,比如Logistics Regression,数据最好要做归一化,如果数据不归一化,那么那些方差特别大的特征就会成为主特征,影响模型的计算,就可以做这个事情。再或者后面要降到的核函数问题,核函数SVM能解决非线性可分问题,主要也是基于使用 来做非线性特征变换。

作为一个决策面:
当样本的标号 的时候,该样本为正样本。如果样本被正确分类,那么
当样本的标号 的时候,该样本为负样本。如果样本被正确分类,那么

究竟什么是决策面?
答:决策面就是能够将正负样本分开的点的集合,比如上面的模型中,决策面的数学表达式为:,决策面就是这个式子的解集,所以,一般我们就直接用这个式子代表决策面了。可以看到,对于这个决策面的数学表达式而言, 的数值并不重要。比如,,后一个决策面的参数数值是前一个决策面数值的两倍,但这两个决策面的解是一样的,也就是说其得到的点集是一样的,那么这两个表达式所表示的就是同一个决策面。所以,这里我要强调一点,对于一个线性决策面而言,重要的不是 的取值,重要的是
比值比值决定了一个决策面的点集,也就决定了一个决策面。


1.2 最优决策面

对于线性可分的二分类问题而言,使用 感知机 算法,可以得到很多很多满足上述要求的决策面,比如下图中,就是可以将正负两类数据分开的两个决策面。
Perceptron_cant_choose.png-19.7kB

那么,在这些决策面中,哪个决策面,才是最优的决策面呢?首先,需要明确,上述的决策面,都是可以将训练样本正确分类的决策面,也就是说,上述决策面的 训练误差 都为0。要从这些训练误差都为0的模型中,选出一个最好的模型,很自然的,就需要考虑模型的 泛化误差

最大间隔分类器认为,决策面的泛化误差可以用训练样本集合中,离决策面最近的样本点到决策面的间隔(margin)来表示,离决策面最近的样本点,到决策面的间隔(margin)越大,那么,这个决策面的泛化误差就越小。直观的来讲,最优决策面差不多就是下面这幅图中,中间的那个决策面。

2.jpg-20.4kB


1.3 最小间隔

什么是间隔?
答:首先,要搞清楚是谁和谁的间隔,在这里指的是一个 训练样本点决策面 之间的间隔。

那么,间隔又如何定义的呢?
答:间隔,就是样本点到决策面之间的距离,由中学的知识就可以知道,一个样本点 到一个面 ,的距离为(这里可以直接认为是点到直线的距离):

但这个距离在数值上会存在正负的问题,由于样本点类别取值 ,所以样本点到决策面的间隔可以改为:

的时候,如果样本被正确分类, ,上述样本点到决策面的间隔 取正值
的时候,如果样本被正确分类, ,上述样本点到决策面的间隔 仍然取正值
这样,分类正确的样本点的间隔就永远是正的了。

显然,一旦决策面有了,那么训练集合中的每个样本点 到决策面都会有一间隔 。自此,就可以定义样本集合到决策面最小的间隔 为:

既然 是最小间隔,毫无疑问,对于任意一个样本点 而言:


1.4 最小间隔最大化

前面已经说了,要使用决策面在训练样本中的最小间隔 来表示决策面的训练误差:最小间隔 越大,那么其泛化误差就越小,模型就越好。而我们这里,就是在所有可选的决策中,找出其对应的最小间隔 最大的那个决策面,而决策面是用参数 定义的,所以,最小间隔最大化可以形式化为:

用优化理论的形式重写一下上面的式子,可以得到:

将上面的约束条件变一下型可得:

在前面已经提到过,对于一个决策面 而言, 重要的不是 的取值, 的所得到的的点集是一样的,即其决策面是一样的,这里真正重要的是 比值

比值,决定了一个决策面的点集,也就决定了一个决策面。

所以,只要有一个决策面,那么,唯一确定的是比值,但是, 具体的取值是可以改变的,只要 按比例改变,决策面就是确定不变的。

也就是说,比值比值不变的情况下,是可以任意取值的。这样的话,为了便于计算,我们就取:

那么,上面的式子又可以改写为:

可以看到,上面的式子最大化的目标函数变成了 ,很容易知道,其等价于 最小化 ,那么最小间隔最大化,最终就可以变为下面这个最小化的约束优化问题:

这里,最小间隔为:

在网上博客还有现有的书籍中,对于最小间隔最大化的解释,都使用了函数间隔和几何间隔的概念,我个人在第一次接触这两个概念的时候,就有些被弄糊涂了,理解了这两个概念之后,又感觉这种解释过于冗余、牵强,完全是为了解释最小间隔最大化而解释最小间隔最大化。所以,这里我直接抛弃函数间隔和几何间隔的概念,给出我个人的一种解释。

最小间隔最大化后得到的决策面,就是我们要找的泛化误差最小的决策面。对于下图中两特征的二分类问题而言,可以看出, 最小间隔为,即,正样本到决策面的最小间隔为;同时,负样本到决策面的最小间隔也为。所以正负样本之间的最小间隔为

Svm_max_sep_hyperplane_with_margin.png-41.8kB

由于间隔最小的样本点 满足:

所以,间隔最小的正样本点 满足:

间隔最小的负样本点 满足:

这里定义,拥有最小间隔的正负样本点为支持向量(support vector),也就是上图中 所对应的那三个样本点。

关于支持向量机的名字,这里可以稍微说一下,因为这个名字并不是特别的好理解。首先是支持(support),根据柯林斯词典,support的主要意思:the activity of providing for or maintaining by supplying with money or necessities,表示的是提供一些必须品的意思。vector指的就是样本点,这个问题不大。那么问题来了,为什么将间隔最小的那些样本点叫做support vector(或者可以直接说是support point)呢?答:从图中可以看出,对于决策面而言,要想唯一的确定这个决策面,就是要根据最小的间隔 来得到,也就是说,决策面仅仅和拥有最小间隔的那些样本点相关,和其他那些间隔大于最小间隔的样本点,是没有关系的。即:拥有最小间隔的那些样本点是决策面所必须的,而间隔大于最小间隔的样本点的有无,对决策面并不构成影响。所以将拥有最小间隔的那些样本点叫做support point, 也就是support vector。


1.5 拉格朗日对偶性

在求解约束最优化问题的过程中,我们常常会使用拉格朗日对偶性(Lagrange duality),把原始问题(primal problem)转换为对偶问题(dual problem)来求解,基于对偶问题的求解来得到原始问题的解。这个方法在统计学中经常使用,不仅仅本文的SVM算法用到了拉格朗日对偶性,后面要讲的最大熵模型也用到了拉格朗日对偶性。这里仅仅对拉格朗日对偶性做一个简述,我个人认为,主要知道其概念和结果即可,无需深究。拉格朗日对偶性的详细说明,可以参见Boyd的《Convex Optimization》,该书用一整个章节的篇幅来详细的论述了拉格朗日对偶性的问题。

对于一个线性规划问题,我们称之为原始问题,都有一个与之对应的线性规划问题我们称之为对偶问题。原始问题与对偶问题的解是对应的,得出一个问题的解,另一个问题的解也就得到了。并且原始问题与对偶问题在形式上存在很简单的对应关系:
- 目标函数对原始问题是极大化,对偶问题则是极小化
- 原始问题目标函数中的系数,是对偶问题约束不等式中的右端常数,而原始问题约束不等式中的右端常数,则是对偶问题中目标函数的系数
- 原始问题和对偶问题的约束不等式的符号方向相反
- 原始问题约束不等式系数矩阵转置后,即为对偶问题的约束不等式的系数矩阵
- 原始问题的约束方程数对应于对偶问题的变量数,而原始问题的变量数对应于对偶问题的约束方程数
- 对偶问题的对偶问题是原始问题

1、原始问题

假设,有,他们是定义在空间上的连续可微的函数,也就是可导函数的意思。其约束最优化问题为:

这里是不等式优化,而是等式优化。

上面这种约束优化问题的形式成为原始问题。

现在,引入拉格朗日函数:

这里 是拉格朗日乘子,且,。也就是说,不等式约束 的拉格朗日乘子要大于等于0,而等式约束 的拉格朗日乘子并没有限制。

现在考虑最大化这个拉格朗日函数,定义:

对于上面的最大化式子有:

综上所述,可以知道:

由于原始最优化问题就是要在满足约束条件下,求解最小化的。而由上可知,在满足约束条件的情况下,

也就是说,原始约束最优化问题:

中的 就可以用 来代替。

于是乎,原始约束最优化问题就变成了一个极小极大化的问题:

很显然,这个极小极大化问题,和原始问题是等价的。

为了方便,这里定义原始问题(primal problem)的最优解为:

2、对偶问题

对于一块磁铁而言,磁铁有N极和S极,N极和S极只是同一块磁铁的不同表现而已,这两个极性虽然不同,但是却拥有相同的本质:磁。他们是相辅相成的,是同一个事物的两种不同表现。就像有阴必有阳;有光明必有黑暗;而阴阳本为一体,明暗实为一物,他们都是同一个东西的不同表现而已,这个是世间万物的规律。

对偶问题和原始问题也是一样,他们是优化问题的两个不同表现形式而已,他们本质上是一个东西,只是表现的方式相反罢了。

考虑原始问题:

原始问题是以 为参数,以 为变量的极大化问题。既然对偶问题是原始问题关于优化问题的相反的表达方式,那么对偶问题就可以写成,以 为变量,以 为参数的极小化问题(记住一点:本质相同,表现相反):

原始问题最终是被极小化,成为了一个极小极大化的问题:

对偶问题,要和其相反,就需要被极大化,而称为一个极大极小化的问题:

上面的式子,就称为拉个朗日函数的极大极小问题,并定义对偶问题(dual problem)的最优解为:

由于:

所以:

上面这是式子说明,的所有的解,都不大于的解。那么,毫无疑问,对偶问题的最优解和原始问题的最优解也满足这个式子:

在我们常见的问题中,只要满足一定的条件,就可以使得,这里 就是最优解。这里所说的一定的条件,指的就是KKT条件。

3、KKT条件

对于原始问题 和 对偶问题而言, 分别是原始问题和对偶问题的解的充分必要条件是 满足KKT条件:

上述的KKT条件,看起来很吓人,其实很容易理解:函数 是以 为参数的,那么其最优解 定然满足 函数 的梯度为0,这就是KKT条件的前三个等式:

前面已经说明过,函数 要能够使用,最初的优化问题必须满足不等式约束 以及其相关的拉格朗日乘子 的约束:

而最后一个KKT条件,对应的就是 的等式约束:


1.6 最小间隔最大化求解

求解最小间隔最大化,就是要求解式子:

而求解上面的式子,用的到方法,就是拉格朗日对偶性。这里,在原来的最小化的目标函数前面加了 ,并不会影响最后的最优解,但是对后面的公式推导相对有利,故而加上了个

将它作为原始的优化问题,应用拉格朗日对偶性,通过求解对偶问题(dual problem)来得到原始问题(primal problem)的最优解,这个最优解,就对应于最优的决策面。

这样做的优点主要有两个:
一、对偶问题相对来说比较容易求解
二、可以很自然的引入核函数,进而推广到非线性分类器中

首先,构建拉格朗日函数,由于上面的约束优化问题中只有不等式约束,所以为所有的不等式约束添加拉格朗日乘子: ,则拉格朗日函数为:

根据前面关于拉格朗日对偶性的说明可以很容易知道,这个原始问题为极小极大问题:

其对应的对偶问题为极大极小问题:

求解内部极小化

这里首先求解内部的极小化问题:

显然,这个极小化问题是以 为参数的,那么,先使 求导,并令其为0:

那么,就有:

带入到 中,就可以得到:

上面推导的导数第二步使用了:,最终可以得到:

这里的 的內积。

求解外部极大化

前面已经将内部的极小化求解得到了,这里再在其求解的结果上加上外层的极大化,那么就有下面这个约束优化问题:

这个就是原问题的对偶问题,当然了,可以将这个对偶问题的目标函数的符号换一下,让它成为一个最小化的问题:

公式推导到这个地方,就可以知道,上面这个最小化问题,就是我们最终要求解的问题,其最小化的目标函数是以 为参数的。

也就是说,假设最优解是 。这里暂时不讨论如何求得这个最优解,其具体的求解算法会在后面详细的论述,现在假设,我们可以通过某种算法,将上面的这个最小化的优化问题的最优解求出来。

那么,在已知这个最优解的情况下,我们来看一下,基于这个最优解,SVM的决策面是什么样的?

根据原始问题的KKT条件可以知道:

那么,就有:

这里,根据已经求得的 ,就可以将 求出来了。决策面的参数有两个: 求出来了,剩下的就是 了。

在前面讨论过,SVM是间隔最大化的决策面,支持向量对应的就是间隔最小的那些点,由前面关于间隔最大化的讨论可以知道,支持向量满足下面这个公式:

而根据前面对原始问题的讨论,可以知道,满足这个公式的点 (支持向量) ,在拉格朗日函数中,所对应的 。所以,我们只需要找到一个 , 就可以得到 :

同时,需要注意:,并带入 ,就可以将上面这个式子重写为:

当然,为了稳妥起见,很多时候,我们会将所有的支持向量 对应的 都求出来,然后用其均值,作为最终的 。这里 是支持向量的集合,也就是 所对应的点集:

这样,就可以求得最终的决策超平面为:

分类决策函数可以写为:

这里就可以发现:


1.7 SVM、LDA、Logistics Regression 算法比较

在之前的文章线性判别分析(Linear Discriminant Analysis)中就说过:凡是分类算法,必定有决策面,而这些分类算法所不同的是:决策面是线性的还是非线性的;以及如果得到这个决策面。

对于Logistics Regression

对于一个二分类问题,在Logistics Regression中,假设后验概率为Logistics 分布:

这里,使用一个单调的变换函数,logit 函数:,那么就可以得到:

所以Logistics Regression的决策面就是:

对于Linear Discriminant Analysis

这里假设是类别的类条件概率密度函数, 是类别的先验概率,毫无疑问有。根据贝叶斯理论有:

LDA假设是均值不同,方差相同的高斯分布,所以其类条件概率密度函数可以写为:

这里,特征的维度为维,类别的均值为,所有类别的方差为

LDA和前面提到的Logistics Regression采用的单调变换函数一样,都是logit 函数:,对于二分类问题有:

所以LDA的决策面就是:

显然,在LDA中,和Logistics Regression不同的是,LDA的决策面是由各个数据分布的方差和类别中心决定的。

对于SVM

对于SVM而言,我么假设,最大间隔会带来最小的泛化误差。但是,反过来思考,这个假设真的是真确的吗?在讨论LDA和Logistics Regression的时候,我们其实也是说他们的决策面是最优的。那么,到底那个算法得到的决策面才是最好的呢?

说到这个问题,让我突然想起来前段时间的一件事情,一同学面试,面试官问他:Logistics Regression对数据分布有什么要求?他并不知道怎么回答,后来回来和他们实验室的人讨论了许久,也没有结果。其实这个回答非常的简单:

我们所面对的所有的机器学算法,都是有适用范围的,或者说,我们所有的机器学习算法都是有约束的优化问题。而这些约束,就是我们在推导算法之前所做的假设。

比如:Logistics Regression,上面已经明确说明了,在Logistics Regression中,假设后验概率为Logistics 分布;再比如:LDA假设是均值不同,方差相同的高斯分布;这些都是我们在推导算法之前所做的假设,也就是算法对数据分布的要求。

而对于SVM而言,它并没有对原始数据的分布做任何的假设,这就是SVM和LDA、Logistics Regression区别最大的地方。这表明SVM模型对数据分布的要求低,那么其适用性自然就会更广一些。如果我们事先对数据的分布没有任何的先验信息,即,不知道是什么分布,那么SVM无疑是比较好的选择。

但是,如果我们已经知道数据满足或者近似满足高斯分布,那么选择LDA得到的结果就会更准确。如果我们已经知道数据满足或者近似满足Logistics 分布,那么选择Logistics Regression就会有更好的效果。

通过这三个方法的比较,我只想说明一件事情:机器学习算法是死的,但,人是活的。使用什么机器学习算法,是根据实际问题要求,和数据的具体分布而定的。



二、软间隔最大化分类器

在这篇文章之前所有的讨论中,假设,所面对的数据在特征空间中是线性可分的,那么,最终得到的SVM可以在输入空间中得到一个准确的判别面,尽管其对应的判别面可能是一个非线性判别面。

然而,在现实的数据中,数据是线性不可分的(或者近似线性可分)。换一种说法就是:类条件分布存在重叠。如果这样,上面讲的算法最终只会有两种结果:1、决策面会出现严重的震荡,而无法收敛;2、即便收敛到了一个非线性的决策面,其决策面也会十分的复杂,泛化能力低。

因此,我们就需要对原始的SVM算法做一定的改动,让它对数据的要求,从线性可分扩展到线性不可分。即:允许部分训练数据存在分类错误的情况,以得到一个相对比较好的决策面。 这个改动后的SVM一般被称为 软间隔最大化分类器 ,而与之相对应的,前面论述的只可以解决线性可分数据的SVM,称为 硬间隔最大化分类器


2.1 软间隔最大化分类器的两个问题

那么,现在就有两个问题摆在我们面前:

1.在SVM中,对于非线性可分的数据而言,哪些样本点是存在分类错误的样本点?
2.对于分类错误的点,软间隔最大化分类器 如何处理以得到相对比较好的决策面?

两个问题,就是软间隔最大化分类器的核心问题,回答了这两个问题,掌握了软间隔最大化分类器。

哪些是分类错误的样本点

首先必须要知道,面对一个非线性可分的数据集,哪些样本点是分类错误的样本点?可以先看下面这幅图:
image_1aogssta61j891jqn6l8qe168d9.png-63.9kB

图中,左边那幅图对应的是数据线性可分时,SVM的状态。此时有决策面: ,也就是之前讨论的 ,只是写法不同而已。根据前面“最小间隔最大化”小章节的讨论可知:最小间隔为,也就是之前的表达式:。这种状态,是所有数据点都分类正确,且最小间隔最大分类的状态。

图中,右边那幅图对应的就是数据线性不可分时,SVM的状态。此时决策面依然是:,最小间隔仍然为。不过,右图中 就是非线性可分数据在SVM中分类错误的点。

那么总结一下,在非线性可分的情况下,样本点的状态一共有下面五种:
1.非支持向量,即是在 两侧,被正确分类的样本点。这些样本点对于SVM的决策面没有贡献。
2.在边界上面的点,这个是支持向量,且被正确分类。
3.在内部,被正确分类的点,比如,这些也是支持向量。
4.在决策面上的点,这些点可以拒绝判断,也可以直接认为是分类正确的点。
5.真正的被分类错误的点:,这些点直接走到了决策面的另一边去了。

很容易发现,相对于数据线性可分的情况而言,非线性可分数据的状态多了三种情况,也就是上面五种情况的后三种,线性可分的数据只存在前面两种情况。

而后面三种情况的样本点的间隔,都比最小间隔 也就是图中的 要小一些,所以,后面这三种情况,就是SVM认为的错误的样本点(即便情况3、情况4样本被分类正确了),软间隔最大化分类器 就是要针对后面这三种情况来做文章。


分类错误的样本点的处理:软间隔变量

前面提到了,后面三种情况的样本点的间隔,都比最小间隔 也就是图中的 要小一些。这里首先要考虑的问题就是,如何用公式来表达后面这三种情况?这里就引入了一个最小间隔 的比例因子:软间隔变量 是最小间隔 的比例系数,或者叫做倍数。下面先分别讨论如何将软间隔变量 应用到上面的后三种情况中:

为了将前面的第一种情况:非支持向量,即是在 两侧,被正确分类的样本点。和第二种情况:在边界上面的点,这个是支持向量,且被正确分类。也统一的用软间隔变量 来表示,这里将SVM的优化公式重写为下面这个形式:

而前面第一种情况和第二种情况所对应的

和“最小间隔最大化”章节中讨论的一样,比值 不变的情况下,是可以任意取值的。这样的话,为了便于计算,我们就取:

那么,上面的式子又可以改写为:

可以看到,上面的式子是最大化 ,很容易知道,其等价于 最小化 ,那么最小间隔最大化,最终就可以变为下面这个式子:

这里,最小间隔为:


2.2 软间隔最大化分类器 的优化公式

上面提到的第五种情况,真正的被分类错误的点:,这些直接走到了决策面的另一边去了的点,所对应的 。如果说我们知道 ,那么,就可以说,这个 软间隔最大化分类器 的训练错误样本数,最多为 个。让训练误差尽量的小也是我们的一个优化目标,这样,软间隔最大化分类器 就成了一个多目标的优化问题:

由于上面两个优化目标的限制条件是一样的,可以将两个优化目标合成一个优化目标:

这里的参数 是损失参数(cost parameter),用于权衡。一般我们将视为模型的复杂度,而将视为模型的错误率,损失参数 就是在模型复杂度和模型的错误率之间找一个平衡,这个值一般作为模型的一个输入变量,需要人工设置:

需要强调:是对于SVM而言,分类错误的样本点 的分类错误间隔相对于最小间隔 的比例。我们不可能让错误的比例无限的增长,那样分类错误就太大了。所以,我们需要对错误间隔进行限制,而限制的手段,就是为总的错误间隔比例加一上限:。这是软间隔最大化分类器 优化公式的另一种解释。


2.3 软间隔最大化分类器 的对偶问题

这里的步骤和 1.5 拉格朗日对偶性 几乎雷同,首先将 软间隔最大化分类器 的优化公式转换为拉个朗日函数的形式,其原始的优化公式为:

拉个朗日函数为:

其中, 为拉格朗日乘子。将 分别对 求偏导:

就可以得到:

将上面三个式子带入到 中,和之前 1.6 最小间隔最大化求解 中的推导一样,最终可以得到:

这里的 的內积。

再对求极大化,即可得到 软间隔最大化分类器 的对偶问题:

这个就是原问题的对偶问题,当然了,可以将这个对偶问题的目标函数的符号换一下,,让它成为一个最小化的问题,并将后面三个式子做一个合并:

这就是 软间隔最大化分类器 的对偶问题,和前面相比,这里的对偶问题只是限制条件 和前面不同,其他的是一模一样的。


2.4 软间隔最大化分类器 求解

很显然,得到了软间隔最大化分类器 的对偶形式之后,其优化求解出来的就是最优解 。这里再次说明:假设 我们已经通过某种算法得到了,至于这个算法是什么后面的章节会详细的说明,这里不同担心。

仿照 1.5 拉格朗日对偶性 中的公式推导 ,假设 为最优解,可以很容易推出 软间隔最大化分类器 拉格朗日优化的KKT条件为:

在假设知道 的情况下,由KKT条件的第一个公式: 可以知道,的最优解为:

再找到一个 ,其所对应的样本点满足:,那么,就可以和前面的推导一样,得到:

同时,需要注意:,并带入 ,就可以将上面这个式子重写为:

当然,为了稳妥起见,很多时候,我们会将所有的支持向量 对应的 都求出来,然后用其均值,作为最终的 。这里 是支持向量的集合,也就是 所对应的点集:

这样,就可以求得最终的决策超平面为:

分类决策函数可以写为:


2.5 对参数 的讨论

基于上面的推导,可以很容易的看出,软间隔最大化分类器 就是在 硬间隔最大化分类器 的基础上,处理非线性可分的数据。而参数起着决定样本点类别的作用,那么,这里就对这两个参数做一下讨论,看看这两个参数是如何判断非线性可分数据集中的样本点的类别的。

为了方便,这里直接用一张表格说明参数 和样本点之间的关系,图种叉叉的部分,说明这种情况并不存在,下面将对这个表格做详细的说明:

image_1aoiga7581tpml1qk7eduu1it7m.png-75.9kB

在 2.1 软间隔最大化分类器的两个问题 中,就讨论过,非线性可分情况下,SVM中的样本点一共有五种情况,也就是上面表格中的所对应的五种情况。

从表格中可以粗略的观察到:
- 当 时,对应的样本点是非支持向量;当 时,对应的样本点是支持向量
- 当 时,对应的样本点可以被正确的分类;当 时,对应的样本点分类错误

现在基于参数 对上面五种情况再做更详细的讨论:

1.当时,此时的样本点 并不是支持向量,其被完全的分类正确,样本点满足:
变量关系:当时,由KKT条件中的第三条:可以知道,;再由KKT条件第七条: 可以知道:;最后根据KKT条件的第四条和第五条,可以很容易知道:

2.当时,此时样本点刚好在SVM的间隔边界上,是支持向量,被正确分类,样本点满足:
变量关系:当 时,由KKT条件中的第三条:可以知道,;再由KKT条件第七条:,可以知道:。最后根据KKT条件的第四条和第五条,可以很容易知道:

3.当时,此时样本点在SVM的正确的间隔边界内,是支持向量,被正确分类,样本点满足:
变量关系:当时,由KKT条件中的第三条:可以知道,;再由KKT条件第六、七条:,可以知道:。根据KKT条件的第四条和第五条,可以很容易知道:。那么,此时,所以,即,其对应的样本点在分类正确的间隔中。

4.当时,此时样本点在SVM决策面上,是支持向量,被正确分类,样本点满足:
变量关系:这里的变量关系的分析和第三种情况一样,差别仅仅是 ,由:,可以很容易知道: ,这样,样本点就刚好在SVM的决策面上了。

5.当时,是支持向量,被错误分类,样本点满足:
变量关系:这里的变量关系的分析和第三种情况一样,差别仅仅是 ,由:,可以很容易知道: ,这样,样本点就在决策面错误的一边,被错误分类了。

由于变量是我们最终要求解的变量,这里再单独对变量做一个总结。首先,这里取如下,即SVM的决策面函数:

那么,根据前面的表格,可以很容易得到:

总的来说就是:



三、基于核函数的非线性SVM

使用上面提到的 软间隔最大化分类器 在一定程度上,可以解决非线性可分问题。但是,其实质上是用一个线性的决策面,在允许部分训练样本点出现分类错误的前提下,得到的SVM。软间隔最大化分类器 对于数据是近似线性可分的情况,效果还是不错的,但是对于完全的线性不可分的情况,其分类效果就不太好了。此时,就需要通过某种手段,将SVM从线性分类器扩展成为非线性分类器,而这个手段,就是“核技巧”。

核技巧在机器学习中的应用是非常的广泛的,特别是从2000年之后,各个大牛们对核技巧的研究也越来越深入,这里仅仅对核技巧做一些简单的说明,方便在SVM中使用,后面会使用专门的文章来详细讨论核技巧。

在前面对SVM的推导中,最后得到的判别函数为:

上式中有两个东西需要格外注意,和<\phi(x_i),\phi(x)>

所代表的就是一种空间映射,是核技巧必备的一个元素,这也是为什么本文从一开始推导SVM的公式的时候,使用的就是而不是单纯的的原因。

指的是 的內积。这里可以看到,SVM的判别函数最终变成了的內积的求解。

实际上,这两点,就是核技巧的核心,下面分别对这两点进行说明:


3.1 特征映射解决非线性可分问题

一般来说,如果能用一个超曲面将正负训练样本完全分开,则称这种问题为非线性可分问题。

非线性可分问题一般是非常的难求的,对于近似线性可分的非线性可分问题,还可以考虑使用上面的 软间隔最大化的SVM来得到一个分类器,但是如果数据非线性十分的强,以至于无法近似线性分开的时候,我们一般就考虑对数据空间做一个空间变换,将维度提升,在低维空间中非线性可分的问题,在高维空间中可能变成线性可分的问题,在高维空间中训练一个线性分类器,对数据进行分类。

注意:维度提升后,在高维空间,是可能变成线性可分!!!是可能!!!,说白了,数据从低维空间映射到高维空间之后,到底会成什么状态,没人说得准。虽然从低维到高维之后,数据是否线性可分,存在不确定性,但也不失为一种有效的手段,并且,其在实际的应用中表现的也还不错。这个就像深度学习算法一样,那货到底干了什么事情,没人说得准,反正最终效果还不错。

提升维度的过程大致可以从下面这个例子中看出来:

image_1aojh556d19rsbvnl1m369nv9.png-73.3kB

左图中对应的就是原始数据,显然左图中的数据是线性不可分的。然后通过映射:

将数据从原始特征空间映射到新的特征空间。即,原始特征空间是二维的,中的样本点可以用来表示,新的特征空间是三维的,中的样本点可以用来表示。这样,上面的映射过程,就可以表示为:

image_1aoji1shr9j5dlbiga16qllqim.png-90.3kB

左图对应的是新的空间中,用一个平面就将变换后的数据分开;右图则对应原始空间中需要一个分线性的决策面,才可以将数据分开。

可以很容易的看出,在新的特征空间中,数据已经是线性可分的了。这就是提升数据维度,使得原空间的分线性可分问题变成新空间的线性可分问题的过程。

上面的例子说明,用线性模型求解非线性分类问题分为两个步骤:1、首先使用一个变换,将原空间的数据映射到更高维度的新空间;2、在新的数据空间中,用线性分类学习方法,从训练数据中学习模型。


3.2 核函数

前面也提到过,在前面对SVM的推导中,最后得到的判别函数为:

从公式中可以明显看出,对这个判别函数的求解最终变成了对的计算。这里的就是上面提到的特征变换,用于解决非线性可分的问题。

按照一般的思维方式,要求解,那么,就需要我们先定义,再根据,分别计算出 ,最后计算出它们的內积。

这是一个非常繁琐的步骤,而且,由于对高维空间具体的数据分布知之甚少,我们并不能确定一个映射是否一定能够使得原始数据在高维空间中线性可分,所以一般也很难确具体的映射公式定;或者说,我们一般很难显式的定义出

既然如此,是否可以将直接看成一个函数,不显式的定义,而是给定了后,就直接将计算出来的方法呢?有!这就是核函数!!!!

核函数的定义:假设,将原始的输入空间为(可能是欧式空间 或者是一个离散集合),新的特征空间为(希尔伯特空间),如果存在一个从的映射:

使得对所有的,函数满足条件:

则称为一个核函数。其中为映射函数,的內积。

基于前面的讨论,可以得出结论:核技巧的想法就是,在学习与预测中,仅仅定义核函数,而不显式的定义映射函数

一般来说,直接计算相对比较容易,而通过<\phi(x_1),\phi(x_2)>的计算反而比较的复杂。

映射函数一般是将原始空间的维度升高,有时候会变成无穷维度。


3.3 非线性映射定与核函数的关系

为了说明上面这两个特点,这里举个例子:假设,输入空间是,核函数是
1. 取特征空间,即维度升高一个维度,此时可以取:

或者也可以取:

  1. 取特征空间,即维度升高两个维度,此时可以取:


3.4 常用的核函数

此处本应该讲讲,如何来构造核函数的,但是这个知识点实在是太过复杂,直接放在后面专门讲核技巧的文章中。

一个函数是否能称为核函数,是有非常严格的要求的,但是,我们在实际的使用中,一般都会使用一些常用的核函数,这里提供四个最常用的核函数,关于这些常用核函数的说明,也将放在后面专门讲核函数的文章中。

1.Polynomial 核函数:

2.Gaussian 核函数:

3.Sigmoid 核函数:

4.RBF 核函数:


3.5 对无穷维度的定性理解

每次在读一些关于核函数的书籍或者网上的博客的时候,总是会提到:核函数不需要显示的定义特征空间以及特征映射,使得学习算法隐式的在高维的特征空间中进行,甚至可以在无穷维度中进行。

这句话的前部分,已经说明过了,核函数的确不需要显示的定义特征空间以及特征映射,就是可以完成学习过程。但是,甚至可以在无穷维度中进行到底是怎么回事?我所看到的书籍和网络博客中,却没有进一步的讨论。我在这里做一个简略的说明,这需要会涉及一些核函数构造的知识,比较复杂,这里仅仅做定性的分析,详细的讨论也会放在后面专门讲解核技巧的文章中。

在高等数学中,有无穷级数的概念,举个简单的例子:

根据上面这个无穷级数的式子,可以很容易的推断出,指数型的核函数,可以变成无穷维度的多项式映射的结果:

对于Gaussian 核函数:

由于这是一个指数型的核函数,根据前面的讨论,可以定性的判断出,基于无穷级数,Gaussian 核函数的映射函数,可以是无穷维度的。其具体的公式会在后面专门讲核函数的文章中说明,这里仅仅是一个定性的理解。

下面,以一分代码来说明一下SVM的应用:

  1. # -*- coding: utf-8 -*-
  2. """
  3. @author: duanxxnj@163.com
  4. @time: 2015-07-17_13-59
  5. SVM分类算法示例
  6. 为了绘图方便,这里仅仅使用iris数据集的前两个特征作为样本特征
  7. LinearSVC 使用的是平方合页损失
  8. SVC(kernel=‘linear’) 使用的是正则化合页损失
  9. LinearSVC 使用留一法(one-vs-rest)处理多类问题
  10. SVC 使用的是one-vs-one的方法处理多类问题
  11. 从图中很容易看出one-vs-rest方法和one-vs-one所产生的决策面的区别
  12. """
  13. print __doc__
  14. import numpy as np
  15. import matplotlib.pyplot as plt
  16. from sklearn import svm, datasets
  17. # 导入iris数据
  18. # 这个数中一共有三个类别
  19. # 每个类别50个样本
  20. # 每个样本有四个特征
  21. iris = datasets.load_iris()
  22. X = iris.data[:, [2, 3]] # 这里仅仅两个特征作为样本特征
  23. y = iris.target
  24. C = 1.0 # SVM正则化参数
  25. # 使用线性核学习SVM分类器
  26. svc = svm.SVC(kernel='linear', C=C).fit(X, y)
  27. # 直接使用线性SVM分类器
  28. linear_SVC = svm.LinearSVC(C=C).fit(X, y)
  29. # 使用rbf(径向基)核学习SVM分类器
  30. rbf_svc = svm.SVC(kernel='rbf', gamma=0.7, C=C).fit(X, y)
  31. # 使用多项式核学习SVM分类器
  32. poly_svc = svm.SVC(kernel='poly', degree=3, C=C).fit(X, y)
  33. # 生成绘图用的网格
  34. x0_min, x0_max = X[:, 0].min() - 1, X[:, 0].max() + 1
  35. x1_min, x1_max = X[:, 1].min() - 1, X[:, 1].max() + 1
  36. xx0, xx1 = np.meshgrid(np.arange(x0_min, x0_max, 0.02),
  37. np.arange(x1_min, x1_max, 0.02))
  38. titles = ['SVC with linear kernel',
  39. 'LinearSVC',
  40. 'SVC with RBF kernel',
  41. 'SVC with polynomial kernel']
  42. color = ['r']*50 + ['g']*50 + ['b']*50
  43. for i, clf in enumerate((svc, linear_SVC, rbf_svc, poly_svc)):
  44. plt.subplot(2, 2, i + 1)
  45. plt.subplots_adjust(wspace=0.4, hspace=0.4)
  46. z = clf.predict(np.c_[xx0.ravel(), xx1.ravel()])
  47. z = z.reshape(xx0.shape)
  48. plt.contourf(xx0, xx1, z, cmap=plt.cm.Paired, alpha=0.8)
  49. plt.scatter(X[:, 0], X[:, 1], c=color)
  50. plt.xlabel('feature_1')
  51. plt.ylabel('feature_2')
  52. plt.xlim(xx0.min(), xx0.max())
  53. plt.ylim(xx1.min(), xx1.max())
  54. plt.title(titles[i])
  55. plt.show()

figure_1-1.png-92.5kB



其实,关于SVM算法,如果是入门,看到这个地方,就已经不用再往下深究了。后面是SMO算法的推导,如果不清楚,并不影响SVM的理解。



四、SMO算法

前面已经得到 软间隔最大化分类器 的对偶问题,现在基于核函数,可将对偶问题写为如下形式:

其KKT条件为:

其中:

直接在求解SVM的时候,都是说,假设已经将 求了出来,然后再计算 的,但是并没有说明,如果计算 ,这里就来说明一下 的计算。

在上面这个问题中,变量就是拉格朗日乘子 ,且每个变 都和一个样本点 相对应,也就是说,变量的个数,是训练样本的数目 。 一般来说, 是一个非常大的数目,使用普通的凸优化算法,虽然肯定可以将上面的问题解出来,但是算法耗时太长,就需要一种相对简单的算法来得到 。这样的算法有很多, 这里就其中最流行的算法 SMO(Sequential Minimal Optimization)做一个介绍。

本文关于 SMO算法的说明,主要参考的是 Platt, John C.《 Fast training of support vector machines using sequential minimal optimization》,1998。

由于有 个变量,所以基于训练样本训练SVM是一个非常大的 quadratic programming (QP)optimization problem,即二次最优化问题,在这里也就是上面的软间隔最大化分类器 的对偶问题,这个优化问题在实际中太大,以至于几乎无法得到优化结果。

SMO算法将原始的非常大的 QP优化问题 分解成了一系列非常小的可解的QP优化问题。SMO算法最诱人的地方在于,这些分解后的小的 QP优化问题 ,都是拥有解析解的,也就是说,求解这些小的 QP优化问题 不需要通过非常耗时的循环来得到问题的结果。这样SMO算法的空间复杂度是训练样本的线性函数,这就是使得 SMO 算法可以处理特别大的样本集合的训练问题。由于不需要矩阵计算,使得 SMO算法 在实际的数据集的测试中,其计算复杂度介于线性复杂度和二次复杂度之间。SMO算法的计算复杂度和SVM的模型也有关系,线性核SVM计算速度较快。在实际测试中发现,如果训练样本是稀疏数据集(sparse data sets),那么,SMO算法的效率会极其高。


4.1 最小的QP优化问题

对于SVM的 QP优化问题 ,由于有下面这个限制条件:

所以最小的 QP优化问题 仅仅包含两个拉格朗日乘子 的优化。

这个原因很简单,这里朗格朗日乘子的数目一共有个 个,如果一次只优化其中的一个拉格朗日乘子的话,就需要将剩下的所有的个拉格朗日乘子固定住。但是由于有上面这个等式限制,剩下的所有的个拉格朗日乘子一旦被固定住之后,拉格朗日乘子也会被固定住,就无法优化了。这里假设被优化的是 ,如果只固定这一个变量,那么就有:

所以,这里最小的优化子问题是优化两个拉格朗日乘子,而固定住其他所有的变量。

SMO算法的每一步都是做两件事情:1、选择两个拉格朗日乘子;2、优化这两个拉格朗日乘子。按照原文的说法就是:an analytic method for solving for the two Lagrange
multipliers, and a heuristic for choosing which multipliers to optimize。一个解两拉格朗日乘子的解析算法、一个启发式的拉格朗日乘子选择方法。


4.2 二变量拉格朗日乘子解法

由于原始的 QP优化问题,是个变量的,为了求解二变量的 QP优化问题 ,首先需要对约束条件进行分析,然后在此约束条件下求极小值。

不失一般性,这里假设所选择的两个拉格朗日乘子是 ,而其余的变量 都是固定不变的。

原始的约束条件如下:

由于现在仅仅考虑两个拉格朗日乘子是 ,所以约束条件可以改写为下面这个形式:

对于其中的等式约束,由于等式约束的右边是一个定值,这里直接使用一个变量来表示。


异号

对于异号的情况,用图形将上面这个约束表示出来就如下图所示:
二变量2.PNG-13.8kB

首先,基于不等式约束:

可以得到 只能在图中的绿色区域 内。

然后,由于异号,不是一般性,这里直接考虑(如果反过来,也无所谓,只是换一下变量的名字,对结果没影响)。那么,等式约束就是一条直线,即图中的红色和蓝色两条线中的一条,且该直线和对角线平行。

而等式约束和不等式约束的交集,就是图中绿色区域内的红色线段和蓝色线段。注意,最终的约束,都是线段,是绿色区域里面的 红色线段 和 蓝色线段。

因此,要求的是目标函数在一条平行于对消线的线段上的最优解,这就使得两个变量的最优解问题,转换成为了变量的优化问题(因为一旦一个变量定了,另一个也定了)。这里不妨假设,需要优化的变量为

这里假设问题的原始解为 ,经过本次优化之后的最优解为 。由于优化变量为 ,而 都必须满足上面这幅图,所以,可以从图中得到 的约束为为:

这里 是下界,其确定方式是上图中 两个点,这两个点是约束线段的下端点,所以这两个点的 较大的一个要作为 的下界,也即是上图坐标中标红的数值:

这里的 是上界, 其确定方式是上图中 两个点,这两个点是约束线段的上端点,所以这两个点的 较小的一个要作为 的上界,也即是上图坐标中标红的数值:

也就是说,此时 有了上面的新的约束。


同号

同号的时候,等式约束为 ,此时也是一条平行于对角线的直线,只是与异号时方向垂直,其他的分析是一样的,这里就不再重复,原文中将中情况的图都做出出来:

image_1aov920mhf7s169m1afq1lfv8m39.png-40.2kB

左图即 异号的情况,右图是同号的情况。

很容易得到,在同号的时候有约束:


优化结果

这里仅仅给出优化的结果,并不给出证明,具体证明可以参考《统计学习方法》。

目标函数沿着沿着对角线的二次导数可以表示为:

在一般的情况下,目标函数是正定的,那么,沿着等式约束必然有一个最小值,并且必然大于0。在这种情况下,SMO算法沿着等式约束得到的最优解为:

由于在前面已经定义过,这里可以直接定义为:

注意上面的下标,既有,也有。很容易看出, 是输出 对于输入 的预测值和 的真实值值 之差。

由于上面仅仅考虑了等式约束,现在,将前面的结果加上不等式约束:

那么,最终的 的结果为:

这里的是剪辑的意思, 仅仅是线性约束得到的结果,但是并未经过 剪辑,所以将不等式约束之后的结果,成为剪辑之后的 ,即:

在求得由等式约束,就可以很容易得到,的结果为:

很容易看到,此时 改变的量相同,但是方向相反。

这样就得到了


4.3 二变量拉格朗日乘子的选择

前面是先给出了 的优化方法,但是并未说明,算法中具体要选择哪 两个变量 做为 来优化。这一节就详细的说明一下 的选择方法。

原文中,将这里的变量选择方法称为启发式(Heuristics )算法。其基本思路是:
1. 因为KKT条件是最优解的充分必要条件,所以,如果所有变量的解都满足最优化问题的KKT条件,那么,这个最优化问题的解就得到了。
2. 如果KKT条件不满足,则选择两个变量,而固定其他变量,这对这两个选择的变量,构建一个二变量QP优化问题,这两个变量其中一个是违反KKT条件最严重的哪一个变量,另一个则是由约束条件自动选择的。


第一个变量的选择

SMO算法选择第一个变量,是选择违反KKT条件最严重的那个变量,这里的KKT条件就是:

其中:

将第一个变量的选择称为外层循环(outer loop),外层循环首先需要遍历整个训练样本,判断是否存在违反上述KKT条件的样本点。如果某个样本点 违反了KKT条件,那么该样本点 就有可能在下一步被优化。

在遍历过程中,外层循环首先遍历所有 的样本点,这些样本点代表的就是在margin边界上面的点。如果这里面的样本点违反了KKT条件,那么优先优化这些样本点。

如果 的样本点都满足KKT条件,那么在遍历整个训练样本集合,检验他们是否都满足KKT条件。

最终,是要根据上面的选择优先级,选出一个违反KKT条件最严重的样本点。

什么是违反KKT条件最严重的样本点?
答:举个例子,如果一个样本点满足 ,那么根据KKT条件,其应该也满足 , 但是,如果它不满足后面这个等式的话,就说这个样本点违反了KKT条件。其严重程度,自然是定义为 ,即数值上偏离的程度。

还有一点就是,由于KKT条件过于的严格,比如 ,这个条件一般很难达到,所以在检验KKT条件的时候,都是在一定的误差限 内检验KKT条件的, 即

上面就是对第一个变量的启发式选择方法。


第二个变量的选择

SMO算法对第二个变量的选择称为内层循环。这里,外层循环已经将第一个变量 找好了,现在需要在内层循环中,将第二个变量 找到。对第二个变量的选择所遵循的标准就是: 的变化步长要尽量的大。

由于前面已经得到了:

为了使得 的步长足够的大,一种直观的选择方式就是选择能使得

由于 在选择第一个变量的时候已经确定了,所以其对应的 也确定了。

如果说,在某种特殊情况下,内层循环所选择的 并不能使得目标函数有足够的下降,则采用下面的启发式规则来继续选择 : 遍历在间隔边界上的所有的支持向量点,依次将其作为 来使用。如果再这种情况下,目标函数仍然没有足够的下降的话,那么就放弃当前的 重新选择一个 来实现遍历的选择。


4.3 阈值计算

每次基于上面的变量选择和变量优化之后,都需要对阈值 做一次更新。对 的更新,自然是要找在margin边界上的点来更新是最方便的,即 的点。由此时的KKT条件:

可以很容易知道:

,进而有:

所以:

这里为了简化表达,定义

又根据前面关于 的定义可以知道:

拆开后有:

变换一下这个式子就可以得到:

将上面这个式子带入到中,就可以得到:

同样的计算方式,可以得到,当 时,有:

如果 同时满足 ,那么:

否通则的话:

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注