欢迎来到Doc100.Net免费学习资源知识分享平台!
您的位置:首页 > 程序异常 >

【svm学习札记】svm_理论基础3

更新时间: 2014-05-17 12:21:25 责任编辑: Author_N7

 

【svm学习笔记】svm_理论基础3

回顾一下上文的思路,对于线性可分问题,我们可以用超平面将训练样本分开。但是通常超平面有很多个,我们选择距离两类样本点几何间隔最大的那个,这样能够使得模型错误率的“上界”最小。而这个问题,有进一步的转化为求超平面法向量||w||的值最小的问题。好,今天就从这里开动。


【线性可分问题 之 问题转化 之 凸二次规划】


||w||表示向量w的“范数”,最常用的是二阶范数,怎么算呢?就是把向量w中的每个元素都平方,再求和,然后再开二次方根。嗯,我们从前在学习高数的时候经常算类似的东西,虽然我现在也想不起来高数到底学什么了,呵呵。那其实这个问题很简单啊,让w中的每个元素都取值为零,则计算出的结果为零,最小啊。这时候w表示原点。怎么回事?有地方不对。


是由地方不对,我们忘了要这个超平面干什么了——它是用来分隔两类训练样本的,这是他的约束条件。所以,目标函数修正如下:

min              pow (||w||, 2.0) / 2

subject to    y(i) ( <w * x(i)> + b ) > 0

Sorry 我用的C的语法来描述公式。把最小化||w||转化成了最小化它的平方,在数学上是等价的,形式上却有很多好处。

通常来讲,两类线性可分样本之间都有一定的间隔(想一想,如果没有这样的间隔,那么必然两类都有样本在这个分类面上,那么这些样本如何分类呢),而我们也要把这个间隔表示在上面的目标函数中。通常,这个间隔取值为1。为啥是这个值呢?0.5行不?其实啊,个人认为啊,也行!为什么这么说呢?再回顾上一篇文章中,我们之所以要优化||w||,其实我们要优化Theta,Theta表示了样本点到分类面的几何间隔。而我们优化的方法呢,一定是固定一个几何间隔,然后来优化Theta,也就是现在的||w||。这个间隔只要是一个固定的常量值就行了,以后的数学推导,直接将它带着,对优化的方法和结果不影响。但是还有个疑问,就是如果这个值非常大,例如都超过了样本集合的最大直径(集合中两个样本点之间的最远距离),那还怎么分啊?嗯,是的。不过不同的是,那个是“几何间隔”,是经过“归一化”之后得到的;而我们现在这个1,是在归一化之前,不是一个几何意义上的距离的概念。哦,我知道还有问题,先列出公式吧。总之,加上间隔之后,目标函数修正如下:

min              pow (||w||, 2.0) / 2

subject to    y(i) ( <w * x(i)> + b ) -1 >= 0

约束条件中可以用“=”了。

回到上面那个问题,为啥不是几何距离,就可以呢?就能确保把两类样本都间隔开呢?我是这么理解的,举个例子吧:假设是在一个二维平面上,有个点是(1, 1),它和原点(0, 0)的距离很容易计算出是1;如果不是几何距离的概念,那我可以把(1, 1)进行缩放,例如都扩大两倍,得到(2, 2),则和原点的距离变为4。同样,在上面的约束条件中,也可以进行类似的缩放。我要说的是,有个间隔就好,他的值本身并不重要。如果还有问题,那么好吧,我承认在这里面我也有点糊涂。


优化上面的约束条件下的目标函数,有个专有名词,很cool,叫“凸二次规划问题”。简单解释一下。首先,上面的问题是一个优化问题,而优化问题又称为规划问题;其次,上面的目标函数是二次函数,所以叫二次规划问题;最后,上述的约束条件定义了一个凸集(集合中任意取两点连成一条直线,直线上的点依然在集合内部,想象成一个圆或者椭圆内部区域),所以又称为“凸二次规划问题”。


