Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

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

: Christmann, A.; Fischer, P.; Joachims, T.


Computational statistics 17 (2002), No.2, pp.273-288
ISSN: 0943-4062
ISSN: 0723-712X
Journal Article
Fraunhofer AIS ( IAIS) ()

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.