15
$\begingroup$

If I have a 50 dimensional hypercube. And I define it's boundary by $0<x_j<0.05$ or $0.95<x_j<1$ where $x_j$ is dimension of the hypercube. Then calculating the proportion of points on the boundary of the hypercube will be $0.995$. What does it mean? Does it mean that rest of the space is empty? If $99\%$ of the points are at the boundary then the points inside the cube must not be uniformly distributed?

$\endgroup$
2
  • 4
    $\begingroup$ No, it means the periphery is more spacious, and the effect is commensurate with the dimensionality. It is somewhat counterintuitive. This phenomenon has consequences on the distribution of the distance between random pairs of nodes that become relevant when you want to cluster or calculate nearest neighbors in high-dimensional spaces. $\endgroup$
    – Emre
    Feb 2 '18 at 18:25
  • $\begingroup$ Calculate what proportion of the points on a line segment are near its boundary. Then points in a square. Then points in a cube. What can you say about them? $\endgroup$
    – user253751
    Feb 3 '18 at 11:38
32
$\begingroup$

Speaking of '$99\%$ of the points in a hypercube' is a bit misleading since a hypercube contains infinitely many points. Let's talk about volume instead.

The volume of a hypercube is the product of its side lengths. For the 50-dimensional unit hypercube we get $$\text{Total volume} = \underbrace{1 \times 1 \times \dots \times 1}_{50 \text{ times}} = 1^{50} = 1.$$

Now let us exclude the boundaries of the hypercube and look at the 'interior' (I put this in quotation marks because the mathematical term interior has a very different meaning). We only keep the points $x = (x_1, x_2, \dots, x_{50})$ that satisfy $$ 0.05 < x_1 < 0.95 \,\text{ and }\, 0.05 < x_2 < 0.95 \,\text{ and }\, \dots \,\text{ and }\, 0.05 < x_{50} < 0.95. $$ What is the volume of this 'interior'? Well, the 'interior' is again a hypercube, and the length of each side is $0.9$ ($=0.95 - 0.05$ ... it helps to imagine this in two and three dimensions). So the volume is $$\text{Interior volume} = \underbrace{0.9 \times 0.9 \times \dots \times 0.9}_{50 \text{ times}} = 0.9^{50} \approx 0.005.$$ Conclude that the volume of the 'boundary' (defined as the unit hypercube without the 'interior') is $1 - 0.9^{50} \approx 0.995.$

This shows that $99.5\%$ of the volume of a 50-dimensional hypercube is concentrated on its 'boundary'.


Follow-up: ignatius raised an interesting question on how this is connected to probability. Here is an example.

Say you came up with a (machine learning) model that predicts housing prices based on 50 input parameters. All 50 input parameters are independent and uniformly distributed between $0$ and $1$.

Let us say that your model works very well if none of the input parameters is extreme: As long as every input parameter stays between $0.05$ and $0.95$, your model predicts the housing price almost perfectly. But if one or more input parameters are extreme (smaller than $0.05$ or larger than $0.95$), the predictions of your model are absolutely terrible.

Any given input parameter is extreme with a probability of only $10\%$. So clearly this is a good model, right? No! The probability that at least one of the $50$ parameters is extreme is $1 - 0.9^{50} \approx 0.995.$ So in $99.5\%$ of the cases, your model's prediction is terrible.

Rule of thumb: In high dimensions, extreme observations are the rule and not the exception.

$\endgroup$
5
  • 7
    $\begingroup$ Worth using the OP's quote "Does it mean that rest of the space is empty?" and answering: No, it means that the rest of the space is relatively small . . . Or similar in your own words . . . $\endgroup$ Feb 2 '18 at 15:41
  • 2
    $\begingroup$ Really nice explanation of the term "curse of dimensionality" $\endgroup$
    – ignatius
    Dec 19 '18 at 12:04
  • $\begingroup$ Wondering if the following is correct: taking this example, if a set of features are evenly distributed along [0,1] in each of the 50 dimensions, the (99.5% -0.5%) = 99% of the the volume (hypercube feature space) captures only the 10% values of each feature $\endgroup$
    – ignatius
    Dec 19 '18 at 12:16
  • $\begingroup$ "Any given input parameter is extreme with a probability of only 5%." I think this probability is 10%. $\endgroup$
    – Rodvi
    Feb 1 '20 at 15:04
  • $\begingroup$ @Rodvi: You are right of course, thanks! Fixed it. $\endgroup$ Feb 3 '20 at 10:39
10
$\begingroup$

You can see the pattern clearly even in lower dimensions.

1st dimension. Take a line of length 10 and a boundary of 1. The length of the boundary is 2 and the interior 8, 1:4 ratio.

2nd dimension. Take a square of side 10, and boundary 1 again. The area of the boundary is 36, the interior 64, 9:16 ratio.

3rd dimension. Same length and boundary. The volume of the boundary is 488, the interior is 512, 61:64 - already the boundary occupies almost as much space as the interior.

4th dimension, now the boundary is 5904 and the interior 4096 - the boundary is now larger.

Even for smaller and smaller boundary lengths, as the dimension increases the boundary volume will always overtake the interior.

$\endgroup$
-1
$\begingroup$

The best way to "understand" it (though it is IMHO impossible for a human) is to compare the volumes of a n-dimensional ball and a n-dimensional cube. With the growth of n (dimensionality) all the volume of the ball "leaks out" and concentrates in the corners of the cube. This is a useful general principle to remember in the coding theory and its applications.

The best textbook explanation of it is in the Richard W. Hamming's book "Coding and Information Theory" (3.6 Geometric Approach, p 44).

The short article in Wikipedia will give you a brief summary of the same if you keep in mind that the volume of a n-dimensional unit cube is always 1^n.

I hope it will help.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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