Two SVM tutorials linked in class website please read both High level presentation with applications Hearst 1998 Detailed tutorial Burges 1998 Support Vector Machines Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 22nd 2005 2006 Carlos Guestrin 1 Announcements Third homework is out Due March 1st Final assigned by registrar May 12 1 4p m Location TBD 2006 Carlos Guestrin 2 Linear classifiers Which line is better Data Example i w x j w j x j 2006 Carlos Guestrin 3 w x b 0 Pick the one with the largest margin w x j w j x j 2006 Carlos Guestrin 4 w x b 0 Maximize the margin 2006 Carlos Guestrin 5 w x b 0 But there are a many planes 2006 Carlos Guestrin 6 w x b 0 Review Normal to a plane 2006 Carlos Guestrin 7 margin 2 1 0 w x b x w x b 1 w x b Normalized margin Canonical hyperplanes x 2006 Carlos Guestrin 8 margin 2 1 0 w x b x w x b 1 w x b Normalized margin Canonical hyperplanes x 2006 Carlos Guestrin 9 1 w x b 0 w x b w x b 1 Margin maximization using canonical hyperplanes margin 2 2006 Carlos Guestrin 10 1 w x b 0 w x b w x b 1 Support vector machines SVMs Solve efficiently by quadratic programming QP Well studied solution algorithms margin 2 Hyperplane defined by support vectors 2006 Carlos Guestrin 11 What if the data is not linearly separable Use features of features of features of features 2006 Carlos Guestrin 12 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 2006 Carlos Guestrin 13 Slack variables Hinge loss If margin 1 don t care If margin 1 pay linear penalty 2006 Carlos Guestrin 14 Side note What s the difference between SVMs and logistic regression SVM Logistic regression Log loss 2006 Carlos Guestrin 15 What about multiple classes 2006 Carlos Guestrin 16 One against All Learn 3 classifiers 2006 Carlos Guestrin 17 Learn 1 classifier Multiclass SVM Simultaneously learn 3 sets of weights 2006 Carlos Guestrin 18 Learn 1 classifier Multiclass SVM 2006 Carlos Guestrin 19 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 2006 Carlos Guestrin 20 SVMs Duality and the Kernel Trick Machine Learning 10701 15781 Carlos Guestrin Carnegie Mellon University February 22nd 2005 2006 Carlos Guestrin 21 SVMs reminder 2006 Carlos Guestrin 22 You will now Learn one of the most interesting and exciting recent advancements in machine learning The kernel trick High dimensional feature spaces at no extra cost But first a detour Constrained optimization 2006 Carlos Guestrin 23 Constrained optimization 2006 Carlos Guestrin 24 Lagrange multipliers Dual variables 2006 Carlos Guestrin 25 Dual SVM derivation 1 the linearly separable case 2006 Carlos Guestrin 26 Dual SVM derivation 2 the linearly separable case 2006 Carlos Guestrin 27 w x b 0 Dual SVM interpretation 2006 Carlos Guestrin 28 Dual SVM formulation the linearly separable case 2006 Carlos Guestrin 29 Dual SVM derivation the non separable case 2006 Carlos Guestrin 30 Dual SVM formulation the non separable case 2006 Carlos Guestrin 31 Why did we learn about the dual SVM There are some quadratic programming algorithms that can solve the dual faster than the primal But more importantly the kernel trick Another little detour 2006 Carlos Guestrin 32 Reminder from last time What if the data is not linearly separable Use features of features of features of features Feature space can get really large really quickly 33 2006 Carlos Guestrin number of monomial terms Higher order polynomials d 4 m input features d degree of polynomial d 3 d 2 number of input dimensions 2006 Carlos Guestrin grows fast d 6 m 100 about 1 6 billion terms 34 Dual formulation only depends on dot products not on w 2006 Carlos Guestrin 35 Dot product of polynomials 2006 Carlos Guestrin 36 Finally the kernel trick Never represent features explicitly Compute dot products in closed form Constant time high dimensional dotproducts for many classes of features Very interesting theory Reproducing Kernel Hilbert Spaces Not covered in detail in 10701 15781 more in 10702 2006 Carlos Guestrin 37 Polynomial kernels All monomials of degree d in O d operations How about all monomials of degree up to d Solution 0 Better solution 2006 Carlos Guestrin 38 Common kernels Polynomials of degree d Polynomials of degree up to d Gaussian kernels Sigmoid 2006 Carlos Guestrin 39 Overfitting Huge feature space with kernels what about overfitting Maximizing margin leads to sparse set of support vectors Some interesting theory says that SVMs search for simple hypothesis with large margin Often robust to overfitting 2006 Carlos Guestrin 40 What about at classification time For a new input x if we need to represent x we are in trouble Recall classifier sign w x b Using kernels we are cool 2006 Carlos Guestrin 41 SVMs with kernels Choose a set of features and kernel function Solve dual problem to obtain support vectors i At classification time compute Classify as 2006 Carlos Guestrin 42 What s the difference between SVMs and Logistic Regression Loss function High dimensional features with kernels SVMs Logistic Regression Hinge loss Log loss Yes No 2006 Carlos Guestrin 43 Kernels in logistic regression Define weights in terms of support vectors Derive simple gradient descent rule on i 2006 Carlos Guestrin 44 What s the difference between SVMs and Logistic Regression Revisited Loss function High dimensional features with kernels Solution sparse SVMs Logistic Regression Hinge loss Log loss Yes Yes Often yes Almost always no 2006 Carlos Guestrin 45 What you need to know Dual SVM formulation How it s derived The kernel trick Derive polynomial kernel Common kernels Kernelized logistic regression Differences between SVMs and logistic regression 2006 Carlos Guestrin 46 Acknowledgment SVM applet http www site uottawa ca gcaron applets htm 2006 Carlos Guestrin 47 Acknowledgment SVM applet http www site uottawa ca gcaron applets htm 2006 Carlos Guestrin 48
View Full Document
Unlocking...