THE BIAS-VARIANCE TRADEOFF

This page gives some additional informations about the bias-variance tradeoff.

 ______________________________________________

A model is a set of estimators

We'll use regression as an example. The data is supposed to have been generated by a process :

y = f(x₁, x₂ , ..., x_p) + ε

where f is deterministic, and ε is random with 0 mean. A regression model y^* = f ^*(x₁, x₂ , ..., x_p) is built from the sample. Let x₀ be a point of the feature space. Then f ^*(x₀) is hoped to be close to y₀ = f(x₀), the true value of the regression function.

Because of the randomness of ε, that is, the randomness of the sample, the model depends on the actual sample used to build it. Another sample would have led to a different model, and therefore a different response at x₀. So the response of a model at any point is a random variable.

In the terminology of Statistics, such a regression model therefore puts at each and every point x₀ of the the feature space a random variable that is an estimator of y₀, the true value of the regression function at this point. This estimator is denoted by f ^*(y , x = x₀), or f ^*₀  for short.

Bias-variance decomposition

We here focus on the response error at x₀ (although a more general study can be conducted on the entire space, taking into account the unconditional probability distribution p(x)).

The estimator f ^*₀ is good if its realizations are close to the true value y₀ in a probabilistic sense, that is, for instance, if its Mean Square Error (MSE) :

MSE = E[( f ^*₀ - y₀)²]

is small.

It is easily shown that :

MSE = Bias² + Variance

where "Bias" and "Variance" are that of the response of the model, considered as an estimator of y₀.

So the errors made by a model have two origins :

• The Bias, that measures how far the model response f ^*(x₀)  is from the value f(x₀) of the true regression function on the average (that is, over all possible samples),
• The Variance, that measures how sensitive f ^*(x₀) is to the particular sample that was used for building the model.

Models come in families

It is never the case that a data set makes obvious the choice of a particular model architecture. The analyst will always consider several candidate models, and his goal is of course to select the model with the most accurate response (on new data).

For example, in the case of regression, it is common to have many candidate independent variables (the regressors). A large part of the effort of model building will consist in identifying an adequate subset of regressors to be incorporated into the model. But each subset of regressors will yield a model, so a family of models is to be considered. At point x₀, each of these models will have its own bias, its own variance, and therefore its own error level (MSE).

The bias-variance tradeoff

The bias-variance tradeoff principle states that within a given family of models :

• A model with a low bias has a large variance.
• A model with a low variance has a large bias.
• The best model (lowest MSE) in the family will have neither a very low bias, nor a very low variance.

Identifying this best model with certainty is of course impossible, as this would require knowing the true regression function f(x). But attempts can be made to identify models which are probably good. This is the object of "model selection" (see below).

Model complexity

It is convenient to consider the number of parameters (the complexity of the model) as a way to sort models in a family. The bias-variance tradeoff then states that, in the family of models :

• Low complexity models have a low variance but a large bias.
• High complexity models have a low bias but a large variance.

Consequently, the "best" model will always have a number of parameters that is neither too small nor too large. The analyst will have to find the proper tradeoff between bias and variance within this family of models, largely (but not only) by tuning the number of parameters.

Overparametrization and Overfitting

The true performance of a model is that observed on new data that did not take part to the construction of the model, not the observed performance on the design data.

• For a model that is higly biased because its complexity is too low, these two performances are similar, and both poor.
• But for a model with too large a variance because its complexity is too high (overparametrization), one will observe :
• Excellent (but meaningless) performance on the design data,  and
• Poor performance on new data because of the high variance of the local estimators.
  This is called overfitting.

For example, if  f ^* is chosen in the family of polynomials, then higher degree polynomials (large number of parameters) can get closer to the data points than lower degree polynomials, thus leading to a lower quadratic error. In fact, if the design set contains n data points, it is well known that a n-degree polynom will go exactly through the points, thus reducing the error on the design set to 0. But this polynom undergoes oscillations that are both very large and whose features strongly depend on the exact positions of the points, thus conducing to a model with a huge variance and very large response errors.
 

Let's insist again : even a moderate overparametrization can cause the variance of the model to grow in an explosive way. Because this phenomenon is masked by excellent performances on the design set, and becomes visible only when it is too late (that is, when the model is put to work on new data), it tends to be overlooked by the newcomer to data modeling.

The bias-variance tradeoff is universal

We illustrated the bias-variance tradeoff with regression as an example. But the bias-variance tradeoff is absolutely universal and shows up under different guises in any kind of data modeling. Let's give a few additional examples :

• Piecewise Linear Regression

When data is not distributed around a straight line, but rather around a slightly convex curve, Simple Linear Regression may be replaced by several SLR models, each one operating in a different region of the regressor space. But in how many regions should this domain be partitioned ?

We use this example for illustrating the bias-variance tradeoff with an interactive animation ().

• Multiple Linear Regression
  

Multiple Linear Regression has no adjustable degree, as polynomial regression does. The response surface is always a hyperplane, that will never undergo the oscillations that we just mentioned for polynoms. So MLR might seem to be safe from overfitting. But it's not : as the dimension of the space of regressors gets larger and larger (more and more variables incorporated into the model), this hyperplane will fit the data points better and better, thus making the Sum of Squared Residuals smaller and smaller.

One of the main questions in Multiple Linear Regression is therefore the identification of the best set of predictors, "best" in the sense of overall MSE, and therefore in the sense of the bias-variance tradeoff.

• Ridge Regression

Ridge Regression is a variant of MLR that artificially introduces a bias on the parameters of the model, and consequently on its predictions too. It is expected that this bias will cause a reduction in the variance of the model parameters and predictions. The amount of bias is controled by a "ridge parameter", that acts as if the number of parameters of the model was actually smaller than the number of regressors.

