支持向量机简介.pptx
主要内容lSVM的理论基础l相关基础知识l线性支持向量机的求解l非线性支持向量机核方法l算法归纳 第1页/共34页关于SVM思想：思想：通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。途径：途径：构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题件的二次规划问题(constrained quadratic programing),(constrained quadratic programing),求解该问题，求解该问题，构造分类超平面，从而得到决策函数。构造分类超平面，从而得到决策函数。第2页/共34页SVM的理论基础传统机器学习方法的经验风险最小化原则统计学习理论的结构化风险最小化原则VC维泛化误差的边界第3页/共34页经验风险最小化原则ERM传统的学习理论主要是基于经验风险最小化原则（ERM）的。第4页/共34页学习机器的预测输出的期望风险可以表示为：在训练过程中，输入与输出组成训练样本(x，y)，提供给学习机器。在测试过程中，训练后的学习机器对于输入x给出预测输出。为广义参数（所有参数的集合）。预测输出可表示为为损失函数，用来衡量两个变量之间的不一致程度。因此，机器学习问题也可以表示为，从一组独立同分布的观测样本出发，通过最小化风险泛函R(a)，确定学习机器的广义参数a的过程。第5页/共34页最小化期望风险R(a)，必须利用联合概率F(x,y)的信息。在实际中，联合分布未知，只有观测样本。用算术平均值逼近期望风险。由于Remp(a)是用已知的训练样本（经验数据）定义的，因此称为经验风险。用经验风险Remp(a)最小化来代替期望风险R(a)最小化，来求出学习机器的参数a的方法-经验风险最小化原则ERM。第6页/共34页多年来，经验风险最小化原则作为解决模式识别等机器学习问题的基本思想，几乎统治了这个领域内的所有研究。理论表明，当训练数据趋于无穷多时，经验风险收敛于实际风险。因此经验风险最小化原则隐含地使用了训练样本无穷多的假设条件。复杂度高的学习机器，往往具有较低的经验风险。因此，经验风险最小化原则的结果，将使学习机器变得越来越复杂。因此，如何根据实际问题，在学习机器的经验风险和模型复杂度之间取得合理的折衷，从而使学习机器具有更高的泛化性能，是非常重要的问题。第7页/共34页VC维统计学习理论是关于小样本进行归纳学习的理论，其中一个重要的概念就是VC维（Vapnik-Chervonenkis dimension）。模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散。函数集的VC维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。第8页/共34页VC维VC维反映了函数集的学习能力。一般而言，VC维越大则学习机器越复杂，学习容量越大。一般地，对于n维空间Rn中，最多只能有n个点是线性独立的，因此Rn空间超平面的VC维是n+1。Rn空间中的超平面共有n+1个独立的参数，恰好等于VC维数。在非线性情况下学习机器的VC维通常是无法计算的，通过变通的办法巧妙地避开直接求VC维的问题。第9页/共34页泛化误差的边界统计学习理论从VC维的概念出发，推导出了关于经验风险和实际风险之间关系的重要结论，称作泛化误差的边界。Remp(a)表示经验风险；(h/l)称为置信风险；（置信范围，VC信任）l是样本个数；参数h称为一个函数集合的VC维。当h/l较大时，置信风险较大，此时用经验风险近似期望风险就会出现较大的误差。如果样本数较多，使得h/l较小，则置信风险就会较小，经验风险最小化的最优解就会接近真正的最优解。对于一个特定的学习问题，当样本数固定时，如果学习机器的VC维越高（复杂度越高），则置信风险越大，导致真实风险与经验风险之间可能的差就越大，因此设计在设计分类器时，不但要使经验风险尽可能小，而且要控制其VC维也尽可能小，从而缩小置信风险，使期望风险最小。-SRM第10页/共34页结构风险最小化原则SRM“结构风险最小化原理”的基本想法：如果我们要求风险最小，就需要使得不等式中两项相互权衡，共同趋于极小；另外，在获得的学习模型经验风险最小的同时，希望学习模型的泛化能力尽可能大，这样就需要h值尽可能小，即置信风险最小。如果固定训练样本数目l的大小，则控制风险R(a)的参量有两个：Remp(a)和h。(1)经验风险Remp(a)依赖于学习机器所选定的函数f(a,x),这样，我们可以通过控制a来控制经验风险。(2)VC维h依赖于学习机器所工作的函数集合。为了获得对h的控制，可以将函数集合结构化，建立h与各函数子结构之间的关系，通过控制对函数结构的选择来达到控制VC维h的目的。第11页/共34页支持向量机通过最大化分类边界以最小化VC维，也即在保证经验风险最小的基础上最小化置信风险，从而达到最小化结构风险的目的，因此支持向量机方法实际上就是结构风险最小化思想的具体实现。分类空间最大，置信风险最小，经验风险越逼近真实风险第12页/共34页主要内容lSVM的理论基础l相关基础知识l线性支持向量机的求解l非线性支持向量机核方法l算法归纳第13页/共34页相关基础知识1.分类问题2.两类可分问题的线性分类机3.求解线性分类问题的优化方法（拉格朗日乘子）4.对偶理论第14页/共34页1、分类问题设有两类模式C1和C2，为符号函数，称为决策（分类）函数。是从模式C1和C2中抽样得到的训练集，其中寻求RM上的一个实函数集，对于任给的未知模式，有或者当g(x)为线性函数时，称为线性分类机，当g(x)为非线性函数时，称为非线性分类机。第15页/共34页2、两类可分问题的线性分类机对于线性可分的两类模式C1和C2，能够准确将其分开的直线不是唯一的。第16页/共34页假设，已知分类线l的法线矢量为w0，则分类线的表达式为：g(x)到原点距离为直线l1和l2与分类线l之间的间隔距离为k，则这两条边界线的表达式分别为：寻找最大带宽的问题，转化为寻找g(x)使k达到最大的问题了。取直线l1和l2的表达式可改写为：当k增大时，变小。第17页/共34页因此，寻找最大带宽k的问题，就转化为寻找|w|的问题。为了计算上的方便，取目标函数为1/2|w|。对于任意学习样本（Xn,yn）,其分布必然在直线l1之上或直线l2 之下。合并后为：在选择分类线的过程中，上式对于任何学习样本都必须成立。在此前提下寻找最宽边界的问题，最后可以表示成一个约束优化问题：因此，总结出两类分类机算法：第18页/共34页3、求解线性分类问题的优化方法 上式只涉及到变量w的二次关系|w|，因此是一个二次规划问题。二次规划问题有唯一的最优解，不存在局部最优，这是本算法的突出优点。最优化问题的基本概念：（1）无约束问题全局最优的充分必要条件：（2）二维等式约束问题：第19页/共34页空间曲线得到约束问题解的条件为；引入Lagrange乘子，构造Lagrange函数在X*约束问题解的条件可以表达为第20页/共34页归纳出“一般约束问题”的必要性条件：此条件也称为“KKT条件（Karush-Kuhn-Tucher条件）”。实际上，对于凸一般约束问题，(4-17)式条件就是充分必要条件。第21页/共34页4、对偶问题（1）原始问题与对偶问题（2）Wolfe对偶问题第22页/共34页主要内容lSVM的理论基础l相关基础知识l线性支持向量机的求解l非线性支持向量机核方法l算法归纳第23页/共34页线性支持向量机的求解两类可分情况两类线性可分的支持向量机问题是一个二次规划问题（目标函数上多了一个平方），满足强对偶性条件如下：上式中：约束条件的意思就是要保证每个学习样本都能够被正确分类。总共有N个学习样本，相应地就有N个约束表达式。用 表示Lagrange乘子，则上式的Lagrange函数为第24页/共34页线性支持向量机的求解两类可分情况求解过程如下：（1）求对偶函数 令 得到：带入前式化简得：（2）由 求解Lagrange乘子 令：可以解出所有的Lagrange乘子 第25页/共34页线性支持向量机的求解两类可分情况（3）解出分类函数g(X)的法向矢量W：（4）由 所对应的学习样本 是支持向量，它们恰好位于分类边带线上，其余与 对应的约束条件中的样本点，都位于上边带 之上或下边带 之下，这些点的存在并不影响分类函数的位置。可求出：把求出的W,b带入分类函数表达式，可得最后的分类函数为：第26页/共34页主要内容lSVM的理论基础l相关基础知识l线性支持向量机的求解l非线性支持向量机核方法l算法归纳第27页/共34页非线性支持向量机核方法特征空间的非线性映射和核函数（1）首先来看一个例子。（2）核函数：,其中 是核函数,(,)是内积,是从输入空间 到高维特征空间H 的非线性映射.从而实现了把低维输入空间 中的非线性可分问题转化成了高维特征空间H 中的线性可分问题,并且巧妙地解决了在高维特征空间H 中计算的“维数灾难”等问题.（3）常用的核函数：多项式：径向基：双曲正弦：,傅立叶核、样条核第28页/共34页非线性支持向量机核方法利用核函数的方法，两类非线性可分问题转化成了线性问题，其相应的分类函数为：与线性可分类问题的区别在于，将其中的点积运算换成核函数运算（以Gaussian径向基函数为例）第29页/共34页非线性支持向量机核方法关于核函数的选取包括：核函数类别选择、核函数参数选择、二次规划参数选择常用的方法：（1）利用专家的先验知识预先给定核函数（2）在选取核函数时，分别试用不同的核函数，归纳衰减最小的核函数就是最好的核函数（3）混合核函数方法（目前选取核函数的最佳方法）最后的说明：在机器学习领域，给定了核函数，即相当于选择了：输入模式的相似测度；数据的一个线性表示一个假设函数空间正则化风险函数相关函数第30页/共34页算法归纳 用MatLab语言实现SVM分类算法的流程第31页/共34页SVMSVM方法的特点非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射;对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心;支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”(transductive inference),大大简化了通常的分类和回归等问题。第32页/共34页SVMSVM方法的特点SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:增、删非支持向量样本对模型没有影响;支持向量样本集具有一定的鲁棒性;有些成功的应用中,SVM 方法对核的选取不敏感。第33页/共34页感谢您的观看！第34页/共34页
