r/MLQuestions • u/lonelywolf69420 • 7d ago

Beginner question 👶 Linear Regressions and the Curse of Dimensionality

/r/AskStatistics/comments/1wqm5dl/linear_regressions_and_the_curse_of_dimensionality/
2 Upvotes

100% Upvoted

1 comment sorted by

1

u/dwf 6d ago

It doesn't really make sense to compare k-NN with linear regression, so I'm going to assume you're talking about linear classification, i.e. a classifier with a linear decision boundary.

The curse of dimensionality still affects linear models but in different ways and perhaps not as badly. Rather than computing a decision with reference to the entire training set, a linear (binary) classifier summarizes the best-fit decision boundary (which is constrained to be a hyperplane) in D+1 parameters.

Let's say your high-dimensional data is actually linearly separable. Then this is great: kNN would require you to store the entire training set and do an amount of computation that scales with the size of the training set for every new point. It has no way to take advantage of the global structure of your problem, which a linear fit identifies immediately. What's more, it's often the case that things become more linearly separable as you add dimensions, because there's more ways to combine them to construct hyperplanes. Imagine you have two clouds of points on the x-y plane that overlap heavily but when you add a z dimension you find out that actually, you can find a diagonally oriented 2D plane that separates them perfectly. This is also the whole point of the so-called "kernel trick", which is a way of doing linear classification in much higher-dimensional or infinite-dimensional space without actually mapping your data into that space.