Support vector machine classification via parameterless robust linear programming

Abstract

We show that the problem of minimizing the sum of arbitrary-norm real distances to misclassified points, from a pair of parallel bounding planes of a classification problem, divided by the margin (distance) between the two bounding planes, leads to a simple parameterless linear program. This constitutes a linear support vector machine (SVM) that simultaneously minimizes empirical error of misclassified points while maximizing the margin between the bounding planes. Nonlinear kernel SVMs can be similarly represented by a parameterless linear program in a typically higher dimensional feature space.