2
$\begingroup$

In this lecture (minute 42), the professor says that the number of training examples we need to densely cover the space of training vectors grows exponentially with the dimension of the space. So we need $4^2=16$ training data points if we're working on $2D$ space. I'd like to ask why this is true and how is it proved/achieved? The professor was talking before about K-Nearest Neighbors and he was using $L^{1}$ and $L^{2}$ metrics. I don't think these metrics induce a topology that makes a discrete set of points dense in the ambient space.

$\endgroup$
1
  • 2
    $\begingroup$ $N^d=e^{d\ln(N)}$ is exponential in the dimension $d$. Fill a unit cube in dimension $d$ with small cubes of side length/diameter $1/N$. $\endgroup$ Mar 19 at 17:58
2
$\begingroup$

First, let's try to build some intuition for what we mean when we say that we want to "densely cover" a $d$-dimensional space $\mathbb{R}^d$ of real numbers. For simplicity, let's assume that all values in all dimensions are restricted to lie in $[0, 1]$. Even with just a single dimension $d=1$, there are actually already infinitely many different possible values even in such a restricted $[0, 1]$ range.

But generally we don't actually care about literally covering every single possible value. Generally, we expect that points in this $d$-dimensional space that are "close" to each other also "behave" similarly, that there's some level of "continuity". Hence, to get "sufficient" or "good" or "dense" coverage of the space, you can somewhat informally assume that every data point you have occupies some space around it. This is the intuition behind Lutz Lehmann's comment under your question: you can think of every point as being a $d$-dimensional cube occupying some volume of your $d$-dimensional space.

Now, if you have a $d$-dimensional space of size $[0, 1]$ along every dimension, and you have little cubes that occupy a part of that space (for instance, cubes of size $0.1$ in every dimension), you will indeed find that the number of cubes you need to fill up your space scales exponentially in $d$. The basic idea is: if some number of cubes $K$ is sufficient to fill up the $d$-dimensional space, and if you then increase the dimensionality to $d+1$, you'll need $dK$ cubes to fill the new space. When you add a new dimension, the complete previous space becomes essentially just one "slice" of the new space.

For dimensions $d = 1, 2, 3$, this is fairly easy to visualise. If you have $d=1$, your space is really just a line, or a line segment if you constrain the values to lie in $[0, 1]$. If you have a $[0, 1]$ line segment, and you have little cubes of length $0.1$, you'll need just ten of them to fill up the line.

Now imagine that you add the second dimension. Suddenly your line becomes an entire plane, or a $10\times10$ square grid. The $10$ cubes are now only sufficient to fill up a single row, and you'll have to repeat this $10$ times over to fill up the entire $2$D space; you need $10^2 = 100$ cubes.

Now imagine that you add the third dimension. What used to be a plane gets "pulled out" into an entire three-dimensional cube -- a large cube, which will require many little cubes to fill! The plane that we had previously is again just a flat slice in this larger $3$D space, and the entire strategy for filling up a plane will have to be repeated $10$ times over to fill up $10$ such slices of the $3$D space; this now requires $10^3 = 1000$ cubes.

Past $3$ dimensions, the story continues in exactly the same way, but is a bit harder for us humans to visualise.

$\endgroup$
3
  • $\begingroup$ Thank you for the answer. It's much more detailed. So when we say "densely cover the space", it doesn't mean that our points are dense in this space but that they have some space around them and with which we can cover the whole space. $\endgroup$
    – Daviiid
    Mar 19 at 20:06
  • $\begingroup$ @Daviiid Well, points are still points. Mathematically, they don't occupy any space around them. But "densely covered" isn't a very precise definition, it's a bit informal. The basic intuition is that it should "feel like" you "sufficiently" cover most areas of the space, that you don't have any huge subsections of the space that are completely empty without any points in them at all. $\endgroup$
    – Dennis Soemers
    Mar 19 at 20:23
  • $\begingroup$ ♦ yes you're right. Thank you again. $\endgroup$
    – Daviiid
    Mar 19 at 20:57

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.