# Why is the curse of dimensionality also called the empty space phenomenon?

The curse of dimensionality refers to the fact that the huge number of correlated features tends to increase the complexity of the treatment that has to be applied to the data set. This is also called the empty space phenomenon. So, does anyone know the relation between those two?

• The curse of dimensionality is about the space getting empty very rapidly as we add new dimensions. For many tasks, such as classification, this add too much freedom and hinders generalization to unseen data. – Vladislavs Dovgalecs May 5 '15 at 23:29
• Why "add freedom"? I thought that space gets empty means it would decrease the freedom. – Joseph Stone May 6 '15 at 12:02
• – Sycorax May 6 '15 at 14:07
• I'd elaborate on xeon's point like this: it's always up to you, the modeler, to determine the complexity of your model. The curse manifests itself by punishing you more harshly for allowing more freedom. As you add complexity to your model, it relies on smaller and smaller regions of your space to make inferences, and the curse means that these smaller regions are going to contain lots of empty space. – Matthew Drury May 6 '15 at 15:32
• @MatthewDrury, 'smaller regions contain lots of empty space' , here, empty space simply means the modeler cannot make any inferences? – Joseph Stone May 6 '15 at 17:31

This comes up, for example, in $k$ nearest neighbors classification. Here we attempt to classify a new point by searching for the $k$ training points closest to it. In small dimensions, which is what people have concrete experience with and hence hence intuition for, these $k$ points all tend to be close by, as the entire space is is rather densely populated with training examples. But in large dimensions, the intuition fails - the $k$ nearest points tend to be quite far away, with much empty space in between.
Here's a short explanation of what that may be getting at. Let's suppose all of our features are binary, this simplifies that math but is not essential. Then there are $2^{100}$ possible combinations of features. Now $\log_2(10^{12}) \approx 40$, that is $10^{12} \approx 2^{40}$, so the proportion of feature combinations "unaccounted for" is approximately $\frac{2^{100}}{2^{40}} = 2^{60}$. Now just observe that $\log_{10}(2^{60}) \approx 18$, so $2^{60} \approx 10^{18}$.