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

我有一片天

和夏花一起绚烂

 
 
 

日志

 
 

SVM  

2010-11-04 17:18:03|  分类: 压缩感知CS |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
转自sjtu,hengluo:
转自sjtu hengluo:
Solu兄要我写点什么,可实在知道的很少,只好写写自己看书看论文的经过。 所以这一切是从SVM开始的。我喜欢通过一些直观的东西理解,所以下面的讨论就集中在二 类问题上(y=-1 or +1),并且样本数据是二维的(X=(x1,x2))。平面上的点的二分类问 题。我们的目标是从一堆训练数据(比如L个(xi,yi)对,这里还要做限制,就是这些数据是 来自一个潜在分布,并且相互之间是独立的,这些限制对于Vapnik证明的那些界是必要的 )中学到一些什么,我们把目标再定低一点,希望学到给定样本数据Xt,如何推出它的类别 Yt。 该如何处理这种问题呢?一种简单的方法就是我们假定这些数据(或其背后的分布)来 自于(或者足够接近)某个候选模型集,这样问题就进一步简化了,变成了一个搜索问题 (如何在某个候选集中选一个模型使得其能够较好地解释训练数据)。看来好像问题已经 简化得很厉害了,但这里还有两个问题,首先到底在一个什么样的模型集中搜索,其次什 么是“比较好的解释”,前者是模型复杂度的问题,也就是正则化的问题,后者则是损失 函数的问题。(当然这里还有很多很多的问题,如先验知识、数据中是否有噪声、样本数 据的各维中是否有冗余是否相关等等)。 我们先看看模型复杂度,无论是奥姆斯剃刀理论还是“杀鸡焉用宰牛刀”都告诉我们, 对于简单的问题不要用太复杂的方法。但标准是什么呢?如何分辨指甲刀和西瓜刀呢?通 常我们要看这把刀能干什么(并且是至多能做什么)。这里要解决的问题是分类,那么要 看的就是一个模型集的分类能力(给定某个样本数据x,给出其相应的类别,也就是说所谓 “分类”可以看作对样本数据的解释)。VC维就是描述这种能力的一种度量。一个模型集 是由很多模型组成的,每个模型可以对样本数据做出一种解释(也就是给定任意样本数据 使用该模型可以给出一个确定的类别),一个模型集的VC维是一个正整数,表示使用这个 模型集可以“至多”“任意”解释的样本数据的个数。例如一个模型集的VC维是3,就表示 这个模型集可以“至多”“任意”解释3个样本数据,所谓“任意解释”,就是给定3个样 本数据(x1,x2,x3),我们可以在这个模型集中找到2^3=8个模型,每个模型分别 给出不同的类别给这3个样本数据(如,模型f1将x1,x2,x3,分类为-1-1-1,f2为-1-1+1,.. .,f8为+1+1+1),所谓“至多”就是我们只能“找到”(也就是说不要求任意3个样本数据 可以被任意解释)3个样本数据被任意解释而无法找到4个。 VC维的意义主要 是在概念上而非计算上,因为通常很多模型的VC维都是无法求得的。 但也有一些特殊的模型集的VC维是可以直接求得的,比如n维空间的所有“超平面”的 VC维就是n+1。我们回到上面的问题设定,我们考虑2维平面上所有的直线组成的模型集( 易见每条直线都可以将整个平面分为两部分,+1类,-1类,线上的部分可以随便 算到+1类或-1类),我们发现我们可以很容易找到3个点(样本数据),只要这3个点不共 线,我们便可以找到8条直线给出这3个点的所有的类别可能。但 4个点却无法找到,可以 证明n维空间的所有超平面的VC维就是n+1。 这样一来使用超平面就可以方便的控制模型的复杂度,但这里存在一个问题,那就是这 里的VC维是与样本数据的维数相关的,这为后面使用核方法就造成了困难。所以考虑另一 种相近的模型集,这个模型集里的模型是一个个“超平板”--带有确定厚度的 超平面,每个“超平板”将空间分为两部分,自己再占一部分,自己占的这部分不做解释 (拒绝分类)(由于VC维是能够“找到”若干个样本,所以尽管不是对整个样本空间进行 解释,但并不影响VC维的计算。那这样做影响了什么呢?这是个问题)。并且Vapnik 证明了这个板的厚度是这个模型集的VC维的上界,从而控制模型集的复杂度可以通过控制 板的厚度来实现。这是一个重要的进步,这个模型集的复杂度与样本数据的维数无关了, 也使得SVM使用kernel trick成为可能。 为什么厚的板的VC维就小呢?Learing with kernels里面有个很好的图。简单起见,我 们去掉超平面的那个常数项,考虑2维平面,也就是所有的超平板都过原点,假定样本数据 都分布在半径为R的以原点为圆心的圆内,可见随着板的厚度的增加,我们就没有办法再找 到3个点能够被任意解释了。也就是说尽管在一个很高维的空间我们仍旧可以通过控制板的 厚度,使得我们的模型集的复杂度不是很大。(但这里有对数据分布的限制,那个R,这会 造成什么问题呢? 这是个问题)。 这个板的厚度也就是通常提到的分类面的margin,对于这个margin还有很多其他的解释 ,如margin引入了robust啊等等,但我觉得对于SVM关键是维数无关。
前面提到一个分类器的训练包含两个问题损失函数以及正则化(很多监督学习算法的目 标函数也都是不同的损失函数与不同的正则化项的组合)。前者是衡量当前候选分类器在 训练数据上的性能(对应贝叶斯方法中的似然函数),后者则是衡量当前学习器所来自的 模型集的复杂度(对应贝叶斯方法中的先验概率)。Vapnik关于分类器的推广能力的界也 就是这两部分,也就是说如果我们能在一个非常简单的模型集中找到一个分类器,使得其 能非常好地解释训练数据(具有很小的损失),那么这个分类器将会以很大的概率在未来 的数据上表现很好。这也就引出了Vapnik的结构风险最小化,所谓结构风险最小化也就是 首先确定一组嵌套的模型集(F1包含于F2。。。FN),并且随着下标的增加模型集的VC维也 随之增加,也就是从模型集F1开始模型集变得越来越复杂。我们从每个模型集中选出一个 分类器(f1,f2,...,fN),使得每个分类器均在各自的模型集中使得损失函数最小。这样 我们就同时获得上面两个问题(模型复杂度以及候选分类器在训练集上的损失)的答案。 利用Vapnik的界在模型复杂度与训练集上的表现进行折中,我们就可以找到一个最佳的分 类器了。 这个指导原则其实也可以从“奥姆斯剃刀理论(如无必要勿增实体)”来解释。 但要找到能够实现结构风险最小化的算法是很困难的,Vapnik找了二十多年(我的估计 )。最后找到了SVM,并且SVM也成了最好的分类算法之一,但戏剧化的是:SVM为什么会有 如此优异的性能却并不是前面的margin theory以及结构风险最小化所能解释的。直到今天 这个问题似乎还不是很清楚,后面我还想稍微(我知道的非常有限)提一些这方面的工作 。 实现结构风险最小化存在两个困难,首先如前面提过的大多数的模型集的VC维是无法得 到的,其次便是这一组嵌套的模型集还应当足够的复杂(也就是有足够的能力去解释复杂 的数据)。前面的一个问题使用线性模型集可以得到其相应的VC维,并且通过使用margin ,我们还可以得到一个维数无关的对于模型集的VC维的估计。后面一个问题的答案则要由 核方法(kernel methods)来回答。 线性模型集无法处理线性不可分的情况,如当年的感知器无法处理异或问题,从而使得 神经网络沉寂多年。所谓异或问题,假设4个样本点,+1类为点(1,1)和点(-1,-1),-1类为 点点(-1,1) 和点(1,-1),可见从所有2维平面上的直线中寻找,我们也无法找到一条直 线能够解决到这样的问题(使得两类样本分别在直线的两侧)。 为了能够处理线性不可分的情况,我们把样本数据映射到更高维的空间去(x->ph(x), 简单起见,我们假设x在d维欧氏空间,ph(x)在D维欧氏空间,D>d,ph(x)所在的空间常被 称之为“特征空间”),这时有个Cover's Theorem,这个定理保证在维度越高数据越可能 是线性可分。也就是我们将在这个高维空间寻找超平面,希望这个超平面能够分类训练数 据(使得两类样本分别在直线的两侧)。但空间的维数越高,所使用的超平面集的VC维就 越大。但这时上面的margin theory就可以发挥作用了,我们不使用超平面,而使用超平板 集,只要这些板的厚度足够,我们依旧可以控制模型集的VC维(复杂度)。 那么直接使用某个函数ph(.)进行映射,之后在ph(.)的空间中寻找最厚的并且能正确分 类训练数据的超平板,不就可以了吗?困难之处在于,由于往往我们需要将训练数据映射 到相当高维的空间(比如手写数字识别中使用5阶多项式就相当于将数据映射到了一个10^ 10的高维空间),从而使得计算具体的ph(x)变得非常困难。 无论“奥姆斯剃刀理论”或者“没有免费的午餐(凡事都要付出代价)”,都告诉我们 别做多余的事,仔细研究我们面临的问题(将数据映射到高维空间,寻找具有最大厚度的 超平面,使用这个超平面对将来的数据进行分类),我们其实不需要高维空间数据具体的 值(即我们不需要确切的ph(x)),我们只需要知道的是任意两个输入空间的数据Xi与Xj映 射到高维空间后他们之间的内积(也就是 < ph(Xi), ph(Xj)>,内积是一个标量,可以看 作是两个向量,ph(Xi)与 ph(Xj),之间的相似程度)。并且我们发现数学中有一类双变元 函数就具有这样的特性(k(Xi, Xj)= < ph(Xi), ph(Xj)>),这样一来我们就不需要去考虑 具体映射(ph(x))的形式了,我们只需要知道通过使用核函数(前面的那个双变元函数) 就可以得到数据被映射到高维空间后的内积。 这样一来,只要一个学习算法只需要知道数据间的内积,那么他就可以通过使用核函数 从而被核化,从而就有了核PCA,核LDA等等一大批kernel methods,也成就了Scholkopf, Smola等人。 仍旧是“没有免费的午餐”,我们不去求具体的映射(ph(x)),那么我们付出的代价 是什么呢?不知道具体的映射,仅知道任意向量间的内积,使得我们无法知道向量与原点 的关系,但这一点对于我们寻找超平面划分数据是没有影响的。 至此SVM产生所面临的困难全被扫除了。有趣的是关于核函数的文章是1990发的,92年 Vapnik提出了SVM,不知kernel trick是不是老瓦的最后障碍。 放假在家手边资料很少,所以很多都是信口开河,大家要有所警惕啊
  评论这张
 
阅读(493)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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