支持向量机(svm).pptx

1、支持向量机,Support Vector Machine 姓名：xxx 日期:2016-1-9,目录,统计学习理论 推广性的界 结构风险最小 支持向量机基础,统计学习理论,支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理上,VC维,统计学习理论的一个核心概念就是VC维，模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2的h次方种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是它能打散的最大样本数目h。若对任意数目的数据样本都有函数能将它们打散，则函数集的VC维是无穷的。,统计学习理论,反映了函数集的学习能力，VC维越

2、大则学习机器越复杂(学习能力越强)。目前，尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。例如在N维空间中线形分类器和线性实函数的VC维是N+1。,我们认为2D线性分类器的VC维是3，而不是4。即，2D线性分类器可以打散集合大小为3的样本集合，不能打散有4个样本的集合。,推广性的界,经验风险（Remp(w)）与实际风险R(w)之间的关系，即推广性的界。经验风险和实际风险之间至少以概率1- 满足如下关系,其中，h是函数集的VC维，L是样本数。,风险:与真实解之间的误差,就叫做风险 ，即误差的累积叫做风险 经验风险：即训练误差，在样本数据中的结果与真实结果的之间的差值

3、,推广性的界,注：传统的机器学习方法就是把经验风险最少化作为努力的目标，导致许多分类函数在样本中能100%正确，而在真实分类中却不行，其推广性差。,上述结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)；二是置信风险。可以简单地表示为： R(w)Remp(w)+(L/h),置信风险：我们对数据样本结果的信任程度，与样本数量L，另一个是VC维h有关。其表达式如下：(L/h)=,推广性的界,式中表明，学习机器VC维，置信范围 ， 导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要经验风险最小，还要使VC维尽量小以缩小置信范围

4、，才能取得较小的实际风险，即对未来样本有较好的推广性。,结构风险最小,在此基础上，统计学习理论提出了一种新的策略解决该问题，就是首先把函数集 f(x,a) 分解为一个函数子集序列： S1 S2S3S4. S。 使各子集能够按照VC维的大小排列，即：h1=h2=h3=h4。 这样在同一子集中置信范围就相同；在每一个子集中寻找最小经验风险和置信范围，取得实际风险的最小值，称作结构风险最小化(structural risk minimization，SRM)，即SRM准则。如下图：,结构风险最小,结构风险最小,统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小， 即结构风险最小。,支

5、持向量机基础,SVM是从线性可分情况下的最优分类面发展而来的，其基本思想可以用二维情况说明。,分类超平面：(w.x)+b=0 判决函数： 间隔： 几何间隔： 最大间隔问题： 在间隔固定为1时，寻求最小的w ,支持向量机基础,从上图中，我们容易看出，最优化目标就是最大化几何间隔，并且注意到几何间隔与w 反比，因此我们我们只需寻找最小的w ，即,对于这个目标函数，可以用一个等价的目标函数来替代：,支持向量机基础,为使分类面对所有样本正确分类并且具备分类间隔，就要求它满足如下约束：,支持向量机基础,优化问题：,为解决这个约束问题的最优解，引入Lagrange函数：,式中i=0为Lagrange乘子。

6、 为求函数的最小值，分别对w、b、 i求偏微并令他们等于0，于是有：,支持向量机基础,为求函数的最小值，分别对w、b、 求偏微并令他们等于0，于是有：,可以将上述求最优面的问题转化为对偶问题：,支持向量机基础,支持向量机基础,这是一个二次函数寻优的问题，存在唯一的解。若a*为最优解，则有：,式中 为不为零的样本，即支持向量。 是分类阈值，可由约束条件,解上述问题后得到的最优分类函数为,支持向量机基础,线性不可分情况核函数的引入,低维不可分问题高维未必不可分,支持向量机基础,一个简单的例子,二维平面中分类曲线为椭圆（线性不可分）,支持向量机基础,两维向三维的映射：,在三维空间中线性可分 分类面： 根据支持向量机求得决策函数为,支持向量机基础,高维空间中支持向量机得出的决策函数可改写成： 因此得出一般的情形： 对于线性不可分的样本，作一个低维到高维的映射，使之在高维的空间中线性可分，在高维空间中采用最大间隔标准得出决策函数，由于巧妙的选取核函数，决策函数中在计算内积时只需换成核函数即可。 优点：由于核函数的特性，只需计算低维空间内积，而无需计算高维空间的内积，因此计算量与样本维数