Explain "Curse of dimensionality" to a child

Question

I heard many times about curse of dimensionality, but somehow I'm still unable to grasp the idea, it's all foggy.

Can anyone explain this in the most intuitive way, as you would explain it to a child, so that I (and the others confused as I am) could understand this ones for good?

---

EDIT:

Now, let's say that the child somehow heard about clustering (for example, they know how to cluster their toys :) ). How would the increase of dimensionality make the job of clustering their toys harder?

For example, they used to consider only the shape of the toy and the color of the toy (one-color toys), but now need to consider the size and the weight of toys also. Why is it more difficult for the child to find similar toys?

---

EDIT 2

For the sake of discussion I need to clarify that by - "Why is it more difficult for the child to find similar toys" - I also mean why is the notion of distance lost in high-dimensional spaces?

Answer 1

Probably the kid will like to eat cookies, so let us assume that you have a whole truck with cookies having a different colour, a different shape, a different taste, a different price ...

If the kid has to choose but only take into account one characteristic e.g. the taste, then it has four possibilities: sweet, salt, sour, bitter, so the kid only has to try four cookies to find what (s)he likes most.

If the kid likes combinations of taste and colour, and there are 4 (I am rather optimistic here :-) ) different colours, then he already has to choose among 4x4 different types;

If he wants, in addition, to take into account the shape of the cookies and there are 5 different shapes then he will have to try 4x4x5=80 cookies

We could go on, but after eating all these cookies he might already have belly-ache ... before he can make his best choice :-) Apart from the belly-ache, it can get really difficult to remember the differences in the taste of each cookie.

As you can see (@Almo) most (all?) things become more complicated as the number of dimensions increases, this holds for adults, for computers and also for kids.

Answer 2

The analogy I like to use for the curse of dimensionality is a bit more on the geometric side, but I hope it's still sufficiently useful for your kid.

It's easy to hunt a dog and maybe catch it if it were running around on the plain (two dimensions). It's much harder to hunt birds, which now have an extra dimension they can move in. If we pretend that ghosts are higher-dimensional beings (akin to the Sphere interacting with A. Square in Flatland), those are even more difficult to catch. :)

Answer 3

Ok, so let's analyze the example of the child clustering its toys.
Imagine the child has only 3 toys:

1. a blue soccer ball
   
2. a blue freesbe
3. a green cube (ok maybe it's not the most fun toy you can imagine)

Let's do the following initial hypothesis regarding how a toy can be made:

1. Possible colors are: red, green, blue
2. Possible shapes are: circle, square, triangle

Now we can have have (num_colors * num_shapes) = 3 * 3 = 9 possible clusters.

The boy would cluster the toys as follows:

• CLUSTER A) contains the blue ball and the blue freesbe, because thay have the same color and shape
• CLUSTER B) contains the super-funny green cube

Using only these 2 dimensions (color, shape) we have 2 non-empty clusters: so in this first case 7/9 ~ 77% of our space is empty.

Now let's increase the number of dimensions the child has to consider. We do also the following hypothesis regarding how a toy can be made:

3. Size of the toy can vary between few centimeters to 1 meter, in step of ten centimeters: 0-10cm, 11-20cm, ..., 91cm-1m
4. Weight of the toy can vary in a similar manner up to 1 kilogram, with steps of 100grams: 0-100g, 101-200g, ..., 901g-1kg.

If we want to cluster our toys NOW, we have (num_colors * num_shapes * num_sizes * num_weights) = 3 * 3 * 10 * 10= 900 possible clusters.

The boy would cluster the toys as follows:

• CLUSTER A) contains the blue soccer ball because is blue and heavy
• CLUSTER B) contains the blue freesbe because is blue and light
• CLUSTER C) contains the super-funny green cube

Using the current 4 dimensions (shape, color, size, weigth) only 3 clusters are non empty: so in this case 897/900 ~ 99.7% of the space is empty.

