Support-Vector Networks

Inside the paper

The problem

A classifier that separates two groups cleanly in its training data may still generalize poorly, and real training sets may contain overlapping classes. Earlier optimal-hyperplane methods assumed that a separating surface could classify every training example correctly.

The idea

Construct a wide-margin separator while permitting violations, then use dot products in a feature space to make the boundary nonlinear in the original inputs. The resulting decision depends on selected training examples called support vectors.

How it works

• Represent each example by a feature vector and choose a separating hyperplane with a large margin between the two classes.
• Introduce a penalty for margin violations, allowing the optimization to handle examples that cannot be separated perfectly.
• Solve the resulting constrained optimization problem; examples with nonzero coefficients become the support vectors used by the classifier.
• Replace feature-space dot products with a kernel, such as a polynomial, so the nonlinear feature mapping need not be calculated explicitly.

What it showed

The authors compare polynomial support-vector classifiers with other methods on handwritten digit recognition and report competitive accuracy. Their experiments also illustrate the effect of the penalty and polynomial degree on classification.

Read it for

Read Sections 2 and 3 together to see how the margin changes when errors are allowed, then Section 4 for the kernel construction. Section 6.2 and its digit results connect the method to an application; the longer appendix can wait.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.