Foundation of Machine Learning [Part04]

《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∈S￿w￿￿w￿MehryarMohri-FoundationsofMachineLearningpage6OptimizationProblemConstrainedoptimizati

9、on:12min￿w￿w,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:￿m￿m∇wL=w−αiyixi=0⇐⇒w=αiyixi.i=1i=1￿m￿m∇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:wL1￿m￿m￿m￿m2L=￿αiyixi￿−αiαjyiyj(xi·xj)−αiyib+αi.2i=1i,j=1i=1i=1￿￿￿￿￿￿￿￿1Pm0−αiαjyiyj(xi·xj)2i,j=1Thus,￿m1￿mL=αi−αi

12、αjyiyj(xi·xj).2i=1i,j=1MehryarMohri-FoundationsofMachineLearningpage10DualOptimizationProblemConstrainedoptimization:￿m1￿mmaxαi−αiαjyiyj(xi·xj)α2i=1i,j=1￿msubjectto:αi≥0∧αiyi=0,i∈[1,m].i=