Outline Optimal Hyperplanes CS4780 Machine Learning Fall 2009 Optimal hyperplanes and margins Hard margin Support Vector Machine Primal optimization problem Soft margin Support Vector Machine Thorsten Joachims Cornell University Reading Schoelkopf Smola Chapter 7 1 7 3 7 5 online Optimal Hyperplanes Linear Hard Margin Support Vector Machine Assumption Training examples are linearly separable Hard Margin Separation Goal Find hyperplane with the largest distance to the closest training examples Optimization Problem Primal Support Vectors Examples with minimal distance i e margin Non Separable Training Data Soft Margin Separation Idea Maximize margin and minimize training error 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 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 trade off between margin and training error 1 Example Reuters acq Varying C Controlling Soft Margin Separation Soft Margin OP Primal i is upper bound on number of training errors C is a parameter that controls trade off between margin and training error Example Margin in High Dimension Training Sample Strain y x1 x2 x3 x4 x5 x6 x7 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 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 Hyperplane 6 0 95 0 95 0 0 05 0 05 1 b 0 05 0 05 0 2