支持向量机简介

支持向量机简介主要内容SVM的理论基础相关基础知识线性支持向量机的求解非线性支持向量机——核方法算法归纳关于SVM思想：通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。途径：构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题(constrainedquadraticprograming),求解该问题，构造分类超平面，从而得到决策函数。SVM的理论基础传统机器学习方法的经验风险最小化原则统计学习理论的结构化风险最小化原则VC维泛化误差的边界经验风险最小化原则ERM传统的学习理论主要是基于经验风险最小化原则（ERM）的。学习机器的预测输出的期望风险可以表示为：•在训练过程中，输入与输出组成训练样本(x，y)，提供给学习机器。在测试过程中，训练后的学习机器对于输入x给出预测输出。•a为广义参数（所有参数的集合）。•预测输出可表示为•为损失函数，用来衡量两个变量之间的不一致程度。•因此，机器学习问题也可以表示为，从一组独立同分布的观测样本出发，通过最小化风险泛函R(a)，确定学习机器的广义参数a的过程。最小化期望风险R(a)，必须利用联合概率F(x,y)的信息。在实际中，联合分布未知，只有观测样本。用算术平均值逼近期望风险。•由于Remp(a)是用已知的训练样本（经验数据）定义的，因此称为经验风险。•用经验风险Remp(a)最小化来代替期望风险R(a)最小化，来求出学习机器的参数a的方法----经验风险最小化原则ERM。多年来，经验风险最小化原则作为解决模式识别等机器学习问题的基本思想，几乎统治了这个领域内的所有研究。理论表明，当训练数据趋于无穷多时，经验风险收敛于实际风险。因此经验风险最小化原则隐含地使用了训练样本无穷多的假设条件。复杂度高的学习机器，往往具有较低的经验风险。因此，经验风险最小化原则的结果，将使学习机器变得越来越复杂。因此，如何根据实际问题，在学习机器的经验风险和模型复杂度之间取得合理的折衷，从而使学习机器具有更高的泛化性能，是非常重要的问题。VC维统计学习理论是关于小样本进行归纳学习的理论，其中一个重要的概念就是VC维（Vapnik-Chervonenkisdimension）。模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散。函数集的VC维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。VC维VC维反映了函数集的学习能力。一般而言，VC维越大则学习机器越复杂，学习容量越大。一般地，对于n维空间Rn中，最多只能有n个点是线性独立的，因此Rn空间超平面的VC维是n+1。Rn空间中的超平面共有n+1个独立的参数，恰好等于VC维数。在非线性情况下学习机器的VC维通常是无法计算的，通过变通的办法巧妙地避开直接求VC维的问题。泛化误差的边界统计学习理论从VC维的概念出发，推导出了关于经验风险和实际风险之间关系的重要结论，称作泛化误差的边界。Remp(a)表示经验风险；Ψ(h/l)称为置信风险；（置信范围，VC信任）l是样本个数；参数h称为一个函数集合的VC维。当h/l较大时，置信风险较大，此时用经验风险近似期望风险就会出现较大的误差。如果样本数较多，使得h/l较小，则置信风险就会较小，经验风险最小化的最优解就会接近真正的最优解。对于一个特定的学习问题，当样本数固定时，如果学习机器的VC维越高（复杂度越高），则置信风险越大，导致真实风险与经验风险之间可能的差就越大，因此设计在设计分类器时，不但要使经验风险尽可能小，而且要控制其VC维也尽可能小，从而缩小置信风险，使期望风险最小。-SRM结构风险最小化原则SRM“结构风险最小化原理”的基本想法：如果我们要求风险最小，就需要使得不等式中两项相互权衡，共同趋于极小；另外，在获得的学习模型经验风险最小的同时，希望学习模型的泛化能力尽可能大，这样就需要h值尽可能小，即置信风险最小。如果固定训练样本数目l的大小，则控制风险R(a)的参量有两个：Remp(a)和h。(1)经验风险Remp(a)依赖于学习机器所选定的函数f(a,x),这样，我们可以通过控制a来控制经验风险。(2)VC维h依赖于学习机器所工作的函数集合。为了获得对h的控制，可以将函数集合结构化，建立h与各函数子结构之间的关系，通过控制对函数结构的选择来达到控制VC维h的目的。支持向量机通过最大化分类边界以最小化VC维，也即在保证经验风险最小的基础上最小化置信风险，从而达到最小化结构风险的目的，因此支持向量机方法实际上就是结构风险最小化思想的具体实现。分类空间最大，置信风险最小，经验风险越逼近真实风险主要内容SVM的理论基础相关基础知识线性支持向量机的求解非线性支持向量机——核方法算法归纳相关基础知识1.分类问题2.两类可分问题的线性分类机3.求解线性分类问题的优化方法（拉格朗日乘子）4.对偶理论1、分类问题设有两类模式C1和C2，N221y,y,y,NXXXT1sgnXg为符号函数，称为决策（分类）函数。是从模式C1和C2中抽样得到的训练集，其中MnRX1-,1ny寻求RM上的一个实函数集，对于任给的未知模式，有120,0,gCgCXXXX或者12sgn1,sgn1,gCgCXXXX当g(x)为线性函数时，称为线性分类机，当g(x)为非线性函数时，称为非线性分类机。2、两类可分问题的线性分类机对于线性可分的两类模式C1和C2，能够准确将其分开的直线不是唯一的。假设，已知分类线l的法线矢量为w0，则分类线的表达式为：000gbXWXg(x)到原点距离为00bW直线l1和l2与分类线l之间的间隔距离为k，则这两条边界线的表达式分别为：100200::lbklbkWXWX寻找最大带宽的问题，转化为寻找g(x)使k达到最大的问题了。取0kWW0bbk直线l1和l2的表达式可改写为：0kWW12:1:1lblbWXWX当k增大时，变小。因此，寻找最大带宽k的问题，就转化为寻找||w||的问题。为了计算上的方便，取目标函数为1/2||w||。对于任意学习样本（Xn,yn）,其分布必然在直线l1之上或直线l2之下。121;1,1;1,nnnnnnnngbyCgbyCXWXXXWXX合并后为：1nnybWX在选择分类线的过程中，上式对于任何学习样本都必须成立。在此前提下寻找最宽边界的问题，最后可以表示成一个约束优化问题：2,1min2..1,1,2,,bnnstybnN因此，总结出两类分类机算法：3、求解线性分类问题的优化方法上式只涉及到变量w的二次关系||w||，因此是一个二次规划问题。二次规划问题有唯一的最优解，不存在局部最优，这是本算法的突出优点。最优化问题的基本概念：（1）无约束问题全局最优的充分必要条件：（2）二维等式约束问题：*0fX0,..,min2121xxcctsxxffXX21,0:xxffclXX空间曲线**00fccXXX得到约束问题解的条件为；引入Lagrange乘子α，构造Lagrange函数XXXcfL,在X*约束问题解的条件可以表达为****,***0,*0LfcLcXXXXXXXXXX归纳出“一般约束问题”qppicpictsxxxfiiMTM,,2p,10,,2,10..min21XXRXX的必要性条件：**,***0*01,2,,*01,2,,*01,2,,**01,2,,TiiiiiLfcipcipppqipcipXXXΑΑXΑXCXΑXXX，，此条件也称为“KKT条件（Karush-Kuhn-Tucher条件）”。实际上，对于凸一般约束问题，(4-17)式条件就是充分必要条件。4、对偶问题（1）原始问题与对偶问题（2）Wolfe对偶问题主要内容SVM的理论基础相关基础知识线性支持向量机的求解非线性支持向量机——核方法算法归纳线性支持向量机的求解两类可分情况两类线性可分的支持向量机问题是一个二次规划问题（目标函数上多了一个平方），满足强对偶性条件如下：上式中：约束条件的意思就是要保证每个学习样本都能够被正确分类。总共有N个学习样本，相应地就有N个约束表达式。用表示Lagrange乘子，则上式的Lagrange函数为2,1min2..10,1,2,,bnnstybnNTN21A1,0n2121121111,,121212NnnnnNNnnnnnnNNNnnnnnnnnnLbybybybyWAWWXWWXWWX线性支持向量机的求解两类可分情况求解过程如下：（1）求对偶函数令得到：带入前式化简得：（2）由求解Lagrange乘子令：可以解出所有的Lagrange乘子,,,min,,MbLbLbWRRWAWA,,0,,0bLbLbWWAWA1100NnnnnNnnnyyWXNnnNnNkknknknXXyyAbWL11121),,(0,,1,,max,,nnLbWAn1,,101,2,,NnkknknkLbyynNWAXXN,,,21线性支持向量机的求解两类可分情况（3）解出分类函数g(X)的法向矢量W：（4）由所对应的学习样本是支持向量，它们恰好位于分类边带线上，其余与对应的约束条件中的样本点，都位于上边带之上或下边带之下，这些点的存在并不影响分类函数的位置。可求出：把求出的W,b带入分类函数表达式，可得最后的分类函数为：1NnnnnyWX0nnny,X0k1l2l1NkkknnnknbyyyWXXXkNnknnnNnnnnyyyg11,,XXXXX主要内容SVM的理论基础相关基础知识线性支持向量机的求解非线性支持向量机——核方法算法归纳非线性支持向量机——核方法特征空间的非线性映射和核函数（1）首先来看一个例子。（2）核函数：,其中是核函数,(,)是内积,Φ是从输入空间到高维特征空间H的非线性映射.从而实现了把低维输入空间中的非线性可分问题转化成了高维特征空间H中的线性可分问题,并且巧妙地解决了在高维特征空间H中计算的“维数灾难”等问题.（3）常用的核函数：多项式：径向基：双曲正弦：,傅立叶核、样条核jijiKXXXX,jiKXX,nRnRpK1YXYX2YXYXeKYXYXtanhK非线性支持向量机——核方法利用核函数的方法，两类非线性可分问题转化成了线性问题，其相应的分类函数为：与线性可分类问题的区别在于，将其中的点积运算换成核函数运算（以Gaussian径向基函数为例）kNnknnnNnnnnyKyKyg11,,XXXXXMmjmimjMiMjijijixxxxxxxx12211XX