3.支持向量机(一)

10-13 841 views

1 简介

支持向量机基本上是最好的有监督学习算法了。这次斯坦福提供的学习材料,让我重新学习了一些 SVM知识。我看很多正统的讲法都是从 VC 维理论和结构风险最小原理出发,然后引出 SVM 什么的,还有些资料上来就讲分类超平面什么的。这份材料从前几节讲的 logistic 回归出发,引出了 SVM,既揭示了模型间的联系,也让人觉得过渡更自然。

2 重新审视 logistic 回归

Logistic 回归目的是从特征学习出一个 0/1 分类模型,而这个模型是将特性的线性组合作为自变量,由于自变量的取值范围是负无穷到正无穷。因此,使用 logistic 函数(或称作sigmoid 函数)将自变量映射到(0,1)上,映射后的值被认为是属于 y=1 的概率。

形式化表示就是

假设函数

3-image1

其中 x 是 n 维特征向量,函数 g 就是 logistic 函数。

3-image2

的图像是

3-image3

可以看到,将无穷映射到了(0,1)。

而假设函数就是特征属于 y=1 的概率。

3-image4

当我们要判别一个新来的特征属于哪个类时,只需求ℎθ(x),若大于 0.5 就是 y=1 的类,反之属于 y=0 类。

再审视一下ℎθ(x),发现ℎθ(x)只和θTx有关,θTx >0,那么ℎθ(x) > 0.5,g(z)只不过是用 来映射,真实的类别决定权还在 。还有当θTx ≫ 0时,ℎθ(x)=1,反之ℎθ(x)=0。如果我们只从θTx出发,希望模型达到的目标无非就是让训练数据中 y=1 的特征θTx ≫ 0,而是 y=0 的特征θTx ≪ 0。Logistic 回归就是要学习得到θ,使得正例的特征远大于 0,负例的特征远小于 0,强调在全部训练实例上达到这个目标。

图形化表示如下:

3-image5

中间那条线是θTx = 0,logistic 回顾强调所有点尽可能地远离中间那条线。学习出的结果也就中间那条线。考虑上面 3 个点 A、B 和 C。从图中我们可以确定 A 是×类别的,然而C 我们是不太确定的,B 还算能够确定。这样我们可以得出结论,我们更应该关心靠近中间分割线的点,让他们尽可能地远离中间线,而不是在所有点上达到最优。因为那样的话,要使得一部分点靠近中间线来换取另外一部分点更加远离中间线。我想这就是支持向量机的思路和 logistic 回归的不同点,一个考虑局部(不关心已经确定远离的点),一个考虑全局(已经远离的点可能通过调整中间线使其能够更加远离)。这是我的个人直观理解。

3 形式化表示

我们这次使用的结果标签是 y=-1,y=1,替换在 logistic 回归中使用的 y=0 和 y=1。同时将θ替换成 w 和b。以前的θTx= θ0 + θ1x1+ θ2 x2+ ⋯ + θnxn ,其中认为x0 = 1。现在我们替 换θ0为 b,后面替换 θ1x1 + θ2 x2+ ⋯ + θnxn 为w1x1  + w2 x2 + ⋯ + wnxn (即 wTx)。这样, 我们让θTx =wTx + b,进一步ℎθ(x)= g(θTx ) = g( wTx+ b)。也就是说除了 y 由 y=0变为y=-1,只是标记不同外,与 logistic 回归的形式化表示没区别。再明确下假设函数ℎw,b (x) = g( wTx+ b)

上一节提到过我们只需考虑    的正负问题,而不用关心 g(z),因此我们这里将 g(z)做一个简化,将其简单映射到 y=-1 和 y=1 上。映射关系如下:

3-image44

4 函数间隔(functional margin)和几何间隔(geometric margin)

给定一个训练样本( x(i)y(i)),x 是特征,y 是结果标签。i 表示第 i 个样本。我们定义函数间隔如下:3-image45

