# Bias-variance decomposition

I found the following in The Elements of Statistical Learning.

Suppose we have 1000 training examples $x_i$ generated uniformly on $[-1,1]^p$. Assume that the true relationship between $X$ and $Y$ is $$Y = f(X) = e^{-8||X||^2}$$ without any measurement error. We use the 1-nearest-neighbour rule to predict $y_0$ at the test-point $x_0 = 0$. Denote the training set by $\mathcal T$. We can compute the expected prediction error at $x_0$ for our procedure, averaging over all such examples of size 1000. Since the problem is deterministic, this is the mean squared error (MSE) for estimating $f(0)$:

\begin{align}\text{MSE}(x_0) &= E_\mathcal T[f(x_0)-\hat y_0]^2\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0)]^2 + [E_\mathcal T(\hat y_0)-f(x_0)]^2\\ &= \mbox{Var}_\mathcal T(\hat y_0) + \mbox{Bias}^2(\hat y_0) \end{align}

I don't quite understand what they mean by the problem being deterministic. Also, how exactly do they get from the first line to the second line? I played around with the binomial formula but I can't seem to derive this.

\begin{align} \text{MSE}(x_0) &= E_\mathcal T[f(x_0)-\hat y_0]^2\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0) + E_\mathcal T(\hat y_0)-f(x_0)]^2\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0)]^2 + E_\mathcal T[E_\mathcal T(\hat y_0)-f(x_0)]^2 + 2E_\mathcal T([\hat y_0 - E_\mathcal T(\hat y_0)][E_\mathcal T(\hat y_0)-f(x_0)])\\ &= E_\mathcal T[\hat y_0 - E_\mathcal T(\hat y_0)]^2 + [E_\mathcal T(\hat y_0)-f(x_0)]^2\\ &= \mbox{Var}_\mathcal T(\hat y_0) + \mbox{Bias}^2(\hat y_0), \end{align} where fourth equality is true since $E_\mathcal T([\hat y_0 - E_\mathcal T(\hat y_0)]) = E_\mathcal T(\hat y_0) - E_\mathcal T(\hat y_0) = 0$ and $E_\mathcal T[E_\mathcal T(\hat y_0)-f(x_0)]^2 =[E_\mathcal T(\hat y_0)-f(x_0)]^2$, since $f(x_0)$, $E_\mathcal T(\hat y_0)$ are constants.
To answer the first request: They are interested in the case where the random variable $X$ takes $x_0=0$ value with probability $1$, thus the problem is deterministic. Refer ://en.m.wikipedia.org/wiki/Degenerate_distribution for more, degenerate and deterministic terms are interchangeable.
• @akkarin I have explained how the fourth equality comes about after all the steps are done in the answer itself. Basically the third summand in the third equality becomes $0$ since $E_\mathcal T([\hat y_0 - E_\mathcal T(\hat y_0)]) = E_\mathcal T(\hat y_0) - E_\mathcal T(\hat y_0) = 0.$ Feel free to ask further if something's not clear. Feb 18, 2017 at 6:25
• So which rules do you use to factorise the third summand? Why does it become 0? The expectation is taken of the whole thing rather than just $(\hat y_0 - E_\mathcal T(\hat y_0)$, right? Also, even if the third summand becomes 0, why are the second summands in third and fourth line equivalent? In the third line there is one more expectation taken? Feb 18, 2017 at 13:12
• @akkarin Notice $[E_\mathcal T(\hat y_0)-f(x_0)]$ is a constant. In whole of this analysis the only random variable is $\hat y_0$ with statistics given by $\mathcal T$. This answers both of your questions. $\\$And just for an information I have used "Linearity of Expectation" from second to third equality step. Feb 18, 2017 at 14:09