curse of dimensionality
In plain wordsThe problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much.
An umbrella name for the difficulties in learning, search and estimation that grow, often exponentially, with the number of variables describing each item. Holding the spacing between samples fixed, every added dimension multiplies the number of points needed, so any realistic dataset leaves most of the space empty; nearly all of a high-dimensional ball's volume lies in a thin shell at its surface; and for many distributions a point's nearest and farthest neighbors end up almost equally far away, which undermines k-nearest neighborsk-nearest neighbors, n.: Predicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average., clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size. and density estimationdensity estimation, n.: Working out from a sample of data how likely different values are, by drawing a smooth curve or surface showing where data points bunch up and where they are rare.. In classification it appears as the peaking (Hughes) phenomenon: with a fixed training set, adding features first improves accuracy and then degrades it. Remedies include dimensionality reductiondimensionality reduction, n.: Squeezing data that has many measurements per item into far fewer numbers while keeping the patterns that matter, so it is easier to visualize, store or learn from., feature selectionfeature selection, n.: Choosing which of the available input measurements a model should use and dropping the rest, so the model becomes simpler, faster and often more accurate., regularizationregularization, n.: Any technique that stops a model from memorizing its training examples too closely — often by penalizing complexity — so that it works better on new data. and models with a strong inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases.. Deep learning succeeds in very high dimensions largely because real data occupy low-dimensional, structured regions (manifold hypothesismanifold hypothesis, n.: The idea that real-world data, such as photos of faces, fills only a thin, smoothly curved sliver of the vast space of all possible data — which is why learning from examples works at all.) rather than the whole space.
With 2,000 gene features and 300 patients, the curse of dimensionality made nearest-neighbor matching meaningless.
Origin
Coined by the mathematician Richard Bellman in his 1957 book Dynamic Programming to describe how the number of states, and hence the computation, explodes as variables are added to an optimization problem. G. F. Hughes described the related peaking effect in pattern recognition in 1968, and Kevin Beyer and colleagues analyzed the concentration of nearest-neighbor distances in 1999.
Usage note
Often invoked loosely for any difficulty caused by many features. The counterpoint 'blessing of dimensionality' notes that high-dimensional representations can make classes easier to separate linearly.
Related
- dimensionality reductiondimensionality reduction, n.: Squeezing data that has many measurements per item into far fewer numbers while keeping the patterns that matter, so it is easier to visualize, store or learn from.
- feature selectionfeature selection, n.: Choosing which of the available input measurements a model should use and dropping the rest, so the model becomes simpler, faster and often more accurate.
- k-nearest neighborsk-nearest neighbors, n.: Predicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average.
- manifold hypothesismanifold hypothesis, n.: The idea that real-world data, such as photos of faces, fills only a thin, smoothly curved sliver of the vast space of all possible data — which is why learning from examples works at all.
- dimensionalitydimensionality, n.: How many separate numbers are needed to describe something. A point on a map needs two; an AI's description of a single word may use thousands.
- overfittingoverfitting, n.: When a model learns its training examples too well — quirks and noise included — so it does great on data it has seen but poorly on anything new, like a student who memorizes answers without understanding.
Sources
- Bellman, R. (1957). Dynamic Programming. Princeton University Press.
- Hughes, G. F. (1968). On the Mean Accuracy of Statistical Pattern Recognizers. IEEE Transactions on Information Theory 14(1).
- Beyer, K., Goldstein, J., Ramakrishnan, R. & Shaft, U. (1999). When Is 'Nearest Neighbor' Meaningful? Proc. ICDT 1999.
Mentioned in
approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster., Bellman equationBellman equation, n.: A rule saying that how good a situation is equals the reward you get now plus how good the next situation is, slightly discounted — so long-term planning can be solved one step at a time., DBSCANDBSCAN, n.: A clustering method that finds groups as crowded regions of data separated by sparse ones, so it can discover oddly shaped groups and set stray points aside as noise., density estimationdensity estimation, n.: Working out from a sample of data how likely different values are, by drawing a smooth curve or surface showing where data points bunch up and where they are rare., dimensionalitydimensionality, n.: How many separate numbers are needed to describe something. A point on a map needs two; an AI's description of a single word may use thousands., dimensionality reductiondimensionality reduction, n.: Squeezing data that has many measurements per item into far fewer numbers while keeping the patterns that matter, so it is easier to visualize, store or learn from., dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step., Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length., feature selectionfeature selection, n.: Choosing which of the available input measurements a model should use and dropping the rest, so the model becomes simpler, faster and often more accurate., k-nearest neighborsk-nearest neighbors, n.: Predicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average., nonparametric modelnonparametric model, n.: A model that lets the data decide how complex it becomes: the more examples it gets, the more detail it can capture — for instance, one that predicts by comparing a new case with every stored example., Richard BellmanRichard Bellman, prop. n.: An American mathematician who invented dynamic programming, a way of solving long chains of decisions step by step, which became the mathematical core of reinforcement learning., manifold hypothesismanifold hypothesis, n.: The idea that real-world data, such as photos of faces, fills only a thin, smoothly curved sliver of the vast space of all possible data — which is why learning from examples works at all.