Machine learning curse of dimensionality explained?

Question

I'm having trouble understanding the curse of dimensionality. Specifically, I came across it while doing the scikit-learn tutorial in python. Can someone please explain the below in a simpler manner? Sorry I have been trying to understand for the longest time and can't understand how they came up with the calculation for number of training examples to achieve an efficient KNN estimator?

Here is the explanation:

For an estimator to be effective, you need the distance between neighboring points to be less than some value d, which depends on the problem. In one dimension, this requires on average n ~ 1/d points. In the context of the above KNN example, if the data is described by just one feature with values ranging from 0 to 1 and with n training observations, then new data will be no further away than 1/n. Therefore, the nearest neighbor decision rule will be efficient as soon as 1/n is small compared to the scale of between-class feature variations.

If the number of features is p, you now require n ~ 1/d^p points. Let’s say that we require 10 points in one dimension: Now 10^p points are required in p dimensions to pave the [0, 1] space. As p becomes large, the number of training points required for a good estimator grows exponentially.

link here

EDIT: also is the tilde (~) supposed to represent approximate in that example? or the python tilde operator?

Answer 1

Translating that paragraph:

Let there be a set of features that describe a data point. Maybe you're looking at the weather. That set of features might include things like temperature, humidity, time of day, etc. So each data point might have one feature (if you're only looking at temperature) or it might have 2 features (if you're looking at temperature and humidity) and so on. What this paragraph is saying is that based on the number of dimensions your data has (how many features it has), the more difficult it is to make an estimator. This is because if you simply have one feature of data, or 1-dimensional data, then when you go to graph this data, you get a line graph, and imagining a line graph between let's say 0-50 degrees C, it only takes 50 random points before each data point is about 1 degree from any other data point. Now let's think about 2 dimensions, talking about humidity and temperature, now it's trickier to find that d such that all the points are within "d" units of each other. Imagine temperature is still between 0-50 but now humidity is also between 0-100%. How many random points does it take to get all the points within 1 or 2 of each other? Now it's 100 * 50 or ~5,000! Now imagine 3 dimensions, etc etc. You start needing way more points to ensure that every point is within d of some other point. To make your life easier try assuming "d" is 1 and see what happens. Hope that helps!

Answer 2

matty-d has already provided a very good answer, but I found another answer that explains this problem equally as well, from a Quora user Kevin Lacker:

Let's say you have a straight line 100 yards long and you dropped a penny somewhere on it. It wouldn't be too hard to find. You walk along the line and it takes two minutes.

Now let's say you have a square 100 yards on each side and you dropped a penny somewhere on it. It would be pretty hard, like searching across two football fields stuck together. It could take days.

Now a cube 100 yards across. That's like searching a 30-story building the size of a football stadium. Ugh.

The difficulty of searching through the space gets a lot harder as you have more dimensions. You might not realize this intuitively when it's just stated in mathematical formulas, since they all have the same "width". That's the curse of dimensionality. It gets to have a name because it is unintuitive, useful, and yet simple.

Answer 3

That example can give some intuition of the problem, but is actually not a rigorous proof at all: that's only an example where many samples are needed to get a "good" space coverage. There could be (and there are indeed, e.g. hexagons in 2D already) much more efficient coverages than a regular grid... (the sophisticated area of low discrepancy sequences is devoted to this) ...and proving that even with such better coverings there is still some curse of dimensionality is quite another issue. Actually in certain function spaces there are even ways to circumvent this apparent problem.