8
$\begingroup$

My question is about the 1-nearest neighbor classifier and is about a statement made in the excellent book The Elements of Statistical Learning, by Hastie, Tibshirani and Friedman. The statement is (p. 465, section 13.3):

"Because it uses only the training point closest to the query point, the bias of the 1-nearest neighbor estimate is often low, but the variance is high."

The book is available at
http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.html

For starters, we can define what bias and variance are. From the question "how-can-increasing-the-dimension-increase-the-variance-without-increasing-the-bi" , we have that:

"First of all, the bias of a classifier is the discrepancy between its averaged estimated and true function, whereas 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."

Could someone please explain why the variance is high and the bias is low for the 1-nearest neighbor classifier?

$\endgroup$
10
$\begingroup$

The bias is low, because you fit your model only to the 1-nearest point. This means your model will be really close to your training data.

The variance is high, because optimizing on only 1-nearest point means that the probability that you model the noise in your data is really high. Following your definition above, your model will depend highly on the subset of data points that you choose as training data. If you randomly reshuffle the data points you choose, the model will be dramatically different in each iteration. So

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)

will be high, because each time your model will be different.

Example In general, a k-NN model fits a specific point in the data with the N nearest data points in your training set. For 1-NN this point depends only of 1 single other point. E.g. you want to split your samples into two groups (classification) - red and blue. If you train your model for a certain point p for which the nearest 4 neighbors would be red, blue, blue, blue (ascending by distance to p). Then a 4-NN would classify your point to blue (3 times blue and 1 time red), but your 1-NN model classifies it to red, because red is the nearest point. This means, that your model is really close to your training data and therefore the bias is low. If you compute the RSS between your model and your training data it is close to 0. In contrast to this the variance in your model is high, because your model is extremely sensitive and wiggly. As pointed out above, a random shuffling of your training set would be likely to change your model dramatically. In contrast, 10-NN would be more robust in such cases, but could be to stiff. Which k to choose depends on your data set. This highly depends on the Bias-Variance-Tradeoff, which exactly relates to this problem.

$\endgroup$
  • $\begingroup$ Thanks @alexvii. You are saying that for a new point, this classifier will result in a new point that "mimics" the test set very well. And if the test set is good, the prediction will be close to the truth, which results in low bias? Correct? Or am I missing out on something? $\endgroup$ – FredikLAa May 11 '15 at 12:23
  • $\begingroup$ I added some information to make my point more clear. $\endgroup$ – Alex VII May 11 '15 at 12:40
  • $\begingroup$ One more thing: If you use the three nearest neighbors compared to the closest, would you not be more "certain" that you were right, and not classifying the "new" observation to a point that could be "inconsistent" with the other points, and thus lowering bias? $\endgroup$ – FredikLAa May 11 '15 at 18:16
  • $\begingroup$ This is quite well explained on the wikipedia page under the point K-nearest neighbors nearly at the end of the page. $\endgroup$ – Alex VII May 11 '15 at 20:21
11
$\begingroup$

You should keep in mind that the 1-Nearest Neighbor classifier is actually the most complex nearest neighbor model. By most complex, I mean it has the most jagged decision boundary, and is most likely to overfit. If you use an N-nearest neighbor classifier (N = number of training points), you'll classify everything as the majority class. Different permutations of the data will get you the same answer, giving you a set of models that have zero variance (they're all exactly the same), but a high bias (they're all consistently wrong). Reducing the setting of K gets you closer and closer to the training data (low bias), but the model will be much more dependent on the particular training examples chosen (high variance).

$\endgroup$
  • $\begingroup$ thanks @Matt. One question: how do you know that the bias is the lowest for the 1-nearest neighbor? How do you know that not using three nearest neighbors would be better in terms of bias? $\endgroup$ – FredikLAa May 11 '15 at 18:18
  • $\begingroup$ Imagine a discrete kNN problem where we have a very large amount of data that completely covers the sample space. Any test point can be correctly classified by comparing it to its nearest neighbor, which is in fact a copy of the test point. Bias is zero in this case. If we use more neighbors, misclassifications are possible, a result of the bias increasing. This example is true for very large training set sizes. In reality, it may be possible to achieve an experimentally lower bias with a few more neighbors, but the general trend with lots of data is fewer neighbors -> lower bias. $\endgroup$ – Nuclear Wang May 12 '15 at 8:47
3
$\begingroup$

Here is a very interesting blog post about bias and variance. The section 3.1 deals with the knn algorithm and explains why low k leads to high variance and low bias.

Figure 5 is very interesting: you can see in real time how the model is changing while k is increasing. For low k, there's a lot of overfitting (some isolated "islands") which leads to low bias but high variance. For very high k, you've got a smoother model with low variance but high bias. In this example, a value of k between 10 and 20 will give a descent model which is general enough (relatively low variance) and accurate enough (relatively low bias).

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