# What is an 'input space' and why does the fraction of the input space covered by the training set matter?

In this paper giving an overview of machine learning, the author writes:

Generalizing correctly becomes exponentially harder as the dimensionality (number of features) of the examples grows, because a fixed-size training set covers a dwindling fraction of the input space. Even with a moderate dimension of $100$ and a huge training set of a trillion examples, the latter covers only a fraction of about $10^{-18}$ of the input space. This is what makes machine learning both necessary and hard.

I also don't understand what he means by the input space in this context. I know he's referring to a vector space. I think he might be referring to a vector space which somehow represents all of the parameters. But I don't understand how this relates to the training set examples, and where he's getting the number $10^{18}$ from $100$ features and 1 trillion training examples - is there some way of calculating this, or is it some kind of estimate somehow?

I have the impression that the fraction of the input space covered by the training set relates to the idea that one cannot solve a system of equation with more columns than rows, and I can vaguely see how in machine learning there could generally be issues if one just didn't have many columns compared to rows. But I'm not sure, and I wish I understood why this mattered but I don't even know where to look to find this information.

References

Domingos, P. (2012). A few useful things to know about machine learning. Communications of the ACM, 55(10), 78-87.

• Welcome to our site - I have added some Latex formatting for the math. It's also a good idea to give a full reference to any paper you are citing because if you just include a link, this is vulnerable to "linkrot" if the location changes or the document is taken offline. I've added the reference in for you. – Silverfish Jul 29 '16 at 21:27
• Btw, it is not $10^{18}$. It is $10^{-18}$. Maybe that is the source of the confusion? Also, I think you need change the quote. The last sentence, "I also think...", is not part of the quote. – roundsquare Jul 29 '16 at 21:58

In this example, he is assuming that each dimension is binary so that means there are $2^{100}$ possible inputs. A trillion examples would cover only $1/10^{18}$ (i.e. $10^{-18}$) of that input space.
As a toy example, if you have two points: $(0, 5)$ and $(10, 15)$ the best you can do to fit them is the line $y = x + 5$. But you can't be confident in that because you have no idea how the function acts between $x=0$ and $x=10$ (much less outside this space). This example might seem silly and obvious, but what is talking about is essentially a generalization of this. But the problem is even worse than that because the amount of data you need grows exponentially with the number of dimensions. This is the curse of dimensionality.