Machine Learning

The Curse of Dimensionality

Add axes and space stops behaving: data spreads until every point is alone, a ball becomes all crust, and every distance becomes the same distance.

sampled pointsthe current dwhat the formula predicts

Empty space—

—

Which curse

Dimensions d 2

Fraction of data to capture 10%

Crust thickness 5%

Sample points n 600

Values

What to observe

Empty space. To gather 10% of the data a box must span 63% of every axis at d = 5 and 89% at d = 20, so a "local" neighbourhood stops being local.
Volume in the crust. The outer 5% shell holds under 10% of a disc but over 99% of a 100D ball, because volume scales like r^d.
All distances equal. By d = 60 the spread of the distances is only a few percent of their mean, so nearest and farthest barely differ.
Everything orthogonal. cos θ between random directions has spread1/√d, so at d = 100 nearly every pair sits within a few degrees of 90°.

Shortcuts:space run/pause · s step · r reset · f fullscreen