PaperlayerView exact revision on arXiv

Source-linked AI summary

The Theory Behind Overfitting, Cross Validation, Regularization, Bagging, and Boosting: Tutorial

Benyamin Ghojogh, Mark Crowley

arXiv:1905.12787v2stat.MLcs.LG

TL;DR

The tutorial addresses how estimation error and model complexity relate to overfitting and how common validation, regularization, bagging, and boosting methods work. It develops these ideas theoretically using error decompositions and SURE, then presents examples across machine learning and computer vision. The paper concludes by introducing the methods and explaining their theoretical rationale within the tutorial’s stated scope.

  • Problem

    The tutorial examines overfitting and related methods by asking how their error behavior and theoretical mechanisms can be characterized.

  • Method

    The paper synthesizes definitions, error analyses using SURE, and theoretical explanations of cross validation, regularization, bagging, and boosting.

  • Results

    The tutorial explains that validation detects rising true error during overfitting, regularization penalizes complexity, and bagging reduces estimation variance.

  • Takeaways & Limitations

    The paper provides a unified tutorial framework connecting model complexity, generalization, regularization, bagging, and boosting across machine learning and computer vision examples.

  • Takeaways & Limitations

    Validation must remain disjoint from training, and bagging’s variance benefit depends on the trained models not being highly correlated.

Abstract

from arXiv · show

In this tutorial paper, we first define mean squared error, variance, covariance, and bias of both random variables and classification/predictor models. Then, we formulate the true and generalization errors of the model for both training and validation/test instances where we make use of the Stein's Unbiased Risk Estimator (SURE). We define overfitting, underfitting, and generalization using the obtained true and generalization errors. We introduce cross validation and two well-known examples which are $K$-fold and leave-one-out cross validations. We briefly introduce generalized cross validation and then move on to regularization where we use the SURE again. We work on both $\ell_2$ and $\ell_1$ norm regularizations. Then, we show that bootstrap aggregating (bagging) reduces the variance of estimation. Boosting, specifically AdaBoost, is introduced and it is explained as both an additive model and a maximum margin model, i.e., Support Vector Machine (SVM). The upper bound on the generalization error of boosting is also provided to show why boosting prevents from overfitting. As examples of regularization, the theory of ridge and lasso regressions, weight decay, noise injection to input/weights, and early stopping are explained. Random forest, dropout, histogram of oriented gradients, and single shot multi-box detector are explained as examples of bagging in machine learning and computer vision. Finally, boosting tree and SVM models are mentioned as examples of boosting.

1. Introduction

The tutorial establishes training, test, and validation datasets before introducing a theoretical treatment of overfitting, cross validation, regularization, bagging, and boosting.

  • Dataset setup: The dataset D contains disjoint training and test subsets, with an optional validation subset V.Training observations are used to fit models, while test observations are not used for training.
  • Bias and variance intuition: Figure 1 organizes estimation quality by bias and variance, identifying high bias/high variance as worst and low bias/low variance as best.The center of each circle represents the true value.
  • Tutorial scope: The paper introduces overfitting, cross validation, generalized cross validation, regularization, bagging, and boosting.It also explains why these methods work theoretically and gives machine-learning and computer-vision examples.

2. Mean Squared Error, Variance, and Bias

This section defines variance, covariance, bias, and MSE for random-variable estimates, then extends these concepts to estimated models and ensemble classifiers.

  • Random-variable measures: Variance measures squared deviation of an estimate from its mean, while bias measures deviation of its mean from the original variable.The paper introduces these quantities as core measures for analyzing estimation quality.
  • Random-variable measures: Mean squared error measures how much an estimate deviates from the original variable and combines bias and variance.The dart example illustrates four combinations of high and low bias and variance.
  • Random-variable measures: Covariance quantifies joint variation between two estimates and is zero when the corresponding random variables are independent.The paper notes that the reverse implication does not generally hold.
  • Model measures: For models, the true function is unknown, observations are noisy, and a trained estimated model predicts outputs for training or test inputs.The same bias, variance, and MSE definitions are applied to model estimates.
  • Ensemble models: Ensemble-model analysis defines prediction error, bias, and variance relative to the Bayes-optimal prediction and majority-vote classification.The paper discusses these definitions for ensemble methods such as bagging and boosting.

3. Mean Squared Error of the Estimation of Observations

