注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

互联网产品经理的窝

梦想社:一个人为了梦想,始终没有停下自己的脚步

 
 
 

日志

 
 

支持向量机: Maximum Margin Classifier(A)- 转载  

2011-08-01 12:44:14|  分类: 机器学习&数据挖 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

写在最前面,感谢博主的辛勤劳动,不仅博文写的清晰深刻,而且排版甚佳。

感谢~

支持向量机即 Support Vector Machine,简称 SVM 。我最开始听说这头机器的名号的时候,一种神秘感就油然而生,似乎把 Support 这么一个具体的动作和 Vector 这么一个抽象的概念拼到一起,然后再做成一个 Machine ,一听就很玄了!

不过后来我才知道,原来 SVM 它并不是一头机器,而是一种算法,或者,确切地说,是一类算法,当然,这样抠字眼的话就没完没了了,比如,我说 SVM 实际上是一个分类器 (Classifier) ,但是其实也是有用 SVM 来做回归 (Regression) 的。所以,这种字眼就先不管了,还是从分类器说起吧。

SVM 一直被认为是效果最好的现成可用的分类算法之一(其实有很多人都相信,“之一”是可以去掉的)。这里“现成可用”其实是很重要的,因为一直以来学术界和工业界甚至只是学术界里做理论的和做应用的之间,都有一种“鸿沟”,有些很 fancy 或者很复杂的算法,在抽象出来的模型里很完美,然而在实际问题上却显得很脆弱,效果很差甚至完全 fail 。而 SVM 则正好是一个特例——在两边都混得开。

好了,由于 SVM 的故事本身就很长,所以废话就先只说这么多了,直接入题吧。当然,说是入贴,但是也不能一上来就是 SVM ,而是必须要从线性分类器开始讲。这里我们考虑的是一个两类的分类问题,数据点用 x 来表示,这是一个 n 维向量,而类别用 y 来表示,可以取 1 或者 -1 ,分别代表两个不同的类(有些地方会选 0 和 1 ,当然其实分类问题选什么都无所谓,只要是两个不同的数字即可,不过这里选择 +1 和 -1 是为了方便 SVM 的推导,后面就会明了了)。一个线性分类器就是要在 n 维的数据空间中找到一个超平面,其方程可以表示为

wTx+b=0

一个超平面,在二维空间中的例子就是一条直线。我们希望的是,通过这个超平面可以把两类数据分隔开来,比如,在超平面一边的数据点所对应的 y 全是 -1 ,而在另一边全是 1 。具体来说,我们令 f(x)=wTx+b ,显然,如果 f(x)=0 ,那么 x 是位于超平面上的点。我们不妨要求对于所有满足 f(x)<0 的点,其对应的 y 等于 -1 ,而 f(x)>0 则对应 y=1 的数据点。当然,有些时候(或者说大部分时候)数据并不是线性可分的,这个时候满足这样条件的超平面就根本不存在,不过关于如何处理这样的问题我们后面会讲,这里先从最简单的情形开始推导,就假设数据都是线性可分的,亦即这样的超平面是存在的。

如图所示,两种颜色的点分别代表两个类别,红颜色的线表示一个可行的超平面。在进行分类的时候,我们将数据点 x 代入 f(x) 中,如果得到的结果小于 0 ,则赋予其类别 -1 ,如果大于 0 则赋予类别 1 。如果 f(x)=0,则很难办了,分到哪一类都不是。事实上,对于 f(x) 的绝对值很小的情况,我们都很难处理,因为细微的变动(比如超平面稍微转一个小角度)就有可能导致结果类别的改变。理想情况下,我们希望 f(x) 的值都是很大的正数或者很小的负数,这样我们就能更加确信它是属于其中某一类别的。

从几何直观上来说,由于超平面是用于分隔两类数据的,越接近超平面的点越“难”分隔,因为如果超平面稍微转动一下,它们就有可能跑到另一边去。反之,如果是距离超平面很远的点,例如图中的右上角或者左下角的点,则很容易分辩出其类别。

实际上这两个 Criteria 是互通的,我们定义 functional margin 为 γ?=y(wTx+b)=yf(x),注意前面乘上类别 y 之后可以保证这个 margin 的非负性(因为 f(x)<0 对应于 y=?1 的那些点),而点到超平面的距离定义为 geometrical margin 。不妨来看看二者之间的关系。如图所示,对于一个点 x ,令其垂直投影到超平面上的对应的为 x0 ,由于 w 是垂直于超平面的一个向量(请自行验证),我们有

x=x0+γww

又由于 x0 是超平面上的点,满足 f(x0)=0 ,代入超平面的方程即可算出

γ=wTx+bw=f(x)w

不过,这里的 γ 是带符号的,我们需要的只是它的绝对值,因此类似地,也乘上对应的类别 y 即可,因此实际上我们定义 geometrical margin 为:

γ?=yγ=γ?w

由于文章的超过了网易博文的最大长度,分成两篇。

支持向量机: Maximum Margin Classifier-转载(1) - 梦想社 - 梦想社

郁闷!~

  评论这张
 
阅读(168)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017