台大-李宏毅-B站机器学习视频-课件神经网络与深度学习Structured SVM

StructuredSupportVectorMachine,Hung-yiLee,StructuredLearning,WeneedamorepowerfulfunctionfInputandoutputarebothobjectswithstructuresObject:sequence,list,tree,boundingbox,Xisthespaceofonekindofobject,Yisthespaceofanotherkindofobject,UnifiedFramework,ThreeProblems,ExampleTask:ObjectDetection,Sourceofimage:/viewdoc/download?doi=95.6007&rep=rep1&type=pdfhttp:/www.vision.ee.ethz.ch/hpedemo/gallery.php,Keepinmindthatwhatyouwilllearntodaycanbeappliedtoothertasks.,ExampleTask,Problem1:Evaluation,F(x,y)islinear,=,Openquestion:WhatifF(x,y)isnotlinear?,Problem2:Inference,=argmax(,),(),=1.1,(),=8.2,(),=0.3,(),=10.1,(),=-1.5,(),=5.6,max,Problem2:Inference,ObjectDetectionBranchandBoundalgorithmSelectiveSearchSequenceLabelingViterbiAlgorithmThealgorithmscandependon,GeneticAlgorithmOpenquestion:Whathappensiftheinferenceisnotexact?,Problem3:Training,Trainingdata:,Principle,WeshouldfindF(x,y)suchthat,forall,Letsignoreproblems1and2andonlyfocusonproblem3today.,Outline,Outline,Assumption:Separable,Thereexistsaweightvector,StructuredPerceptron,Input:trainingdatasetOutput:weightvectorwAlgorithm:Initializew=0doForeachpairoftrainingexampleFindthelabelmaximizing,If,updatewuntilwisnotupdated,(problem2),Wearedone!,WarningofMath,Inseparablecase,toobtaina,youonlyhavetoupdateatmost2times,R:thelargestdistancebetween,and,:margin,Notrelatedtothespaceofy!,ProofofTermination,wisupdatedonceitseesamistake,(therelationofwkandwk-1),(Allincorrectlabelforanexample),(Alltrainingexamples),Assumethereexistsaweightvectorsuchthat,Assume=1withoutlossofgenerality,Remind:weareconsideringtheseparablecase,ProofofTermination,wisupdatedonceitseesamistake,(therelationofwkandwk-1),Analysis,(largerandlarger?),(Separable),ProofofTermination,Analysis,(largerandlarger?),(sowhat),wisupdatedonceitseesamistake,(therelationofwkandwk-1),=0,ProofofTermination,?,(mistake),AssumethedistancebetweenanytwofeaturevectorsissmallerthanR,ProofofTermination,EndofWarning,Inseparablecase,toobtaina,youonlyhavetoupdateatmost2times,R:thelargestdistancebetween,and,:margin,Notrelatedtothespaceofy!,Howtomaketrainingfast?,Margin:Isiteasytoseparableredpointsfromtheblueones,Normalization,Allfeaturetimes2,Largermargin,lessupdate,Thelargestdistancesbetweenfeatures,Outline,Non-separableCase,Whenthedataisnon-separable,someweightsarestillbetterthantheothers.,Undoubtedly,isbetterthan.,DefiningCostFunction,DefineacostCtoevaluatehowbadawis,andthenpickthewminimizingthecostC,=1,=max,Whatistheminimumvalue?,Otheralternatives?,(Stochastic)GradientDescent,(Stochastic)Gradientdescent:,Weonlyhavetoknowhowtocompute.,=1,=max,However,thereis“max”in.,Findwminimizingthecost,Whenwisdifferent,theycanbedifferent.,Spaceofw,max,=,=,=,(Stochastic)GradientDescent,Fort=1toT:,UpdatetheparametersTtimes,Randomlypickatrainingdata,=max,=,=,stochastic,Ifweset=1,thenwearedoingstructuredperceptron.,Locatetheregion,simple,Outline,Basedonwhatwehaveconsidered.,Treatallincorrectyequally,Therightcaseisbetter.,verybad!,acceptable,Consideringtheincorrectones,Closetocorrectbox,Differentfromcorrectbox,smaller,larger,Howtomeasurethedifference,DefiningErrorFunction,:differencebetweenand,=1,:areaofboundingboxy,(0),AnotherCostFunction,margin,margin,=max,+,GradientDescent,=max,=,max,+,Ohno!Problem2.1,=max,+,AnotherViewpoint,Minimizingthenewcostfunctionisminimizingtheupperboundoftheerrorsontrainingset,=1,=1,Proofthat,Itishard!,Becauseycanbeanykindofobjects,canbeanyfunction,Wewanttofindminimizing(errors),upperbound,servesasthesurrogateof,=argmax,AnotherViewpoint,=max,+,=argmax,+,=,+,max,+,0,=,Proofthat,MoreCostFunctions,=max,+,Marginrescaling:,Slackvariablerescaling:,=max,1+,Outline,Regularization,=1,=122+=1,Keeptheincorrectanswerfromamargindependingonerrors,wclosetozerocanminimizetheinfluenceofmismatch.,Trainingdataandtestingdatacanhavedifferentdistribution.,=max,+,Regularization:Findthewclosetozero,Regularization,=,=max,+,+,=1,WeightdecayasinDNN,=1,=122+=1,Outline,StructuredSVM,=max,+,+,=max,+,+,+,For:,Aretheyequivalent?,WewanttominimizeC,StructuredSVM,=max,+,Findminimizing,=122+=1,For:,For:,Slackvariable,Findw,1,minimizing,StructuredSVM,Ify=:,=0,=0,Itispossiblethatnowcanachievethis.,margin,margin,margin,StructuredSVM-Intuition,(lotsofinequalities),slackvariable,0,(0maketheconstraintsmorestrict),StructuredSVM-Intuition,(lotsofinequalities),1,1,2,2,Trainingdata:,1,1,2,(lotsofinequalities),(lotsofinequalities),1,2,2,10,20,For1,For2,StructuredSVM-Intuition,StructuredSVM,Toomanyconstraints,SolveitbythesolverinSVMpackage,QuadraticProgramming(QP)Problem,Outline,Sourceofimage:,CuttingPlaneAlgorithm,Parameterspace,ColoristhevalueofCwhichisgoingtobeminimized:,1,Solutionwithoutconstraints,Solutionwithconstraints,Imagecredit:YisongYue,=122+=1,CuttingPlaneAlgorithm,Parameterspace,1,Greenline:Removethisconstraintwillnotinfluencethesolution,Redlines:determinethesolution,Althoughtherearelotsofconstraints,mostofthemdonotinfluencethesolution.,:averysmallsetof,workingset,Imagecredit:YisongYue,Elementsinworkingsetisselectediteratively,CuttingPlaneAlgorithm,For:,Find,1minimizingC,=122+=1,Initialize1,Addelementsinto1,obtainsolutionw,SolveaQPproblem,Repeatedly,CuttingPlaneAlgorithm,Strategiesofaddingelementsintoworkingset,Noconstraintatall,SolvingQP,Initialize=,Thesolutionwisthebluepoint.,Imagecredit:YisongYue,CuttingPlaneAlgorithm,Strategiesofaddingelementsintoworkingset,Therearelotsofconstraintsisviolated,Findthemostviolatedone,Supposeitistheconstraintfromy,Extenttheworkingset,=,y,Imagecredit:YisongYue,CuttingPlaneAlgorithm,Strategiesofaddingelementsintoworkingset,Imagecredit:YisongYue,Findthemostviolatedone,Givenwandfromworkingsetsathand,whichconstraintisthemostviolatedone?,Constraint:,ViolateaConstraint:,DegreeofViolation,+,argmax,+,Themostviolatedone:,CuttingPlaneAlgorithm,1,1,2,2,Giventrainingdata:,WorkingSet1,2,Repeat,SolveaQPwithWorkingSet1,2,Find,1minimizing,122+=1,QP:,CuttingPlaneAlgorithm,Until1,2,doesntchangeanymore,Returnw,Foreachtrainingdata,:,Updateworkingset,=argmax,+,findthemostviolatedconstraints,1,1,2,2,Giventrainingdata:,WorkingSet1,2,Repeat,SolveaQPwithWorkingSet1,2,Trainingdata:,1,1,2,2,Find,1,2minimizing,122+=12,QP:,Thereisnoconstraint,Solution:=0,1=,2=,=0,Trainingdata:,1,1,2,2,1=,2=,=0,=1.0,=1.0,=1.0,=0.25,=0.90,=0.88,2=,1,1=argmax1,+01,2=argmax2,+02,Trainingdata:,1,1,2,2,Find,1,2minimizing,122+=12,QP:,1,2,2=,Solution:=1,=1,Trainingdata:,1,1,2,2,=-0.99,=-1.10,=1.01,=1.25,=0.97,=1.55,1,2=,=1,1=argmax1,+11,2=argmax2,+12,Trainingdata:,1,1,2,2,Find,1,2minimizing,122+=12,QP:,1,2,2=,2,1,Theprocessrepeatsiteratively,ConcludingRemarks,Multi-classSVM,Problem1:EvaluationIfthereareKclasses,thenwehaveKweightvectors1,2,=,:vectorrepresentationof,=,=,1,2,0,0,0,=,1,2,Multi-classSVM,Problem2:Inference,=,=max1,2,=max1,2,Thenumberofclassesareusuallysmall,sowecanjustenumeratethem.,Multi-classSVM,Problem3:Training,For:,For:,Findw,1,minimizing,=,=,Sometypesofmisclassificationsmaybeworsethanothers.,=,=1,=,=100,(definedasyourwish),ThereareonlyN(K-1)constraints.,BinarySVM,SetK=2,For:,1,2,=1,Ify=1:,121,Ify=2:,211,1,1,ConcludingRemarks,BeyondStructuredSVM,InvolvingDNNwhengenerating,DNN,StructuredSVM,Ref:HaoTang,Chao-hongMeng,Lin-shanLee,Aninitialattemptforphonemerecognitionusing