Support Vector Machines Optimal Hyperplanes CS4780 5780 Machine Learning Fall 2011 Thorsten Joachims Cornell University Reading Schoelkopf Smola Chapter 7 1 7 3 7 5 online Outline Optimal hyperplanes and margins Hard margin Support Vector Machine Primal optimization problem Soft margin Support Vector Machine Optimal Hyperplanes Assumption Training examples are linearly separable Hard Margin Separation Goal Find hyperplane with the largest distance to the closest training examples Optimization Problem Primal d d Support Vectors Examples with minimal distance i e margin d Non Separable Training Data Limitations of hard margin formulation For some training data there is no separating hyperplane Complete separation i e zero training error can lead to suboptimal prediction error Soft Margin Separation Idea Maximize margin and minimize training error Hard Margin OP Primal Soft Margin OP Primal Slack variable i measures by how much xi yi fails to achieve margin i is upper bound on number of training errors C is a parameter that controls tradeoff between margin and training error Controlling Soft Margin Separation i is upper bound on number of training errors C is a parameter that controls trade off between margin and training error Soft Margin OP Primal Large C Small C Example Reuters acq Varying C Example Margin in High Dimension Training Sample Strain y x1 x2 x3 x4 x5 x6 x7 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 b w1 w2 w3 w4 w5 w6 w7 Hyperplane 1 1 1 0 0 0 0 0 2 Hyperplane 2 0 0 0 1 1 1 1 0 Hyperplane 3 1 1 1 0 0 0 0 0 Hyperplane 4 0 5 0 5 0 0 0 0 0 0 Hyperplane 5 1 1 0 0 0 0 0 0 0 0 05 0 05 Hyperplane 6 0 95 0 95 0 05 0 05 0