Slide 1Linear ClassifiersLinear ClassifiersLinear ClassifiersClassifier MarginMaximum MarginWhy Maximum Margin ?Estimate the MarginEstimate the MarginMaximize the Classification MarginMaximum MarginMaximum MarginMaximum MarginQuadratic ProgrammingLinearly Inseparable CaseLinearly Inseparable CaseLinearly Inseparable CaseLinearly Inseparable CaseLinearly Inseparable CaseLinearly Inseparable CaseDual Form of SVMDual Form of SVMSuppose we’re in 1-dimensionSuppose we’re in 1-dimensionHarder 1-dimensional DatasetHarder 1-dimensional DatasetHarder 1-dimensional DatasetCommon SVM Basis FunctionsQuadratic Basis FunctionsDual Form of SVMDual Form of SVMSlide 32Slide 33Kernel TrickKernel TrickSVM Kernel FunctionsKernel TricksKernel TricksKernel TricksNonlinear Kernel (I)Nonlinear Kernel (II)Reproducing Kernel Hilbert Space (RKHS)Reproducing Kernel Hilbert Space (RKHS)Kernelize Logistic RegressionDiffusion KernelDiffusion KernelDiffusion KernelDiffusion Kernel: PropertiesDoing Multi-class ClassificationKernel LearningKernel LearningReferencesSupport Vector MachineRong JinLinear Classifiersdenotes +1denotes -1•How to find the linear decision boundary that linearly separates data points from two classes?Linear Classifiersdenotes +1denotes -1Copyright © 2001, 2003, Andrew W. Moore Linear ClassifiersAny of these would be fine....but which is best?denotes +1denotes -1Copyright © 2001, 2003, Andrew W. MooreClassifier Margindenotes +1denotes -1Define the margin of a linear classifier as the width that the boundary could be increased by before hitting a datapoint.Copyright © 2001, 2003, Andrew W. MooreMaximum Margindenotes +1denotes -1The maximum margin linear classifier is the linear classifier with the maximum margin.This is the simplest kind of SVM (called an Linear SVM)Copyright © 2001, 2003, Andrew W. MooreWhy Maximum Margin ?denotes +1denotes -11. If we’ve made a small error in the location of the boundary (it’s been jolted in its perpendicular direction) this gives us least chance of causing a misclassification.2. There’s some theory (using VC dimension) that is related to (but not the same as) the proposition that this is a good thing.3. Empirically it works very very well.Copyright © 2001, 2003, Andrew W. MooreEstimate the Margin•What is the distance expression for a point x to a line wx+b= 0?denotes +1denotes -1xCopyright © 2001, 2003, Andrew W. MooreEstimate the Margin•What is the classification margin for wx+b= 0?denotes +1denotes -1xCopyright © 2001, 2003, Andrew W. MooreMaximize the Classification Margindenotes +1denotes -1xCopyright © 2001, 2003, Andrew W. MooreMaximum Margindenotes +1denotes -1xCopyright © 2001, 2003, Andrew W. MooreMaximum Margindenotes +1denotes -1xMaximum MarginQuadratic programming problem•Quadratic objective function•Linear equality and inequality constraints•Well studied problem in ORCopyright © 2001, 2003, Andrew W. MooreQuadratic Programmingarg min2TTRc + +uu ud uFindnmnmnnmmmmbuauauabuauauabuauaua...:......22112222212111212111)()(22)(11)()2()2(22)2(11)2()1()1(22)1(11)1(...:......enmmenenennmmnnnnmmnnnbuauauabuauauabuauauaAnd subject ton additional linear inequality constraintse additional linear equality constraintsQuadratic criterionSubject toCopyright © 2001, 2003, Andrew W. MooreLinearly Inseparable Casedenotes +1denotes -1This is going to be a problem!What should we do?Copyright © 2001, 2003, Andrew W. MooreLinearly Inseparable Casedenotes +1denotes -1• Relax the constraints• Penalize the relaxationCopyright © 2001, 2003, Andrew W. MooreLinearly Inseparable Casedenotes +1denotes -1• Relax the constraints• Penalize the relaxationCopyright © 2001, 2003, Andrew W. MooreLinearly Inseparable Casedenotes +1denotes -11e2e3eStill a quadratic programming problemCopyright © 2001, 2003, Andrew W. MooreLinearly Inseparable CaseCopyright © 2001, 2003, Andrew W. MooreLinearly Inseparable CaseSupport Vector MachineRegularized logistic regressionCopyright © 2001, 2003, Andrew W. MooreDual Form of SVMHow to decide b ?Copyright © 2001, 2003, Andrew W. MooreDual Form of SVMdenotes +1denotes -11w x b�+ =r r1w x b�+ =-r rwrCopyright © 2001, 2003, Andrew W. MooreSuppose we’re in 1-dimension What would SVMs do with this data?x=0Copyright © 2001, 2003, Andrew W. MooreSuppose we’re in 1-dimensionNot a big surprisePositive “plane”Negative “plane”x=0Copyright © 2001, 2003, Andrew W. MooreHarder 1-dimensional Datasetx=0Copyright © 2001, 2003, Andrew W. MooreHarder 1-dimensional Datasetx=0Copyright © 2001, 2003, Andrew W. MooreHarder 1-dimensional Datasetx=0Copyright © 2001, 2003, Andrew W. MooreCommon SVM Basis Functions•Polynomial terms of x of degree 1 to q •Radial (Gaussian) basis functionsCopyright © 2001, 2003, Andrew W. MooreQuadratic Basis Functions mmmmmmxxxxxxxxxxxxxxxxxx11321312122221212:2:22:22:2:221)(xΦConstant TermLinear TermsPure Quadratic TermsQuadratic Cross-TermsNumber of terms (assuming m input dimensions) = (m+2)-choose-2= (m+2)(m+1)/2= m2/2Copyright © 2001, 2003, Andrew W. MooreDual Form of SVMCopyright © 2001, 2003, Andrew W. MooreDual Form of SVMQuadratic Dot Products-- mmmmmmmmmmmmbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaa113213121222212111321312122221212:2:22:22:2:2212:2:22:22:2:221)()( bΦaΦ1miiiba12miiiba122  mimijjijibbaa1 12+++Copyright © 2001, 2003, Andrew W. MooreQuadratic Dot Products- )()( bΦaΦ  mimijjijimiiimiiibbaababa1 11221221Just out of casual, innocent, interest, let’s look at another function of a and b:2)1.( ba1.2).(2 baba12121miiimiiibaba1211 1  miiimimjjjiibababa122)(11 112  miiimimijjjiimiiibabababaCopyright © 2001, 2003, Andrew W. MooreKernel