89
$\begingroup$

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?

$\endgroup$

11 Answers 11

78
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If this explains the right concept (I don't really know if it does), then I like this answer because I'm pretty sure a child could understand it. $\endgroup$ – Almo Aug 28 '15 at 13:35
  • 14
    $\begingroup$ I like your answer but I feel like it's half way there. I would like to see an answer that addresses how distances become increasingly less meaningful as the number of dimensions increases. $\endgroup$ – TrynnaDoStat Aug 28 '15 at 15:34
  • 1
    $\begingroup$ @TrynnaDoStat: well I answered the question, it did not ask for distances ? I think that none of the answers posted until now talk about distances? Am i too curious if I ask why you only ask it at me ? $\endgroup$ – user83346 Aug 28 '15 at 15:45
  • 3
    $\begingroup$ @fcoppens Because your answer is the one I like the best =) $\endgroup$ – TrynnaDoStat Aug 28 '15 at 17:32
  • $\begingroup$ So if you have more dimensions then you need also more data, which might not be possible. $\endgroup$ – Anton Andreev Feb 2 '18 at 14:00
53
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ Oh, this is a good one! I would even went into 1D direction... Maybe a caterpillar moving in a tube? $\endgroup$ – Greg Aug 31 '15 at 8:05
  • 2
    $\begingroup$ Good point... So maybe a very thin tree branch, with a caterpillar on it? It somehow approximates one dimension. Naturally birds do hunt them, maybe a crow nearby? $\endgroup$ – Greg Aug 31 '15 at 8:57
  • 1
    $\begingroup$ Oh! The gravity manipulation would not be enough, if the crows learned a tactic (they are very smart!): they hunt in twos, when one is approaching from below and the other from above. They know if the bug uses the superpower, it would weigh the odds in favor of one of those crows. Hmmm.... So, what about a bug with two super-powers: gravity manipulation and time compressing? Wouldn't that count as a freakingly hard to hunt down bug in 5 dimensions? $\endgroup$ – Greg Aug 31 '15 at 9:20
  • 1
    $\begingroup$ Catching 2 dogs running around can be viewed as a hunt in 4d, 10 dogs in 20d, 10 swallows in 30d ... $\endgroup$ – denis Aug 31 '15 at 10:56
  • 1
    $\begingroup$ @Greg, "catching" has really nothing to do with dimension, they're just running around independently (some too independently.) $\endgroup$ – denis Aug 31 '15 at 13:03
19
$\begingroup$

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:

  1. Size of the toy can vary between few centimeters to 1 meter, in step of ten centimeters: 0-10cm, 11-20cm, ..., 91cm-1m
  2. 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!

$\endgroup$
  • $\begingroup$ I like your explanation very much, thank you. I understand the sparsity of the space much better now, but could you "illustrate" the part why is it hard for the child to find which toys are more similar in case of more dimensions? Correct me if I'm wrong, but, I understand that the notion of distance is corrupted in such spaces, so it is harder to determine which toys are more similar. Why is that? $\endgroup$ – Marko Aug 28 '15 at 13:11
  • $\begingroup$ This argument appears to confound size with dimensionality. The division of lengths and weights into ten bins is arbitrary. Although introducing these two new factors adds only two dimensions to the setting, the binning inflates your estimate of the "size" of the "space." Yet, without changing the situation at all, you could have binned size and weight into $10^{100}$ bins and concluded that essentially all of the space is "empty". $\endgroup$ – whuber Aug 28 '15 at 13:52
  • $\begingroup$ @whuber: you're right, to keep it too simple I used the wrong words $\endgroup$ – ndrplz Aug 28 '15 at 14:10
  • $\begingroup$ @whuber: but dimension is often seen as a measure of (some concept of ) "size" $\endgroup$ – kjetil b halvorsen Aug 28 '15 at 17:43
  • $\begingroup$ @Kjetil that is an interesting point that could very well be worth exploring. But wouldn't you think it important to clarify the sense in which a dimension is a "size" and to distinguish it from other meanings of "size" in a statistical setting? $\endgroup$ – whuber Aug 28 '15 at 17:49
