Interactive demo · Foundations of Deep Learning · Chapter 6

The curse of dimensionality: four ways high-dimensional space defies intuition

Pick a dimension D. (1) The fraction of a unit ball's volume within ε of its surface is 1 − (1 − ε)D, which tends to 1 for any fixed ε. (2) The radius of a standard Gaussian vector concentrates near √(D − 1) with spread about 1/√2, far from the mode of the density at the origin. (3) Distances from one random point to many others become nearly equal, so "nearest" loses its meaning. (4) A grid with k cells per axis has kD cells, so a fixed data set leaves almost all of them empty and a grid classifier cannot classify most new points. Every histogram is a seeded Monte Carlo sample checked against the formula.

Dimension D

Grid cells per axis k

Training points N (panel 4)

Try these

Samples: 2000 points for panels 1 and 2, 500 for panel 3, N training and N test points for panel 4, from a seeded generator. Panel 1 draws a uniform point in the ball through its radius U1/D. The Iris line uses the first min(D, 4) measurements of the 150 flowers, a k-cell grid on each, and leave-one-out: a flower is unclassifiable when no other flower shares its cell.

In the lecture notes