可想而知,当 y(i)= 1时,在我们的 g(z)定义中,wTx( i) + b ≥ 0, ̂y(i)的值实际上就是|wTx( i)  +  b|。反之亦然。为了使函数间隔最大(更大的信心确定该例是正例还是反例),当y(i) = 1时, wTx( i) + b应该是个大正数,反之是个大负数。因此函数间隔代表了我们认为特征是正例还是反例的确信度。

继续考虑 w 和 b,如果同时加大 w 和 b,比如在(wTx( i) + b)前面乘个系数比如 2,那么所有点的函数间隔都会增大二倍,这个对求解问题来说不应该有影响,因为我们要求解的 是wTx + b= 0,同时扩大 w 和 b 对结果是无影响的。这样,我们为了限制 w 和 b,可能需 要加入归一化条件,毕竟求解的目标是确定唯一一个 w 和 b,而不是多组线性相关的向量。 这个归一化一会再考虑。

刚刚我们定义的函数间隔是针对某一个样本的,现在我们定义全局样本上的函数间隔

3-image6

说白了就是在训练样本上分类正例和负例确信度最小那个函数间隔。

接下来定义几何间隔,先看图

3-image7

假设我们有了 B 点所在的wTx + b= 0分割面。任何其他一点,比如 A 到该面的距离以y(i)表示,假设 B就是 A在分割面上的投影。我们知道向量 在分割面上的投影。我们知道向量 BA 的方向是 w(分割面的梯度) ,单位向量是w / ||w||。A点是( x(i)y(i)),所以B点是 x=  x(i)  = y(i)  * w / ||w|| (初中几何知识),带入wTx + b= 0得,

3-image46

进一步得

3-image8

y(i)实际上就是点到平面距离。

再换种更加优雅的写法:

3-image9

当||w|| = 1时,不就是函数间隔吗?是的,前面提到的函数间隔归一化结果就是几何间 隔。他们为什么会一样呢?因为函数间隔是我们定义的,在定义的时候就有几何间隔的色彩。同样,同时扩大 w 和 b,w 扩大几倍,||w||就扩大几倍,结果无影响。同样定义全局的几何间隔

3-image10

5 最优间隔分类器(optimal margin classifier)

回想前面我们提到我们的目标是寻找一个超平面,使得离超平面比较近的点能有更大的间距。也就是我们不考虑所有的点都必须远离超平面,我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。形象的说,我们将上面的图看作是一张纸,我们要找一条折 线,按照这条折线折叠后,离折线最近的点的间距比其他折线都要大。形式化表示为:

3-image11

这里用||w||=1 规约 w,使得wTx + b是几何间隔。

到此,我们已经将模型定义出来了。如果求得了 w 和 b,那么来一个特征 x,我们就能 够分类了,称为最优间隔分类器。接下的问题就是如何求解 w 和 b 的问题了。

由于||w|| = 1不是凸函数,我们想先处理转化一下,考虑几何间隔和函数间隔的关系,

γ = ̂y / ||w|| ,我们改写一下上面的式子:

3-image12

这时候其实我们求的最大值仍然是几何间隔,只不过此时的 w 不受||w|| = 1的约束了。然而这个时候目标函数仍然不是凸函数,没法直接代入优化软件里计算。我们还要改写。前面说到同时扩大 w 和 b 对结果没有影响,但我们最后要求的仍然是 w 和 b 的确定值,不是 他们的一组倍数值,因此,我们需要对 ̂做一些限制,以保证我们解是唯一的。这里为了简 便我们取 ̂y = 1。这样的意义是将全局的函数间隔定义为 1,也即是将离超平面最近的点的距离定义为1/ ||w|| 。由于求1/ ||w||的最大值相当于求 1/2 ||w||2的最小值,因此改写后结果为:3-image13

 

这下好了,只有线性约束了,而且是个典型的二次规划问题(目标函数是自变量的二次函数)。代入优化软件可解。

 

到这里发现,这个讲义虽然没有像其他讲义一样先画好图,画好分类超平面,在图上标示出间隔那么直观,但每一步推导有理有据,依靠思路的流畅性来推导出目标函数和约束。