The paper derives true error for unseen and training instances, showing when empirical error is reliable and when SURE adds a model-complexity correction.

  • Case I: Instance outside the training set: For instances outside the training set, the empirical error is a good estimate of true error because the noise-related term is constant.The paper therefore permits minimizing empirical error to minimize true error in this case.
  • Case II: Instance in the training set: For training instances, SURE relates true error to empirical error plus a correction involving the model’s sensitivity to training observations.Stein’s Lemma supplies the mathematical step used to derive this relation.
  • Case II: Instance in the training set: The derivative ∂bfi/∂yi measures how much the model estimate changes when a training observation moves, serving as a complexity or overfitting measure.A simple least-squares line changes little, whereas a curve passing through all points can change substantially.
  • Case II: Instance in the training set: When training observations are used, minimizing empirical error can increase model complexity and eventually stop reducing true error.The resulting training error can therefore underestimate performance on unseen data.
  • Estimating σ: The noise standard deviation σ is estimated from training observations, but the estimator itself depends on model complexity.The paper recommends a high-bias, low-variance estimator such as a least-squares line for this purpose.

4. Overfitting, Underfitting, and Generalization

Underfitting uses an overly simple model with high bias and low variance, whereas overfitting uses an overly complex model with low bias and high variance; both impair generalization.

  • Underfitting: Underfitting is characterized by low variance, high bias, and low complexity.The paper also calls underfitting overgeneralization.
  • Overfitting: Overfitting is characterized by high variance, low bias, and high complexity.The model fits the training data closely but may perform poorly on unseen instances.
  • Generalization: Generalization is the ability to estimate unseen out-of-sample data, and both underfitting and overfitting can weaken it.A good fit estimates unseen test instances with smaller error.
  • Overfitting: In overfitting, training error is very small while test true error is usually poor.This discrepancy is the central practical warning in the section.

5. Cross Validation

Cross validation separates training, validation, and test roles to estimate out-of-sample performance, tune model parameters, and detect overfitting. K-fold and leave-one-out procedures reuse disjoint data partitions, while validation monitoring helps identify when training should stop.

  • Cross validation estimates unseen-data performance and helps select training complexity or tune model parameters.
  • K-fold Cross Validation: K-fold cross validation randomly divides D into K partitions, trains on K−1 partitions, tests on the remaining partition, and averages the test errors.
  • Leave-One-Out Cross Validation: Leave-one-out cross validation uses one instance as the test set and the remaining data for training, making it useful for small datasets.
  • Validation and Test Separation: Training, validation, and test sets should be disjoint; using test data for optimization is cheating, while overlap between training and validation can obscure overfitting.
  • Overfitting Detection: Validation error typically decreases before increasing as training continues, so early stopping selects the last model with the lowest recent validation error.

6. Generalized Cross Validation

Generalized cross validation reformulates leave-one-out error for linear estimators using the hat matrix and an average diagonal approximation. The paper identifies this criterion as related to SURE.

  • The hat matrix Γ maps observations to model estimates; linear regression uses Γ = X(XᵀX)^−1Xᵀ.
  • LOOCV: Leave-one-out cross validation can be computed without retraining for every instance by using full-data estimates and the hat-matrix relationship.
  • Generalized Cross Validation: Generalized cross validation replaces each diagonal hat-matrix value with its average, expressed through the matrix trace and model dimension.
  • Generalized Cross Validation: The paper relates generalized cross validation to Stein’s Unbiased Risk Estimator.

7. Regularization

Regularization augments the objective with a complexity penalty, using ℓ2 or ℓ1 norms to control model complexity and avoid overfitting. ℓ2 shrinks weak directions, while ℓ1 can set weak coordinates exactly to zero and thereby produce sparse solutions.

  • Regularized optimization: Regularized optimization adds a complexity penalty Ω(.) to the objective J(.) with strength α > 0.The penalty substitutes for a difficult complexity derivative in the SURE-based optimization.
  • Regularized optimization: Regularization minimizes the true error rather than training error, helping avoid overfitting caused by minimizing training error alone.
  • ℓ2 norm regularization: ℓ2 regularization preserves effective Hessian directions while shrinking weak directions close to zero.The shrinkage factor is λ_j/(λ_j + α); directions with λ_j ≫ α are largely preserved, whereas directions with λ_j ≪ α are nearly eliminated.
  • ℓ1 norm regularization: ℓ1 soft thresholding sets a weak coordinate to zero when |x*_j| < α/h_j, unlike ℓ2 regularization, which only shrinks weak solutions toward zero.
  • ℓ1 norm regularization: ℓ1 regularization promotes sparsity because its diamond-shaped penalty can contact objective contours where some variables are exactly zero.The paper also calls ℓ1 regularization lasso and describes soft thresholding and coordinate descent as solution methods.

7.4. Examples in Machine Learning: Regression, Weight Decay, Noise Injection, and Early Stopping

