Curse of dimensionality

Why does measuring more features of each item make the items harder rather than easier to tell apart?

Measure two things about each item and you can plot them on a page; the similar ones cluster. Measure a thousand things and, by any reasonable account of information, you should know each item far better. Yet methods that lean on distance — find the nearest examples, average over the neighbours, draw a boundary between the clumps — get worse as the measurements accumulate, and often much worse.

The reflex explanation is that there is not enough data to fill the space. That is true and it is not the whole story, because the difficulty persists in ways that adding data does not repair. Something about distance itself changes when there are many coordinates, and it is worth seeing what.

Begin with volume, because volume is where the strangeness starts. Take the unit cube and ask how big a small cube must be to contain one per cent of it. In one dimension, an interval of length 0.01. In two, a square of side 0.1. In general the side length is the hundredth root taken d times over, and that climbs alarmingly: about 0.22 in three dimensions, 0.63 in ten, 0.955 in a hundred. To capture one hundredth of a hundred-dimensional cube, your "local" neighbourhood must span more than ninety-five per cent of every single axis. Locality, in the sense we mean it on a page, has stopped existing.

The same fact shows up as emptiness in the middle. A ball inscribed in the cube from minus one to one occupies about a quarter of one per cent of that cube by the tenth dimension, and the fraction keeps falling. Nearly all the volume is out in the corners, and there is almost nothing where our intuition puts the bulk of a solid.

Now let that act on distances. Give each item d coordinates drawn independently. The squared distance between two items is a sum of d independent contributions. As d grows, that sum has a mean growing in proportion to d, but a spread growing only like the square root of d — so the typical distance grows while the variation around it grows much more slowly. Divide one by the other and the contrast between pairs shrinks towards nothing. Beyer and colleagues put this precisely in 1999: under fairly broad conditions, the ratio of the farthest distance to the nearest converges to one as dimension increases. Every point becomes about equally far from every other.

Sit with what that does to a nearest-neighbour method. It still returns a nearest neighbour — the arithmetic never fails. But if the nearest is only a hair closer than the farthest, the label "nearest" has stopped carrying meaning, and a trace of noise reorders the list. The method has not broken; the quantity it consults has become uninformative.

So why is more measurement not simply more knowledge? Here is the crux, and it is the part the slogan hides. Each added coordinate contributes to the distance whether or not it says anything about the difference you care about. Signal enters through a few coordinates; noise enters through all of them, and accumulates. A useful feature does help — adding genuinely informative measurements cannot make the underlying problem harder in principle. The curse is not a penalty for dimension as such. It is what happens when dimensions are added faster than information is.

Which is why the effect is far milder in practice than the geometry threatens. Real measurements are heavily redundant: the pixels of a photograph, the sensors on an engine, the words of a document are not independent, and the data typically sits near a surface of much lower intrinsic dimension inside its ambient space. Distance methods work on images at all because the effective dimension is nothing like the pixel count.

Three refinements are worth holding on to.

The first is that "sparsity of data" and "concentration of distances" are two different problems that travel together. The first is about sample size and would in principle yield to more examples — though the number required grows exponentially, so "in principle" is doing a lot of work. The second is a property of the geometry and does not yield to more examples at all.

The second is an apparent contradiction that turns out to be the same fact. High dimension makes records easy to identify exactly while making them hard to compare by distance: a handful of behavioural attributes will single out an individual uniquely in a large database, precisely because the space is so vast that almost nobody collides. Uniqueness rises; metric contrast falls. Both follow from the same emptiness.

The third is that everything above assumes coordinates that are independent and comparably scaled. Correlation reduces effective dimension, and unequal scaling breaks things sooner — one coordinate measured in a large unit can dominate the distance entirely. This is also why the remedies are not "collect less" but "measure the right thing": select features, reduce dimension, or learn a metric that weights coordinates by their relevance.

• How intrinsic dimension is estimated, and why real datasets so often turn out far thinner than their column count suggests.
• Why approximate nearest-neighbour indexes such as locality-sensitive hashing are built to fail gracefully rather than to find the true nearest point.

Every term the collection defines is gathered in the glossary.