Understand the illustration of the curse of dimensionality?

Question

I understand how the curse of high dimensionality works when most features are irrelevant in this highly cited article: A Few Useful Things to Know About Machine Learning, but I get stuck in reading the following illustration:

This is because in high dimensions all examples look alike. Suppose, for instance, that examples are laid out on a regular grid, and consider a test example $x_t$. If the grid is d-dimensional, $x_t$’s 2d nearest examples are all at the same distance from it. So as the dimensionality increases, more and more examples become nearest neighbors of $x_t$, until the choice of nearest neighbor (and therefore of class) is effectively random

The first sentence is unintuitive. Especially, why If the grid is d-dimensional, $x_t$’s 2d nearest examples are all at the same distance from it?

To make it concrete, there are two coordinates(A and B) in a 2d plane:

Using geogebra

Suppose that (0, 0) is the test example, and we can see that A is closer to it than B. I wonder if B would be as close to the test example as A in any higher dimensional space? If so, how? If not, how would all samples look alike?

Answer 1

Let's look at the first few dimensions.

• For $d=1$, if examples are laid out on a regular grid, this just means that they are at equal distances on a straight line, e.g., at the integers. We can assume that our test example $x_t$ is at the origin, $x_t=0$. There are two nearest neighbors with equal distance $1$, namely the points at $1$ and $-1$.

• For $d=2$, we have a plane, and the regular grid could consist of all the two-dimensional integer points. For a test example again (without loss of generality) at the origin, there are four nearest neighbors, again all with distance $1$: $(0,1)$, $(-1,0)$, $(0,-1)$ and $(1,0)$.

• For $d=3$, we have a regular grid in three-dimensional space. Our test example at the origin now has six nearest neighbors, all at distance $1$.

In general, since we have $d$ dimensions and can assume that our regular grid just consists of the $d$-dimensional integer points, we can take the test example at the origin, and then we can find all $2d$ nearest neighbors by choosing one of the $d$ dimensions and setting that coordinate to either $1$ or $-1$, and leaving all other coordinates at $0$.

The problem this illustrates is that if there is no structure in our problem (i.e., our examples are on a regular grid, with no clusters, perhaps with some noise), then selecting a fixed number $k$ of nearest neighbors may simply mean picking them at random, since there are so many nearest neighbors, which may only be differentiated because of noise.

Answer 2

Especially, why If the grid is d-dimensional, $x_t$’s 2d nearest examples are all at the same distance from it? Could anyone please visualize the illustration(if possible)?

The example speaks about a regular grid.

In a regular grid you have for each grid line (on each dimension) two neighbouring nodes one at +1 and one at -1.

For a non-regular distribution the 2d nearest neighbours are not anymore at an exactly similar distance and there is some randomness. But the example with the regular grid shows that there are a lot of directions in which a nearest neighbour can be found (and this makes it easier for noise to overtake the signal).

Answer 3

I think @Stephan Kolassa explains well what the authors meant in that paragraph. The theoretical basis for "in high dimensions all samples look alike" is layed out in section 3.4 Instability Result of this paper.

Skipping the proof on page 6, essentially

... all points converge to the same distance from the query point. Thus under these conditions, the concept of nearest neighbor is no longer useful.

I think if the authors cite this paper instead of using that grid example, the presentation would be much clearer. Results in higher dimensions can be unintuitive because we live in a 3-d world.

Answer 4

imagine the unit cube $[0,1]^d$. All training data is sampled uniformly within this cube, i.e. $∀i,x_i∈[0,1]^d$, and we are considering the $k=10$ nearest neighbors of such a test point.

Let ℓ be the edge length of the smallest hyper-cube that contains all k-nearest neighbor of a test point. Then $ℓ^d≈\frac{k}{n}$ and $ℓ≈(\frac{k}{n})^{1/d}$. If n=1000, how big is ℓ?

So as d≫0 almost the entire space is needed to find the 10-NN.

To simulate the phenomenon, I conducted the following experiment(implement the example in the reference):

import matplotlib.pyplot as plt
%matplotlib inline
plt.rcParams.update({'figure.figsize':(7,5), 'figure.dpi':100})
import numpy as np
np.random.seed(0) 
from scipy.spatial import distance_matrix
min_val = 0
max_val = 1
n = 1000

for d in (2, 3, 10, 100, 1000, 10000):
    a = np.random.rand(n, d)
    b = np.random.rand(n, d)
    distances = distance_matrix(a, b)
    distances = np.array(distances).flatten()
    plt.hist(distances, bins=100, weights=np.ones(len(distances)) / len(distances))
    # plt.gca().set(title='Frequency Histogram', ylabel='Frequency')
    plt.show() 

And the plots align very well with those in the reference.

References:

1. Lecture 2: k-nearest neighbors