Topic:simple is the best V.S. no free lunch——SVM V.S. other models

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

今天听一个讲述SVM(Support Vector Machine)模型与其他模型区别的讲座,这里整理如下:(主要参考书籍是bengio先生的《deep learning》还有周志华老师的西瓜书《机器学习》)

svm的思维还是很bug(这里是闪光点的意思,惊艳)的,解决问题的角度啊,很吸引人,很神奇的思维,有很直观的视角和很严格的数学基础。svm的反其道行之的思想太好了,其他模型,想分的好,,,都是试图让模型的capacity变大(这里capacity指:样本数据),SVM恰恰相反,SVM的精髓是simple is the best,而其他的是 no free lunch。

一、初始阶段

咱今天主题是讨论两大高手的对决,第一大高手,叫做no free lunch,分类在他的眼中,很简单。有一堆样本x1~xN,,有一堆类别标号1~K,这个高手眼中的分类,是寻找一个函数f,使得f(x)约等于他的类别标号。于是,他开始寻寻觅觅这个函数,究竟是啥样的。

{x=x1,x2,x3,x4.....xn}--------f(theta)---------->{y=1,2,3,4,5.....k}

第一个念头就是,线性函数啦,这是最简单的关系,于是,他希望:每一个yi 都能等于一个<a,xi>+b,所以他的函数,拟定为f(x;theta)=<a,x>+b, 其中a,b控制着这个线性函数的(斜率与截距),所以他的目的呢,就是,给定一堆x1~xn 以及对应的y1,~yn,来得到这个斜率和截距,使得 sum_i yi- f(xi;theta)最小,这样的斜率和截距就是能够分类这组数据的斜率和截距。其中,theta={a,b},表示整个模型种参数集合,在他的线性函数里面,那就是斜率和截距。那么究竟为什么先考虑线性关系,这是没有原因的,因为高手就想这么简单,因为简单,所以采用。

二、进阶:广义线性模型

总之这段大家要理解,分类=求函数,在初期,这位高手,用线性关系,就能做很好的分类任务了,给定一组(x,y) ,他就能求对应线性函数的斜率和截距,来进行分类,所向披靡,但是,外界困难重重,忽然有一天,他发现,很多分类问题,他的武器失效了,有很多分类的映射关系,并不是线性的,所以这把武器就用不上了,于是,他开始潜心研究新的武器,研究的新的武器,就是,广义线性模型:

f(x)=ax^2+bx+c=(a,b)(x^2;x)+c

这样一个模型,仍然能写成f(x)=a(x)+b这样的形式,但是此时的x,已经变成了(x^2;x)这样的方式了,这个就叫做,多项式意义下的广义线性函数,把线性函数,变成高次非线性函数,来完成模型的能力的提升。那么问题来了:拟合都用多项式函数逼近么 有没有考虑指数函数 或对数函数之类的?这时候他还比较笨,还没有考虑。

这个高人,从线性模型,利用升幂次来得到广义线性模型,又成功称霸了分类,于是,他为了防止敌人破解,又在研究其他的类似的函数武功。于是,他看到了一本武林秘籍:神经网络。他发现,y=<a,x>+b 在神经网络里,多了一个东西,那个东西就是他缺少的,就是一个非线性函数,在神经网络里,一个基本的运算单元,叫做神经元:y=S(<a,x>+b)这个高手发现,他的线性函数,和神经元,就差了一个S(S是一个非线性函数,具体是哪个非线性函数,根据解决问题不用,其结构也不同),而引入这个非线性S,就能解决它的非线性问题,于是,他把大量的神经元,组合起来。。。。就形成了神经网络,Y=S(<A,x>+B)。没完,他这次一口气,弄了更高级的,他把Y=S(<A,x>+B)这个进一步发展,变成Y=U*S(<A,x>+B),把非线性的,再经过一个他的线性,然后他发现这样的形式,Y=U*S(<A,x>+B) :f(x)->y,能够逼近,一切的f,换句话说:他已经完全解决了分类问题了,回到开头,分类的任务是找到一个f,满足f(x)=y,现在如果f的形式为Y=U*S(<A,x>+B)。就能包罗万象。

