Bias–variance tradeoff
In statistics and machine learning, the bias–variance tradeoff describes the relationship between a model's complexity, the accuracy of its predictions, and how well it can make predictions on previously unseen data that were not used to train the model. In general, as the number of tunable parameters in a model increases, it becomes more flexible, and can better fit a training data set. That is, the model has lower error or lower bias. However, for more flexible models, there will tend to be greater variance to the model fit each time we take a set of samples to create a new training data set. It is said that there is greater variance in the model's estimated parameters. The bias–variance dilemma or bias–variance problem is the conflict in trying to simultaneously minimize these two sources of error that prevent supervised learning algorithms from generalizing beyond their training set:
The bias error is an error from erroneous assumptions in the learning algorithm. High bias can cause an algorithm to miss the relevant relations between features and target outputs (underfitting). The variance is an error from sensitivity to small fluctuations in the training set. High variance may result from an algorithm modeling the random noise in the training data (overfitting). The bias–variance decomposition is a way of analyzing a learning algorithm's expected generalization error with respect to a particular problem as a sum of three terms, the bias, variance, and a quantity called the irreducible error, resulting from noise in the problem itself.
Motivation
The bias–variance tradeoff is a central problem in supervised learning. Ideally, one wants to choose a model that both accurately captures the regularities in its training data, but also generalizes well to unseen data. Unfortunately, it is typically impossible to do both simultaneously. High-variance learning methods may be able to represent their training set well but are at risk of overfitting to noisy or unrepresentative training data. In contrast, algorithms with high bias typically produce simpler models that may fail to capture important regularities (i.e. underfit) in the data. It is an often made fallacy to assume that complex models must have high variance. High variance models are "complex" in some sense, but the reverse need not be true. In addition, one has to be careful how to define complexity. In particular, the number of parameters used to describe the model is a poor measure of complexity. The model
f
a , b
( x ) = a sin ( b x )
{\displaystyle f_{a,b}(x)=a\sin(bx)}
has only two parameters (
a , b
{\displaystyle a,b}
) but it can interpolate any number of points by oscillating with a high enough frequency, resulting in both a high bias and high variance. An analogy can be made to the relationship between accuracy and precision. Accuracy is one way of quantifying bias and can intuitively be improved by selecting from only local information. Consequently, a sample will appear accurate (i.e. have low bias) under the aforementioned selection conditions, but may result in underfitting. In other words, test data may not agree as closely with training data, which would indicate imprecision and therefore inflated variance. A graphical example would be a straight line fit to data exhibiting quadratic behavior overall. Precision is a description of variance and generally can only be improved by selecting information from a comparatively larger space. The option to select many data points over a broad sample space is the ideal condition for any analysis. However, intrinsic constraints (whether physical, theoretical, computational, etc.) will always play a limiting role. The limiting case where only a finite number of data points are selected over a broad sample space may result in improved precision and lower variance overall, but may also result in an overreliance on the training data (overfitting). This means that test data would also not agree as closely with the training data, but in this case the reason is inaccuracy or high bias. To borrow from the previous example, the graphical representation would appear as a high-order polynomial fit to the same data exhibiting quadratic behavior. Note that error in each case is measured the same way, but the reason ascribed to the error is different depending on the balance between bias and variance. To mitigate how much information is used from neighboring observations, a model can be smoothed via explicit regularization, such as shrinkage.
Bias–variance decomposition of mean squared error
Suppose that we have a training set consisting of a set of points
x
1
, … ,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
and real-valued labels
y
i
{\displaystyle y_{i}}
associated with the points
x
i
{\displaystyle x_{i}}
. We assume that the data is generated by a function
f ( x )
{\displaystyle f(x)}
such as
y = f ( x ) + ε
{\displaystyle y=f(x)+\varepsilon }
, where the noise,
ε
{\displaystyle \varepsilon }
, has zero mean and unit variance
σ
2
{\displaystyle \sigma ^{2}}
. That is,
y
i
= f (
x
i
) +
ε
i
{\displaystyle y_{i}=f(x_{i})+\varepsilon _{i}}
, where
ε
i
{\displaystyle \varepsilon _{i}}
is a noise sample. We want to find a function
f ^
( x ; D )
{\displaystyle {\hat {f}}\!(x;D)}
, that approximates the true function
f ( x )
{\displaystyle f(x)}
as well as possible, by means of some learning algorithm based on a training dataset (sample)
D = { (
x
1
,
y
1
) … , (
x
n
,
y
n
) }
{\displaystyle D=\{(x_{1},y_{1})\dots ,(x_{n},y_{n})\}}
. We make "as well as possible" precise by measuring the mean squared error between
y
{\displaystyle y}
and
f ^
( x ; D )
{\displaystyle {\hat {f}}\!(x;D)}
: we want
( y −
f ^
( x ; D )
)
2
{\displaystyle (y-{\hat {f}}\!(x;D))^{2}}
to be minimal, both for
x
1
, … ,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
and for points outside of our sample. Of course, we cannot hope to do so perfectly, since the
y
i
{\displaystyle y_{i}}
contain noise
ε
{\displaystyle \varepsilon }
; this means we must be prepared to accept an irreducible error in any function we come up with. Finding an
f ^
{\displaystyle {\hat {f}}}
that generalizes to points outside of the training set can be done with any of the countless algorithms used for supervised learning. It turns out that whichever function
f ^
{\displaystyle {\hat {f}}}
we select, we can decompose its expected error on an unseen sample
x
{\displaystyle x}
(i.e. conditional on
x
{\displaystyle x}
) as follows:
E
D , ε
[
(
y −
f ^
( x ; D )
)
2
]
=
(
Bias
D
[
f ^
( x ; D )
]
)
2
+
Var
D
[
f ^
( x ; D )
]
+
σ
2
{\displaystyle \mathbb {E} _{D,\varepsilon }{\Big [}{\big (}y-{\hat {f}}\!(x;D){\big )}^{2}{\Big ]}={\Big (}\operatorname {Bias} _{D}{\big [}{\hat {f}}\!(x;D){\big ]}{\Big )}^{2}+\operatorname {Var} _{D}{\big [}{\hat {f}}\!(x;D){\big ]}+\sigma ^{2}}
where
Bias
D
[
f ^
( x ; D )
]
≜
E
D
[
f ^
( x ; D ) − f ( x )
]
=
E
D
[
f ^
( x ; D )
]
−
f ( x )
=
E
D
[
f ^
( x ; D )
]
−
E
y
|
x
[
y ( x )
]
{\displaystyle {\begin{aligned}\operatorname {Bias} _{D}{\big [}{\hat {f}}\!(x;D){\big ]}&\triangleq \mathbb {E} _{D}{\big [}{\hat {f}}\!(x;D)-f(x){\big ]}\\&=\mathbb {E} _{D}{\big [}{\hat {f}}\!(x;D){\big ]}\,-\,f(x)\\&=\mathbb {E} _{D}{\big [}{\hat {f}}\!(x;D){\big ]}\,-\,\mathbb {E} _{y|x}{\big [}y(x){\big ]}\end{aligned}}}
and
Var
D
[
f ^
( x ; D )
]
≜
E
D
[
(
E
D
[
f ^
( x ; D ) ] −
f ^
( x ; D )
)
2
]
{\displaystyle \operatorname {Var} _{D}{\big [}{\hat {f}}\!(x;D){\big ]}\triangleq \mathbb {E} _{D}\left[\left(\mathbb {E} _{D}[{\hat {f}}\!(x;D)]-{\hat {f}}\!(x;D)\right)^{2}\right]}
and
σ
2
=
E
y
[
(
y −
f ( x )
⏟
E
y
|
x
[ y ]
)
2
]
{\displaystyle \sigma ^{2}=\operatorname {E} _{y}{\Big [}{\big (}y-\underbrace {f(x)} _{E_{y|x}[y]}{\big )}^{2}{\Big ]}}
The expectation ranges over different choices of the training set
D = { (
x
1
,
y
1
) … , (
x
n
,
y
n
) }
{\displaystyle D=\{(x_{1},y_{1})\dots ,(x_{n},y_{n})\}}
, all sampled from the same joint distribution
P ( x , y )
{\displaystyle P(x,y)}
which can for example be done via bootstrapping. The three terms represent:
the square of the bias of the learning method, which can be thought of as the error caused by the simplifying assumptions built into the method. E.g., when approximating a non-linear function
f ( x )
{\displaystyle f(x)}
using a learning method for linear models, there will be error in the estimates
f ^
( x )
{\displaystyle {\hat {f}}\!(x)}
due to this assumption; the variance of the learning method, or, intuitively, how much the learning method
f ^
( x )
{\displaystyle {\hat {f}}\!(x)}
will move around its mean; the irreducible error
σ
2
{\displaystyle \sigma ^{2}}
. Since all three terms are non-negative, the irreducible error forms a lower bound on the expected error on unseen samples. The more complex the model
f ^
( x )
{\displaystyle {\hat {f}}\!(x)}
is, the more data points it will capture, and the lower the bias will be. However, complexity will make the model "move" more to capture the data points, and hence its variance will be larger.
Derivation
The derivation of the bias–variance decomposition for squared error proceeds as follows. For convenience, we drop the
D
{\displaystyle D}
subscript in the following lines, such that
f ^
( x ; D ) =
f ^
( x )
{\displaystyle {\hat {f}}\!(x;D)={\hat {f}}\!(x)}
. Let us write the mean-squared error of our model:
MSE
( x )
≜
E
[
(
y −
f ^
( x )
)
2
]
=
E
[
(
f ( x ) + ε −
f ^
( x )
)
2
]
since
y ≜ f ( x ) + ε
=
E
[
(
f ( x ) −
f ^
( x )
)
2
]
+
2
E
[
(
f ( x ) −
f ^
( x )
)
ε
]
+
E
[
ε
2
]
{\displaystyle {\begin{aligned}{\text{MSE}}(x)&\triangleq \mathbb {E} {\Big [}{\big (}y-{\hat {f}}\!(x){\big )}^{2}{\Big ]}\\&=\mathbb {E} {\Big [}{\big (}f(x)+\varepsilon -{\hat {f}}\!(x){\big )}^{2}{\Big ]}&&{\text{since }}y\triangleq f(x)+\varepsilon \\&=\mathbb {E} {\Big [}{\big (}f(x)-{\hat {f}}\!(x){\big )}^{2}{\Big ]}\,+\,2\ \mathbb {E} {\Big [}{\big (}f(x)-{\hat {f}}\!(x){\big )}\varepsilon {\Big ]}\,+\,\mathbb {E} [\varepsilon ^{2}]\end{aligned}}}
We can show that the second term of this equation is null:
E
[
(
f ( x ) −
f ^
( x )
)
ε
]
=
E
[
f ( x ) −
f ^
( x )
]
E
[
ε
]
since
ε
is independent from
x
= 0
since
E
[
ε
]
= 0
{\displaystyle {\begin{aligned}\mathbb {E} {\Big [}{\big (}f(x)-{\hat {f}}\!(x){\big )}\varepsilon {\Big ]}&=\mathbb {E} {\big [}f(x)-{\hat {f}}\!(x){\big ]}\ \mathbb {E} {\big [}\varepsilon {\big ]}&&{\text{since }}\varepsilon {\text{ is independent from }}x\\&=0&&{\text{since }}\mathbb {E} {\big [}\varepsilon {\big ]}=0\end{aligned}}}
Moreover, the third term of this equation is nothing but
σ
2
{\displaystyle \sigma ^{2}}
, the variance of
ε
{\displaystyle \varepsilon }
. Let us now expand the remaining term:
E
[
(
f ( x ) −
f ^
( x )
)
2
]
=
E
[
(
f ( x ) −
E
[
f ^
( x ) ] +
E
[
f ^
( x ) ] −
f ^
( x )
)
2
]
=
E
[
(
f ( x ) −
E
[
f ^
( x ) ]
)
2
]
+
E
[
(
E
[
f ^
( x ) ] −
f ^
( x )
)
2
]
+
2
E
[
(
f ( x ) −
E
[
f ^
( x ) ]
)
(
E
[
f ^
( x ) ] −
f ^
( x )
)
]
{\displaystyle {\begin{aligned}&\operatorname {\mathbb {E} } \left[\left(f(x)-{\hat {f}}\!(x)\right)^{2}\right]\\[1ex]&=\operatorname {\mathbb {E} } \left[\left(f(x)-\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]+\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]-{\hat {f}}\!(x)\right)^{2}\right]\\[1ex]&={\color {Blue}\operatorname {\mathbb {E} } \left[\left(f(x)-\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\right)^{2}\right]}\,+\,\operatorname {\mathbb {E} } \left[\left(\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]-{\hat {f}}\!(x)\right)^{2}\right]\\&\quad \,+\,2\ {\color {PineGreen}\operatorname {\mathbb {E} } \left[\left(f(x)-\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\right)\left(\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]-{\hat {f}}\!(x)\right)\right]}\end{aligned}}}
We show that:
E
[
(
f ( x ) −
E
[
f ^
( x )
]
)
2
]
=
E
[
f ( x
)
2
]
−
2
E
[
f ( x )
E
[
f ^
( x )
]
]
+
E
[
E
[
f ^
( x )
]
2
]
= f ( x
)
2
−
2
f ( x )
E
[
f ^
( x )
]
+
E
[
f ^
( x )
]
2
=
(
f ( x ) −
E
[
f ^
( x )
]
)
2
{\displaystyle {\begin{aligned}{\color {Blue}\mathbb {E} {\Big [}{\big (}f(x)-\mathbb {E} {\big [}{\hat {f}}(x){\big ]}{\big )}^{2}{\Big ]}}&=\mathbb {E} {\big [}f(x)^{2}{\big ]}\,-\,2\ \mathbb {E} {\Big [}f(x)\ \mathbb {E} {\big [}{\hat {f}}(x){\big ]}{\Big ]}\,+\,\mathbb {E} {\Big [}\mathbb {E} {\big [}{\hat {f}}(x){\big ]}^{2}{\Big ]}\\&=f(x)^{2}\,-\,2\ f(x)\ \mathbb {E} {\big [}{\hat {f}}(x){\big ]}\,+\,\mathbb {E} {\big [}{\hat {f}}(x){\big ]}^{2}\\&={\Big (}f(x)-\mathbb {E} {\big [}{\hat {f}}(x){\big ]}{\Big )}^{2}\end{aligned}}}
This last series of equalities comes from the fact that
f ( x )
{\displaystyle f(x)}
is not a random variable, but a fixed, deterministic function of
x
{\displaystyle x}
. Therefore,
E
[
f ( x )
]
= f ( x )
{\displaystyle \operatorname {\mathbb {E} } \left[f(x)\right]=f(x)}
. Similarly
E
[
f ( x
)
2
]
= f ( x
)
2
{\displaystyle \operatorname {\mathbb {E} } \left[f(x)^{2}\right]=f(x)^{2}}
, and
E
[
f ( x )
E
[
f ^
( x ) ]
]
= f ( x )
E
[
E
[
f ^
( x ) ]
]
= f ( x )
E
[
f ^
( x ) ]
{\displaystyle \operatorname {\mathbb {E} } \left[f(x)\,\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\right]=f(x)\,\operatorname {\mathbb {E} } \left[\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\right]=f(x)\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]}
. Using the same reasoning, we can expand the second term and show that it is null:
E
[
(
f ( x ) −
E
[
f ^
( x ) ]
)
(
E
[
f ^
( x ) ] −
f ^
( x )
)
]
=
E
[
f ( x )
E
[
f ^
( x ) ]
−
f ( x )
f ^
( x )
−
E
[
f ^
( x )
]
2
+
E
[
f ^
( x ) ]
f ^
( x )
]
= f ( x )
E
[
f ^
( x ) ]
−
f ( x )
E
[
f ^
( x ) ]
−
E
[
f ^
( x )
]
2
+
E
[
f ^
( x )
]
2
= 0
{\displaystyle {\begin{aligned}&{\color {PineGreen}\operatorname {\mathbb {E} } \left[\left(f(x)-\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\right)\left(\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]-{\hat {f}}\!(x)\right)\right]}\\&=\operatorname {\mathbb {E} } \left[f(x)\,\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\,-\,f(x){\hat {f}}\!(x)\,-\,\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]^{2}+\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\,{\hat {f}}\!(x)\right]\\&=f(x)\,\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\,-\,f(x)\,\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]\,-\,\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]^{2}\,+\,\operatorname {\mathbb {E} } [{\hat {f}}\!(x)]^{2}\\&=0\end{aligned}}}
Eventually, we plug our derivations back into the original equation, and identify each term:
MSE
( x )
=
(
f ( x ) −
E
[
f ^
( x ) ]
)
2
+
E
[
(
E
[
f ^
( x ) ] −
f ^
( x )
)
2
]
+
σ
2
= Bias
[
f ^
( x )
]
2
+
Var
[