斯坦福CS229机器学习笔记-Lecture8- SVM支持向量机 之核方法 + 软间隔 + SMO 算法

  • Post author:
  • Post category:其他




作者:teeyohuang



邮箱:



teeyohuang@163.com




本文系原创,供交流学习使用,转载请注明出处,谢谢


声明:此系列博文根据斯坦福CS229课程,吴恩达主讲 所写,为本人自学笔记,写成博客分享出来


博文中部分图片和公式都来源于CS229官方notes。


CS229的视频和讲义均为互联网公开资源

Lecture8

主要内容如下:


·Kernels (核方法)


·Soft Margin(软间隔) –非线性可分的情况


·SMO algorithm

1.Kernels (核方法)

上一节课的最后我们已经推出了一些有用的结论:

这是我们探讨核方法的出发点

假设我们现在有一个输入属性(input attribute)x,有时候我们会将这个x给映射到一组新的集合上去,

比如如下例子,采用特征映射 (feature mapping)  φ:

我们把得到的这组新的量称为 输入特征(input features)

这样,如果我们想通过新的这组input features求解svm,只需要把之前讲过程中的所有出现了x的地方用φ(x)代替就ok了。

假设现在有内积

<x,z>

,则直接将其写为<φ(x) φ(z)>,我们将这个内积定义为一个核:

一般φ(x)的维度都比较高,直接把φ(x)计算并表示出来显得很复杂,但是计算K(x,z)的复杂度一般要低一些,所以往往不必把φ(x)或者φ(z)显示地表达出来。举个例子说明:

下面看另一个核的例子,


如果φ(x)和φ(z)很接近,那么它们的内积就比较大,也就是说期望核的值K(x,z)比较大;如果它们彼此远离,甚至接近正交,那么它们的内积K(x,z)就会比较小,甚至于接近0。


所以我们可以认为核函数K(x,z)能够在一定程度上测定φ(x)和φ(z)的相似性,或者说x和z的相似性。比如下面这个核函数:

如果

x和z接近的话,值就会接近1;反之x和z相隔很远的话,值会接近0

那么我们能够在SVM中用到这个核吗?对于这个具体的例子来说,是可以的,这个核其实被称作Gaussian kernel,实际上对应了一个无限维度的映射函数φ。

但是问题来了,我们该


如何判定一个核函数




K




是否合法(有效)呢?


换句话说,我们能否

找到一个合适的




特征映射函数φ



使得


K =  <φ(x) φ(z)>

对于当前问题的所有x和z都成立。如果根本都找不到一个合适的φ,说明我们无法从x,z构建出这样一个核函数!

实际上有一个结论,给出了函数K是合法的核的充分必要条件


①先来看必要条件

假设现在已知K是一个合法的核函数,对应着一个映射函数φ。

现在,考虑包含了m个点的有限集合(不一定非得是训练集) :

使得有一个m x m大小的矩阵K,的元素

Kij  =  K(x(i), x(j)).


这样的一个矩阵


K


被称为


kernel matrix


(核矩阵)


根据基本的数学知识,内积是可交换的,即




<φ(x) φ(z)>  =  <φ(z) φ(x)>




那么显然,对于刚刚那个核矩阵来说,


Kij = Kji





也就是说,


K


矩阵是对称矩阵


接下来,对于任意一个向量


z


,φ


k


(x)


是φ


(x)


中的第


k


个值,有如下推导:

从而得知K是一个positive semi-definite matrix  —半正定矩阵。




必要条件


就为:如果K是一个合法的核函数,那么K函数对应的

K


矩阵就一定是一个





对称的半正定矩阵







实际上,这个



条件也是充分条件



,使得


K


是一个合法的核,称为


Mercer kernel

Mercer定理:任何的半正定函数都可以作为核函数。

给出了判定一个核函数是否是合法的标准。

其实总结起来,核方法的作用就是将特征映射到高维空间中去,所以也不局限于SVM中应用,

2.L1 norm soft Margin

在这之前,我们探讨的都是数据线性可分的情况,但是有时候数据是线性不可分的,如下图左图;

或者即便线性可分,但是分割函数并不理想,如下图右图:

所以我们就希望算法对这些极端值不敏感,这样就相当于尽量忽略这些极端值,那么剩下的大部分样本就还是线性可分的。

这些极端值无法满足间隔大于等于1的

约束条件

,所以我们对每个样本点再引入一个松弛变量

ξi




0,使得间隔函数加上松弛变量大于等于1.即约束条件变为:

