# How can increasing the dimension increase the variance without increasing the bias in kNN?

My question is about understanding Figure 2.8 in The Elements of Statistical Learning (2nd edition). The topic of the section is how increasing dimension influence the bias/variance.

I can roughly understand Figure 2.7 in ESL, but have no idea about 2.8. Any explanation on the roughly unchanged bias, or the dominating variance? I cannot imagine how they change when the dimension is increasing.

Following is the detail:

Suppose we have 1000 training examples $x_i$ generated uniformly on $[-1,1]^p$. Assume that the true relationship between $X$ and $Y$ (capital letters for variables) is $$Y=F(X)=\frac12(X_1 + 1)^3$$ where $X_1$ denotes the first component of $X$ ($X$ has totally $p$ components, in other words, features). We use the 1-nearest-neighbor 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 samples of size 1000. This is the mean squared error (MSE) for estimating $f(0)$:

\begin{align} \operatorname{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 \\ &= \operatorname{Var}_{\mathcal{T}}(\hat{y}_0) + \operatorname{Bias}^2(\hat{y}_0) \end{align}

The figure is below. The right plot is the case with increasing $p$ (dimension). • Not everybody has the book. Can you show the picture (or a similar one) so others can understand the question? It would be helpful in answering it as well. – Andy Mar 31 '15 at 16:47
• @Andy I'm really sorry for the unclear statement. Now I updated the question. – Bor Mar 31 '15 at 17:56
• @Bor the question was put on hold because on this site we try to maintain questions and answers that are self-contained and so useful for more people then the original poster. Describing your question in detail (like it is now) makes it more readable for other users and also helps you to get an high-quality answer. Btw, welcome to our site! – Tim Mar 31 '15 at 18:40
• I changed the title & added the [knn] tag to make it more specific to the figure you are trying to understand. I'm not sure that the phenomenon discussed will always work out the same under other circumstances. – gung - Reinstate Monica Mar 31 '15 at 20:34
• @gung Thank you. I asked this question just because I got confused when reading the book, and I think understanding is the most important thing. I think the relationship among bias, variance and dimension is the core issue behind this question. – Bor Mar 31 '15 at 20:41

First of all, the bias of a classifier is the discrepancy between its averaged estimated and true function, wheras the variance of a classifier is the expected divergence of the estimated prediction function from its average value (i.e. how dependent the classifier is on the random sampling made in the training set).

Hence, the presence of bias indicates something basically wrong with the model, whereas variance is also bad, but a model with high variance could at least predict well on average.

The key to understand examples generating Figures 2.7 and 2.8 is:

The variance is due to the sampling variance of the 1-nearest neighbor. In low dimensions and with $N = 1000$, the nearest neighbor is very close to $0$, and so both the bias and variance are small. As the dimension $p$ increases, the nearest neighbor tends to stray further from the target point, and both bias and variance are incurred. By $p = 10$, for more than $99\%$ of the samples the nearest neighbor is a distance greater than $0.5$ from the origin.

Recall the the target function of the example generating Figure 2.7 depends on $p$ variables, and hence the MSE error is largely due to the bias.

Conversely, in Figure 2.8 the target function of the example depends only on $1$ variable, and thus the variance dominates. More generally, this happens when you are dealing with low dimensions.

I hope this could help.

• Thanks a lot. I've also read that segment, but I still cannot understand why variance dominates when the target function depends on only 1 variable, as well as the increasing trend of variable. – Bor Mar 31 '15 at 19:25
• the problem is that the k-nn doesn't know that only one variable is important. so in finding the nearest neighbour it is using the distance with all the other dimensions too. - so the chances of getting a point close on x1 dimension just because the overall distance is small gets smaller and smaller as dimension increases – seanv507 Mar 31 '15 at 19:41
• @seanv507 great comment. I just posted an answer where the core idea is the same as yours. It took me so long that I couldn't see your comment. Thank you! – Bor Mar 31 '15 at 20:26

Well, I don't know whether it's appropriate to answer a question asked by myself... But I think I have a relatively intuitive answer and I just wanna share it.

First let me add the true function in Figure 2.7 for comparison: $$Y=f_1(X)=e^{-8||X||^2}$$ and the one in Figure 2.8 is $$Y=f_2(X)=\frac12(X_1+1)^3$$

As @stochazesthai said, the true function of 2.7 depends on all $p$ components and 2.8 only $1$ component. On the other hand, the 1-NN algorithm involves the ordinary norm (by default), so the distance is measured by all components. Another thing to mention is that the expectation is taken to the estimated target $\hat{y}$ over the sample distribution.

Now consider the input $X$. Given any distance $d$ to the origin, when $p=1$, there're only $2$ choices of the value of $X$, which are $d$ and $-d$. When $p$ is increasing, with any fixed distance, the choices of $X$ will be dramatically increased, where the value of the first component $X_1$ can be oscillating more and more freely.

Then consider the 1-NN. When $p$ is increasing, as @stochazesthai quoted, the nearest neighbor of origin will be far away with high probability, which means that the smallest $||X||$ will be large.

Hence for $f_1$ (where $||X||$ involved), $E(\hat{y}_0)$ will increase a lot when $p$ is increasing, so the bias will increase significantly; but at the same time $\hat{y}_0$ will also be large with high probability, so the variance will not increase too much.

On the other hand, for $f_2$ (where only $X_1$ involved), when $p$ is increasing, as I mentioned above, $X_1$ can oscillate more and more dramatically with the same distance $E_{\mathcal{T}}(\hat{y}_0)$. So the increasing of variance will dominate, but $E_{\mathcal{T}}(\hat{y}_0)$ itself will not change a lot, so the bias will roughly unchanged in comparing with variance.