11SVMsMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityOctober 19th, 2009©Carlos Guestrin 2005-20092005-2007 Carlos Guestrin 2Linear classifiers – Which line is better?Data:Example i:w.x = ∑jw(j)x(j)22005-2007 Carlos Guestrin 3Pick the one with the largest margin!w.x = ∑jw(j)x(j)2005-2007 Carlos Guestrin 4Maximize the margin32005-2007 Carlos Guestrin 5But there are a many planes…2005-2007 Carlos Guestrin 6Review: Normal to a plane42005-2007 Carlos Guestrin 7Normalized margin – Canonical hyperplanesx-x+2005-2007 Carlos Guestrin 8Normalized margin – Canonical hyperplanesx-x+52005-2007 Carlos Guestrin 9Margin maximization using canonical hyperplanes2005-2007 Carlos Guestrin 10Support vector machines (SVMs) Solve efficiently by quadratic programming (QP) Well-studied solution algorithms Hyperplane defined by support vectors62005-2007 Carlos Guestrin 11What if the data is not linearly separable?Use features of features of features of features….2005-2007 Carlos Guestrin 12What 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 mistakes72005-2007 Carlos Guestrin 13Slack variables – Hinge loss If margin ≥ 1, don’t care If margin < 1, pay linear penalty2005-2007 Carlos Guestrin 14Side note: What’s the difference between SVMs and logistic regression?SVM:Logistic regression:Log loss:82005-2007 Carlos Guestrin 15What about multiple classes?2005-2007 Carlos Guestrin 16One against AllLearn 3 classifiers:92005-2007 Carlos Guestrin 17Learn 1 classifier: Multiclass SVMSimultaneously learn 3 sets of weights2005-2007 Carlos Guestrin 18Learn 1 classifier: Multiclass SVM102005-2007 Carlos Guestrin 19What 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
View Full Document
Unlocking...