Error Correction in Learning using SVMs
Preprint
Abstract
This paper is concerned with learning binary classifiers under adversarial label-noise. We introduce the problem of error-correction in learning where the goal is to recover the original clean data from a label-manipulated version of it, given (i) no constraints on the adversary other than an upper-bound on the number of errors, and (ii) some regularity properties for the original data. We present a simple and practical error-correction algorithm called SubSVMs that learns individual SVMs on several small-size (log-size), class-balanced, random subsets of the data and then reclassifies the training points using a majority vote. Our analysis reveals the need for the two main ingredients of SubSVMs, namely class-balanced sampling and subsampled bagging. Experimental results on synthetic as well as benchmark UCI data demonstrate the effectiveness of our approach. In addition to noise-tolerance, log-size subsampled bagging also yields significant run-time benefits over standard SVMs.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- The Balanced Accuracy and Its Posterior Distribution2010
- Random classification noise defeats all convex potential boostersMachine Learning, 2009
- Maximum margin classifiers with noisy data: a robust optimization approach2006
- Hardness of Learning Halfspaces with Noise2006
- New Results for Learning Noisy Parities and Halfspaces2006
- Bagging Equalizes InfluenceMachine Learning, 2004
- Applying Support Vector Machines to Imbalanced Datasets2004
- On the difficulty of approximately maximizing agreementsJournal of Computer and System Sciences, 2003
- A polynomial-time algorithm for learning noisy linear threshold functions2002
- Smooth Boosting and Learning with Malicious Noise2001