The Curse of Dimensionality

Question 1

A random point in a unit square has roughly what chance of lying within 0.001 of a border?

Accepted Answer

About 0.4% — The formula is 1 − (1 − 2ε)^d, which at d = 2 and ε = 0.001 gives 0.3996%. Being extreme along any dimension is rare in two dimensions.

Question 2

The same probability in a 10,000-dimensional unit hypercube is:

Accepted Answer

Greater than 99.999999% — Every added dimension is another chance to be extreme and they compound. Most points in a high-dimensional hypercube are very close to the border.

Question 3

Two random points in a 1,000,000-dimensional unit hypercube are on average about how far apart?

Accepted Answer

About 408.25 — Roughly the square root of one million over six. Both points lie inside a box of side 1, and they are four hundred units apart.

Question 4

The mean distance between two uniform points grows approximately as:

Accepted Answer

The square root of d divided by 6 — It is an asymptotic result: at d = 2 it gives 0.577 where the exact expected distance is 0.5214, so it only becomes accurate for large d.

Question 5

Why does high-dimensional sparsity break k-nearest neighbours?

Accepted Answer

Because every instance is far from every other, so "nearest" means little — Training methods based on distance or similarity are much less effective when most instances are far apart.

Question 6

With 100 features all ranging from 0 to 1, the number of training instances needed for instances to sit within 0.1 of each other on average exceeds:

Accepted Answer

The number of atoms in the observable universe — And 100 features is "significantly fewer than in the MNIST problem". The required count grows exponentially with dimension.

Question 7

Predictions in high dimensions are less reliable mainly because:

Accepted Answer

New instances land far from any training instance, so predictions extrapolate — Predictions rest on much larger extrapolations than in lower dimensions.

Question 8

The two main approaches to dimensionality reduction are:

Accepted Answer

Projection and manifold learning — Projection drops a perpendicular onto a lower-dimensional subspace; manifold learning tries to unroll a shape a plane cannot capture.

Question 9

Projection works as an approach because in most real problems:

Accepted Answer

Instances lie within or close to a much lower-dimensional subspace — Many features are almost constant and others are highly correlated, so the data occupies far less of the space than its dimension suggests.

Question 10

Losing information during dimensionality reduction is, in Géron's comparison, like which kind of lossy compression?

Accepted Answer

Compressing a photograph and visibly degrading its quality — It can make your system perform slightly worse, "especially if you reduce dimensionality too much".

What changes as the dimension grows

What happens as dimensions grow?

Test your knowledge

A random point in a unit square has roughly what chance of lying within 0.001 of a border?

Learn these first

Interview Questions

References & Further Reading

Love this visualization?