Support Vector Machines--支持向量机

10.9SupportVectorMachines22020/1/30ir.dlut.edu.cnoutline10.9SupportVectorMachines◆10.9.1OptimalSeparatingHyperplane◆10.9.2TheNonseparableCase:SoftMarginHyperplane◆10.9.3KernelFunctions◆10.9.4SupportVectorMachinesforRegression32020/1/30ir.dlut.edu.cn10.9.1OptimalSeparatingHyperplane◆Letusstartagainwithtwoclassesanduselabels-1/+1forthetwoclasses.Thesampleis.◆whichcanberewrittenas◆Maximizesthemargin.◆when,thedistanceoftothediscriminantcanbewrittenas,10.9SupportVectorMachines{,}ttxr{1,1}trtx42020/1/30ir.dlut.edu.cn◆whichwewouldliketobeatleastsomevaluep.◆maximizep•butthereareaninfinitenumberofsolutionsthatwecangetbyscalingwandforauniquesolution,wefixpllwll=1◆Thus,tomaximizethemargin,weminimize|lwll.◆UsingLagrangemultipliersgetanunconstrainedproblem:10.9.1OptimalSeparatingHyperplane0(),||||tTrwxwtw0()()tTtgxrwxw52020/1/30ir.dlut.edu.cn有不等式约束问题的极值求法，问题如下：拉格朗日公式：◆和都是拉格朗日算子。如果按这个公式求解，会出现问题，因为我们求解的是最小值，而这里的已经不是0了，我们可以将调整成很大的正值，来使最后的函数结果是负无穷。因此我们需要排除这种情况，我们定义下面的函数：拉格朗日对偶min()wfw..st()0,1,...,()0,1,...,iigwikhwil11(,,)()()()kliiiiiiLwfwgwhwii()igwi,:0()max(,,)iPawLw62020/1/30ir.dlut.edu.cn得到：进而得到：问题转化：◆考虑并定义另一个问题：◆将问题转化为先求拉格朗日关于w的最小值，将和看作是固定值。之后在求最大值。对偶问题：拉格朗日对偶,:0min()min()minmax(,,)ip(,)min(,,)DwLwii(,)D,:0,:0max(,)maxmin(,,)iiDwLw,:0,:0maxmin(,,)minmax(,,)iiwwLwLw72020/1/30ir.dlut.edu.cnKKT条件：实现问题转化：拉格朗日对偶,:0,:0maxmin(,,)minmax(,,)min()ii82020/1/30ir.dlut.edu.cn拉格朗日对偶问题：将问题具体化：问题转化：10.9.1OptimalSeparatingHyperplanemin()wfw..st()0,1,...,()0,1,...,ttgwtkhwtl21()||||2fww0()1()tTttgwrwxwt=1,...,N，,:0,:0maxmin(,,)minmax(,,)min()ii92020/1/30ir.dlut.edu.cn◆SubjecttotheconstraintsthatthegradientofLpwithrespecttowandWoare0andalsothat：thedual：◆whichwemaximizewithrespecttoonly,subjecttotheconstraintsSummary：10.9.1OptimalSeparatingHyperplane0it0,1,11(maxmin)2ttttttTtTttrtrwrxwwxwx00()TtttTtwxwrxxw0,ttttyxxw102020/1/30ir.dlut.edu.cn等式约束非线性规划的拉格朗日问题：QP问题112020/1/30ir.dlut.edu.cnAsimpleexample4x3x2x1xx1=(0,0),r1=+1x2=(1,0),r2=+1x3=(2,0),r3=-1x4=(0,2),r4=-1222d1234223341234t1L()()(444)200,t122020/1/30ir.dlut.edu.cnAsimpleexample00001010201200002Q1111q1111A0b1234012013/41/41120312002144231113w,02224()3220wgxxx12340000111101012101201100021011110132020/1/30ir.dlut.edu.cnCoordinateascent◆S.t.SMO1()2tststTstdtLrrxx142020/1/30ir.dlut.edu.cnDefineslackvariables,Newmodel：UsingLagrangemultipliersgetanunconstrainedproblem:thedual：10.9.2TheNonseparableCase:SoftMarginHyperplane0t0()1tTttrwxw21min||||2ttwC..st0()10tTtttrwxw152020/1/30ir.dlut.edu.cnThechangeofKKTconditions：10.9.2TheNonseparableCase:SoftMarginHyperplane00()1ttTtrwxw0()1ttTtCrwxw00()1ttTtCrwxw()0ttgw0()1()ttTtgwrwxwt=1,...,N，162020/1/30ir.dlut.edu.cn10.9.3KernelFunctions172020/1/30ir.dlut.edu.cnFeaturemapping◆Mappingfunction:◆ThechangeofSVM：DefinethecorrespondingKerneltobe：10.9.3KernelFunctions2()(,)xxx122212();xxxxxxxxx00,Tttttwwyxxw0(),()ttttyxxw182020/1/30ir.dlut.edu.cnAsimpleexample:polynomialsofdegreeq:radial-basisfunctions:sigmoidalfunctions:10.9.3KernelFunctions(,)()()Kxyxy1122122122122()2xxxxxxxxx00(,)TttttwwyKxxw192020/1/30ir.dlut.edu.cnThevalidofkernel:◆ifthereissomefeaturemappingsothatforallx,z?◆Kernelmatrix:◆TheoremMercer10.9.3KernelFunctionskerKavalidnelthecorrespondingkernelmatrixissymmetricpositivesemi-denite.202020/1/30ir.dlut.edu.cnUsealinearmodel:UsetheE-sensitivelossfunction:Analogoustothesoftmarginhyperplane,weintroduceslackvariablestoaccountfordeviationsoutoftheE-zoneandweget10.9.4SupportVectorMachinesforRegression212020/1/30ir.dlut.edu.cn