How does size of the dataset depend on VC dimension of the hypothesis class?

Question

This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in this video prof. is trying to explain how we should interpret the VC dimension in terms of what it means in layman terms, and why do we need it in practice.

The first part I think I understand, please correct me if I am wrong. VC Dimension dictates the number of effective parameters (i.e. degrees of freedom) that model has. In other words, the number of parameters the model needs in order to cover all possible label combinations for the chosen dataset. Now, the second part is not clear to me. The professor is trying to answer the question:

How does knowing the VC dimension of the hypothesis class affect number of samples we need for training?

Again, I apologize if all of this may be trivial, but I am new to the field and wish to learn as much as I can, so I can implement better and more efficient programs in practice.

Answer 1

From [1] we know that we have the following bound between the test and train error for i.i.d samples:

$$ \mathbb{P}\left(R \leqslant R_{emp} + \sqrt{\frac{d\left(\log{\left(\frac{2m}{d}\right)}+1\right)-\log{\left(\frac{\eta}{4}\right)}}{m}}\right) \geqslant 1-\eta $$

$R$ is the test error, $R_{emp}$ is the training error, $m$ is the size of the training dataset, and $d$ is the hypothesis class's VC dimension. As you can see, the training and test errors have some relations to the dataset's size ($m$) and $d$.

Now, in terms of PAC learnability, we want to find a (lower or upper) bound for $m$ such that the absolute difference between $R$ and $R_{emp}$ will be less than a given $\epsilon$ with a given probability of at least $1-\eta$. Hence, $m$ can be computed in terms of $\epsilon$, $\eta$, and $d$. For example, it can be proved ([2]) to train a binary classifier with $\epsilon$ difference between test and train error with the probability of at least $1-\eta$, we need $O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon} \right)$ i.i.d sample data, i.e., $m = O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon}\right)$. See more example and references here.

Answer 2

Given a hypothesis set $H$, the set of all possible mappings from $X\to Y$ where $X$ is our input space and $Y$ are our binary mappings: $\{-1,1\}$, the growth function, $\Pi_H(m)$, is defined as the maximum number of dichotomies generated by $H$ on $m$ points. Here a dichotomy is the set of $m$ points in $X$ that represent a hypothesis. A hypothesis is just a way we classify our points. Therefore with two labels we know,

$$\Pi_H(m)\leq 2^m$$

This is just counts every possible hypothesis. The VC dimension is then the largest $m$ where $\Pi_H(m)=2^m$.

Consider a 2D perceptron, meaning our $X$ is $\mathbb{R}^2$ and our classifying hyperlane is one-dimensional: a line. The VC dimension will be 3. This is because we can shatter (correctly classify) all dichotomies for $m=3$. We can either have all points be the same colour, or one point be a different colour - which is $2^3=8$ dichotomies. You may ask what if the points we are trying to classify are collinear. This does not matter because we are concerned with resolving the dichotomies themselves, not the location of the points. We just need a set of points (wherever they may be located) that exhibits that dichotomy. In other words, we can pick the points such that they maximize the number of dichotomies we can shatter with one classifying hyperplane (a triangle): the VC dimension is a statement of the capacity of our model.

To make this clear, consider $m=4$. We can represent the truth table of the XOR gate as a dichotomy but this is not resolvable by the perceptron, no matter where we choose the location of the points (not linearly separable). Therefore, we can resolve a maximum of 8 dichotomies, so our VC dimension is 3. In general, the VC dimension of perceptrons is $d+1$ where $d$ is the dimension of $X$ and $d-1$ is the dimension of the classifying hyperplane.

Answer 3

The VC dimension represents the capacity (the same Vapnik, the letter V from VC, calls it the "capacity") of a model (or, in general, hypotheses class), so a model with a higher VC dimension has more capacity (i.e. it can represent more functions) than a model with a lower VC dimension.

The VC dimension is typically used to provide theoretical bounds e.g. on the number of samples required for a model to achieve a certain test error with a given uncertainty or, similarly, to understand the quality of your estimation given a certain dataset.

Just to give you an idea of how the bounds look like, have a look at the theorem on page 6 (of the pdf) of the paper An overview of statistical learning theory (1999) by Vapnik.

Have also a look at this answer, where I provide more info about the VC dimension, in particular, in the context of neural networks.

Answer 4

Since the mathematical details have already been covered by other answers, I will try to provide an intuitive explanation. I will answer this assuming the question meant $model$ and not $learning$ $algorithm$.

One way to think of $\mathcal V \mathcal C$ dimension is that it is an indicator of the number of functions (i.e a set of functions) you can choose from to approximate your classification task over a domain. So a model (here assume neural nets, linear separators, circles, etc whose parameters can be varied) having $\mathcal V \mathcal C$ dimension of $m$ shatters all subsets of the single/multiple set of $m$ points it shatters.

For a learning algorithm, to select a function, which gives accuracy close to the best possible accuracy (on a classification task) from the aforementioned set of functions (shattered by your model, which means it can represent the function with $0$ error) it needs a certain sample size of $m$. For the sake of argument, let's say your set of functions (or the model shatters) contains all the possible mappings from $\mathcal X \rightarrow \mathcal Y$ (assume $\mathcal X$ contains $n$ points i.e finite sized, as a result number of functions possible is $2^n$). One of the function it will shatter is the function which performs the classification, and thus you are interested in finding it.

Any learning algorithm which sees $m$ number of samples can easily pick up the set of functions which agrees on these points. The number of these functions agreeing on these sampled $m$ points but disagreeing on the $n-m$ points is $2^{(n-m)}$. The algorithm has no way of selecting from these shortlisted functions (agreeing on $m$ points) the one function which is the actual classifier, hence it can only guess. Now increase the sample size and the number of functions disagreeing keeps falling and the algorithms probability of success keeps getting better and better until you see all $n$ points when your algorithm can identify the mapping function of the classifier exactly.

The $\mathcal V \mathcal C$ dimension is very similar to the above argument, except it doesn't shatter the entire domain $\mathcal X$ and only a part of it. This limits the models capability to approximate a classification function exactly. So your learning algorithm tries to pick a function from all the functions your model shatter, which is very close to the best possible classification function i.e there will exist a best possible (not exact) function (optimal) in your set of functions which is closest to the classification function and your learning algorithm tries to pick a function which is close to this optimal function. And thus again, as per our previous argument it will need to keep increasing the sample size to reach as close as possible to the optimal function. The exact mathematical bounds can be found in books, but the proofs are quite daunting.