Fundamentals for Binary Classification Under Label Noise
Abstract
This chapter surveys fundamental results for binary classification under label noise. Binary classification under label noise involves training models on datasets where class labels are partially incorrect, leading to degraded performance and misclassification. We distinguish poisoning attacks from noise processes and formalize random classification noise, Massart noise, and malicious classification noise within the probably approximately correct (PAC) framework. These models capture different adversarial strengths and data-generation realities. We then highlight some core ideas and representative results. In particular, we explain why random classification noise preserves the expected ordering of hypotheses and thus supports learning using the empirical risk minimization (ERM) principle, how sample complexity depends on the noise rate, and why learning algorithms often require an upper bound on the corruption level, as well as how such a bound may be estimated from data in the case of random classification noise. We also discuss computational aspects of ERM under noise and present a canonical negative result technique -- the method of induced distributions -- within the malicious noise model where the adversary has more power and may affect not only the label of an example but also the instance. We conclude with pointers to related work and a taxonomy that organizes classical label-noise models using the NCAR/NAR/NNAR lens.
- Comment
- 59 pages, 6 figures, 3 tables. Preprint of a chapter published in the book Mathematics and Artificial Intelligence (Springer)
- Journal ref
- In: M. C. Golumbic and F. Hoffman (eds.), Mathematics and Artificial Intelligence, Springer, Cham, 2027, pp. 37-96
- DOI
- 10.1007/978-3-032-39161-2_3