# Derivation of bias-variance decomposition expression for K-nearest neighbor regression

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?

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.

• Bias^2 should be (f(x_0) - ...)^2, no? – James LT Feb 24 '18 at 22:53
• The answer has mixed the concepts of $\hat f$ and $f$. The computation of bias is totally wrong, this briefly shows how it should be done. – Logan Jun 26 '20 at 11:17

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}}.$$