接下来介绍的是手工求解的方法了,一种更优的求解方法。

6 拉格朗日对偶(Lagrange duality)

先抛开上面的二次规划问题,先来看看存在等式约束的极值问题求法,比如下面的最优 化问题:

3-image14

目标函数是 f(w),下面是等式约束。通常解法是引入拉格朗日算子,这里使用β来表示 算子,得到拉格朗日公式为

3-image15

L 是等式约束的个数。

然后分别对 w 和β求偏导,使得偏导数等于 0,然后解出 w 和β 。至于为什么引入拉格 朗日算子可以求出极值,原因是 f(w)的 dw 变化方向受其他不等式的约束,dw 的变化方向 与 f(w)的梯度垂直时才能获得极值,而且在极值处,f(w)的梯度与其他等式梯度的线性组合 平行,因此他们之间存在线性关系。(参考《最优化与 KKT 条件》)

然后我们探讨有不等式约束的极值问题求法,问题如下:

3-image16

我们定义一般化的拉格朗日公式

3-image17

这里的 和 都是拉格朗日算子。如果按这个公式求解,会出现问题,因为我们求解的 是最小值,而这里的gi(w) ≤ 0,我们可以将αi调整成很大的正值,来使最后的函数结果是 负无穷。因此我们需要排除这种情况,我们定义下面的函数:

3-image18

这里的 P 代表 primal。假设gi(w)> 0或者ℎi(w ) ≠ 0,那么我们总是可以调整 和 来 使得θp(w)有最大值为正无穷。而只有 g 和 h 满足约束时,θp(w)为 f(w)。这个函数的精妙 之处在于 ≥ 0,而且求极大值。

因此我们可以写作

3-image19

这样我们原来要求的 min f(w)可以转换成求minw θp(w)了。

3-image20

我们使用p来表示minw θp(w)。如果直接求解,首先面对的是两个参数,而αi也是不等式约束,然后再在 w 上求最小值。这个过程不容易做,那么怎么办呢?

我们先考虑另外一个问题

3-image21

D 的意思是对偶, θD(α, β)将问题转化为先求拉格朗日关于 w 的最小值,将α和β看作是固定值。之后在θD(α, β)求最大值的话:

3-image23

这个问题是原问题的对偶问题,相对于原问题只是更换了 min 和 max 的顺序,而一般 更换顺序的结果是 Max Min(X) <= Min Max(X)。然而在这里两者相等。用 d来表示对偶问题如下:

3-image24

下面解释在什么条件下两者会等价。假设 f 和 g 都是凸函数,h 是仿射的(affine,there exists αi, bso that hi(w) = aTiw+b)。并且存在 w 使得对于所有的 i,gi(w) < 0。在这种假设下,一定存在w,  α,  β 使得w 是原问题的解, α,  β是对偶问题的解。还有 p= d = L(w,  α,  β)。另外,w,  α,  β满足库恩-塔克条件(Karush-Kuhn-Tucker, KKT condition),该条件如下:

3-image27

所以如果w,  α,  β满足了库恩-塔克条件,那么他们就是原问题和对偶问题的解。让我们再次审视公式(5),这个条件称作是 KKT dual complementarity 条件。这个条件隐含了如 果 α > 0,那么 gi(w) = 0。也就是说,gi(w) = 0时,w 处于可行域的边界上,这时才是 起作用的约束。而其他位于可行域内部( gi(w)  < 0的)点都是不起作用的约束,其 α = 0。这 个 KKT 双重补足条件会用来解释支持向量和 SMO 的收敛测试。

这部分内容思路比较凌乱,还需要先研究下《非线性规划》中的约束极值问题,再回头 看看。KKT 的总体思想是认为极值会在可行域边界上取得,也就是不等式为 0 或等式约束里 取得,而最优下降方向一般是这些等式的线性组合,其中每个元素要么是不等式为 0 的约束, 要么是等式约束。对于在可行域边界内的点,对最优解不起作用,因此前面的系数为 0。