这里的模型:

y=ax+b;             (1)线性模型

y=s(ax+b);            (2)加入非线性函数,此时模型是非线性的

y=a'(s(ax+b))+b';                 (3)再加入一个线性变换解决分类问题

所以此时,这个函数里面需要确定的就是,2个斜率,2个截距,就能确定这个f,也就是决策函数。全局逼近的意思是:给定一个误差e总能找到|f-f(theta)|<e。不要U能否实现全局逼近呢?不能。那不是可以嵌套无数层 斜率 和截距的 表达式?可以,这就是深度。因为u是非线性函数,不能讲括号打开,乘不进去。

刚才讲到高手发明出来嵌套,这里重新说一下,(1)中是最初阶段的高手,这里线性函数,a,b分别是斜率和截距,(2)是进阶高手,还是a,b,但是多了一个确定的非线性已知函数S。(3)是终极高手,就是把第一阶段和第二阶段,合起来了,练就终极阶段,其实就是嵌套,当他发现,这个函数,能够逼近一切函数的时候,他就功成名就了,似乎终结了。但是,逼近有个代价,如果逼近的函数越复杂,y=a1(s(a2*x+b2))+b1,   a1,a2,的维度就要相应增加,换句话说就是模型的(宽度,特征维度)太高,他的核心思想就是:no free lunch,如果你要逼近复杂的函数,,,我就要增加维度
越复杂,我越要加,没有轻轻松松就能让你逼近很好的函数,没有免费午餐,是这个高手的宗旨,但是问题来了,维度越高,,就会产生维数灾难,其次,维数越高,对应的a,b里面的数值就越多,例如一个n维度的a,就有n个值,当维度很高的时候,例如10000维,那等价于我要求,10000个未知数,而如果你提供的(x,y)都小于10000,那么我就不可能求出来10000个未知数(欠定问题),换句话说,要练神经网络的武功,却没有足够的基础(样本不够,数据少),,,
你就练不了,非常容易走火入魔,这下这个高手慌了,旗下弟子走火入魔无数,核心原因就是,他们自身的训练样本的基础,不足以学习这门高深武功,于是走火入魔死了。那就是说神经网络对应超定问题,对应过拟合,不适合小样本,这个函数需要的训练样本比实际所求数据的纬度要高。

三、终极阶段

高手的弟子,由于基础不够,没有那么多训练样本,来学习这个神功,使得这个no free lunch的神话,渐渐消失,不断提升复杂度来吃午饭,让很多人走火入魔饿死了的时候,在地球的另外一端,来了个另外一位高人,叫支撑矢量机(SVM),他的世界里:最简单的才是最好的,他提出了另外一种分类的思想,回顾刚才的思路,是找一个f,将,x映射到y,通过调整f的参数,来让这个映射更接近,而支撑矢量机的思路不一样,他把分类建立成如下的模型: 两类能分开,那么,中间一定有个分类界面,将这两类分开,他的思想就是,用一个函数g(x)去对这个分类界面进行表示。使得一类g(x)>0,另外一类g(x)<0,来实现分类的目的,有了这个想法,,,这个高手就贯彻最简单是最好的思想,什么样的分类界面最简单呢:当然是一条直线最简单了,于是,,g(x)=ax+b
还是我们熟知的这个线性模型,但是此时g(x)不再是映射到y的思想,而是去逼近分类面的思想。关于g(x):二维是个线,高维都是超平面,总之是个线性的面。这个高手有了用函数去确定分类面的思想,就开始去想办法找到这个分类面,他的想法在这里,对于一个分类问题,其实能分开的面很多,但是,他希望找到一个面,能够让这两类的距离最远,就是找最大的边界,使得两类的距离最大,而g(x)=ax+b ,a是啥?a就是超平面的法向量了,于是,他要最大化这个间距,就等价于这样的式子:

min_<a,b> 1/2*||a||2    s.t.  yi(<a,xi>+b)>=1, i =1,.....n            (4)

