Error decomposition
Theory
Assume the true conditional data generating process has the form
\[ p(y|x) = \frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(y - f(x))^2}{2\sigma^2}\right), \]
which is often written as \(Y = f(X) + \epsilon\). We call \(f\) the systematic information that \(X\) carries about \(Y\), and \(\epsilon\) the noise.
Suppose we have found some \(\hat f\). How far is \(\hat f\) from the truth.
Reducible and irreducible error
At a fixed input \(x\), with \(\hat f\) fixed,
\[ \mathrm{E}_{Y|X=x}\bigl[(Y - \hat f(x))^2\bigr] = \underbrace{\bigl(f(x) - \hat f(x)\bigr)^2}_{\text{reducible}} + \underbrace{\mathrm{Var}(\epsilon)}_{\text{irreducible}}. \]
Here the expectation is over the noise in the test response only. The training set, and therefore \(\hat f\), is held fixed.
The second term does not depend on our method. No model can beat it. If someone reports a test error below the irreducible error, either they are lucky on a small test set, or something has leaked.
Bias and variance
Now let the training set \(\mathcal D\) vary as well. Then \(\hat f\) is random too, and the reducible part splits,
\[ \mathrm{E}_{\mathcal D}\,\mathrm{E}_{Y|X=x}\bigl[(Y - \hat f(x))^2\bigr] = \underbrace{\bigl(f(x) - \mathrm{E}_{\mathcal D}[\hat f(x)]\bigr)^2}_{\text{bias}^2} + \underbrace{\mathrm{Var}_{\mathcal D}\bigl(\hat f(x)\bigr)}_{\text{variance}} + \underbrace{\mathrm{Var}(\epsilon)}_{\text{irreducible}}. \]
Note that there are two different expectations in this expression. One is over the noise in the test point, the other is over the training sets. Confusing them is the most common source of trouble with this formula.
Bias is how far the average fit is from the truth. A linear model fitted to curved data has high bias, and collecting more data does not help.
Variance is how much the fit moves when we get a different training set. A degree 10 polynomial fitted to 20 points has high variance. Collecting more data does help.
The tradeoff
Flexibility lowers bias and raises variance. The test error is the sum, so it falls at first and then rises again. The best model is neither the least nor the most flexible one.
The word overfitting means we are on the right of that minimum. The word underfitting means we are on the left.
Inductive bias
Every method makes assumptions about what a reasonable function looks like. That set of assumptions is the inductive bias of the method.
Linear regression assumes the response is a linear function of the input. \(k\) nearest neighbours assumes that nearby inputs have similar outputs. A convolutional network assumes that a useful feature in one part of an image is also useful in another part.
For a given data set, the inductive bias of one method can be better than that of another. No method works best on every data set.