7 最优间隔分类器(optimal margin classifier)

重新回到 SVM 的优化问题:

3-image28

我们将约束条件改写为:

3-image29

从 KKT 条件得知只有函数间隔是 1(离超平面最近的点)的线性约束式前面的系数ai > 0, 也就是说这些约束式gi(w) = 0,对于其他的不在线上的点( gi(w)< 0),极值不会在他们所在的范围内取得,因此前面的系数ai = 0.注意每一个约束式实际就是一个训练样本。

看下面的图:

3-image30

实线是最大间隔超平面,假设×号的是正例,圆圈的是负例。在虚线上的点就是函数间隔是 1 的点,那么他们前面的系数αi > 0,其他点都是αi = 0。这三个点称作支持向量。构造拉格朗日函数如下:

3-image31

注意到这里只有  没有  是因为原问题中没有等式约束,只有不等式约束。

下面我们按照对偶问题的求解步骤来一步步进行,

3-image32

首先求解 L(w,  b,  a)的最小值,对于固定的, L(w,  b,  a)的最小值只与 w 和 b有关。对 w 和 b 分别求偏导数。3-image34

3-image35

并得到

3-image36

将上式带回到拉格朗日函数中得到,此时得到的是该函数的最小值(目标函数是凸函数)化简过程如下:

3-image47

“倒数第 4 步”推导到“倒数第 3 步”使用了线性代数的转置运算,由于αiy(i)都是 实 数 , 因 此 转 置 后 与 自 身 一 样 。“ 倒 数 第 3 步 ” 推 导 到 “ 倒 数 第 2 步 ” 使 用 了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法运算法则。最后一步是上一步的顺序调整。

最后得到:

3-image37

由于最后一项是 0,因此简化为

3-image38

这里我们将向量内积(x(i))Tx(j)表示为<x(i),x(j)>。

此时的拉格朗日函数只包含了变量αi 。然而我们求出了αi 才能得到 w 和 b。

接着是极大化的过程

3-image32

3-image41

前面提到过对偶问题和原问题满足的几个条件,首先由于目标函数和线性约束都是凸函 数,而且这里不存在等式约束 h。存在 w 使得对于所有的 i, gi(w)< 0。因此,一定存在w, α使得w是原问题的解,α是对偶问题的解。在这里,求αi 就是求α了。如果求出了  ,根据

3-image36

即可求出 w(也是w,原问题的解)。然后

3-image42

即可求出 b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。关于上面的对偶问题如何求解,将留给下一篇中的 SMO 算法来阐明。这里考虑另外一个问题,由于前面求解中得到

3-image36

我们通篇考虑问题的出发点是wTx + b,根据求解得到的αi,我们代入前式得到,

3-image43

也就是说,以前新来的要分类的样本首先根据 w 和 b 做一次线性运算,然后看求的结 果是大于 0 还是小于 0,来判断正例还是负例。现在有了 ,我们不需要求出 w,只需将新来 的样本和训练数据中的所有样本做内积和即可。那有人会说,与前面所有的样本都做运算是 不是太耗时了?其实不然,我们从 KKT 条件中得到,只有支持向量的αi > 0,其他情况αi = 0。因此,我们只需求新来的样本和支持向量的内积,然后运算即可。这种写法为下面要提到的核函数(kernel)做了很好的铺垫。这是上篇,先写这么多了。

 

7.混合高斯模型(Mixtures of Gaussians)和 EM 算法

这篇讨论使用期望最大化算法(Expectation-Maximization)来进行密度估计(density estimation)。 与k-means 一样,给定的训练样本是{x (1), … ,x (m)},我...

阅读全文

6. K-means聚类算法

K-means也是聚类算法中最简单的一种了,但是里面包含的思想却是不一般。聚类属于无监督学习,以往的回归、朴素贝叶斯、SVM等都是有类别标签y的,也就是说样例...

阅读全文

欢迎留言