Curse of dimensionality is a term coined by Richard Bellman applied to the problem caused by the rapid increase in volume associated with adding extra dimensions to a (mathematical) space.

Leo Breiman gives as an example the fact that 100 observations cover the one-dimensional unit interval ^* on the real line quite well. One could draw a histogram of the results, and draw inferences. If one now considers the corresponding 10-dimensional unit hypersquare, 100 observations are now isolated points in a vast empty space. To get similar coverage to the one-dimensional space would now require 10²⁰ observations, which is at least a massive undertaking.

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.

See also: quasi-random.

Reference

• Bellman, R.E. 1961. Adaptive Control Processes. Princeton University Press, Princeton, NJ.

malédiction de la dimensionalité