这样的式子,来找到这样的超平面a,和b。约束部分的意思想说明:主要是让正样本计算结果为正,负的负。最小化距离是:两个平面的距离,看来大家解析几何都忘光了,哈哈,需要的知识就是解析几何,两个平面的距离,如果两个平面平行,距离=2/||a||。

四、bug阶段

这个高手进一步发现,其实这个超平面,总是由一些边界的样本x,形成,毫无例外,给这些形成超平面的样本,起了个名字:叫做支撑矢量,很明显,2点确定一条直线。也就是,我要确定一个直线,只需要2个样本,就足够了。他又一次应验了,simple is the best。于是呢,,,这个法向量a呢,总是由x的线性组合来表示a=sum_i wi*xi。于是,代入刚才的方程

g(x)=a'*x+b=x'sum_i wi*xi +b =sum_i wi*x'xi +b       (5)

其中a'表示向量a的转秩。x'同a‘。

这就是一个完全的代换,变成这样的方式,把求a,b,变成求w,b,模型没有变,还是个线性的

g(x)=<w,(x)>+b,只不过,这个x变成了x'*x.这一项,还是个线性的,可以看到,,,,由于2点确定一条直线,所以,要估计g(x),,,只需要2个样本每类,就能,2类就是4个样本,就能确定这个g(x)。极大的减少了需要的基础,完全是最简单的是最好的,一切非线性函数,一定是大于2个才能确定,这就是精髓之一,,最最核心的一个,,,用极度少量的“训练支撑矢量(样本)”就能完成函数的估计。那两平面还有其他的划分的方式么?怎么划分都没有直线好。直线是最简单的。如何找“训练支撑矢量(样本)”?求上面(4)优化。

五、精髓bug

可以看到,SVM这个高手,训练一个用于分类的函数,仅仅需要“2个”样本,而第一个高手神经网络,要大量的样本,所以SVM,走上了武林巅峰,但是遗留下来一个问题,这里,SVM都是线性可分,都是线性问题,高手PK,都是非线性问题,怎么办,这里,SVM无能为力,但是,他给了一个很巧妙地思路,他的思想就是,,我能用最简单的方式,解决某个空间内的线性可分问题,如果你的空间,并不是线性可分的,即x并不是线性可分的,那么,我换个空间去,,做个特征变换P(x),如果P是非线性变换,,,,那么,按照理论:永远存在这样一个P,使得P(x)是线性可分的然后有了这个基础:

 

g(P(x))=a'*P(x) +b =sum_i wi*K(x,xi)+b       (7)

就有了核函数K(x,xi)的引入,至于这个核函数究竟是什么,这个不知道,可以没有表达式。用核函数,来代替上面的,使得算法本身没任何变化,但是,等价于给x换了个空间,所以SVM也解决了非线性问题,这时候,有人就问了,那究竟是哪个非线性空间呢???这个高手说::::这个。。。。我就不知道了,,,,和你的数据有关,所以,,,SVM的分类函数的复杂度,成功转移到:找一个非线性空间的难度这个难度,其实并不亚于第一个高手补基础的难度,所以,其实这两大高手,一个是函数复杂,但是容易找到,另外一个是,函数简单,但是找不到空间,所以,其实两个算法平分秋色,这场武林PK,就告一段落了!

找不到非线性空间可以理解为找不到核函数,但是,为啥SVM很好用,就是因为,码农很多,一个一个去试,总能找到。

神经网络难点在于找函数,SVM难点在于,找空间,然后找空间相对找函数,更符合码农喜好,所以前N年,SVM占优了,因为大家都喜欢简单,这个教义的思想符合大众口味。

1997年开始SVM框架,2005年开始高端SVM,有了svm框架, 进一步就是,learning kernel, 就是找空间;有了nn(神经网络)框架, 进一步找函数。

核的优势是,算法不变,变换函数不需要知道。

后话准则:1)没有标准下任何算法都一样。

2)用排列组合的方式解释深度,会有不一样的收获。

最后,感谢文博。如有理解偏差处,请指正。

 


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: 机器学习 | 标签: , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。