SVMs Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University October 19th 2009 1 Carlos Guestrin 2005 2009 Linear classifiers Which line is better Data Example i w x j w j x j 2005 2007 Carlos Guestrin 2 1 Pick the one with the largest margin w x j w j x j 2005 2007 Carlos Guestrin 3 Maximize the margin 2005 2007 Carlos Guestrin 4 2 But there are a many planes 2005 2007 Carlos Guestrin 5 Review Normal to a plane 2005 2007 Carlos Guestrin 6 3 Normalized margin Canonical hyperplanes x x 2005 2007 Carlos Guestrin 7 Normalized margin Canonical hyperplanes x x 2005 2007 Carlos Guestrin 8 4 Margin maximization using canonical hyperplanes 2005 2007 Carlos Guestrin 9 Support vector machines SVMs Solve efficiently by quadratic programming QP Well studied solution algorithms Hyperplane defined by support vectors 2005 2007 Carlos Guestrin 10 5 What if the data is not linearly separable Use features of features of features of features 2005 2007 Carlos Guestrin 11 What if the data is still not linearly separable Minimize w w and number of training mistakes Tradeoff two criteria Tradeoff mistakes and w w 0 1 loss Slack penalty C Not QP anymore Also doesn t distinguish near misses and really bad mistakes 2005 2007 Carlos Guestrin 12 6 Slack variables Hinge loss If margin 1 don t care If margin 1 pay linear penalty 2005 2007 Carlos Guestrin 13 Side note What s the difference between SVMs and logistic regression SVM Logistic regression Log loss 2005 2007 Carlos Guestrin 14 7 What about multiple classes 2005 2007 Carlos Guestrin 15 One against All Learn 3 classifiers 2005 2007 Carlos Guestrin 16 8 Learn 1 classifier Multiclass SVM Simultaneously learn 3 sets of weights 2005 2007 Carlos Guestrin 17 Learn 1 classifier Multiclass SVM 2005 2007 Carlos Guestrin 18 9 What you need to know Maximizing margin Derivation of SVM formulation Slack variables and hinge loss Relationship between SVMs and logistic regression 0 1 loss Hinge loss Log loss Tackling multiple class One against All Multiclass SVMs 2005 2007 Carlos Guestrin 19 10
View Full Document
Unlocking...