Need more intuition for the curse of dimensionality

Question

People despise using Eucliean distance in higher dimensional spaces because it is not a viable metric. People argue that the distance between two vectors becomes very large as the number of dimensions increases.

But to me: it makes sense as we add more dimensions that the Eucliean distance between two points in high dimensional space becomes larger as we add more dimensions. I don't quite see the problem here.

How does inflating the distance between two vectors invalidate the metirc itself? The magnitude of the distances may be larger, but why can't it still be a viable comparison metric?

The book elements of statistical learning gives a nice picture trying to describe why Eucliean distance fails:

Okay - so what? The distance between two points gets larger and larger? Why does that invalidate the metric? It makes perfect sense that the distance between these two vectors is larger as we add new dimensions because they are more dissimilar to one another in the newer dimensions.

Let's think of an example where we collected lengths of a bunch of toys:

• 5.3
• 2.2
• 1.2

The nearest point for a new toy 4.2 is 5.3 based on Euclidean distance. Now let's add another dimension called width of these toys.

• <5.3, 5.6>
• <2.2, 2.1>
• <1.2, 0.4>

An our new point is <4.2, 0>. Now the nearest point is <2.2, 2.1>. This makes sense. Because the second dimension is widely different there. People argue that distances become less meaningful. But I can still successfully apply it here and the resulting distance makes perfect sense to me.

Anyway I don't fully understand this hatred towards Euclidean distance - it seems to make perfect sense to me!

Answer 1

I am used to an essentially same but a bit more illustrative example, in my opinion.

Let $x_1,...x_l$ be i.i.d. and uniformly distributed in the unit $n$-ball centered at the origin. Then it can be shown (I'm not writing out the derivation now, let me know if you're interested) that the median of the maximum of Euclidean distances of these points from the origin $m=\text{med}\max_l(\rho(x_1,0),...,\rho(x_l,0))$ is $$ m=\left[1-2^{-1/l}\right]^{1/n} $$ Obviously, $m\to_{n\to\infty}1$.

Now, for some intuition about the curse of dimensionality, imagine that we want to classify the point at the origin using a $kNN$ classifier (for simplicity even with $k=1$). What this formula gives us is that when the dimensionality of the feature space becomes large enough, typically the points of our training sample will "almost surely" (not exactly in the measure-theoretic sense) will be lying almost on the boundary of our unit ball and, thus, will have almost the same Euclidean distance from our point, rendering comparisons of distances to the point of interest effectively useless.

This is how I like to think about the catchphrase "In a high-dimensional space, almost all points are almost equally as distant from each other". Hope this intuition satisfies you.

EDIT Proof of the formula:

1) Let $r(x)=\rho(x, 0)$. Then the distribution function of $r$ is given by $$ F_r(t)=P(\rho(x, 0)<t)=\frac{V_n(t)}{V_n(1)}=t^n, $$ where $V_n(t)$ is the volume of an N-dimensional ball of a radius $t$.

2)Let $M(X)=\max (r(x_1),...,r(x_l))$. Then the distribution of $M$ is $$ F_M(t)=P(M<t)=1-P(M\geq{t})=1-(1-F_r(t))^l=1-(1-t^n)^l. $$

3) Now, the definition of $m$ is $F_M(m)=1/2$. Simple arithmetics now give the claim.

Answer 2

There is one respect in which the Euclidean distance is not comfortable because the distance tends to increase with dimension: comparison of distances between two pairs of points when the dimension of the first pair is different than that of the second pair.

Suppose there are two points $x$ and $y$ in $\mathbb{R}^n$ and you want to calculate the distance between them. Suppose that in the beginning only the first coordinate is revealed to you, and the observed distance is $d_1=\sqrt{(x_1-y_1)^2}$. After that, another coordinate is revealed, and the observed distance becomes $d_2=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2}$. Chances are that $d_2>d_1$ even though the two points $x$ and $y$ are the same in both cases. That means you have trouble comparing the distances in different dimensions (but you still can meaningfully compare distances between different points when the dimension is fixed).

Taking, for example, the mean of coordinate-by-coordinate distance ($d=\frac{1}{n}\sum_{i=1}^n |x_i-y_i|$) could be a remedy.