Comparison between various regression depth methods and the support vector machine to approximate the minimum number of misclassifications

The minimum number of misclassifications achievable with affine hyperplanes on a given set of labeled points is a key quantity in both statistics and computational learning theory. However, determining this quantity exactly is NP-hard, c.f. Hoffgen, Simon and van Horn (1995). Hence, there is a need to find reasonable approximation procedures. This paper introduces two new approaches to approximating the minimum number of misclassifications achievable with affine hyperplanes. Both approaches are modifications of the regression depth method proposed by Rousseeuw and Hubert (1999) for linear regression models. Our algorithms are compared to the existing regression depth algorithm (cf. Christmann and Rousseeuw, 1999) for various data sets. We also used a support vector machine approach, as proposed by Vapnik (1998), as a reference method