A Mathematical Foundation for Robust Machine Learning based on Bias-Variance Trade-off

Ou Wu, Weiyao Zhu, Yingjun Deng, Haixiang Zhang, Qing-Hu HouarXiv 2021 · OpenReview

TL;DR

This paper proposes a unified mathematical framework for Robust Machine Learning (RML) by grounding it in the well-established bias-variance trade-off theory. It defines concepts like "easy," "hard," and "quite-hard" samples and uses these to analyze and unify various RML techniques, offering new insights into their behavior and potential improvements.

What Problem Does This Paper Address?

In machine learning, it's often assumed that training samples are independent and identically distributed (i.i.d.). However, in reality, different samples contribute differently to the learning process. Some are easy to learn, some are noisy, and some are particularly challenging. This unequal contribution significantly impacts model performance. Existing Robust Machine Learning (RML) methods, which aim to handle these variations, often use conflicting strategies (e.g., prioritizing hard vs. easy samples) and lack a unified theoretical basis for comparison and understanding. This paper aims to bridge this gap by providing a mathematical foundation for RML based on the bias-variance trade-off.

Methods

The core of this paper is the development of a theoretical framework for RML built upon the bias-variance trade-off. Key methodological contributions include:

  • Formal Definitions: Introducing precise mathematical definitions for concepts like "easy," "hard," "quite-hard" samples, and "relative learning difficulty" between data sets.
  • Bias-Variance Decomposition for RML: Extending the bias-variance decomposition to analyze the impact of different sample types on the learning error.
  • Balance Point Analysis: Defining and analyzing the "balance point" of a model's complexity, which is where bias and variance are optimally balanced for a given dataset. The paper investigates how various RML techniques shift this balance point.
  • Categorization of Hyperparameters: Classifying hyperparameters into three types based on their influence on bias, variance, or the training procedure.
  • Propositional Framework: Proving a series of propositions that mathematically describe how changes in sample weights, bias, or variance affect the balance point and, consequently, model complexity.
  • Unified Framework: Proposing a unified weighting scheme that combines elements of Self-Paced Learning (SPL) and Focal Loss to handle different sample types.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and framework development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bias-Variance as the Unifying Principle: The paper convincingly argues that the bias-variance trade-off is the fundamental principle underlying various RML strategies, providing a common language to understand their diverse approaches.
  • "Easy," "Hard," and "Quite-Hard" Samples Defined: By mathematically defining these sample categories based on their contribution to bias and variance, the paper offers a rigorous way to analyze their impact.
  • Balance Point as a Complexity Indicator: The "balance point" serves as a crucial metric for understanding how RML techniques influence model complexity and generalization.
  • Weighting Strategies Directly Impact Balance Point: The propositions clearly demonstrate how modifying sample weights (e.g., increasing weights for hard samples) directly shifts the balance point, leading to more complex models.
  • Unified Framework for SPL and Focal Loss: The proposed unified weighting function offers a principled way to combine the strengths of SPL (favoring easy samples) and Focal Loss (favoring hard samples).

Key Results

The paper's primary results are theoretical:

  • Mathematical Framework: A formal framework for RML based on bias-variance trade-off, including definitions and propositions.
  • Analysis of Existing Methods: New insights into how classical RML algorithms like SVM, Focal Loss, SPL, and AdaBoost operate within this framework, explaining their behavior in terms of shifting the balance point.
  • Unified Weighting Scheme: A proposed weighting function that unifies SPL and Focal Loss, offering a flexible approach to sample weighting.
  • Theoretical Understanding of Sample Difficulty: Formal definitions for easy, hard, and quite-hard samples that provide a theoretical basis for sample selection and weighting.

Limitations and Future Work

  • Mathematical Foundation of Bias-Variance: The authors acknowledge that the bias-variance trade-off theory itself lacks a fully rigorous mathematical foundation, and Assumption 1 (bias decreases, variance increases with complexity) is widely used but not strictly proven.
  • Feasible Calculation: While theoretical definitions for sample difficulty are provided, the paper notes that practical, feasible calculation steps for identifying hard samples and creating EMH splits are not directly provided.
  • Empirical Validation: The paper focuses on theoretical analysis. Future work will involve solidifying the mathematical basis of bias-variance trade-off, improving the RML framework, and developing more effective robust learning algorithms based on this framework. The effectiveness of the proposed unified strategies also needs empirical verification.

Summary updated

Abstract

A common assumption in machine learning is that samples are independently and identically distributed (i.i.d). However, the contributions of different samples are not identical in training. Some samples are difficult to learn and some samples are noisy. The unequal contributions of samples has a considerable effect on training performances. Studies focusing on unequal sample contributions (e.g., easy, hard, noisy) in learning usually refer to these contributions as robust machine learning (RML). Weighing and regularization are two common techniques in RML. Numerous learning algorithms have been proposed but the strategies for dealing with easy/hard/noisy samples differ or even contradict with different learning algorithms. For example, some strategies take the hard samples first, whereas some strategies take easy first. Conducting a clear comparison for existing RML algorithms in dealing with different samples is difficult due to lack of a unified theoretical framework for RML. This study attempts to construct a mathematical foundation for RML based on the bias-variance trade-off theory. A series of definitions and properties are presented and proved. Several classical learning algorithms are also explained and compared. Improvements of existing methods are obtained based on the comparison. A unified method that combines two classical learning strategies is proposed.
BibTeX
@misc{wu2021mathematical,
  author = {Ou Wu and Weiyao Zhu and Yingjun Deng and Haixiang Zhang and Qing-Hu Hou},
  title = {{A Mathematical Foundation for Robust Machine Learning based on Bias-Variance Trade-off}},
  year = {2021},
  eprint = {2106.05522},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.05522},
}
Figure