5
$\begingroup$

In what way does the curse of dimensionality affect the predictions? I know that as the number of predictors increases the observations that are geometrically near decrease, so we have to spread out more to capture the nearest neighbours.

So my question is , in what other ways, than being computationally expensive , does the curse of dimensionality cause the non-parametric model to perform poorly?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Suppose you want to do regression in some 1d data in this way you should optimize the cost function which can be for example LSE. in other words you should search in 1d space to access the optimum point, but if you modify your input to 2d then you should find optimum point in 2d space. In other words if you needed one loop in 1d for find optimum point in here you roughly need two loop (for(for(...))) to find optimum. $\endgroup$
    – Panda
    Feb 26, 2017 at 13:16
  • 1
    $\begingroup$ Yes, that gets included under the computationally expensive,which I have already mentioned in the question , my question is how else? $\endgroup$
    – Fenil
    Feb 26, 2017 at 13:38
  • 1
    $\begingroup$ There's a good discussion of this on Wiki en.wikipedia.org/wiki/Curse_of_dimensionality. To me, much of the concern seems driven by computational and combinatorial complexity in optimizing a fixed, closed form algorithm. Probit models are an example of this: when the dependent variable in a probit model had more than 3 levels, observers opined that it could take 10,000 years of CPU for the solution to converge. With the approximating workarounds available today such as hierarchical Bayesian, bootstrap, jacknife, random forest, divide and conquer, etc., CoD has been greatly mitigated. $\endgroup$
    – Mike Hunter
    Feb 26, 2017 at 13:53
  • 1
    $\begingroup$ I'm sorry but both comments are not relevant. The curse of dimensionality (in statistics/machien learning) is not about computational complexity. $\endgroup$
    – Adrien
    Feb 28, 2017 at 15:59

3 Answers 3

Reset to default
8
$\begingroup$

The idea of nearest neighbours is that, due to continuity, other points close to your point of interest have values close to the value of your point of interest. If you have to spread very far out to find the 100 (for example) closest points, well then these points are not very close or neighbours anymore, and thus there's no reason that their values are relevant at all to help you predict the value at your point of interest!

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ +1. I believe that in high-dimensional space, everything starts to be nearly equidistant from everything else, so as you say you have to look pretty far from yourself to find $k$ neighbors. In addition, the distance to your $k$ neighbors will tend to not be that much smaller than distances to everyone else, so you don't get a lot of traction. $\endgroup$
    – Wayne
    Feb 28, 2017 at 17:07
1
$\begingroup$

The curse is that a lot of of things that work in lower dimension don't scale well (i.e. grow/shrink too fast compare to linear) with dimension. E.g. a measure of data quality is more than 2 times worse when you double the number of dimension. The curse comes in many form: the range of the data, the density of the data, the distribution, etc.

Take the example from ESL book. Says in every 1 dimension the possible values are in $[0,1]$, your data covers $[0.1,0.9]$, i.e. the range of data $r=0.8$. That's pretty good of a range if your data is just 1D.

The generalization of range to dimension $p$ is $0.8^p$. As $p$ increase, the range of your data shrinks really fast. In 2D, $p=2$, even though in each dimension, your data spans 80% of possible range, the 'volume' range that it capture is only 64%. In 10D, $p=10$, your data only cover 10% of the space! If you want to cover 80% of the space, in each dimension, your data need to span $0.8^{\frac{1}{10}} \approx 0.98$% of possible range - that's very expensive.

Improve this answer
$\endgroup$
0
$\begingroup$

It curses mainly in computational sense. However, if you expand the dimensionality from small to large to infinite, asymptotically any point that's not this point becomes infinitely far away.

If you're at point O, and are looking at points A and B, then both $OA=\infty$ and $OB=\infty$, and you can't distinguish which one is farther.

Improve this answer
$\endgroup$

Your Answer

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

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