13
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ +1, the link is very good indeed! I have edited in a quote and an example image, but if you can in addition provide a brief summary of what is explained there it would be even better. $\endgroup$ – amoeba Jun 17 '16 at 10:45
  • 1
    $\begingroup$ Thanks for the suggestion. I have edited the response accordingly. $\endgroup$ – kostas Jun 17 '16 at 10:55
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 Very clear, thanks. This should be the accepted answer. $\endgroup$ – MiniQuark Nov 27 '16 at 19:33
7
$\begingroup$
  • 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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok, thanks for the explanation. So basically it is harder to "fill up" the whole space, so that is why you need a much larger sample? I need to make my question a bit more specific :) I'll edit it, please check the other part also. $\endgroup$ – Marko Aug 28 '15 at 10:13
  • $\begingroup$ Yes, see my edit - will have to think about clustering $\endgroup$ – Christoph Hanck Aug 28 '15 at 11:01
  • 3
    $\begingroup$ I would like to suggest that not only can you imagine a fourth dimension, you have actually imagined extremely high dimensions. A set of $n$ points in a time series is nothing other than a single vector in $n$ dimensions, after all. If you can find a way to translate your concept of the curse of dimensionality to comparisons of such series, then you will have helped others--perhaps even this hypothetical child--understand it, too. $\endgroup$ – whuber Aug 28 '15 at 17:54
  • $\begingroup$ @whuber Here's where the curse comes into the time series example. Let's say that our time series is a random walk over a certain amount of (discrete) time, and at each stage the walker moves a random (iid ~uniform(-1, 1)) amount. You're keeping track of a a fly on a line, say. Now your reactions/eyesight are only so good, and to keep your eyes on the fly without having to all around the line you need it to move at most 0.5 units in either direction. Of course if you wait long enough, the fly will jump this amount and you'll lose it. But, for any fixed length of time, how many paths (cont) $\endgroup$ – Julien Clancy Apr 26 '16 at 17:59
  • $\begingroup$ will cause you to lose track of the fly? The curse of dimensionality says: pretty much all of them, as you let the time get larger. And you can make your eyesight as finitely good as you want (that is, you can detect motions alllllmost 1 in either direction) and the same thing happens. $\endgroup$ – Julien Clancy Apr 26 '16 at 18:00
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Uh, yes, this is the same as the cookie answer by f coppens, but less creative. But it may help the non-childs to see it worded this way... $\endgroup$ – Elvis Aug 29 '15 at 5:58
0
$\begingroup$

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:

$\endgroup$
  • 1
    $\begingroup$ Your example seems to be more related to showing the difference between polynomial and exponential growth, as opposed to the curse of dimensionality. $\endgroup$ – J. M. is not a statistician Aug 30 '15 at 16:20
  • $\begingroup$ polynomial and exponential growth are the curse. If it was linear then encryption wouldn't work, and fusion in a bottle would be easy to simulate. Here is an enumeration of the "curse" (wikipedia hyperlink) - without which computer math would suddenly become much more amazing than it already is. en.wikipedia.org/wiki/… $\endgroup$ – EngrStudent Aug 30 '15 at 17:12
  • $\begingroup$ It is urban lore that in 2008 discovered a huge breakthrough in matrix inversion that drops order below 2, but it was classified and is used for simulations of nuclear weapons or such. $\endgroup$ – EngrStudent Aug 30 '15 at 17:22
  • 1
    $\begingroup$ I was almost convinced up until "used for simulations of nuclear weapons or such". ;P But seriously, Coppersmith-Winograd seems to still be the best, although with an implied constant that only makes it useful for really large matrices. $\endgroup$ – J. M. is not a statistician Aug 30 '15 at 17:26
  • $\begingroup$ Tangentially related to your answer and previous comment: computing the determinant efficiently is not too hard, but computing the permanent is a different matter. $\endgroup$ – J. M. is not a statistician Aug 30 '15 at 17:28
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good extension :-) $\endgroup$ – user83346 Jun 17 '16 at 10:24

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.