# Curse of Dimensionality - Why does “each variable added result in an exponential decrease in predictive power?”

I read this in this blog. So I'm assuming by variable they mean by adding an extra dimension. How does adding a variable exponentially decrease predictive power? What is predictive power? Is there a metric for it?

• Oddly the writer's lone reference (Finney) is not using the word "dimension" in remotely the same sense as the writer is in that blog post; Finney is talking in essentially the same sense as its use in physics that the writer mentions in passing near the start (indeed, the connection to the physics sense is made clear by Finney in the paper; it's how he introduces it). The writer is using dimension in essentially identical manner to the mathematical sense, it's not clear why it's being claimed to be distinct. It's odd to attempt to claim that its use in statistics is distinct from ... – Glen_b Aug 18 '20 at 1:35
• ... both those senses when Finney (writing about dimension in statistics) uses it in the first, physics-like sense and then the post uses it in what seems to be the same as the mathematical sense – Glen_b Aug 18 '20 at 1:36

After reading the blog, what they mean by predictive power is more general speak for accuracy when predicting some quantity with your model.

Although, this isn't entirely related to some data model with $$d$$ inputs. I think the example of integration will explain the curse of dimensionality sufficiently.

Let's say we're trying to calculate the area under some function, denoted by $$f(x)$$. Where $$x$$ is an input to our function (This would be the variable/dimension discussed on the post), and $$f$$ can be any arbitrary function (this could be the model from the post). A nice example function would be a Gaussian,

$$f(x) = \exp(-x^2)$$

If we wish the find the area under this curve from say -5 to 5, we can discretize our input space $$x$$ into $$N$$=100 points (same as the number of samples from the post) between -5 and 5 in steps of 0.1, and compute the integral with a method like the Trapezoidal rule.

Now, let's add another variable/dimension to our model.

If we have a 2-dimensional Gaussian (defined below) and wish to calculate the integral using the same method above, we first discretize $$x$$ and $$y$$ into $$N$$ = 100 points each and sum up $$\textbf{all pairs}$$ of $$x$$ and $$y$$ which would be $$N$$ = 100$$^2$$ points, or 10,000 points.

$$f(x,y) = \exp(- (x^2 + y^2))$$

This is the same as what it says in the blog post "The predictive space increases exponentially, from 25 cm$$^{2}$$ to 125 cm$$^{3}$$." In our case, it was from 100 to 10,000. If we were to go to a 3-dimensional Gaussian, it would be 1,000,000 points needed which becomes pretty difficult to compute!

In short, adding model inputs to a model increases its input space exponentially which require more samples to adequately sample it!

A nice video which explains this exponential increase in samples can be found here -> https://www.youtube.com/watch?v=OyPcbeiwps8