支持向量机(SVM)

支持向量机（SupportVectorMachine）2008-5-15OutlineSVM的理论基础最优分类面广义最优分类面非线性支持向量机SVM的主要特点SVM的研究SVM的应用支持向量机的理论基础迄今为止，关于机器学习问题还没有一种被共同接受的理论框架，关于其实现方法大致可以分为三种:（1）经典的（参数）统计估计方法。如模式识别、神经网络等。现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性：它需要已知样本分布形式；它研究的是样本数目趋于无穷大时的渐近理论。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。支持向量机的理论基础（2）经验非线性方法。如人工神经网络（ANN）。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。（3）统计学习理论（StatisticalLearningTheory或SLT）。它是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题（比如神经网络结构选择问题、局部极小点问题等）。支持向量机的理论基础1992年—1995年，VladimirN.Vapnik在这一理论基础上发展了一种新的通用学习方法──支持向量机（SupportVectorMachine或SVM），在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。一些学者认为，SLT和SVM正在成为继模式识别和神经网络研究之后新的研究热点，并将推动机器学习理论和技术有重大的发展。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小化（SRM）原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(GeneralizationAbility)。支持向量机的理论基础1.期望风险最小化机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计,使它能够对未知输出作出尽可能准确的预测.机器学习问题可以表示为：根据n个独立同分布的观测样本1122(,),(,),,(,)nnxyxyxy（1）在预测函数集{(,)}fxw中寻求一个最优的函数0(,)fxw，使得预测的期望风险()(,(,))(,)RwLyfxwdFxy（2）最小。其中w为函数的广义参数，(,)Fxy为x和y之间未知的联合概率，即x和y之间存在一定的未知依赖关系。支持向量机的理论基础1.期望风险最小化(,(,))Lyfxw为用(,)fxw对y进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。预测函数通常也称作学习函数、学习模型或学习机器。模式识别问题中，损失函数的定义为：0(,)(,(,))1(,)yfxwLyfxwyfxw（3）支持向量机的理论基础2.经验风险最小化在上面的问题表述中,学习的目标在于使期望风险最小化,但是,由于我们可以利用的信息只有样本(1),(2)式的期望风险并无法计算,因此传统的学习方法中采用了所谓经验风险最小化(ERM)准则,即用样本定义经验风险，即定义样本经验风险11()(,(,))nempiiiRwLyfxwn（4）来作为对（2）式的估计，目的是设计算法使它最小化。在模式识别问题中，经验风险就是训练样本的错误率。事实上,用ERM准则代替期望风险最小化并没有经过充分的理论论证,只是直观上合理的想当然做法。而实际上,即使可以假定当n趋向于无穷大时(6)式趋近于(2)式,在很多问题中的样本数目也离无穷大相去甚远.因此，在有限样本条件下，ERM准则下并不一定能使期望风险也较小。支持向量机的理论基础过学习问题ERM准则不成功的一个例子是神经网络的过学习问题.开始,很多注意力都集中在如何使()empRw更小,但很快就发现,训练误差小并不总能导致好的预测效果.某些情况下,训练误差过小反而会导致推广能力的下降,即真实风险的增加,这就是过学习问题.该问题出现的原因：一是因为样本不充分,二是学习机器设计不合理。究其原因，是试图用一个十分复杂的模型去拟合有限的样本,导致丧失了推广能力.学习机器的复杂性与推广性存在着矛盾。结论：有限样本情况下,1)经验风险最小并不一定意味着期望风险最小;2)学习机器的复杂性不但应与所研究的系统有关,而且要和有限数目的样本相适应.支持向量机的理论基础3.VC维定义：对一个指示函数集,如果存在h个样本能够被函数集中的函数按所有可能的2h种形式分开,则称函数集能够把h个样本打散;函数集的VC维就是它能打散的最大样本数目h.若对任意数目的样本都有函数能将它们打散,则函数集的VC维是无穷大.VC维反映了函数集的学习能力,VC维越大则学习机器越复杂(容量越大).学习能力越强。支持向量机的理论基础4.经验风险与真实风险的关系统计学习理论系统地研究了对于各种类型的函数集,经验风险和实际风险之间的关系。得出如下结论：对指示函数集中的所有函数(包括使经验风险最小的函数),经验风险()empRw和实际风险()Rw之间以至少1的概率满足如下关系：ln21ln4emphnhRwRwn（5）其中h是函数集的VC维,n是样本数.这一结论从理论上说明了学习机器的实际风险是由两部分组成的:一是经验风险(训练误差),另一部分称作置信范围,它和学习机器的VC维及训练样本数有关。支持向量机的理论基础4.经验风险与真实风险的关系因此，（5）式可以简单地表示为：()()(/)empRwRwhn（6）它表明,在有限训练样本下,学习机器的VC维越高(复杂性越高)则置信范围越大,导致真实风险与经验风险之间可能的差别越大.这就是为什么会出现过学习现象的原因.机器学习过程不但要使经验风险最小,还要使VC维尽量小以缩小置信范围,才能取得较小的实际风险,即对未来样本有较好的推广性.支持向量机的理论基础5.结构风险最小化（SRM）在传统方法中,选择学习模型和算法的过程就是调整置信范围的过程,如果模型比较适合现有的训练样本(相当于/hn值适当),则可以取得比较好的效果.但因为缺乏理论指导,这种选择只能依赖先验知识和经验,造成了对使用者“技巧”的过分依赖。统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小,如下图所示.这种思想称作结构风险最小化(StructuralRiskMinim-ization或称有序风险最小化)即SRM准则。支持向量机的理论基础5.结构风险最小化（SRM）支持向量机的理论基础5.结构风险最小化（SRM）实现SRM原则的两种思路：（1）在每个子集中求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集.显然这种方法比较费时,当子集数目很大甚至是无穷时不可行.（2）设计函数集的某种结构使每个子集中都能取得最小的经验风险(如使训练误差为0),然后只需选择选择适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是第二种思想的具体实现。最优分类面SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用下图的两维情况说明。图中，实心点和空心点代表两类样本，H为正确分开两类样本的分类线，H1、H2分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类空隙或分类间隔（margin）。所谓最优分类线就是要求分类线不但能将两类正确分开（训练错误率为0），而且使分类间隔最大。要求两类训练样本正确分开就是保证经验风险最小（为0），要求分类间隔最大也就是使推广性的界中的置信范围最小，从而使真实风险最小。最优分类面设线性可分样本集为(,)iixy，i=1,…,n,,1,1dxyR是类别符号。d维空间中线性判别函数的一般形式为(),gxwxb分类面方程为：0wxb，我们可以对它进行归一化，使两类所有样本都满足|()|1gx，即使离分类面最近的样本的|()|1gx，而要求分类线对所有样本正确分类，就是要求样本满足[()]10,iiywxb1,2,...,in（7）此时分类间隔等于2/||w||，使间隔最大等价于使2||||w最小。满足条件(7)且使21||||2w最小的分类面就叫做最优分类面。过两类样本中离分类面最近的点且平行于最优分类面的超平面H1，H2上的训练样本就是使（7）式等号成立的那些样本，他们叫做支持向量（SupportVectors）。最优分类面统计学习理论指出，在d维空间中，设样本分布在一个半径为R的超球范围内，则满足条件||||wc的正则超平面构成的指示函数集(,,)sgn{()},fxwbwxb的VC维满足下面的界2min([],)1.hRcd因此使2||||w最小就是使VC维的上界最小，从而实现结构风险最小化（SRM）准则中对函数复杂性的选择:固定经验风险，最小化期望风险就转化为最小化2||||w，这就是SVM方法的出发点。根据上面的讨论，在线性可分条件下构建最优分类面，就转化为下面的二次规划问题。即在条件（7）的约束下，求函数211()||||()22（8）最优分类面的最小值。我们可以定义如下的Lagrange函数：11(,,)(){[()]1},2niiiiLwbwwywxb（9）其中，1(,,)Tn为与每个样本对应的Lagrange乘子向量，我们的问题是对w和b求Lagrange函数的极小值。把（9）分别对w和b求偏微分并令它们等于0，就可以把原问题转化为如下这种较简单的对偶问题；在约束条件10,niiiy（10a）和0,i1,,in（10b）之下对i求解下列函数的最大值：最优分类面1,11()()2nniijijijiijQyyxx（11）如果i为最优解，那么*1niiiiwyx（12）即最优超平面的权系数向量是训练样本向量的线性组合。这是一个不等式约束下的二次函数极值问题，存在唯一解。根据Kuhn-Tucker条件，这个优化问题的解必须满足：(()1)0,1,,iiiywxbin（13）因此，对多数样本i将为零，取值不为零的i对应于使式（7）中的等式成立的样本即支持向量，它们通常只是全体样本中很少的一部分。最优分类面支持向量（SupportVectors）就是使式（7）中的等号成立的那些样本，如上图中用方框标出的点所示。对这些学习机器来说，支持向量是训练集中的关键元素，它们离决策边界最近；如果去掉所有其他训练点，再重新进行训练，得到的分类面是相同的。在下面的求解过程中我们可以看到，只有支持向量对求解最优超平面有着至关重要的作用，其它的样本点根本用不到。求解上述问题后得到的最优分类函数是：****1()sgn{()}sgn()niiiifxwxbyxxb（14）由于非支持向量对应的*i都是0，因此在对式（14）求和的时候只需考虑支持向量就可以了。*b是分类的域值，可以由任意一个支持向量用式（7）求得或通过两类中的任意一对支持向量取中值求得。因此，有以上方法得到的寻优函数（11）和判别函数（14）称为“最大间隔”支持向量机或称为线性支持向量机。广义最优分类面最优分类面是在线性可分的前提下讨论的，也就是保证训练样本全部被正确分类的，即经验风险为0的前提下，通过最大化分类间隔来获得最好的推广性能。但是在实际应用时，大多数情况下并不能满足线性可分性。即使问题是线性可分的，由于各种原因，训练集中也可