Support Vector Machine Rong Jin Linear Classifiers denotes 1 denotes 1 How to find the linear decision boundary that linearly separates data points from two classes Linear Classifiers denotes 1 denotes 1 Linear Classifiers denotes 1 denotes 1 Any of these would be fine but which is best Copyright 2001 2003 Andrew W Moore Classifier Margin Define the margin of a linear classifier as the width that the boundary could be increased by before hitting a datapoint denotes 1 denotes 1 Copyright 2001 2003 Andrew W Moore Maximum Margin The maximum margin linear classifier is the linear classifier with the maximum margin denotes 1 denotes 1 This is the simplest kind of SVM called an Linear SVM Copyright 2001 2003 Andrew W Moore Why Maximum Margin 1 denotes 1 denotes 1 2 3 Copyright 2001 2003 Andrew W Moore 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 There s some theory using VC dimension that is related to but not the same as the proposition that this is a good thing Empirically it works very very well Estimate the Margin denotes 1 denotes 1 x What is the distance expression for a point x to a line wx b 0 Copyright 2001 2003 Andrew W Moore Estimate the Margin denotes 1 denotes 1 x What is the classification margin for wx b 0 Copyright 2001 2003 Andrew W Moore Maximize the Classification Margin denotes 1 denotes 1 x Copyright 2001 2003 Andrew W Moore Maximum Margin denotes 1 denotes 1 x Copyright 2001 2003 Andrew W Moore Maximum Margin denotes 1 denotes 1 x Copyright 2001 2003 Andrew W Moore Maximum Margin Quadratic programming problem Quadratic objective function Linear equality and inequality constraints Well studied problem in OR Quadratic Programming Find Subject to T u Ru arg min c dT u 2 u Quadratic criterion a11u1 a12u2 a1mum b1 a21u1 a22u2 a2 mum b2 an1u1 an 2u2 anmum bn a n 1 1u1 a n 1 2u2 a n 1 mum b n 1 a n 2 1u1 a n 2 2u2 a n 2 mum b n 2 a n e 1u1 a n e 2u2 a n e mum b n e Copyright 2001 2003 Andrew W Moore e additional linear equality constraints And subject to n additional linear inequality constraints Linearly Inseparable Case denotes 1 denotes 1 This is going to be a problem What should we do Copyright 2001 2003 Andrew W Moore Linearly Inseparable Case denotes 1 denotes 1 Relax the constraints Penalize the relaxation Copyright 2001 2003 Andrew W Moore Linearly Inseparable Case denotes 1 denotes 1 Relax the constraints Penalize the relaxation Copyright 2001 2003 Andrew W Moore Linearly Inseparable Case denotes 1 denotes 1 e3 e1 e2 Still a quadratic programming problem Copyright 2001 2003 Andrew W Moore Linearly Inseparable Case Copyright 2001 2003 Andrew W Moore Linearly Inseparable Case Support Vector Machine Regularized logistic regression Copyright 2001 2003 Andrew W Moore Dual Form of SVM How to decide b Copyright 2001 2003 Andrew W Moore Dual Form of SVM denotes 1 denotes 1 r r w x b 1 r w r r w x b 1 Copyright 2001 2003 Andrew W Moore Suppose we re in 1 dimension What would SVMs do with this data x 0 Copyright 2001 2003 Andrew W Moore Suppose we re in 1 dimension Not a big surprise x 0 Positive plane Negative plane Copyright 2001 2003 Andrew W Moore Harder 1 dimensional Dataset x 0 Copyright 2001 2003 Andrew W Moore Harder 1 dimensional Dataset x 0 Copyright 2001 2003 Andrew W Moore Harder 1 dimensional Dataset x 0 Copyright 2001 2003 Andrew W Moore Common SVM Basis Functions Polynomial terms of x of degree 1 to q Radial Gaussian basis functions Copyright 2001 2003 Andrew W Moore 1 Constant Term 2 x1 2 x2 Linear Terms 2 x m Number of terms assuming 2 x1 input dimensions m 2 Pure Quadratic 2 x2 Terms choose 2 2 m 2 m 1 2 x m x m2 2 2 x1 x2 2 x1 x3 2 x1 xm Quadratic CrossTerms 2 x2 x3 2 x x 1 m 2 xm 1 xm Copyright 2001 2003 Andrew W Moore Quadratic Basis Functions m Dual Form of SVM Copyright 2001 2003 Andrew W Moore Dual Form of SVM Copyright 2001 2003 Andrew W Moore Quadratic Dot Products 1 1 2a1 2b1 2 a2 2b2 2 a 2 b m m 2 2 b1 a1 2 2 a b 2 2 2 2 am bm a b 2a1a2 2b1b2 2a1a3 2b1b3 2a1am 2b1bm 2 a a 2 b b 2 3 2 3 2 a a 2 b b 1 m 1 m 2am 1am 2bm 1bm 1 m 2a b i i i 1 m a b 2 2 i i i 1 m m 2a a b b i i 1 j i 1 j i j Quadratic Dot Products Just out of casual innocent interest let s look at another function of a and b a b 1 2 a b 2 2a b 1 m ai bi 2 ai bi 1 i 1 i 1 a b m m m m 1 2 ai bi a b i 1 2 m 2 2 i i i 1 i j i m ai bi a j b j 2 ai bi 1 m 2a a b b m j i 1 j 1 i 1 i 1 j i 1 m m ai bi 2 i 1 Copyright 2001 2003 Andrew W Moore 2 m aba b i 1 j i 1 i i j m j 2 ai bi 1 i 1 Kernel Trick Copyright 2001 2003 Andrew W Moore Kernel Trick Copyright 2001 2003 Andrew W Moore SVM Kernel Functions Polynomial kernel function Radial basis kernel function universal kernel Copyright 2001 2003 Andrew W Moore Kernel Tricks Replacing dot product with a kernel function Not all functions are kernel functions Are they kernel functions Copyright 2001 2003 Andrew W Moore Kernel Tricks Mercer s condition To expand Kernel function k x y into a dot product i e k x y x y k x y has to be positive semi definite f 2 x dx is finite function i e for any function f x whose the following inequality holds Copyright 2001 2003 Andrew W Moore Kernel Tricks Introducing nonlinearity into the model Computationally efficient Copyright 2001 2003 Andrew W Moore Nonlinear Kernel I Copyright 2001 2003 Andrew W Moore Nonlinear Kernel II Copyright 2001 2003 Andrew W Moore Reproducing Kernel Hilbert Space RKHS Reproducing Kernel Hilbert Space H Eigen decomposition Elements of space H Reproducing property Reproducing Kernel Hilbert Space RKHS Representer theorem Kernelize Logistic Regression How can we introduce nonlinearity into the logistic regression model Copyright 2001 2003 Andrew W Moore Diffusion Kernel Kernel function describes the correlation or similarity between two data points Given that a similarity function s x y Non negative and symmetric Does not obey Mercer s condition How can we generate a kernel …