6
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Bias^2 should be (f(x_0) - ...)^2, no? $\endgroup$ – James LT Feb 24 '18 at 22:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Logan Jun 26 '20 at 11:17
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.