Curse of Dimensionality in machine learning

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

Curse of Dimensionality, in more detail

A dataset with two features lives on a sheet of paper; one with five hundred lives in a space nobody can picture.

Each feature you add multiplies the volume of that space while the number of rows stays exactly the same.

So the data thins out, and your points end up scattered through a vast, mostly empty region.

This is the curse of dimensionality, and its sharpest consequence is what happens to distance.

In high dimensions the distance from a point to its nearest neighbour and to its furthest one converge.

Once those two numbers are almost the same, the word nearest has stopped carrying information.

Every method built on nearness suffers: k-nearest neighbours, k-means and most outlier detection.

The data needed to keep the space evenly covered grows exponentially with each feature.

Ten evenly spaced points cover a line; covering a ten-dimensional cube as well needs ten billion.

Nobody has that much data, so high-dimensional datasets are always sparse in practice.

Models respond by overfitting, because with enough features one can always be found that splits the training rows.

The defences are feature selection, dimensionality reduction such as PCA, and regularization.

Real data helps, because it usually lies on a much lower-dimensional surface inside the big space.

Embeddings work for the same reason: their thousand dimensions are learned rather than arbitrary.

The working rule is to earn every feature, since each one quietly costs you data you may not have.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath Curse of Dimensionality

Volume outruns any sample you can collect

n = k^{d}

$k$ : how many samples you want per axis.
$d$ : the number of dimensions.

Ten samples along each axis is 100 points in two dimensions, a million in six, and $10^{20}$ in twenty.

\text{fraction covered} = r^{d}

Put it the other way: to capture 10 percent of the volume of a 10-dimensional unit cube, an edge must be $0.1^{1/10} \approx 0.8$ of the full range.

A neighbourhood that holds a tenth of the data is therefore 80 percent as wide as the whole space, which makes the word local meaningless.

Distances stop distinguishing anything

\lim_{d \to \infty} \frac{d_{\max} - d_{\min}}{d_{\min}} \to 0

As dimensions grow, the distance from a query to its nearest point and to its furthest point converge on each other.

\mathbb{E}\big[\|\mathbf{x} - \mathbf{y}\|^2\big] = 2d\sigma^2

Every pair of random points ends up at nearly the same distance, because each of the $d$ coordinates adds its own variance to the sum and the total concentrates.

This is why k-NN, k-means, DBSCAN and anything else built on a distance degrade in high dimensions. The ranking they depend on becomes noise.

Where the volume actually sits

\frac{V_{\mathrm{shell}}}{V_{\mathrm{ball}}} = 1 - (1 - \epsilon)^{d}

In 100 dimensions, 99 percent of a ball's volume lies within the outer 5 percent of its radius.

\frac{V_{\mathrm{ball}}}{V_{\mathrm{cube}}} \to 0

The ball inscribed in a cube takes almost none of the cube's volume once $d$ is large, so nearly every point of the cube is in a corner.

Intuition built in two and three dimensions is not merely imprecise here. It is the opposite of what happens.

What saves it in practice

d_{\mathrm{intrinsic}} \ll d

Real data almost never fills its space. Images of faces, sentences and sensor readings lie on a much lower dimensional surface inside the high dimensional box.

The manifold hypothesis is the reason machine learning works on 150,000-dimensional images at all, and it is an assumption about the data rather than a theorem.

Where it fails, no amount of data helps, and the only fix is fewer dimensions.

One high dimensional problem, in order

Count the features and compare that with the number of rows.
Remove features that are constant, duplicated or unrelated to the target.
Project the rest down with PCA or a learned embedding, keeping enough components to hold the variance.
Prefer models that regularise hard or split on single features, since trees and linear models suffer far less than distance-based ones.
Re-measure, because a lower dimensional representation that scores worse was the wrong projection, not proof that the dimensions were needed.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

Why does k-nearest neighbours get worse as you add more features?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.

Study this module →