Fundamentals for Binary Classification Under Label Noise
arXiv:2611.25372 · doi:10.1007/978-3-032-39161-2_3
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.
arXiv comment59 pages, 6 figures, 3 tables. Preprint of a chapter published in the book Mathematics and Artificial Intelligence (Springer)
References in corpus (13)
- Multiple Instance Learning: A Survey of Problem Characteristics and Applications
- Noise Tolerance under Risk Minimization
- Risk bounds for statistical learning
- Adversarial Examples: Opportunities and Challenges
- Making Risk Minimization Tolerant to Label Noise
- Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning
- Certified Defenses for Data Poisoning Attacks
- Adversarial Examples in Modern Machine Learning: A Review
- Distribution-Independent PAC Learning of Halfspaces with Massart Noise
- A Review of Pseudo-Labeling for Computer Vision
- Data Poisoning in Deep Learning: A Survey
- Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data
- Beyond Tsybakov: Model Margin Noise and -Consistency Bounds