Support Vector Machine Classi cation via Parameterless Robust Linear Programming

Abstract

We show that the problem of minimizing the sum of arbitrary-norm real distances to misclassi ed points, from a pair of parallel bounding planes of a classi cation problem, divided by the margin (distance) be- tween the two bounding planes, leads to a simple parameterless linear program. This constitutes a linear support vector machine (SVM) that si- multaneously minimizes empirical error of misclassi ed points while max- imizing the margin between the bounding planes.Nonlinear kernel SVMs can be similarly represented by a parameterless linear program in a typi- cally higher dimensional feature space.