资源描述:
《Foundation of Machine Learning [Part04]》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、FoundationsofMachineLearningLecture4MehryarMohriCourantInstituteandGoogleResearchmohri@cims.nyu.eduSupportVectorMachinesMehryarMohri-FoudationsofMachineLearningThisLectureSupportVectorMachines-separablecaseSupportVectorMachines-non-separablecaseMarginguarante
2、esMehryarMohri-FoundationsofMachineLearningpage3BinaryClassificationProblemNTrainingdata:sampledrawni.i.d.fromsetX⊆Raccordingtosomedistribution,DS=((x1,y1),...,(xm,ym))∈X×{−1,+1}.Problem:findhypothesisinh:X→{−1,+1}H(classifier)withsmallgeneralizationerror.RD(h)
3、Linearclassification:•Hypothesesbasedonhyperplanes.•Linearseparationinhigh-dimensionalspace.MehryarMohri-FoundationsofMachineLearningpage4LinearSeparationw·x+b=0w·x+b=0Classifiers:.H={x→sgn(w·x+b):w∈RN,b∈R}MehryarMohri-FoundationsofMachineLearningpage5OptimalH
4、yperplane:Max.Margin(VapnikandChervonenkis,1965)w·x+b=0marginw·x+b=+1w·x+b=−1Canonicalhyperplane:andchosensuchthatforwbclosestpoints.
5、w·x+b
6、=1
7、w·x+b
8、1Margin:.ρ=min=x∈SwwMehryarMohri-FoundationsofMachineLearningpage6OptimizationProblemConstrainedoptimizati
9、on:12minww,b2subjecttoyi(w·xi+b)≥1,i∈[1,m].Properties:•Convexoptimization.•Uniquesolutionforlinearlyseparablesample.MehryarMohri-FoundationsofMachineLearningpage7OptimalHyperplaneEquationsLagrangian:forallw,b,αi≥0,m12L(w,b,α)=w−αi[yi(w·xi+b)−1].2i=1KKTco
10、nditions:mm∇wL=w−αiyixi=0⇐⇒w=αiyixi.i=1i=1mm∇bL=−αiyi=0⇐⇒αiyi=0.i=1i=1∀i∈[1,m],αi[yi(w·xi+b)−1]=0.MehryarMohri-FoundationsofMachineLearningpage8SupportVectorsComplementarityconditions:αi[yi(w·xi+b)−1]=0=⇒αi=0∨yi(w·xi+b)=1.Supportvectors:vectorssuchthatxiα
11、i=0∧yi(w·xi+b)=1.•Note:supportvectorsarenotunique.MehryarMohri-FoundationsofMachineLearningpage9MovingtoTheDualPluggingintheexpressionofingives:wL1mmmm2L=αiyixi−αiαjyiyj(xi·xj)−αiyib+αi.2i=1i,j=1i=1i=11Pm0−αiαjyiyj(xi·xj)2i,j=1Thus,m1mL=αi−αi
12、αjyiyj(xi·xj).2i=1i,j=1MehryarMohri-FoundationsofMachineLearningpage10DualOptimizationProblemConstrainedoptimization:m1mmaxαi−αiαjyiyj(xi·xj)α2i=1i,j=1msubjectto:αi≥0∧αiyi=0,i∈[1,m].i=