Support Vector Machines Note to other teachers and users of these slides Andrew would be delighted if you found this source material useful in giving your own lectures Feel free to use these slides verbatim or to modify them to fit your own needs PowerPoint originals are available If you make use of a significant portion of these slides in your own lecture please include this message or the following link to the source repository of Andrew s tutorials http www cs cmu edu awm tutorials Comments and corrections gratefully received Andrew W Moore Professor School of Computer Science Carnegie Mellon University www cs cmu edu awm awm cs cmu edu 412 268 7599 Copyright 2001 2003 Andrew W Moore Linear Classifiers x denotes 1 Nov 23rd 2001 f yest f x w b sign w x b denotes 1 How would you classify this data Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 2 1 Linear Classifiers x f yest f x w b sign w x b denotes 1 denotes 1 How would you classify this data Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 3 Linear Classifiers x denotes 1 f yest f x w b sign w x b denotes 1 How would you classify this data Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 4 2 Linear Classifiers x f yest f x w b sign w x b denotes 1 denotes 1 How would you classify this data Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 5 Linear Classifiers x denotes 1 f yest f x w b sign w x b denotes 1 Any of these would be fine but which is best Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 6 3 Classifier Margin x f f x w b sign w x b denotes 1 Define the margin of a linear classifier as the width that the boundary could be increased by before hitting a datapoint denotes 1 Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 7 Maximum Margin x denotes 1 f yest f x w b sign w x b The maximum margin linear classifier is the linear classifier with the um maximum margin denotes 1 Linear SVM Copyright 2001 2003 Andrew W Moore yest This is the simplest kind of SVM Called an LSVM Support Vector Machines Slide 8 4 Maximum Margin x denotes 1 f f x w b sign w x b The maximum margin linear classifier is the linear classifier with the um maximum margin denotes 1 Support Vectors are those datapoints that the margin pushes up against Linear SVM Copyright 2001 2003 Andrew W Moore yest This is the simplest kind of SVM Called an LSVM Support Vector Machines Slide 9 Why Maximum Margin 1 Intuitively this feels safest denotes 1 denotes 1 Support Vectors are those datapoints that the margin pushes up against f x w b sign w b 2 If we ve made a small error inx the location of the boundary it s been The maximum jolted in its perpendicular direction this gives us leastmargin chance linear of causing a misclassification classifier is the 3 LOOCV is easy since the classifier model is linear immune to removal of any with the nonum support vector datapoints maximum margin 4 There s some theory using VC is the dimension that isThis related to but not kind the same as thesimplest proposition thatof this is a good thing SVM Called an LSVM 5 Empirically it works very very well Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 10 5 Specifying a line and margin Pr s las e C t c zon edi Pr 1 s las C t c zone edi 1 Plus Plane Classifier Boundary Minus Plane How do we represent this mathematically in m input dimensions Copyright 2001 2003 Andrew W Moore Pr s las e C t c zon edi Pr 1 s las C ct zone edi 1 Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 11 Plus Plane Classifier Boundary Minus Plane Support Vector Machines Slide 12 6 Specifying a line and margin Pr s las e C t c zon edi 1 b wx 0 b wx b 1 wx Pr 1 s las C t c zone edi 1 Plus Plane Classifier Boundary Minus Plane Plus plane x w x b 1 Minus plane x w x b 1 if w x b 1 1 if w x b 1 Universe explodes if 1 w x b 1 Classify as 1 Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 13 Computing the margin width 1 s las t C one c i z ed Pr 1 b wx 0 b wx b 1 wx s las C t c zone edi r P M Margin Width 1 How do we compute M in terms of w and b Plus plane x w x b 1 Minus plane x w x b 1 Claim The vector w is perpendicular to the Plus Plane Why Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 14 7 Computing the margin width Pr s las e C t c zon edi 1 b wx 0 b wx b 1 wx Pr 1 s las C t c zone edi M Margin Width 1 How do we compute M in terms of w and b Plus plane x w x b 1 Minus plane x w x b 1 Claim The vector w is perpendicular to the Plus Plane Why Let u and v be two vectors on the Plus Plane What is w u v And so of course the vector w is also perpendicular to the Minus Plane Copyright 2001 2003 Andrew W Moore Support Vector Machines Slide 15 Computing the margin width 1 x M Margin Width ss a l ct C zone edi r P 1 How do we compute x s s M in terms of w 1 Cla b ict zone 0 wx d e b 1 and b Pr wx b wx Plus plane x w x b 1 Minus plane x w x b 1 The vector w is perpendicular to the Plus Plane Let x be any point on the minus plane Let x be the closest plus plane point to x Copyright 2001 2003 Andrew W Moore Any location in not mm not R necessarily a datapoint Support Vector Machines Slide 16 8 Computing the margin width Pr s las e C t c zon edi 1 b wx 0 b wx b 1 wx Pr 1 x M Margin Width 1 sx las C e t c zon edi How do we compute M in terms of w and b Plus plane x w x b 1 Minus plane x w x b 1 The vector w is perpendicular to the Plus Plane Let x be any point on the minus plane Let x be the closest plus plane point to x Claim x x w for some value of Why Copyright 2001 2003 Andrew W Moore Support Vector Machines …
View Full Document
Unlocking...