人工智能之支持向量机

支持向量机SupportVectorMachines内容提要统计学习方法概述统计学习问题学习过程的泛化能力支持向量机SVM寻优算法应用支持向量机SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速发展起来VapnikVN.1995.TheNatureofStatisticalLearningTheory.Springer-Verlag,NewYorkVapnikVN.1998.StatisticalLearningTheory.Wiley-IntersciencePublication,JohnWiley&Sons,Inc目前已经在许多智能信息获取与处理领域都取得了成功的应用。支持向量机SVMSVMsarelearningsystemsthatuseahyperplaneoflinearfunctionsinahighdimensionalfeaturespace—Kernelfunctiontrainedwithalearningalgorithmfromoptimizationtheory—LagrangeImplementsalearningbiasderivedfromstatisticallearningtheory—GeneralisationSVMisaclassifierderivedfromstatisticallearningtheorybyVapnikandChervonenkis25线性分类器ayestfxf(x,w,b)=sign(w.x-b)denotes+1denotes-1Howwouldyouclassifythisdata?26线性分类器fxayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)Howwouldyouclassifythisdata?27线性分类器fxayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)Howwouldyouclassifythisdata?28线性分类器fxayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)Howwouldyouclassifythisdata?29线性分类器fxayestdenotes+1denotes-1f(x,w,b)=sign(w.x-b)Howwouldyouclassifythisdata?哪一个分界面是最优的？？210分类超平面Trainingset:(xi,yi),i=1,2,…N;yi{+1,-1}Hyperplane:wx+b=0Thisisfullydeterminedby(w,b)w1x+b1=0w2x+b2=0w3x+b3=0211最大间隔一个超平面，如果它能将训练样本没有错误地分开，并且两类训练样本中离超平面最近的样本与超平面之间的距离是最大的，则把这个超平面称作最优分类超平面（optimalseparatinghyperplane），两类样本中离分类面最近的样本到分类面的距离称为分类间隔，最优超平面也可以称作最大间隔超平面。212最大间隔原则Note1:decisionfunctions(w,b)and(cw,cb)arethesameNote2:butmarginsasmeasuredbytheoutputsofthefunctionxwx+barenotthesameifwetake(cw,cb).Definition:geometricmargin:themargingivenbythecanonicaldecisionfunction,whichiswhenc=1/||w||Strategy:1)weneedtomaximisethegeometricmargin!(cfresultfromlearningtheory)2)subjecttotheconstraintthattrainingexamplesareclassifiedcorrectlywwx+b=0wx+b0wx+b0213支持向量Thetrainingpointsthatarenearesttotheseparatingfunctionarecalledsupportvectors.Whatistheoutputofourdecisionfunctionforthesepoints?214分类问题的数学表示已知：训练集包含个样本点：说明：是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标；是输出指标，或输出.问题：对一个新的模式，推断它所对应的输出是1还是-1.实质：找到一个把上的点分成两部分的规则.l11{(,),,(,)}()lllTxyxyyxnixRx{1,1}iyyxynR2维空间上的分类问题)n维空间上的分类问题.215根据给定的训练集其中，，寻找上的一个实值函数，用决策函数判断任一模式对应的值.sgn()为符号函数，取自变量的符号。可见，分类学习机——构造决策函数的方法(算法)，两类分类问题多类分类问题线性分类学习机非线性分类学习机,{1,1},1,,niixRyilyxnRx()sgn(())fxgx11{(,),,(,)}()lllTxyxyyx()gxxy分类学习方法216SVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。分类学习方法Chap8SVMZhongzhiShi217考虑上的线性可分的分类问题.这里有许多直线能将两类点正确分开.如何选取和？简单问题：设法方向已选定，如何选取？解答：选定平行直线极端直线和取和的中间线为分划直线如何选取？对应一个，有极端直线，称和之间的距离为“间隔”.显然应选使“间隔”最大的。2l3lw2R()0wxbbwwbw2l3lw2233()()llwllw2l3lw最大间隔法的直观导出218数学语言描述12()()wxbkwxbk，w调整，使得b),()-wxbkwxbk（,wbwbkk令，则两式可以等价写为)1,()-1wxbwxb（与此相应的分划直线表达式:)0wxb（23,ll给定适当的法方向后，这两条极端直线可表示为Chap8SVMZhongzhiShi219如何计算分划间隔？考虑2维空间中极端直线之间的间隔情况[x]1[x]2)1wxb（)1wxb（D21bw21bw2222121-1bbD221222D求出两条极端直线的距离：Chap8SVMZhongzhiShi220W2Margin=1b1XWH1平面：H2平面：1b2XW01])[(byiiXW…..(2)…..(1)Chap8SVMZhongzhiShi221分划直线表达式为“间隔”为极大化“间隔”的思想导致求解下列对变量和的最优化问题说明：只要我们求得该问题的最优解，从而构造分划超平面，求出决策函数。上述方法对一般上的分类问题也适用.()0wxb2||||wbw2,1min||||,(1.2.1)2s.t.(())1,1,,(1.2.2)wbiiwywxbilnR**,wb**()0wxb**()sgn(())fxwxb原始问题Chap8SVMZhongzhiShi222求解原始问题为求解原始问题，根据最优化理论，我们转化为对偶问题来求解11111min2..0,0,1lllijijijjijjliiiiyyxxstyilaaaaaa对偶问题为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解ia*a2,1min||||,(1.2.1)2s.t.(())1,1,,(1.2.2)wbiiwywxbil223线性可分问题计算，选择的一个正分量,并据此计算***1(,,)Tlaaa**1liiiiwyxa*a*ja**1ljiijiibyyxxa事实上，的每一个分量都与一个训练点相对应。而分划超平面仅仅依赖于不为零的训练点，而与对应于为零的那些训练点无关。*a*ia*ia,iixy*ia称不为零的这些训练点的输入为支持向量(SV)*iaix构造分划超平面,决策函数**0wxb**sgn(())fxwxb根据最优解224近似线性可分问题1lii1,Tl不要求所有训练点都满足约束条件，为此对第个训练点引入松弛变量(SlackVariable),把约束条件放松到。1iiywxbi,iixy0i1iiiywxb体现了训练集被错分的情况，可采用作为一种度量来描述错划程度。1lii两个目标：1.间隔尽可能大2.错划程度尽可能小2w显然，当充分大时，样本点总可以满足以上约束条件。然而事实上应避免太大，所以需在目标函数对进行惩罚（即“软化”约束条件）i(,)iixyi[x]1[x]2)1wxb（)1wxb（D21bw21bwChap8SVMZhongzhiShi2250C2,,11min2.(())1,1,0,1,liwbiiiiiwCstywxbilil因此，引入一个惩罚参数，新的目标函数变为:体现了经验风险，而则体现了表达能力。所以惩罚参数实质上是对经验风险和表达能力匹配一个裁决。当时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。1liiwCC近似线性可分问题Chap8SVMZhongzhiShi226(广义)线性支持向量分类机算法,{1,1},1,,niixRyilyx11{(,),,(,)}()lllTxyxyyx1.设已知训练集，其中2.选择适当的惩罚参数，构造并求解最优化问题0C111l1i1min2..00,1,lllijijijjijjiiiyyxxstyCilaaaaaa3.计算，选择的一个分量，并据此计算出**1liiiiwyxa*a*0jCa**1ljiiijibyyaxx4.构造分划超平面,决策函数**()0wxb**()sgn(())fxwxb求得***1(,)Tlaaa227非线性分类例子:228Non-linearClassificationWhatcanwedoiftheboundaryisnonlinear?Idea:transformthedatavectorstoaspacewheretheseparatorislinearChap8SVMZhongzhiShi229Non-linearClassificationThetransformationmanytimesismadetoaninfinitedimensionalspace,usuallyafunctionspace.Example:xcos(uTx)Chap8SVMZhongzhiShi230Non-linearSVMsTransformx(x)Thelinearalgorithmdependsonlyonxxi,hencetransformedalgorithmdependsonlyon(x)(xi)UsekernelfunctionK(xi,xj)suchthatK(xi,xj)=(x)(xi)231设训练集，其中假定可以用平面上的二次曲线来分划：{(,),1,}iiTxyil12([],[]),{1,1}Tiiiixxxy12([],[])xx22212132412516[]2[][]2[][]2[][][][][][][]0wwx