The paper applies regularization theory to regression and neural-network training through ridge, lasso, weight decay, noise injection, and early stopping. These methods constrain coefficients, weights, curvature, or training duration to reduce overfitting, with early stopping analytically related to weight decay.

  • Regression: Ridge regression adds αI to X^⊤X, strengthening its diagonal and helping make the matrix full-rank and invertible.Lasso regression instead uses an ℓ1 penalty, produces sparse coefficients, and requires an iterative rather than closed-form solution.
  • Weight Decay: Weight decay penalizes neural-network weights, keeping them relatively small and preventing the network from becoming too nonlinear and overfitted.
  • Noise Injection: Input noise acts as an ℓ2 regularizer on output second derivatives, penalizing significant changes in the network output and preventing overfitting.The paper also interprets weight-noise injection as regularization with a penalty involving the output gradient with respect to weights.
  • Early Stopping: Early stopping can be viewed as ℓ2 regularization or weight decay under a stated equivalence involving the learning rate, iteration index, and regularization parameter.
  • Early Stopping: Early stopping trains the neural network only until overfitting begins, and its inverse iteration count is proportional to the weight-decay regularization parameter.The paper reports empirical studies finding noise injection and weight decay more effective than early stopping for avoiding overfitting, while noting early stopping has its own merits.

8. Bagging

Bagging trains multiple models on bootstrap samples and aggregates their estimates, reducing variance when the models are sufficiently different. The paper connects this mechanism to overfitting and applications including random forests, dropout, HOG, and SSD.

  • 8.1. Definition: Bagging draws k bootstrap samples with replacement, trains one model on each, and aggregates their estimates.The method produces an ensemble rather than a single trained model.
  • 8.2. Theory: When bootstrap-trained models are uncorrelated, bagging reduces estimation variance by a factor of k; highly correlated models provide little improvement.The paper models individual errors using variance s and pairwise covariance c.
  • 8.2. Theory: Because bagging decreases estimation variance, it helps prevent overfitting, especially for high-variance models.The paper characterizes bagging as a variance-reduction meta algorithm and ensemble-learning method based on model averaging.
  • 8.3. Examples: Random forests reduce tree correlation by sampling features in addition to sampling bootstrap training subsets.Using bootstrap samples alone can leave similarly behaving trees highly correlated.
  • 8.3. Examples: Dropout imitates bagging by randomly removing neurons during training and scaling the outputs of all neurons at test time.The paper specifies removal probability p = 0.5.
  • 8.3. Examples: HOG combines gradient histograms from image cells or blocks, while SSD uses differently sized bounding boxes whose weighted losses train a neural network.These are presented as computer-vision examples of bagging.

9. Boosting

Boosting combines weak models into a strong classifier, with AdaBoost updating instance weights and combining classifiers through weighted voting. The paper explains this through additive and maximum-margin views and derives a generalization-error bound that decreases exponentially with the number of models.

  • 9. Boosting: Boosting combines weak models into a strong classifier, and a classifier only slightly better than random can suffice in binary classification.The paper presents boosting as a general meta algorithm for classifiers and regression models.
  • 9.1. Definition: The sign of the weighted sum of trained classifiers is equivalent to majority voting among them.The combined classifier uses model weights such as αj.
  • 9.1. Definition: AdaBoost leaves correctly classified instances unchanged and increases the weights of misclassified instances for subsequent models.A weak classifier with cost 0.5 receives αj = 0 and does not change the weights.
  • 9.2. Additive Model: AdaBoost can be formulated as a forward stage-wise additive model that adds previously trained models one by one.The paper also gives radial basis function neural networks as an example of additive models.
  • 9.3.1. UPPER BOUND ON THE GENERALIZATION ERROR OF BOOSTING: The paper derives an upper bound on AdaBoost’s generalization error from the probability of negative classification margins.The derivation uses normalized weights and Markov’s inequality.
  • 9.3.1. UPPER BOUND ON THE GENERALIZATION ERROR OF BOOSTING: When each model has cost Lj ≤ 0.5 − ξ, the bound decreases exponentially with k, so slightly better-than-random weak models can yield a small error probability.The stated condition uses ξ ∈ (0, 0.5), and the argument is presented for binary classification.
  • 9.3.2. Boosting and SVM: Boosting and SVMs are connected through maximizing classification margins in a high-dimensional feature space.The paper identifies the weighted combination of weak classifiers with a large-margin linear combination in that feature space.

10. Conclusion

The conclusion identifies the work as a tutorial on overfitting, cross validation, generalized cross validation, regularization, bagging, and boosting, with machine-learning and computer-vision examples.

  • 10. Conclusion: The paper explains the theory of overfitting, cross validation, generalized cross validation, regularization, bagging, and boosting.It also provides examples of these methods in machine learning and computer vision.

A. Proof of Stein’s Lemma

The appendix proves Stein’s lemma for independent normally distributed components by applying integration by parts and the definition of expectation.

  • A. Proof of Stein’s Lemma: The proof assumes independent normal components z_i ∼ N(µ_i, σ) and uses independence to factor the joint distribution.The passage explicitly identifies independence as the justification for the factorization.
  • A. Proof of Stein’s Lemma: The derivation proceeds through expectation definitions and integrations over dz1 ... dzd.The proof concludes with Q.E.D.
Loading 1905.12787v2…