Curse of dimensionality
From Wikipedia, the free encyclopedia
The curse of dimensionality is a term coined by Richard Bellman to describe the problem caused by the exponential increase in volume associated with adding extra dimensions to a (mathematical) space.
For example, 100 evenly-spaced sample points suffice to sample a unit interval with no more than 0.01 distance between points; an equivalent sampling of a 10-dimensional unit hypercube with a lattice with a spacing of 0.01 between adjacent points would require 1020 sample points: thus, in some sense, the 10-dimensional hypercube can be said to be a factor of 1018 "larger" than the unit interval. (Adapted from an example by R. E. Bellman, see below.)
Another way to envisage the "vastness" of high-dimensional Euclidean space is to compare the size of the unit sphere with the unit cube as the dimension of the space increases: as the dimension increases, the unit sphere becomes an insignificant volume relative to that of the unit cube; thus, in some sense, nearly all of the high-dimensional space is "far away" from the centre, or, to put it another way, the high-dimensional unit space can be said to consist almost entirely of the "corners" of the hypercube, with almost no "middle". (This is an important intuition for understanding the chi-squared distribution.)
[edit] The curse of dimensionality in machine learning
The curse of dimensionality is a significant obstacle in machine learning problems that involve learning from few data samples in a high-dimensional feature space.
[edit] See also
[edit] Reference
- Bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
- Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.
