Re:Curse of dimensionality
by i2pi on Wednesday May 30, 2012 @08:45PM
(#4045702)
There are two things going on here. First, as other commenters have noted, that as you increase the number of dimensions, the search space grows exponentially. The second, and deeper problem, is that our intuitions about 'volume' fail for higher dimensional problems. As you increase the number of dimensions, the outer shell of any hypercube holds much more volume than the inner portion of the cube. This means that if you were to distribute points with a Gaussian distribution in 2D, most of the mass is near the mean point of the distribution. As you increase the number of dimensions, more and more mass is contained within 'outliers'. In high dimensional space, things that seem unlikely in our usual 3D world become far more probable.
[ Parent
| on HN ]
I find this (and the other comment referencing the volumes of hypercubes) to be interesting. Perhaps exactly because it is so unintuitive. Maybe I could reason it up myself, but what exactly do you see as the "volume" of the inner portion and the "volume" of the shell? Are we talking about the same units here? Are there generic formulae?