支持向量机SVM

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2012/11/9,#,支持向量,机,SVM,主要内容,1.SVM,简介,2.SVM,相关概念解释,3.SVM,原理,3.1,线性可分,3.2,线性不可分,支持向量机简介,支持向量机,(Support Vector Machine),是,Vapnik,等人在,1995,年首先提出的，它在解决,小样本、非线性,及,高维,模式识,别中表现出许多特有的优势。,支持向量机方法是建立在统计学习理论的,VC,维,理论和,结,构风险,最小原理基础上的，根据有限的样本信息在模型的复,杂性（即对特定训练样本的学习精度）和学习能力（即无错,误地识别任意样本的能力）之间寻求最佳折衷，以期获得最,好的推广能力 。,SVM,相关概念解释,VC,维,：对于一个指示函数（即只有,0和1两种取值,的函数）集，如果存在,h,个样本能够被函数集里的函数按照所有可能的,2,h,种形式分开，则称函数集能够把,h,个样本打散，函数集的,VC,维就是能够打散的最大样本数目。,圈代表,0,；点代表,1,；,SVM,相关概念解释,经验风险,：使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值。,根据统计学习理论，学习机器的,实际风险,由,经验风险值,和,置信范围值,两部分组成。而,基于经验风险最小化准则,的学习方法只强调了,训练样本的经验风险最小误差,，,没有最小化置信范围值,，因此其推广能力较差。,缺点：,1.,经验风险主要反映的是样本数据与真实结果的差距，而样本数据在实际项目中只是总体的一小部分；,2.,过度地强调经验风险最小化容易造成,过学习问题,。,SVM,相关概念解释,过学习问题,推广能力,:,将学习机器,(,即预测函数,或称学习函数、学习模型,),对未来输出进行正确预测的能力。,underfitting,Good fit,overfitting,选择了一个足够复杂的分类函数，能够精确的记住每一个样本，但对样本之外的数据可能一律分类错,误。,SVM,相关概念解释,结构风险最小化,即,SRM,准则,:,统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照,VC,维的大小排列,;,在,每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。,一是,经验风险,，代表了分类器在给,定样本上的误差,；,二是,置信风险,，代表了我们在多大程度上可以信任分类器在未知样本上分类的结果。,置信风险与两个量有关，一是,样本数量,，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是,分类函数的,VC,维,(,分类函数的复杂度,),，显然,VC,维越大，推广能力越差，置信风险会变大,.,SVM,相关概念解释,SVM,原理,数据线性可分,2,个类的问题,设两类问题训练样本集为,(,X,1,y,1,), (,X,2,y,2,),(,X,n,y,n,),其中,X,i,R,n, y,i,=,1,-1, i=1,n,，这里线性可分就是指，存在着超平面（,Hyper-plan,e,）,直线,f(x) =,wX,+ b,，,使得训练样本中的一类输入和另一类输入分别位于该超平面的两侧,.,这种线性分类函数在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称,超平面（,Hyper Plane,）！,最优超平面,就是分割的间隙越大越好，把两个类别的点分得越开越好。具有最大边缘超平面,如何求最优超平面,分离超平面可以记作：,W X + b = 0,其中，,W,是权重向量，即,W =,w,1,，,w,2,，,.,，,w,n,，,n,是属性数，,b,是标量，通常称做偏倚。,训练组是二维的，如,X =,（,x,1,，,x,2,），其中,x,1,，,x,2,分别是,X,的属性,A,、,B,的值。我们将,b,看作附加的权重,w,0,，则将分离超平面改写成,b + w,1,x,1,+ w,2,x,2,= 0,这样，位于分离超平面下方的点满足,b + w,1,x,1,+ w,2,x,2, 0,调整权重使得定义边缘侧面的超平面记为,H,1,：,b+ w,1,x,1,+ w,2,x,2, 1,， 对于所有,y,i,= +1,H,2,：,b+ w,1,x,1,+ w,2,x,2, -1,， 对于所有,y,i,= -1,两个边界平面的距离,:,m=2/|w|,如何求最优超平面,求解最优超平面问题可以表示成约束优化问题,Minimize,Subject to,定义,Lagrange,函数,现在，原问题转化为下面这样一个优化问题,求解,w,和,b,，使得对于所有的样本,(x,i,y,i,),，能有,m=2/|w|,最大，其中满足当,y,i,=1,时，,w,T,x,i,+b1,，当,y,i,=-1,时，,w,T,x,i,+b,-1,所以有：,y,i,(,w,T,x,i,+b,),1,如何求最优超平面,分别对,w,和,b,求偏导，并令其为,0,，可得,这实际上是寻找极值条件下,L,函数满足的等式约束,将得到的约束条件,带入原,L,函数，得到,:,该式称为,L,函数的对偶式，由对偶理论可知，最小化,L,式等于最大化以,L,式的约束的拉格朗日乘子为变量的上式,x,1,=(0, 0), y,1,= +1,x,2,=(1, 0), y,2,= +1,x,3,=(2, 0), y,3,= -1,x,4,=(0, 2), y,4,= -1,调用,Matlab,中的二次规划程序，求得,1,2, ,3, ,4,的值，进而求得,w,和,b,的值。,SVM,原理,数据非线性可分,对于无法直接构造分类超平面的样本集，我们需要采取某种方法使其能够被某个“平面”划分,基本思想是通过选择非线性映射,(x),将,x,映射到高维特征空间,Z,，在,Z,中构造最优分类超平面,设训练集 ，其中,假定可以用 平面上的二次曲线来分划：,现考虑把,2,维空间 映射到,6,维空间的变换,上式可将,2,维空间上二次曲线映射为,6,维空间上的一个超平面：,可见，只要利用变换，把,x,所在的,2,维空间的两类输入点映射到,x,所在的,6,维空间，然后在这个,6,维空间中，使用线性学习机求出分划超平面：,最后得出原空间中的二次曲线：,应用,SVM,可以用来,分类,和,预测,应用领域：,手写数字识别、,对象识别、,语音识别、,基准时间序列预测检验,谢谢大家！,