Support Vector MachinesLinear classifiers – Which line is better?Pick the one with the largest margin!Maximize the marginBut there are a many planes…Review: Normal to a planeNormalized margin – Canonical hyperplanesMargin maximization using canonical hyperplanesSupport vector machines (SVMs)What if the data is not linearly separable?What if the data is still not linearly separable?Slack variables – Hinge lossSide note: What’s the difference between SVMs and logistic regression?What about multiple classes?One against AllLearn 1 classifier: Multiclass SVMLearn 1 classifier: Multiclass SVMWhat you need to knowAcknowledgmentTwo SVM tutorials linked in class website (please, read both): High-level presentation with applications (Hearst 1998) Detailed tutorial (Burges 1998)Support Vector MachinesMachine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityFebruary 16th, 2005Linear classifiers – Which line is better?Data:Example i:w.x = ∑jw(j)x(j)Pick the one with the largest margin!w.x+ b = 0w.x = ∑jw(j)x(j)Maximize the marginw.x+ b = 0But there are a many planes…w.x+ b = 0Review: Normal to a planew.x+ b = 0Normalized margin – Canonical hyperplanesw.x+ b = +1w.x+ b = -1w.x+ b = 0margin γx-x+Margin maximization using canonical hyperplanesw.x+ b = +1w.x+ b = -1w.x+ b = 0margin γSupport vector machines (SVMs)w.x+ b = +1w.x+ b = -1w.x+ b = 0margin γ Solve efficiently by quadratic programming (QP) Well-studied solution algorithms Hyperplane defined by support vectorsWhat if the data is not linearly separable?Use features of features of features of features….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 mistakesSlack variables – Hinge loss If margin ≥ 1, don’t care If margin < 1, pay linear penaltySide note: What’s the difference between SVMs and logistic regression?SVM:Logistic regression:Log loss:What about multiple classes?One against AllLearn 3 classifiers:Learn 1 classifier: Multiclass SVMSimultaneously learn 3 sets of weightsLearn 1 classifier: Multiclass SVMWhat 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 SVMsAcknowledgment SVM applet:
View Full Document
Unlocking...