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?
-
$\begingroup$ 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. $\endgroup$– Vladislavs DovgalecsMay 5, 2015 at 23:29
-
$\begingroup$ Why "add freedom"? I thought that space gets empty means it would decrease the freedom. $\endgroup$– Joseph StoneMay 6, 2015 at 12:02
-
$\begingroup$ Related: stats.stackexchange.com/questions/99171/… $\endgroup$– Sycorax ♦May 6, 2015 at 14:07
-
$\begingroup$ 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. $\endgroup$– Matthew DruryMay 6, 2015 at 15:32
-
$\begingroup$ @MatthewDrury, 'smaller regions contain lots of empty space' , here, empty space simply means the modeler cannot make any inferences? $\endgroup$– Joseph StoneMay 6, 2015 at 17:31
1 Answer
I don't think the curse of dimensionality has anything to do with correlation, or at least not in my understanding. The curse is the notion that a local neighborhood of a point in a high dimensional space is not really so local - the number of data points it takes to uniformly "fill" a neighborhood of a point with a fixed volume (think a unit cube centered at that point) grows exponentially with the dimension. Conversely, if you have a fixed number of points, and increase the dimension of the space that they reside in, you will very quickly find yourself in the situation where most of your space is empty.
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.
Suppose the dimension of the input space is 100 and we have a huge training set of a trillion (10^{12}) examples, then the examples will cover only a fraction of about 10^{-18} of the input space. Can anyone explain to me why is that?
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}$.
-
$\begingroup$ Suppose the dimension of the input space is 100 and we have a huge training set of a trillion (10^{12}) examples, then the examples will cover only a fraction of about 10^{-18} of the input space. Can anyone explain to me why is that? $\endgroup$ Jun 1, 2015 at 19:10
-
1$\begingroup$ @JosephStone I added an explanation of those figures to my answer. $\endgroup$ Jun 1, 2015 at 19:35