7
$\begingroup$

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:

enter image description here 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?

$\endgroup$
1
  • 1
    $\begingroup$ "If the grid is d-dimensional, xt’s 2d nearest examples..." Note that the "2d" here is "2 multiplied by d", not an abbreviation for "two-dimensional". $\endgroup$
    – Stef
    Commented Dec 29, 2021 at 15:07

4 Answers 4

12
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ Shouldn't "$2d$ nearest neighbors" be "$2^d$ nearest neighbors"? $\endgroup$
    – mhdadk
    Commented Dec 29, 2021 at 3:01
  • $\begingroup$ You mean that the nearest neighbors would increase as the dimensionality increases, but the non-nearest neighbors would increase faster, then how do all examples look alike? I thought only a small fraction of examples would look alike no matter how high the dimensionality is. $\endgroup$ Commented Dec 29, 2021 at 4:28
  • 2
    $\begingroup$ @mhdadk: no, it's $2d$, not $d^2$. To find an NN from the origin at $0$, we pick one dimension out of $d$, giving us $d$ possibilities, and then go either in the positive or the negative direction, giving us another $2$ possibilities, for $2d$ overall. You are thinking of the entire hypercube, but the vertices at $(\pm 1,\pm 1,0,\dots)$ are not NNs, only $(\pm1,0,0,\dots)$ and $(0,\pm 1, 0, \dots)$ and so forth are. $\endgroup$ Commented Dec 29, 2021 at 8:15
  • 2
    $\begingroup$ @LernerZhang: no, I am not saying the non-NNs increase faster. I am saying that even in a completely unstructured constellation (like that homogeneous regular grid), there are many NNs, so picking any $k$ of them is not more informative than picking $k$ others that are just slightly farther away. The point is that we have little chance of finding actual informative clusters in high dimensions. $\endgroup$ Commented Dec 29, 2021 at 8:17
  • 1
    $\begingroup$ @mhdadk: yes, Cris Luengo pointed out my error. I was in a hurry yesterday. I shouldn't be touching CV when I'm in a hurry... $\endgroup$ Commented Dec 29, 2021 at 8:20
4
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

enter image description here

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 ℓ?

enter image description here

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
$\endgroup$
2
  • $\begingroup$ Any intuition on why $\ell^d \approx \frac{k}{n}$$? $\endgroup$
    – ado sar
    Commented May 28 at 12:54
  • $\begingroup$ Also what is $n$ in this equation? $\endgroup$
    – ado sar
    Commented May 28 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.