如果某个样本的函数间隔为 1- ξ

i

的话,我们就应该对损失函数增加一个代价:Cξ

i


。 所以最终的损失函数和约束条件如下:

损失函数中多出来的那部分代价想表达的意思是,最小化这部分代价意味着

更少的样本点

,会

需要加上这个


ξ

才能满足函数间隔大于1;试想,

如果


ξ


是一个极大的数的话,那么光凭借


ξ


的值就能满足约束条件了

,那么我们的函数间隔那部分就没有意义了,所以

希望


ξ


这部分代价能取的尽量的小

。C是一个常数,用来控制这部分的权重而已。

如果说我们之前讲的

线性

可分

的数据

的SVM可以被称为

线性

可分

支持向量机

,那么这里对于

线性不可分的数据,但是却近似线性可分

(比如只有极个别的极端值,)的数据,是能够通过软间隔来学习出线性SVM的,可称为

线性支持向量

机。

同样可以写出它的拉格朗日乘式,

具体的详细的推导过程我们就不细讲了,参考Lecture7中的详细推导步骤,这里直接给出对偶结果:

我们会发现这个对偶问题与Lecture7中解决线性可分SVM中的对偶问题相比,只是对于αi的约束多了一个:αi≤C,

但要主要的是对于b的计算公式需要进行修改。同时KKT dual-complementarity(对偶互补条件)为:

要想解决这个对偶问题,就会讲到下面的SMO算法

3.SMO algorithm (sequential minimal optimization)顺序最小优化算法

坐标上升法:

先来看一个无约束优化问题:

W是参数α的函数,现在我们先不考虑有关SVM的任何东西,这就是个单纯的优化问题。我们在前面已经就讲过两种优化方法,梯度上升和牛顿方法,可以用来解决这个问题,但是这次提出一个新的方法:坐标上升法:

可以看到在算法的最内层循环中,我们固定除了αi的其余所有参数,然后对于参数αi最大化整个函数,最内层按照α1、α2、α3…的循环(也可以选择其他更复杂的顺序)。

这里朋友们要注意的是 在算argmax,而不是max,

就是说我们这里求的不是函数的最大值,而是使函数能取得最大值的参数αi的最大值

坐标上升算法是一个相当高效的算法,执行过程见下图:

图中的椭圆是我们想要优化的一个二次函数的轮廓。坐标上升算法的初始点为(2,-2),图中描点的路径是到达全局最大的路径。在每一步,坐标上升算法平行地沿着一个轴运动,一次仅有一个变量被优化。简单的说,就是固定x求能使得函数值最大的y,再固定y求能使函数值最大的x,如此循环……

了解了坐标上升算法之后,我们再来看之前提到的对偶问题:

对于这个对偶问题,我们确实需要求解一系列的αi,那么我们能直接使用坐标上升算法吗?



答案是不行!

因为约束条件中的第二个条件所限制,以α1为例:如果想固定除了α1以外的所有其它α是不能做到的,因为:

即因为

它们的和是一个固定值,如果固定了其余m-1个参数,那么这一个参数也就被固定了。

所以不能直接使用坐标上升算法。

但是,如果我们同时更新两个参数,固定其余m-2个参数可否呢?这样其实就可以了,因为这两个参数自己有自己调整的内部空间。

这就是SMO算法,过程如下:

SMO是一个高效的算法的关键原因是,

更新αi,αj可以被高效地计算

可以简单的推导一下:

现在固定除了α1,α2 之外的其余m-2个α,那么就会得到一个新的约束:

因为右侧被固定,就是一个常数而已,改写为:

画出函数图:

因为约束条件中0≤αi≤C,所以α1和α2必须存在于[0,C]×[0,C]的方形区域内,直线为:α1y(1)+α2y(2) = ζ,

与框形区域有两个交点。

可知,固定α1时, α2需要落在[L,H]范围内,否则无法满足条件,此图中L=0.

我们完全可以将α1写作α2的函数:α1 = (ζ − α2y(2)) y(1).

那么优化问题可以被写为:

Y因为其他参数都被固定,所以这可以视为仅仅是一个关于α2的二次函数,如果我们先暂时不考虑α2的限制范围,直接通过梯度方法求得最小值,那么设这个值为:α2-new-unclipped

然后再对其进行截断操作:

之后再把这个值代入优化函数中去求α1即可

我靠这篇博文终于写完了,眼睛都要瞎了……



版权声明:本文为Teeyohuang原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。