Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
In the Elements of statistical learning it is written that the bias-variance decomposition takes the simple form in case of K-nearest neighbor regression fit
$$ Err(x_o)= \sigma_e^2+[f(x_o)-\frac{1}{k}\sum_{l=1}^{k}f(x_o)]^{2} + \frac{\sigma_e^2}{k} $$
Assumption: $x_i$ are fixed only $y_i$ is the source of randomness.
I understand the K-nearest neighbor regression, but can anyone please tell me the derivation of the above equation from the general bias-variance decomposition expression?
The previous answer is wrong in the part of bias derivation. I think the correct and full answer should be the following.
Firstly, I should note that for kNN we use an important assumption that all $X_i$ are fixed in the training set, i.e. $\mathcal{T}=(x_i,Y_i)_{i=1}^N$ (all randomness arises from the $Y_i$). Hence, here the training set $\mathcal{T}=(x_i,Y_i)_{i=1}^N$ is a random variable and its realizations are fixed training sets $(x_i,y_{ki})_{i=1}^N,~ k = 1,2,\ldots$ (these realizations all have exactly the same subset $(x_i)_{i=1}^N$, but each of them has unique target subset $(y_{ki})_{i=1}^N$, where $k$ is the index of $k$-th realization of the random variable $\mathcal{T}$).
Below I use subscript $_\mathcal{T}$ for all variables which depend on training set $\mathcal{T}$ (estimator $\hat{f}_k$ from Hastie's notation is $\hat{f}_{\mathcal{T}}$ in my notation). All such variables are random variables since they are depend on random variable $\mathcal{T}$. Expectation $\mathrm{E}_{\mathcal{T}}[\,\cdot\,]$ is taken over all possible realizations of random variable $\mathcal{T}=(x_i,Y_i)_{i=1}^N$.
For any additive regression model $Y = f(X) + \varepsilon$, where $\mathrm{E}[\varepsilon] =0$, $\mathrm{Var}(\varepsilon) = \sigma^2_\epsilon$, bias-variance decomposition of the expected test error at a fixed test point $X = x_0$ is the following (Hastie p.223 eq.7.9; random variable $Y$ below is a target of $x_0$):
$$\begin{align}\text{Err}(x_0) &= \mathrm{E}_\mathcal{T} \left[\left(Y - \hat{f}_{\mathcal{T}}(x_0) \right)^2 \Big| X= x_0\right] = \\ &= \underbrace{\left(f(x_0) - \mathrm{E}_\mathcal{T}[\hat{f}_{\mathcal{T}}(x_0)] \right)^{2}}_\mathrm{Bias^2} + \underbrace{\mathrm{E}_{\mathcal{T}}\left[\left(\hat{f}_{\mathcal{T}}(x_0) - \mathrm{E}_\mathcal{T}[\hat{f}_{\mathcal{T}}(x_0)]\right)^{2}\right]}_\mathrm{Variance} + \underbrace{\sigma^2_\varepsilon}_\mathrm{Noise}.\end{align}$$
In the case of kNN we can simplify this expression. Firstly, let's evaluate expectation $\mathrm{E}_\mathcal{T}[\hat{f}_{\mathcal{T}}(x_0)]$:
$$\begin{align}\mathrm{E}_\mathcal{T}[\hat{f}_{\mathcal{T}}(x_0)] &= \mathrm{E}_\mathcal{T} \left[\frac{1}{k} \sum_{\ell=1}^k Y_{\mathcal{T},(\ell)}\right] = \mathrm{E}_\mathcal{T}\left[\frac{1}{k} \sum_{\ell=1}^k \Big(f(x_{(\ell)}) + \varepsilon_{\mathcal{T},(\ell)}\Big) \right] =\\ &= \frac{1}{k} \sum_{\ell=1}^k f(x_{(\ell)}) + \frac{1}{k} \sum_{\ell=1}^k \underbrace{\mathrm{E}_\mathcal{T}\left[\varepsilon_{\mathcal{T},(\ell)}\right]}_{=0} = \frac{1}{k} \sum_{\ell=1}^k f(x_{(\ell)}).\end{align}$$
Here we used the aforementioned assumption that $\mathcal{T}=(x_i,Y_i)_{i=1}^N$, hence all possible realisations of $\mathcal{T}$ have exactly the same values of $(x_i)_{i=1}^N$. This means that $x_{(1)}, \ldots, x_{(k)}$, $k$ nearest neighbors of $x_0$, are fixed in all realizations (they are constant for $\mathrm{E}_{\mathcal{T}}[\,\cdot\,]$), therefore $f(x_{(1)}), \ldots, f(x_{(k)})$ are also constant for $\mathrm{E}_{\mathcal{T}}[\,\cdot\,]$.
Next, let's evaluate bias of kNN:
$$\mathrm{Bias}_{knn}^2(x_0) = \left(f(x_0) - \mathrm{E}_\mathcal{T}[\hat{f}_{\mathcal{T}}(x_0)] \right)^{2} = \left(f(x_0) - \frac{1}{k} \sum_{\ell=1}^k f(x_{(\ell)})\right)^2.$$
And variance of kNN is the following:
$$\begin{align}\mathrm{Variance}_{knn}(x_0) &= \mathrm{E}_{\mathcal{T}}\left[\left(\hat{f}_{\mathcal{T}}(x_0) - \mathrm{E}_\mathcal{T}[\hat{f}_{\mathcal{T}}(x_0)]\right)^{2}\right] \\ &= \mathrm{E}_\mathcal{T} \left[\left(\frac{1}{k} \sum_{\ell=1}^k Y_{\mathcal{T},(\ell)} - \frac{1}{k} \sum_{\ell=1}^k f(x_{(\ell)}) \right)^2\right] \\&= \mathrm{E}_\mathcal{T} \left[\left(\frac{1}{k} \sum_{\ell=1}^k \Big(f(x_{(\ell)}) + \varepsilon_{\mathcal{T},(\ell)}\Big) - \frac{1}{k} \sum_{\ell=1}^k f(x_{(\ell)}) \right)^2\right] \\ &= \mathrm{E}_\mathcal{T} \left[\left(\frac{1}{k} \sum_{\ell=1}^k \varepsilon_{\mathcal{T},(\ell)} \right)^2\right] = \frac{1}{k^2} \mathrm{E}_\mathcal{T} \left[\left(\sum_{\ell=1}^k \varepsilon_{\mathcal{T},(\ell)} \right)^2\right] \\ &= \frac{1}{k^2} \mathrm{E}_\mathcal{T} \Bigg[\Bigg(\sum_{\ell=1}^k \varepsilon_{\mathcal{T},(\ell)} - \underbrace{\mathrm{E}_\mathcal{T} \left[\sum_{\ell=1}^k \varepsilon_{\mathcal{T},(\ell)} \right]}_{=0} \Bigg)^2\Bigg] = \frac{1}{k^2} \mathrm{Var}_\mathcal{T} \left(\sum_{\ell=1}^k \varepsilon_{\mathcal{T},(\ell)}\right) \\&= \frac{1}{k^2} \sum_{\ell=1}^k \mathrm{Var}_\mathcal{T}\left(\varepsilon_{\mathcal{T},(\ell)}\right) = \frac{k \sigma^2_\varepsilon}{k^2} = \frac{\sigma^2_\varepsilon}{k}. \end{align}$$
Finally, we get exactly the same bias-variance decomposition for kNN as Hastie (p.223 eq.7.10):
$$\text{Err}_{knn}(x_0) = \underbrace{\left(f(x_0) - \frac{1}{k} \sum_{\ell=1}^k f(x_{(\ell)})\right)^2}_{\mathrm{Bias^2}} + \underbrace{\frac{\sigma^2_\varepsilon}{k}}_{\mathrm{Variance}} + \underbrace{\sigma^2_\varepsilon}_{\mathrm{Noise}}.$$
Edit
This is incorrect as others have noted, see correct answer below this one.
OLD
Let the label of $x$ be given by $Y(x) = f(x) + \epsilon$. Let the nearest neighbors of $x_0$ be $x_i$. Then the variance of this estimate is:
\begin{align} variance &= var \left( \frac{1}{k} \sum_i^k Y(x_i) \right) \\ &= \frac{1}{k^2} \sum_i^k var \left( f(x_i) + \epsilon_i \right) \\ &= \frac{1}{k^2} \sum_i^k var \left( f(x_i) \right) + var \left( \epsilon_i \right) \\ &= \frac{1}{k^2} \sum_i^k var \left( \epsilon_i \right) \\ &= \frac{1}{k^2} k \sigma_\epsilon^2 \\ &= \frac{\sigma^2_\epsilon}{k} \end{align}
$var(f(x_i))=0$ because we have made the strong assumption that the neighbors $x_i$ are fixed, and hence has no variance. $\sigma_\epsilon^2$ by definition is the variance of $\epsilon$.
The squared bias is the square of the difference between the target function $Y$ and the "average prediction" overall all training sets $\tau$, $E_\tau(\hat{f}_k(x_0))$.
\begin{align} bias^2 &= \left( Y(x_0) - E_\tau(\hat{f}_k(x_0)) \right) ^2 \\ &= \left( Y(x_0) - E_\tau\left(\frac{1}{k} \sum_i^k Y(x_i) \right)\right) ^2 \\ &= \left( Y(x_0) - \frac{1}{k} \sum_i^k Y(x_i) \right) ^2 \\ &= \left( f(x_0) + \epsilon_0 - \frac{1}{k} \sum_i^k f(x_i) + \epsilon_i \right) ^2 \\ \end{align}
Assuming fixed neighbors, we get $E_\tau\left(\frac{1}{k} \sum_i^k Y(x_i) \right)= \frac{1}{k} \sum_i^k Y(x_i)$ on line two. Here, all the $\epsilon$ values disappear when we take the expectation of the bias over all test samples $x_0$, because it has zero mean.
