SVM的理解路线图草图——一个初学者的读书笔记
有不对的地方还请大家指正 bow
《统计学习理论的本质》 by Vapnik
函数估计模型
没有什么比用一个概率模型描述或然的现实世界更加保险的了,没有什么比用一个函数来描述一个计算过程更加有效的了.因果永远是理性思维最拿手的.X与Y的发生分别服从各自的分布,但如果(y|x)的分布特殊到某种境界,人们就会有兴趣去想象Y与X的因果关系.我们简化现实模型,将两者的关系夸张到y是x的函数的程度.目的是确定这个函数,根据任意未知的x,给出尽量接近y的预测.候选函数的集合由我们事先给定,计算机需要做的是根据已知的一些(x,y)从函数集合中选择一个尽量使得预测性能最好.
风险最小化;经验风险最小化(ERM)
最保守的风险最小化评价一定是要在真实(x,y)的概率分布下对差异积分.而真实概率分布是难以获取的,因此根据类似大数定理的思维方式,能大胆地认为在样例足够多的时候,可以用经验风险最小化的评价方法.也就是在评价时以学习样例完全代替(x,y)的真实概率分布.
一致性;VC熵
问题是这两种评价的结果是否总是在样例无穷多的时候一致地逼近最优值呢.于是有了很多与一致性等价的命题.一个重要的概念是VC熵,反映了函数集在数目为l的样本上期望的多样性.它与l的比当l趋于无穷的时候如果收敛,等价于一个"一致双边收敛"的命题.
置信范围;VC维
但无情的现实是样例数往往难以达到让我们认为它已经接近无穷多的程度,特别是在比如TC中还会遇到无处不在的Zipf定律.于是我们不得不估计样例数与两种评价结果差距的关系,这种差距叫做置信范围.由此又得到很多不等式.再引入函数集的VC维h.h刻画的是函数集肆意划分样例的能力,它也直接影响了置信范围.这种肆意划分的能力越小,说明置信范围可能越小.
结构风险最小化(SRM)
于是在l一定的时候,我们需要折中的就是选用的函数集的大小.将原有函数集表示成一个嵌套序列,使得他们的VC维h单调.首先选择风险上限(经验风险+置信范围)最低时对应的h和函数集子集,在从中选择经验风险最小的函数,这样的优化策略称为结构风险最小化.
支持向量机(SVM);支持向量
支持向量机(SVM)号称可以在保证经验风险固定较小的前提下,尽量最小化置信范围.其方法是在一个特征空间(好像要是Hilbert空间)上,找出划分两个点集的最优超平面,即使得两个点集沿该平面间隙最大.刚好落在这个间隙边上的向量叫做支持向量.这样的最大化据说就可以和置信范围最小化等价.VC维在这样的过程中是如何发生微妙变化的我还不太清楚.在两个点集不能用超平面完全划分的时候也有与此相适应的算法.推导显示求这样一个超平面,等价于求一个约束二次规划问题.
核函数
还有一个令人庆幸的事实是如果只要求训练这样的超平面并对以后的数据做划分.SVM并不需要知道样例在特征空间中的向量表达或者甚至不需要知道特征空间的维数.它只需要知道任意两个样例映射到此空间后向量的内积.而这样的内积可以在样例(训练集或测试集中的)被映射成某个不可琢磨的特征空间中的向量之前被计算出来,完成这样计算的函数叫核函数.即使样例到特征空间的映射关系都不知道,只要该核函数满足伟大的Mercer定理,这样的特征空间就总能存在,SVM就能工作.
《统计学习理论的本质》 by Vapnik
函数估计模型
没有什么比用一个概率模型描述或然的现实世界更加保险的了,没有什么比用一个函数来描述一个计算过程更加有效的了.因果永远是理性思维最拿手的.X与Y的发生分别服从各自的分布,但如果(y|x)的分布特殊到某种境界,人们就会有兴趣去想象Y与X的因果关系.我们简化现实模型,将两者的关系夸张到y是x的函数的程度.目的是确定这个函数,根据任意未知的x,给出尽量接近y的预测.候选函数的集合由我们事先给定,计算机需要做的是根据已知的一些(x,y)从函数集合中选择一个尽量使得预测性能最好.
风险最小化;经验风险最小化(ERM)
最保守的风险最小化评价一定是要在真实(x,y)的概率分布下对差异积分.而真实概率分布是难以获取的,因此根据类似大数定理的思维方式,能大胆地认为在样例足够多的时候,可以用经验风险最小化的评价方法.也就是在评价时以学习样例完全代替(x,y)的真实概率分布.
一致性;VC熵
问题是这两种评价的结果是否总是在样例无穷多的时候一致地逼近最优值呢.于是有了很多与一致性等价的命题.一个重要的概念是VC熵,反映了函数集在数目为l的样本上期望的多样性.它与l的比当l趋于无穷的时候如果收敛,等价于一个"一致双边收敛"的命题.
置信范围;VC维
但无情的现实是样例数往往难以达到让我们认为它已经接近无穷多的程度,特别是在比如TC中还会遇到无处不在的Zipf定律.于是我们不得不估计样例数与两种评价结果差距的关系,这种差距叫做置信范围.由此又得到很多不等式.再引入函数集的VC维h.h刻画的是函数集肆意划分样例的能力,它也直接影响了置信范围.这种肆意划分的能力越小,说明置信范围可能越小.
结构风险最小化(SRM)
于是在l一定的时候,我们需要折中的就是选用的函数集的大小.将原有函数集表示成一个嵌套序列,使得他们的VC维h单调.首先选择风险上限(经验风险+置信范围)最低时对应的h和函数集子集,在从中选择经验风险最小的函数,这样的优化策略称为结构风险最小化.
支持向量机(SVM);支持向量
支持向量机(SVM)号称可以在保证经验风险固定较小的前提下,尽量最小化置信范围.其方法是在一个特征空间(好像要是Hilbert空间)上,找出划分两个点集的最优超平面,即使得两个点集沿该平面间隙最大.刚好落在这个间隙边上的向量叫做支持向量.这样的最大化据说就可以和置信范围最小化等价.VC维在这样的过程中是如何发生微妙变化的我还不太清楚.在两个点集不能用超平面完全划分的时候也有与此相适应的算法.推导显示求这样一个超平面,等价于求一个约束二次规划问题.
核函数
还有一个令人庆幸的事实是如果只要求训练这样的超平面并对以后的数据做划分.SVM并不需要知道样例在特征空间中的向量表达或者甚至不需要知道特征空间的维数.它只需要知道任意两个样例映射到此空间后向量的内积.而这样的内积可以在样例(训练集或测试集中的)被映射成某个不可琢磨的特征空间中的向量之前被计算出来,完成这样计算的函数叫核函数.即使样例到特征空间的映射关系都不知道,只要该核函数满足伟大的Mercer定理,这样的特征空间就总能存在,SVM就能工作.
有关键情节透露