Adjusting the value of the ridge parameter is convenient way of optimizing the bias-variance tradeoff.

• Discriminant Analysis

The standard linear discriminant functions are fine when the classes have identical covariance matrices, an almost academic situation. What of the more general situation ? Should the discriminant functions be made quadratic, as theory suggests ? Not necessarily so. If the data is sparse (we will return to the notion of "sparse data" in a moment), the linear model might provide more accurate predictions than the "augmented" model, because its contains fewer parameters than its bigger quadratic counterpart.

• Decision Trees

How deeply should a Decision Tree be developed ?  

• Too shallow a tree growth will smooth out the boundaries between classes, thus generating a stable but rigid and therefore inaccurate model.
• On the other hand, an overgrown tree will build overdetailed boundaries that will be mostly determined by the random nature of the data. Consequently, class boundaries will then heavily depend on the particular sample at hand, and the predictions of the model will be unreliable.

The adjustment of the complexity of a Decision Tree is often made a posteriori by a so-called pruning mechanism. The Tree is first purposely grown up to an exagerated depth. Then branches that are deemed superfluous are removed.

• Histograms

A histogram is a very usuful tool for visualizing a distribution emerging from a set of data points. It is also a (not very good) model  for probability density estimation. As such, it is also subject to the bias-variance phenomenon. Here, the parameters are the heights of the bins, and the number of parameters is the number of bins.
• If there are too few bins, the histogram will not detect the features of the distribution of the data points. As a probability density estimator, its bias in then large, and its variance low.
• If there are too many bins, the non-empty, narrow bins will simply be where the data points are, and the histogram then tells nothing about their distribution. As a probability density estimator, its bias in then low, and its variance large.
  You'll find here an interactive animation that illustrates the bias-variance tradeoff for histograms.

The list is endless. All models are subject to the bias-variance tradeoff. More precisely, any model belongs to a family of models, some exhibiting a large bias but a small variance, some exhibiting a small bias but a large variance, the "best" model being somewhere in between.

Sample size

Parametric and non parametric models

            Among the models hereabove mentioned :

• Some are parametric models (Linear Regression, Discriminant Analysis).
• Others are non parametric (Histograms, Decision Trees).

Both these types of models are of course submitted to the bias-variance tradeoff. But recall that parametric models are helped by a large amount of information made available to them through an assumed analytical form of the underlying distribution. Conversely, non parametric models are "on their own" and must compensate, whenever possible, this lack of a priori information by information found in supplementary data.

So, in a situation where it is justified to use a parametric model, its non parametric cousin will suffer from a larger bias, a larger variance, or both (depending in the choices made by the analyst).

The "curse of dimensionality"

            Quite generally, larger samples make for smaller variances. Unfortunately, practical considerations prohibit resorting to arbitrarily large samples to bypass the bias-variance problem.

Conversely, small samples make the bias-variance tradeoff even more accute. For a given bias, the variance of the model response is larger than for a model built from a larger sample.

The sample size issue is both important and complex as a new concept now steps in : that of the dimensiona of the data space. Is a 1000-observation sample large or small ?

• Suppose that you want to make a 10-bin histogram of this 1-dimensional data : then 1000 observations is plentiful, for there will be an average of 100 observations per bin, and the the variance of the histogram will be small, and the bias reasonable.
• Suppose now that the data is 3-dimensional (there are 3 variables {x_i}). You want to make a 3-dimensional histogram for the purpose of probability density estimation, and you want to maintain the 10-bracket resolution per dimension. The "3D-histogram" will then have 10³ = 1.000 bins (cubic boxes), and there will be an average of only 1 observation per bin. Clearly, such a histogram is useless because of its huge variance.

 So sample size by itself means nothing. What really matters is not the number of observations, but the density of the observations in the feature space. This density collapses as more dimensions are added for a given sample size, and therefore as more parameters added to the model.

Conversely, if one wants to maintain the same density (and therefore maintain the accuracy of the model) when more dimensions are added, then the sample size should increase enormously (usually exponentially with the number of dimensions). This is known as the "curse of dimensionality".

It would seem that is some cases, "number of parameters" and "data space dimension" are different issues. For example, in a Multilayer Perceptron (MLP),  it would seem that neurons (and therefore parameters) can be added to the hidden layer without changing the dimension of the data space. But is is not so : the hidden layer of the MLP projects the data on an "intermediate" space, and the dimension of this space is what matters for the linear output layer, and therefore for the model accuracy.

Model selection

In the family of models that is being considered, how is the "best" model going to be identified ? First, we will never be certain that we have identified the best model in the family, because of the random nature of the sample. But it is possible (and necessary) to identify models that are probably fairly good. This can be done in two ways :

• The error level measured on the design set is always lower than the error level observed on new data (an extreme case is that of the polynom of degree n that goes through every point of the design set, the "in-sample" error level being then 0). It is said to be "optimistic". In some cases, additional assumptions about the mechanism that generated the data allow this optimism to be quantified analytically. An estimation of the true error level can then be calculated.
  This is for example the case in Linear Regression. When the assumptions of the Linear Model are met :
• The Coefficient of Determination R² is a measure of the performance of the model on the design set.
• The "Adjusted R²" is a (calculated) estimation of the performance of the model on new data.

The analyst then builds several models, and retains the model with the lowest predicted error level.

•  But most of the time, direct estimation of the error level is not feasible. One then resorts to various computer-intensive simulation techniques like :
• Cross-validation, that repetitively puts aside some of the data to simulate "new" data.
• Bootstrap, that uses the empirical distribution function as an estimate of the true distribution function.

________________________________________________________

Related readings :