支持向量机(svm).pptx

支持向量机支持向量机Support Vector Machine 姓名：xxx 日期:2016-1-9目录目录n统计学习理论n推广性的界n结构风险最小n支持向量机基础统计学习理论统计学习理论支持向量机方法是建立在统计学习理论的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 S2S3S4.S。使各子集能够按照VC维的大小排列，即：h1=h2=h3=0为Lagrange乘子。为求函数的最小值，分别对w、b、i求偏微并令他们等于0，于是有：支持向量机基础为求函数的最小值，分别对w、b、求偏微并令他们等于0，于是有：可以将上述求最优面的问题转化为对偶问题：支持向量机基础支持向量机基础这是一个二次函数寻优的问题，存在唯一的解。若a*为最优解，则有：式中 为不为零的样本，即支持向量。是分类阈值，可由约束条件解上述问题后得到的最优分类函数为支持向量机基础线性不可分情况核函数的引入 低维不可分问题高维未必不可分支持向量机基础一个简单的例子二维平面中分类曲线为椭圆（线性不可分）支持向量机基础两维向三维的映射：在三维空间中线性可分分类面：根据支持向量机求得决策函数为支持向量机基础高维空间中支持向量机得出的决策函数可改写成：因此得出一般的情形：对于线性不可分的样本，作一个低维到高维的映射，使之在高维的空间中线性可分，在高维空间中采用最大间隔标准得出决策函数，由于巧妙的选取核函数，决策函数中在计算内积时只需换成核函数即可决策函数中在计算内积时只需换成核函数即可。优点：由于核函数的特性，只需计算低维空间内积，而无需计算高维空间的内积，因此计算量与样本维数无关，只与样本数有关与样本维数无关，只与样本数有关。参考文献支持向量机分类与回归方法研究作者：孙德山支持向量机的理论与算法研究王国胜支持向量机中若干优化算法研究邵小建支持向量机理论与算法研究综述丁世飞统计学习理论许建华谢谢！