Machine Learning, 2nd Edition

Chapter 11High-Dimensional Data

By lumping all these choices together, we “reduce” the problem to a classical problem of determining the maximum of a given function. […]

There are, however, some details to consider. In the first place, the effective analytic solution of a large number of even simple equations as, for example, linear equations, is a difficult affair. Lowering our sights, even a computational solution usually has a number of difficulties of both gross and subtle nature. Consequently, 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.” Since this is a curse which has hung over the head of the physicist and astronomer for many a year, there is no need to feel discouraged about the possibility of obtaining significant results despite it.

— Richard E. Bellman, Dynamic Programming, 1957

Although it was originally defined in the context of numerical equation-solving and optimization (in the quote above), the curse of dimensionality now serves as a catch-all term describing difficulties which arise when the number of features, , is large. This chapter focuses on a major source of difficulty for the design and application of machine learning algorithms: the fact that high-dimensional Euclidean space has properties which conflict with intuition ...