PRML_ch7.ppt

Ch7.SparseKernelMachinesPatternRecognitionandMachineLearning,C.M.Bishop,2006.,SummarizedbyS.KimBiointelligenceLaboratory,SeoulNationalUniversityhttp:/bi.snu.ac.kr/,2,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,Contents,MaximumMarginClassifiersOverlappingClassDistributionsRelationtoLogisticRegressionMulticlassSVMsSVMsforRegressionRelevanceVectorMachinesRVMforRegressionAnalysisofSparsityRVMsforClassification,3,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,MaximumMarginClassifiers,ProblemsettingsTwo-classclassificationusinglinearmodelsAssumethattrainingdatasetislinearlyseparableSupportvectormachineapproachesThedecisionboundaryischosentobetheoneforwhichthemarginismaximized,supportvectors,4,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,MaximumMarginSolution,Foralldatapoints,ThedistanceofapointtothedecisionsurfaceThemaximummarginsolution,5,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,DualRepresentation,IntroducingLagrangemultipliers,Min.pointssatisfythederivativesofLw.r.t.wandbequal0Dualrepresentation,FindAppendixEformoredetails,6,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,ClassifyingNewData,OptimizationsubjectstoFoundbysolvingaquadraticprogrammingproblem,Karush-Kuhn-Tucker(KKT)ConditionsAppendixE,:supportvectors,or,O(N3),7,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,ExampleofSeparableDataClassification,Figure7.2,8,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,OverlappingClassDistributions,AllowsomemisclassifiedexamplessoftmarginIntroduceslackvariables,9,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,SoftMarginSolution,MinimizeKKTconditions:,:trade-offbetweenminimizingtrainingerrorsandcontrollingmodelcomplexity,:supportvectors,or,10,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,DualRepresentation,DualrepresentationClassifyingnewdataandobtainingb(hardmarginclassifiers),11,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,AlternativeFormulation,v-SVM(Schlkopfetal.,2000),-Upperboundonthefractionofmarginerrors-Lowerboundonthefractionofsupportvectors,12,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,ExampleofNonseparableDataClassification(v-SVM),13,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,SolutionsoftheQPProblem,Chunking(Vapnik,1982)Idea:thevalueofLagrangianisunchangedifweremovetherowsandcolumnsofthekernelmatrixcorrespondingtoLagrangemultipliersthathavevaluezeroProtectedconjugategradients(Burges,1998)Decompositionmethods(Osunaetal.,1996)Sequentialminimaloptimization(Platt,1999),14,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,RelationtoLogisticRegression(Section4.3.2),Fordatapointsonthecorrectside,Fortheremainingpoints,:hingeerrorfunction,15,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,RelationtoLogisticRegression(Contd),FrommaximumlikelihoodlogisticregressionErrorfunctionwithaquadraticregularizer,16,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,ComparisonofErrorFunctions,Hingeerrorfunction,Errorfunctionforlogisticregression,Misclassificationerror,Squarederror,17,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,MulticlassSVMs,One-versus-the-rest:KseparateSVMsCanleadinconsistentresults(Figure4.2)ImbalancedtrainingsetsPositiveclass:+1,negativeclass:-1/(K-1)(Leeetal.,2001)AnobjectivefunctionfortrainingallSVMssimultaneously(WestonandWatkins,1999)One-versus-one:K(K-1)/2SVMsBasedonerror-correctingoutputcodes(Allweinetal.,2000)Generalizationofthevotingschemeoftheone-versus-one,18,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,SVMsforRegression,Simplelinearregression:minimize-insensitiveerrorfunction,quadraticerrorfunction,-insensitiveerrorfunction,19,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,SVMsforRegression(Contd),Minimize,20,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,DualProblem,21,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,Predictions,KKTconditions:,(fromderivativesoftheLagrangian),22,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,AlternativeFormulation,v-SVM(Schlkopfetal.,2000),fractionofpointslyingoutsidethetube,23,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,Exampleofv-SVMRegression,24,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,RelevanceVectorMachines,SVMOutputsaredecisionsratherthanposteriorprobabilitiesTheextensiontoK2classesisproblematicThereisacomplexityparameterCKernelfunctionsarecenteredontrainingdatapointsandrequiredtobepositivedefiniteRVMBayesiansparsekerneltechniqueMuchsparsermodelsFasterperformanceontestdata,25,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,RVMforRegression,RVMisalinearforminChapter3withamodifiedprior,26,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,RVMforRegression(Contd),andaredeterminedusingevidenceapproximation(type-2maximumlikelihood)(Section3.5),Fromtheresult(3.49)forlinearregressionmodels,Maximize,27,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,RVMforRegression(Contd),TwoapproachesByderivativesofmarginallikelihoodEMalgorithmSection9.3.4Predictivedistribution,Section3.3.2,28,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,ExampleofRVMRegression,MorecompactthanSVMParametersaredeterminedautomaticallyRequiremoretrainingtimethanSVM,RVMregression,v-SVMregression,29,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,MechanismforSparsity,onlyisotropicnoise,=,afinitevalueof,30,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,SparseSolution,Pulloutthecontributionfromiin,Using(C.7),(C.15)inAppendixC,31,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,SparseSolution(Contd),ForlogmarginallikelihoodfunctionL,Stationarypointsofthemarginallikelihoodw.r.t.i,Sparsity:measurestheextenttowhichoverlapswiththeotherbasisvectors,Qualityof:representsameasureofthealignmentofthebasisvectorwiththeerrorbetweentandy-i,32,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,SequentialSparseBayesianLearningAlgorithm,InitializeInitializeusing,with,withtheremainingEvaluateandforallbasisfunctionsSelectacandidateIf(isalreadyinthemodel),updateIf,addtothemodel,andevaluateIf,removefromthemodel,andsetUpdateGoto3untilconverged,33,(C)2007,SNUBiointelligenceLab,http:/bi.snu.ac.kr/,RVMforClassification,Probabilisticlinearclassificationmodel(Chapter4)withARDprior,-Initialize-BuildaGaussianapproximationtotheposterio