2
$\begingroup$

In section 2.3 of Elements of Statistical Learning when the text introduces the linear model and k-nearest-neighbour it states:

The linear model makes huge assumptions about structure and yields stable but possibly inaccurate predictions. The method of k-nearest neighbors makes very mild structural assumptions: its predictions are often accurate but can be unstable.

What is the meaning of stability in this context? Please elaborate in relation to the aforementioned methods.

$\endgroup$
3
$\begingroup$

The book Elements of Statistical Learning does not seem to give a formal definition of the concept of "stability" as it is used in this context. The words stable or stability do not occur in the index. However, the following quote seems to indicate the intended meaning (page 16 of second edition):

The linear decision boundary from least squares is very smooth, and apparently stable to fit. It does appear to rely heavily on the assumption that a linear decision boundary is appropriate. In language we will develop shortly, it has low variance and potentially high bias. On the other hand, the $k$-nearest-neighbor procedures do not appear to rely on any stringent assumptions about the underlying data, and can adapt to any situation. However, any particular subregion of the decision boundary depends on a handful of input points and their particular positions, and is thus wiggly and unstable-high variance and low bias.

With the linear model all of the data contributes to the predictions for any particular $x$. This gives low variance, hence its predictions can be stable — but high bias if the linear model is not a good approximation.

With the $k$-nearest neighbors method, for any particular $x$ only the $k$-nearest neighbors contribute to the prediction. As a result the variance is higher, hence its predictions can be unstable — this is especially so if $k$ is much smaller than $n$.The gain is that by only using close points, the approximation could be better, so potentially lower bias. One problem is that if the ambient space of the $x$ is high-dimensional, there might be no really close neighbors anyhow.

Furthermore, for defining neighbors we need a distance measure, a metric. The results of $k$-nearest neighbors depends critically on the definition of the metric, while the linear model does not use such information. The book elements of statistical learning do assume an euclidean metric, bit other choices are of course possible. For the euclidean metric to be meaningful, the different variables must be on comparable scales. If, for instance, you multiply one of the variables by 1000 (changing unit from km to m, for instance) that will change, maybe drastically, the $k$-nearest neighbors solution, while it has no impact on the linear model at all.


Below is the original answer — as historical documentation:

In this context it probably means that when the input data $x$ changes a little, then the predicted value also changes only a little bit, in an easily understood manner, while with $k$-means, this need not be true, some little change in $x$ could cause a surprisingly large change in the prediction.

$\endgroup$
  • $\begingroup$ According to this definition, the linear model is "unstable" too. $\endgroup$ – whuber Aug 19 '15 at 12:41
  • $\begingroup$ @whuber: Why? Do you have a better answer? $\endgroup$ – kjetil b halvorsen Aug 19 '15 at 13:07
  • 1
    $\begingroup$ A basic problem with the linear model is that its results are sensitive to any data that are "influential" or have high "leverage." Both of these are technical terms that refer to quantitative assessments of how the regression estimates or fitted values change when an individual response is varied. This shows that according you your answer, linear regression is "unstable." A better answer would therefore either have to be altogether different or else it would show us quantitatively how points in a k-means fit tend to have greater leverage than comparable points in an OLS fit. $\endgroup$ – whuber Aug 19 '15 at 13:27
  • 1
    $\begingroup$ @whuber & kjetil b halvorsen: Is there a consensus on a correct answer? Also, is there a reason you have been discussing k-means instead of k-NN? $\endgroup$ – jBit Aug 24 '15 at 8:13
  • 1
    $\begingroup$ I agree the newer answer is probably more in line with ESL, but I get where the earlier one was coming from: For k-NN vs. linmod the difference is more than just condition number, as the nearest neighbor mapping is discontinuous as a function of the inputs. $\endgroup$ – GeoMatt22 May 4 '17 at 17:02
1
$\begingroup$

I'd like to illustrate these two using the following comparison.

enter image description here

As you can see the higher the variance the more unstable the prediction will be and the higher the bias the mean of the prediction will be more far away from the target. The linear regresson would be stable but its bias sometimes is high(overfitting); while the KNN might be accurate(low bias) but might be unstable(high variance).

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