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. Richard Bellman (1920–1984) was an applied mathematician, celebrated for his invention of dynamic programming in 1953, and important contributions in other fields of mathematics. ... Volume, also called capacity, is a quantification of how much space an object occupies. ...

Leo Breiman gives as an example the fact that 100 observations cover the one-dimensional unit interval [0,1] 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 and may well be impractical. In mathematics, the unit interval is the interval [0,1], that is the set of all real numbers x such that zero is less than or equal to x and x is less than or equal to one. ... In mathematics, the real line is simply the set of real numbers. ... In statistics, a histogram is a graphical display of tabulated frequencies. ... some unit spheres In mathematics, a unit sphere is the set of points of distance 1 from a fixed central point, where a generalized concept of distance may be used. ...

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. Machine learning is an area of artificial intelligence concerned with the development of techniques which allow computers to learn. More specifically, machine learning is a method for creating computer programs by the analysis of data sets. ...

In particular, as the dimensionality incresases, inferences drawn by a machine learning algorithm require extrapolation, as the points in the training set are too sparse to be able to apply interpolation. In most situations, an extrapolating classifier will have higher variance than an interpolating classifier. In mathematics, extrapolation is a type of interpolation. ... In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ... In probability theory and statistics, the variance of a random variable is a measure of its statistical dispersion, indicating how far from the expected value its values typically are. ...

See also: quasi-random. In mathematics, a low-discrepancy sequence is a sequence with the property that for all N, the subsequence x1, ..., xN is almost uniformly distributed (in a sense to be made precise), and x1, ..., xN+1 is almost uniformly distributed as well. ...

Reference

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