Inside AI

Series on Theories: High Dimensional Data 101

History of the Curse of Dimensionality, Distance Measure Implications, and Unsupervised Learning Methods

Origins

“The purpose of this work is to provide an introduction to mathematical theory of multi-stage decision processes. Since these constitute a somewhat formidable set of terms we have coined the term ‘dynamic programming’ to describe the subject matter. […] Each decision may be thought of as a choice of a certain number of variables which determine the transformation to be employed. Each sequence of choices […] is a choice of a larger set of variables. By lumping all these choices together, we ‘reduce’ the problem to a classical problem of determining the maximum of a given function. […] The determination of this maximum is quite definitely not routine when the number of variables is large. All this may be subsumed under the heading ‘the curse of dimensionality.’ ”

Richard Bellman, 1956 [1]

Many texts on statistics, machine learning, and computer science reference the aforementioned “curse of dimensionality, ” a phrase most frequently attributed to applied mathematician Richard Bellman. Bellman was a prolific writer who created the field of dynamic programming, researching numerical solutions to partial differential equation systems. He authored at least 621 papers and 41 books.[2] It is not clear if Bellman developed the phrase…