北京大学-机器学习-10-SVM-支持向量机-Support-Vector-Machines

第十讲支持向量机邓志鸿北京大学信息科学技术学院2016年4月18日星期一回顾－感知器TheMPmodel输出w2w1wn...x1oniiixwnet0x2xnx0=1w0otherwisexwifxwsignnetsignoniiiniii101)()(00权重perceptronrulewiwi+wiwi=(t-o)xi回顾－多层神经网路输出w2w1wn...x1oniiixwnet0x2xnx0=1w0neteo11SigmoidUnit输入层隐层输出层SigmoidUnit回顾－梯度下降训练误差梯度训练规则nwEwEwEwE,...,,)(102)(21)(DdddotwE2)(21min)(minDddd)(21min)(mindd回顾－逆向传播算法BA(trainingexample,,nin,nout,nhidden)Createafeed-forwardnetworkwithnininputs,nhiddenhiddenunits,andnoutoutputsunits.InitializeallnetworkweightstosmallrandomnumbersUntiltheterminationconditionismet,DoForeachx,tintraining_examples,DoInputtheinstancextotheunitandcomputetheoutputouofeveryunituinthenetwork.Foreachnetworkoutputunitk,calculateitserrortermkForeachnetworkhiddenunith,calculateitserrortermhUpdateeachnetworkweigthwji))(1(kkkkkotoo)()1(hdownstreamkkkhhhhwoojijjijijijix回顾－相关推导求其中注意权重wji仅通过单元netj影响网络。因此，利用微分链式规则，有：计算netj是输出单元netj是隐层单元jijiwEwoutputskkkdotwE2)(21)(Outputs：网络输出单元集合jijdjijjdjidxnetEwnetnetEwEjdnetE)1()(jjjjjdoootnetE)()1(jDownstreamkkjkjjjdwoonetEHomework为什么感知器不能表示XORInput-1-1-111-111Output-111-1a)b)c)d)ExclusiveOR(XOR)Notlinearlyseparablebacd01X1X2支持向量机简介线性SVM无噪音线性可分有噪音线性可分非线性SVM核函数相关讨论总结SVM－简介自上实际60年代开始，V.N.Vapnik等人开始致力于研究有限样本的机器学习问题。经过几十年的研究，Vapnik等人于1992年至1995年发表了一系列的文章，对有限样本的机器学习问题形成了一个比较完整的体系，即所谓的统计学习理论(statisticallearningtheory)基于PAC（ProbablyApproximatelyCorrect）框架给出了关于泛化性能的界，得出了误差与样本数目之间的关系支持向量机SupportVectorMachines，简称SVM基于统计学习理论形成的一种新的机器学习方法，被认为是机器学习研究中的一个重大突破。在文本分类、语音识别、文字识别等众多领域表现优异。支持向量机简介线性SVM无噪音线性可分有噪音线性可分非线性SVM核函数相关讨论总结线性分类器考虑两类线性可分问题太多选择感知器（Perceptron）能找到正确的决策边界（超平面）问题这些决策边界在分类新样本的时候效果是否一样?Class1（正样本）Class2（负样本）线性分类器差的决策边界太接近正样本了！正负样本区分不够！Class1（正样本）Class2（负样本）Class1（正样本）Class2（负样本）最大间隔决策边界对好的决策边界的直观理解决策边界应该与正负样本尽可能地远离。即，应该使得正负样本间的间隔(Margin)m最大mClass1（正样本）Class2（负样本）线性可分－形式化定义定义1：称训练样本是线性可分的，如果存在决策超平面wx＋b=0，使得以下两式成立：11iiyforbxw11iiyforbxw计算间隔wx＋b=1wx＋b=0wx＋b=-1间隔M正超平面PP：{x|wx＋b=1}负超平面NP：{x|wx＋b=－1}向量w与PP、NP正交？w（x－y）=0，xPPyPP计算间隔wx＋b=1wx＋b=0wx＋b=-1x+PPx-NP，且满足min(Distance(x+,x-))x+=x-+w|x+-x-|=Mx+x-计算间隔wx＋b=1wx＋b=0wx＋b=-1x+=x-+wM=|x+-x-|=|w|=x+x-w(x+-x-)=2ww=2ww2ww2线性SVM定义2：称决策超平面是最优的，如果训练集到该超平面的最小距离最大。即，间隔M最大线性SVM目标就是找出最优的超平面。支持向量最大间隔最优超平面求解线性SVM线性最优分离超平面相当于在约束条件：求1)(bxwyii||2maxw求解线性SVM线性最优分离超平面相当于在约束条件：求上述问题是一个有约束的最优化问题，解决这个问题需要求助于最优化领域的有效工具1)(bxwyii2||||min2w不等式约束的最优化问题在求解不等式约束最优化问题时，常常利用拉格朗日对偶性将原问题转换为对偶问题，通过求解对偶问题而得到原问题的解。考虑含不等式约束的最优化问题称上述约束最优化为原问题MjxhNixgxfjixn1,0)(1,0)(约束条件：)(min不等式约束的最优化问题首先，引进广义拉格朗日函数NiMjjjiixhxgxfxL11)()()(),,(拉格朗日乘子，i0考虑如下x的函数),,(max)(:,xLxi0对任何x，如果其违反原问题的约束条件，即：0或者0)(,)(,xhjxgiji有NiMjjjiixhxgxfxi110)()()(max)(:,不等式约束的最优化问题反之，如果x满足原问题的约束条件，则：)()()()(max)(:,xfxhxgxfxNiMjjjiii110任意实数0任意非负数00iiiixgxg)(,)(,因此其他满足原问题约束条件,),()(xxfx不等式约束的最优化问题),,(maxmin)(min:,xLxixx0NjxhNixgxfjixn1010约束条件：,)(,)()(min等价NiMjjjiixxhxgxfi110)()()(maxmin:,广义拉格朗日函数的极小极大问题)(minxpx记不等式约束的最优化问题原问题的对偶问题),,(min),(xLxD),,(minmax),(max:,:,xLxDii00定义广义拉格朗日函数的极大极小问题NixLixD1，0满足),,(minmax),(max,,),(max:,Did0记不等式约束的最优化问题MjxhNiNixgNixgxLxLxLjiiiix10101010000,)(,,)(,)(),,(),,(),,(对偶定理：假设f(x)和gi(x)是凸函数，hj(x)是仿射函数，并且不等式约束是严格可行的，则x，，分别是原问题和对偶问题的解的充分必要条件是它们满足以下的KKT条件：通过求对偶问题的解来获得原问题的解求解线性SVM拉格朗日函数为：注意||w||2=wTwnibxwywiTi101212)(minniiTiiTbxwywwbwL1121))((),,(求解线性SVM原问题的对偶问题为：niiTiiTbwbwbxwywwbwL1121))((min),,(min,,),,(minmax,:bwLbwi0为得对偶问题的解，需要先求L(w,b,)对w和b求极小，再对求极大求解线性SVMniiiixywbwLw10),,(L(w,b,)对w和b求极小，要求L对w和b偏导为0niiiybwLb10),,(niiiixyw1niiiy10求解线性SVMniiiixyw1niiiy10niiTiiTbxwywwbwL1121))((),,(niiTjnjjjiijnjjjTiniiibwbxxyyxyxybwL1111121))((),,(min,niinijTinjjijixxyy11121求解线性SVMniyxxyyiiniiniinijTinjjiji100211111,max求极大对),,(min,bwLbw对偶问题求解线性SVMniyxxyyiiniiniinijTinjjiji100211111,min对偶问题等价表示求解线性SVM如果存在=(1,2,..,n)是对偶问题的解，则存在下标j，j0，并且可按下式求得原问题的解w和b，)(jiiniijiiniixxyybxyw11求解线性SVM原问题满足对偶定理的条件，因此，原问题和对偶问题的解满足KKT条件，故nianibxwynibxwyybwLbxywbwLwiiiiiiniiiniiii101011010011,,)(,)(),,(),,(求解线性SVMniiiixywbwLw10),,(niiiixyw1必存在下标j，j0。如果都为0，则w=0。显然w=0不是原问题的解，矛盾。因此，对j0的下标j，由01)(bxwyjjj01)(bxwyjj1)(bxwyjjjjjjybxwyy)(jjybxw1jjyy)(jiiniijjjxxyyxwyb1求解线性SVM这是一个典型凸二次规划问题，有经典算法求解。niyxxyyiiniiniinijTinjjiji100211111,min求解线性SVM已经提出了很多方法共轭梯度法、积集法和内点法等参见：对于SVM，序列最小优化(sequentialminimaloptimization,SMO)方法比较流行适合处理中、大型规模的数据；思想：把一个大型QP问题分解成多个小型QP问题组成的序列，这些子问题的解决是顺序相关的，而子问题可以直接解析求解而避免用