16
$\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$
3
  • 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, 2018 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$ Feb 3, 2018 at 11:38
  • $\begingroup$ Also, tangentially, relevant, hastie.su.domains/ElemStatLearn/printings/ESLII_print12_toc.pdf You can refer page 22 of this book (Elements of Statistical Learning), where a similar hypothesis is presented to explain the curse of dimensionality. $\endgroup$ Mar 5, 2023 at 14:32

3 Answers 3

33
$\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$
6
  • 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, 2018 at 15:41
  • 2
    $\begingroup$ Really nice explanation of the term "curse of dimensionality" $\endgroup$
    – ignatius
    Dec 19, 2018 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, 2018 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, 2020 at 15:04
  • $\begingroup$ @Rodvi: You are right of course, thanks! Fixed it. $\endgroup$ Feb 3, 2020 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$
2
  • $\begingroup$ What I am a little confused by is by the definition of the boundary ( I am probably missing something) but in one dimension,we would have two points x0 and x1 with a distance of 10 units in between them. What is the boundary here exactly? $\endgroup$ Mar 5, 2023 at 14:43
  • $\begingroup$ The boundary is an arbitrary narrow region around the edge, same dimension as the hypercube. Doesn't matter if for the 10 unit example the boundary is 1 unit, 0.1 unit or less, as the dimension increases the ratio of boundary to not-boundary increases until it becomes the larger of the two. Another way to think of it is points inside the cube but nearer the edge than the centre, which would correspond to a boundary width of 2.5 units. As the dimension goes up, the proportion of points nearer the edge than the centre goes up. $\endgroup$ Mar 7, 2023 at 18:07
-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 and acknowledge you have read our privacy policy.

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