This is an example of what you find on Wikipedia (https://en.wikipedia.org/wiki/Curse_of_dimensionality):
...when the dimensionality increases, the volume of the space increases so fast that the available data become sparse.

---

Edit: I'm not sure i could really explain to a child why distance sometimes goes wrong in high-dimensional spaces, but let's try to proceed with our example of the child and his toys.

Consider only the 2 first features {color, shape} everyone agrees that the blue ball is more similar to the blue freesbe than to the green cube.

Now let's add other 98 features {say: size, weight, day_of_production_of_the_toy, material, softness, day_in_which_the_toy_was_bought_by_daddy, price etc}: well, to me would be increasingly more difficult to judge which toy is similar to which.

So:

1. A large number of features can be irrelevant in a certain comparison of similarity, leading to a corruption of the signal-to-noise ratio.
2. In high dimensions, all examples "look-alike".
   
   

If you listen to me, a good lecture is "A Few Useful Things to Know about Machine Learning" (http://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf), paragraph 6 in particular presents this kind of reasoning.

Hope this helps!

Answer 4

I have come across the following link that provides a very intuitive (and detailed) explanation of curse of dimensionality: http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/

In this article, we will discuss the so called ‘Curse of Dimensionality’, and explain why it is important when designing a classifier. In the following sections I will provide an intuitive explanation of this concept, illustrated by a clear example of overfitting due to the curse of dimensionality.

In a few words this article derives (intuitively) that adding more features (i.e. increasing the dimensionality of our feature space) requires to collect more data. In fact the amount of data we need to collect (to avoid overfitting) grows exponentially as we add more dimensions.

It also has nice illustrations like the following one:

Answer 5

The curse of dimensionality is somewhat fuzzy in definition as it describes different but related things in different disciplines. The following illustrates machine learning’s curse of dimensionality:

Suppose a girl has ten toys, of which she likes only those in italics:

• a brown teddy bear
• a blue car
• a red train
• a yellow excavator
• a green book
• a grey plush walrus
• a black wagon
• a pink ball
• a white book
• an orange doll

Now, her father wants to give her a new toy as a present for her birthday and wants to ensure that she likes it. He thinks very hard about what the toys she likes have in common and finally arrives at a solution. He gives his daughter an all-coloured jigsaw puzzle. When she does not like, he responds: “Why don’t you like it? It does contain the letter w.”

The father has fallen victim to the curse of dimensionality (and in-sample optimisation). By considering letters, he was moving in a 26-dimensional space and thus it was very likely that he would find some criterion separating the toys liked by the daughter. This did not need to be a single-letter criterion as in the example, but could have also been something like

contains at least one of a, n and p but none of u, f and s.

To adequately tell whether letters are a good criterion for determining which toys his daughter likes, the father would have to know his daughter’s preferences on a gargantuan amount of toys¹ – or just use his brain and only consider parameters that are actually conceivable to affect the daughter’s opinion.

---

¹ order of magnitude: $2^{26}$, if all letters were equally likely and he would not take into account multiple occurrences of letters.

Answer 6

• Think of a circle enclosed in unit square.
• Think of a sphere enclosed in the unit cube.
• Think of an n-dimensional hyper sphere enclosed in the n-dimensional unit hyper cube.

The volume of the hyper cube is 1, of course, when measured in $1^n$ units. However, the volume of a hyper sphere shrinks with n growing.

If there was something interesting inside the hyper sphere it's harder and harder to see it in higher dimensions. In $\infty$-dimensional case the hyper sphere disappears! That's the curse.

UPDATE: It seems that some folks didn't get the connection to statistics. You can see the relationship if you imagine picking a random point inside a hyper cube. In two dimensional case the probability that this point is inside the circle (hyper sphere) is $\pi/4$, in three dimensional case it's $\pi/6$ etc. In the $\infty$-dimensional case the probability is zero.

Answer 7

Me: "I am thinking of a small brown animal beginning with 'S'. What is it?"

Her: "Squirrel!"

Me: "OK, a harder one. I am thinking of a small brown animal. What is it?"

Her: "Still a squirrel?"

Me: "No"

Her: "Rat, mouse, vole?

Me: "Nope"

Her: "Umm... give me a clue"

Me: "Nope, but I'll do some thing better: I'll let you answer to a CrossValidated question"

Her: [groans]

Me: "The question is: What is the curse of dimensionality? And you already know the answer"

Her: "I do?"

Me: "You do. Why was it harder to guess the first animal than the second?"

Her: "Because there are more small brown animals than small brown animals beginning with 'S'?"

Me: "Right. And that's the curse of dimensionality. Let's play again."

Her: "OK"

Me: "I'm thinking of something. What is it?"

Her: "No fair. This game is way to hard."

Me: "True. That's why they call it a curse. You just can't do well without knowing the things I tend to think about."

Answer 8

Suppose you want to ship some goods. You want to waste as little space as possible when packaging the goods (i.e., leave as little empty space as possible), because shipping costs are related to volume of the envelope/box. The containers at your disposal (envelopes, boxes) have right angles, so no sacks etc.

First problem: ship a pen (a "line") - you can build a box around it with no space lost.

Second problem: ship a CD (a "sphere"). You need to put it into a square envelope. Depending how old the child is, she may be able to calculate how much of the envelope will remain empty (and still know that there are CDs and not just downloads ;-)).

Third problem: ship a football (soccer, and it has to be inflated!). You will need to put it into a box, and some space will remain empty. That empty space will be a higher fraction of the total volume than in the CD example.

At that point my intuition using this analogy stops, because I cannot imagine a 4th dimension.

EDIT: The analogy is most useful (if at all) for nonparametric estimation, which uses observations "local" to the point of interest to estimate, say, a density or a regression function at that point. The curse of dimensionality is that in higher dimensions, one either needs a much larger neighborhood for a given number of observations (which makes the notion of locality questionable) or a large amount of data.

Answer 9

My 6 yo is more on the verse of the primary cause research, like in "but where did all this gas in the universe come from?"... well, I’ll imagine your child understand "higher dimensions", which seems very unlikely to me.

Let’s ask the following question: pick random points (uniformly) in a $n$-cube $[0,1]^n$, one by one. How long does it take to get a point in the lower corner $\left[ {1\over2}, {1\over2}\right]^n$?

The answer, young lad, is that the probability for a random point to be in this lower corner is $\left({1\over 2}\right)^n$, which means that the expected number of points to draw before hitting the left corner is $2^n$ (by the properties of the geometric distribution). And as you know it from the wheat and chessboard problem, this quickly becomes awfully huge.

Now go pick up your room, daddy’s got to work.

PS about clustering... think about your points scattered in this high dimension box. It’s so big that there are $2^n$ sub-boxes with edges of length ${1\over 2}$. It will take some time before picking two points in the same sub-box. Well that can a problem even when the point are not drawn uniformly at random, but in some clusters. If the clusters are not chosen arbitrarily small, it can take very long before picking two points in the same sub-box. You understand that this hinders clustering...

Answer 10

Fcop offered a great analogy with cookies but have covered only the sampling density aspect of the curse of dimensionality. We can extend this analogy to the sampling volume or the distance by distributing same number of Fcop's cookies in, say, ten boxes in one line, 10x10 boxes flat on the table and 10x10x10 in a stack. Then you can show that to eat the same share of cookies the child will have to open ever more boxes.

It is really about the expectations but let's take a "worst case scenario" approach to illustrate.

If there are 8 cookies and we want to eat a half i.e. 4, from 10 boxes in a worst case we only need to open 6 boxes. That's 60% - just about a half too. From 10x10 (again in a worst case) - 96(%). And from 10x10x10 - 996(99,6%). That's almost all of them!

May be the storage room analogy and distance walked between rooms would do better than boxes here.

Answer 11

There is a classic, textbook, math problem that shows this.

Would you rather earn (option 1) 100 pennies a day, every day for a month, or (option 2) a penny doubled every day for a month? You can ask your child this question.

If you choose option 1,
on day 1 you get 100 pennies on day 2 you get 100 pennies on day 3 you get 100 pennies ... on day 30 you get 100 pennies

on the $n^{th}$ day you get 100 pennies.

the total number of pennies is found by multiplying the number of days by the number of pennies per day:

$$ \sum_{i=1}^{30}100 = 30 \cdot 100 = 3000 $$

If you choose option 2:
on day 1 you get 1 penny on day 2 you get 2 pennies on day 3 you get 4 pennies on day 4 you get 8 pennies on day 5 you get 16 pennies ... on day 30 you get 1,073,741,824 pennies

on the $n^{th}$ day you get $2^n$ pennies.

the total number of pennies is observing that the sum of all prior days is one less than the number of pennies received on the current day: $$ \sum_{i=1}^{30}2^n= \left(2^{31} \right)-1 = 2147483648 - 1 = 2147483647 $$

Anyone with greed will choose the bigger number. Simple greed is easy to find, and requires little thought. Unspeaking animals are easily capable of greed - insects are notoriously good at it. Humans are capable of much more.

If you start out with one penny instead of a hundred the greed is easier, but if you change the power for a polynomial it is more complex. Complex can also mean much more valuable.

About "the curse"
The "most important" physics-related mathematical operation is matrix inversion. It drives solutions of systems of partial differential equations, the most common of which are Maxwell's equations (electromagnetics), Navier Stokes equations(fluids), Poisson's equation (diffusive transfer), and variations on Hookes Law (deformable solids). Each of these equations has college courses built around them.

Raw matrix inversion as taught in Linear Algebra, aka Gauss-Jordan method, requires order of $n^3$ operations to complete. Here "n" is not the number of dimensions, but the number of discretized chunks. It abstracts to number of dimensions easily. If it takes 10 chunks to adequately represent the geometry of a 2d object, it takes at least 10^2 to adequately represent a 3d analog, and 10^2^2 to represent a 4d analog. If you are thinking in terms of geometry you might say "there aren't 4 dimensions" but in terms of physical quantities like temperature, concentration, or velocity in a particular direction each require their own "column" and count as a dimension. Taking these equations from 2d to 3d can increase the "n" by several powers.

The curse exists because if it is overcome there is a pot of golden value at the end of the rainbow. It isn't easy - great minds have engaged the problem vigorously.

link:

• https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Answer 12

Think about cookie attributes (i.e. features, i.e. dimensions) and assume you want to find the one best cookie attributes combination.

With increasing features (dimensions) randomly picking the right becomes improbable. Put in another way: randomly picking a small interval on a line (1D) is easier than picking a small area in (2D) which is easier than picking a small volume in 3D which is easier than picking a small volume and timepoint in 4D (think about meeting your buddy at the play ground but you don't know when). This trend of hardness goes on at higher dimensions.