ESL chapter 2.4 seems to classify linear regression as "model-based", because it assumes $f(x) \approx x\cdot\beta$, whereas no similar approximation is stated for k-nearest neighbors. But aren't both methods making assumptions about $f(x)$?

Later on in 2.4 it even says:

  • Least squares assumes $f(x)$ is well approximated by a globally linear function.
  • k-nearest neighbors assumes $f(x)$ is well approximated by a locally constant function.

The KNN assumption seems like it could also be formalized (though not sure if doing so would lead to the KNN algorithm in the way assuming $f$ is linear leads to linear regression).

So if KNN actually isn't model-based, why? Or am I misreading ESL?


4 Answers 4


It is quite hard to compare kNN and linear regression directly as they are very different things, however, I think the key point here is the difference between "modelling $f(x)$" and "having assumptions about $f(x)$".

When doing linear regression, one specifically models the $f(x)$, often something among the lines of $f(x) = \mathbf{wx} + \epsilon$ where $\epsilon$ is a Gaussian noise term. You can work it out that the maximum likelihood model is equivalent to the minimal sum-of-squares error model.

KNN, on the other hand, as your second point suggests, assumes that you could approximate that function by a locally constant function - some distance measure between the $x$-ses, without specifically modelling the whole distribution.

In other words, linear regression will often have a good idea of value of $f(x)$ for some unseen $x$ from just the value of the $x$, whereas kNN would need some other information (i.e. the k neighbours), to make predictions about $f(x)$, because the value of $x$, and just the value itself, will not give any information, as there is no model for $f(x)$.

EDIT: reiterating this below to re-express this clearer (see comments)

It is clear that both linear regression and nearest neighbour methods aim at predicting value of $y=f(x)$ for a new $x$. Now there are two approaches. Linear regression goes on by assuming that the data falls on a straight line (plus minus some noise), and therefore the value of y is equal to the value of $f(x)$ times the slope of the line. In other words, the linear expression models the data as a straight line.

Now nearest neighbour methods do not care about whether how the data looks like (doesn't model the data), that is, they do not care whether it is a line, a parabola, a circle, etc. All it assumes, is that $f(x_1)$ and $f(x_2)$ will be similar, if $x_1$ and $x_2$ are similar. Note that this assumption is roughly true for pretty much any model, including all the ones I mentioned above. However, a NN method could not tell how value of $f(x)$ is related to $x$ (whether it is a line, parabola, etc.), because it has no model of this relationship, it just assumes that it can be approximated by looking into near-points.

  • $\begingroup$ "one specifically models the f(x)" What does this mean? It seems one could formalize the assumption that f is locally constant. Is it just that KNN cannot be derived by any such formalization? $\endgroup$
    – alecbz
    Commented Jan 4, 2014 at 21:56
  • $\begingroup$ "linear regression will often have a good idea of value of f(x) for some unseen x from just the value of the x" not sure what you mean by this either... you still need the parameters of the linear model, just as you would need parameters for KNN (though its parameters are more involved) $\endgroup$
    – alecbz
    Commented Jan 4, 2014 at 21:57
  • $\begingroup$ Good points, I tried to edited my answer to make it clearer and hopefully answer your points (character limit for comments is low). $\endgroup$ Commented Jan 4, 2014 at 22:16
  • $\begingroup$ +1, this is well explained. 'the difference between "modelling f(x)" and "having assumptions about f(x)"', captures the idea very well, IMO. Perhaps another way of putting this is to consider that modelling f(x) amounts to making assumptions about the data generating process, whereas knn does not do this, but just figures that the value of a given datum might be similar to the value of nearby data. $\endgroup$ Commented Jan 4, 2014 at 22:32
  • $\begingroup$ Hm, okay. Your edit definitely makes it a little clearer, but I'm still having trouble really seeing a formal distinction. It seems that by "modeling" you mean "getting a good idea for the shape of f globally", whereas KNN cares only about the local behavior. So it's this difference in global vs local that makes linear regression modeling and KNN not? $\endgroup$
    – alecbz
    Commented Jan 5, 2014 at 2:42

Linear regression is model-based because it makes an assumption about the structure of the data in order to generate a model. When you load a data set into a statistical program and use it to run a linear regression the output is in fact a model: $\hat{f}(X)=\hat{\beta} X$ . You can feed new data into this model and get a predicted output because you have made assumptions about how the output variable is actually generated.

With KNN there isn't really a model at all - there's just an assumption that the observations that are near each other in $X$-space will probably behave similarly in terms of the output variable. You don't feed a new observation into a 'KNN model', you just determine which existing observations are most similar to a new observation and predict the output variable for the new observation from the training data.

  • $\begingroup$ While intuitively I understand what you mean, the distinction still feels shaky to me... can't you view KNN as being parameterized by a partition of R^d and weights assigned to the partitions? $\endgroup$
    – alecbz
    Commented Jan 5, 2014 at 17:25
  • 1
    $\begingroup$ If someone asked you to justify your predictions you could do so if you used linear regression by explaining the relationships between the inputs and outputs your model assumes. A model attempts to explain the relationship b/w inputs and outputs. KNN doesn't attempt to explain the relationship b/w inputs and outputs, hence there's no model. $\endgroup$
    – tjnel
    Commented Jan 5, 2014 at 17:40

The term model-based is synonymous with "distribution-based" when discussing clustering methods. Linear regression makes distributional assumptions (that the errors are Gaussian). KNN does not make any distributional assumptions. That is the distinction.

  • 1
    $\begingroup$ This makes the most sense so far to me in terms of a formal distinction, although ESL didn't really present linear regression this way. They introduced the squared-error cost function first, kind of arbitrarily (instead of doing an MLE for a Gaussian), used it to find that we should predict f(x) = E(Y | X = x), explained how KNN approximates this under certain assumptions, and then went on to assume f was linear to get linear regression. $\endgroup$
    – alecbz
    Commented Jan 5, 2014 at 17:22
  • $\begingroup$ Interesting proposition, but it'd be much better if we had some references about this. $\endgroup$
    – ivanmp
    Commented Jan 31, 2015 at 13:22

kNN is instance-based

In order to make a prediction for a new observation, you have to keep all the training dataset, because, there is no model about the dataset.

This is how kNN works: given a new observation, we will calculate the distance between this new observation and all the other observations in the training dataset. Then you get the neighbours (the ones that are the closest to the new observation).

If $k=5$, then we look at the 5 closest observations. "a locally constant function" means that after choosing these 5 observations, we don't care about the distances. They are the same, they have the same importance for the prediction.

How can find a model ?

Now, if we try to find a function that is not "locally constant", it would be a normal distribution. In this case, you will get an algorithm call Linear Discriminant Analysis or Naive Bayes (depending on some other assumptions).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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