【线性可分问题 之 问题转化 之 支持向量机】


上面,我们遇到了这么cool的一个问题,可是怎么解呢?

回想一下我们学习的高数。对于没有约束的极值问题,我们可以求导数,并令导数等于零,求得极值。对于有等式约束的极值问题,我们利用拉格朗日乘子,转换成无条件极值问题。那么上面那个呢?是不等式的条件极值问题,咋办?凉拌,呵呵。


还得继续转化。


我们跳出来想一下,我们最终获得的模型参数是什么?是w向量和b向量。而b向量可以通过w向量来获得。(你要问,如何获得?这个我没看具体的推导,我是这样想的:如果分类器描述的是二维空间的一条直线,那么w就是斜率,b就是截距。当w确定的情况下,我们看平面上的样本点,根据样本点之间的间隔,很容易就算出最优分类线与两类样本点之间的最大间隔,也就能够唯一确定最优分类线——间隔中间的那条,也就能确定b的值了。)接着上面的思路,w是根据什么获得的呢?根据的只有训练样本,即是说,w是训练样本的函数,可以表示如下:

w = a(1)y(1)x(1) + a(2)y(2)x(2) + ...... a(n)y(n)x(n)

其中a(i)是一个实数,x(i)和y(i)分别表示样本i的特征向量和分类结果。这样,寻找优化w的问题就转换成了寻找优化a的问题,a的个数与样本数量相同。我在第一次看到这个的时候会问自己,这是不是把问题搞复杂了?其实不是,这里面绝大多数的a的值都是0;而只有那些少数不为0的a,才是模型真正的参数,才是我们将来对未知样本分类的主要考虑依据。而这些不为0的a所对应的训练样本,就是支持向量。最大几何间隔的大小就由他们来决定。

回想一下上文中超平面的定义如下:

g(x) = <w * x> + b

将w的计算方式带入之后,变为

g(x) = < {a(1)y(1)x(1) + a(2)y(2)x(2) + ...... a(n)y(n)x(n)} * x > + b

       = < a(1)y(1)x(1) * x > + < a(2)y(2)x(2) * x > + ...... < a(n)y(n)x(n) * x > + b

       = SUM_i { a(i)y(i)<x(i) * x> } + b

上面的公式中,只有x向量是变量,x(i)表示第i个训练样本,a(i)是实数,表示x(i)。同样的,可以将w带入到上面的优化目标函数中。据Jasper说,经过上面的变换,就将原来的不等式约束变成了等式约束,就得到了解析解,至此,线性可分问题就能解了。

不过我个人是没有看明白,如何就将原来的不等式约束变换成了等式约束;即便是有了等式约束,下面的故事呢?怎么搞出解析解的?Jasper在他的软文里面都没说。这也埋下了一个伏笔,我后文还要看其他的资料来了解相关的知识,这就留到svm训练算法部分来说吧。


看到这个变换,我的收获主要有以下几点:

1. 从前知道支持向量的直观几何意义,但是从代数推到上,不知道他是怎么来的;现在知道了。

2. 了解svm对新样本的分类过程了:就是找到不为零的a(i)以及相应的训练样本,与输入向量做内积,判断内积的值即可。

3. 能初窥一点儿训练过程:在对每个a(i)进行优化的时候,至少要遍历所有训练样本;参数空间受支持向量的影响很大。


这一篇先写到这里。



上一篇:上一篇
下一篇:下一篇

 

随机推荐程序问答结果

 

 

如对文章有任何疑问请提交到问题反馈,或者您对内容不满意,请您反馈给我们DOC100.NET论坛发贴求解。
DOC100.NET资源网,机器学习分类整理更新日期::2014-05-17 12:21:25
如需转载,请注明文章出处和来源网址:http://www.doc100.net/bugs/t/794695/
本文WWW.DOC100.NET DOC100.NET版权所有。