支持向量机(svm)

支持向量机SupportVectorMachine姓名：xxx日期:2016-1-9目录统计学习理论推广性的界结构风险最小支持向量机基础统计学习理论支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理上VC维统计学习理论的一个核心概念就是VC维，模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2的h次方种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是它能打散的最大样本数目h。若对任意数目的数据样本都有函数能将它们打散，则函数集的VC维是无穷的。统计学习理论反映了函数集的学习能力，VC维越大则学习机器越复杂(学习能力越强)。目前，尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。例如在N维空间中线形分类器和线性实函数的VC维是N+1。我们认为2D线性分类器的VC维是3，而不是4。即，2D线性分类器可以打散集合大小为3的样本集合，不能打散有4个样本的集合。推广性的界经验风险（Remp(w)）与实际风险R(w)之间的关系，即推广性的界。经验风险和实际风险之间至少以概率1-η满足如下关系其中，h是函数集的VC维，L是样本数。风险:与真实解之间的误差,就叫做风险，即误差的累积叫做风险经验风险：即训练误差，在样本数据中的结果与真实结果的之间的差值推广性的界注：传统的机器学习方法就是把经验风险最少化作为努力的目标，导致许多分类函数在样本中能100%正确，而在真实分类中却不行，其推广性差。上述结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)；二是置信风险。可以简单地表示为：R(w)≤Remp(w)+Ф(L/h)置信风险：我们对数据样本结果的信任程度，与样本数量L，另一个是VC维h有关。其表达式如下：Ф(L/h)=推广性的界式中表明，学习机器VC维↑，置信范围↑，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。结构风险最小在此基础上，统计学习理论提出了一种新的策略解决该问题，就是首先把函数集{f(x,a)}分解为一个函数子集序列：S1⊂S2⊂S3⊂S4⊂……..⊂S。使各子集能够按照VC维的大小排列，即：h1=h2=h3=h4………。这样在同一子集中置信范围就相同；在每一个子集中寻找最小经验风险和置信范围，取得实际风险的最小值，称作结构风险最小化(structuralriskminimization，SRM)，即SRM准则。如下图：结构风险最小结构风险最小统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。支持向量机基础SVM是从线性可分情况下的最优分类面发展而来的，其基本思想可以用二维情况说明。•分类超平面：(w.x)+b=0•判决函数：•间隔：•几何间隔：•最大间隔问题：在间隔固定为1时，寻求最小的‖w‖sgn(){1,1}iiiywxby()iiiywxbiw支持向量机基础从上图中，我们容易看出，最优化目标就是最大化几何间隔，并且注意到几何间隔与‖w‖反比，因此我们我们只需寻找最小的‖w‖，即对于这个目标函数，可以用一个等价的目标函数来替代：支持向量机基础为使分类面对所有样本正确分类并且具备分类间隔，就要求它满足如下约束：支持向量机基础优化问题：212min..[()]10(1,2,...,)iiwstywxbin为解决这个约束问题的最优解，引入Lagrange函数：式中αi=0为Lagrange乘子。为求函数的最小值，分别对w、b、αi求偏微并令他们等于0，于是有：支持向量机基础为求函数的最小值，分别对w、b、α求偏微并令他们等于0，于是有：可以将上述求最优面的问题转化为对偶问题：支持向量机基础支持向量机基础这是一个二次函数寻优的问题，存在唯一的解。若a*为最优解，则有：式中为不为零的样本，即支持向量。是分类阈值，可由约束条件解上述问题后得到的最优分类函数为支持向量机基础线性不可分情况——核函数的引入低维不可分问题高维未必不可分支持向量机基础一个简单的例子二维平面中分类曲线为椭圆（线性不可分）22112231220wxwxwxxb支持向量机基础两维向三维的映射：22121231212:(,)(,,):(,,2)xxzzzxxxx在三维空间中线性可分分类面：根据支持向量机求得决策函数为'''1122330wzwzwzb**1()sgn{()()]}liiiifzyzzb支持向量机基础高维空间中支持向量机得出的决策函数可改写成：因此得出一般的情形：对于线性不可分的样本，作一个低维到高维的映射，使之在高维的空间中线性可分，在高维空间中采用最大间隔标准得出决策函数，由于巧妙的选取核函数，决策函数中在计算内积时只需换成核函数即可。优点：由于核函数的特性，只需计算低维空间内积，而无需计算高维空间的内积，因此计算量与样本维数无关，只与样本数有关。**1()sgn{(,)}liiiifxyKxxb参考文献《支持向量机分类与回归方法研究》作者：孙德山《支持向量机的理论与算法研究》王国胜《支持向量机中若干优化算法研究》邵小建《支持向量机理论与算法研究综述》丁世飞《统计学习理论》许建华谢谢！