How would you intuitively but rigorously explain what the VC dimension is?

Question

The VC dimension is a very important concept in computational/statistical learning theory. However, the first time you read its definition, you may not immediately understand what it really represents or means, as it involves other concepts, such as shattering, hypothesis class, learning and sets. For example, let's take a look at the definition given by Shai Shalev-Shwartz and Shai Ben-David (p. 70)

DEFINITION $6.5$ (VC-dimension) The VC-dimension of a hypothesis class $\mathcal{H}$, denoted $\operatorname{VCdim}(\mathcal{H})$, is the maximal size of a set $C \subset \mathcal{X}$ that can be shattered by $\mathcal{H}$. If $\mathcal{H}$ can shatter sets of arbitrarily large size we say that $\mathcal{H}$ has infinite VC-dimension.

Without knowing what a hypothesis class is, or what the specific $C$, $X$ and $H$ in this definition are, it's difficult to understand this definition. Even if you are familiar with what a hypothesis class is (i.e. a set of sets, i.e. our set of functions/hypotheses/models, e.g. the set of all possible neural networks with a specific topology) and you know that $C$ and $X$ are sets of input points, it should still not be clear what the VC dimesion really is or represents.

So, how would you intuitively and rigorously explain the exact definition of the VC dimension?

Note that I am not asking for answers like

The VC dimension represents the complexity (or expressive power, richness, or flexibility) of your model/hypothesis class.

Of course, this is easy to memorize, but it's quite vague. So, I am not looking for vague/general answers. I am looking for answers that rigorously but intuitively describe the mathematical definition of the VC dimension. For example, you could provide an illustration that shows what the VC dimension is, and, in your example (e.g. the XOR problem cannot be solved by a set of lines), you can describe what $H$, $C$, and $X$ are, and how they relate to the typical concepts you will find an introductory course to machine learning, but you should not forget to describe the concept of shattering. If you have other ideas of how to illustrate this concept memnomically, feel free to provide an answer.

Answer 1

Trying to explain the idea of VC to some of my colleagues I've discovered quite an intuitive way of laying out the basic idea. Without going through lots of math and notation as I've done in my other answer.

Imagine a following game between two players $\alpha$ and $\beta$ :

1. First, player $\alpha$ plots $d=4$ points on a piece of paper. She may place the points however she likes.
2. Next, player $\beta$ marks several of the drawn points.
3. Finally, player $\alpha$ should draw a circle such that all the marked points are inside the circle, and all the unmarked points - outside. (Points on the boundary considered "inside".)

The player $\alpha$ wins if she can draw such a circle at step #3. The player $\beta$ wins if making such circle is impossible.

If you try to analyze this game then you'll notice that the player $\beta$ has a winning strategy. For any $d=4$ points on a plane, there is always a subset such that player $\alpha$ is unable to draw a required circle. ( I don't want to go into the detailed proof of the strategy - it is straightforward, but cumbersome - I've sketched it my other answer). If we now change the number of points to $d=3$ then the game suddenly becomes winnable by player $\alpha$ - for three points that are not on the same line any subset can be separated by a circle.

The largest number $d$ at which the game is winnable by player $\alpha$ is called the VC dimension of our classification set. So, in the case of 2D discs (insides of a circle) the VC dimension is 3. If one changes the rules to use rectangles instead of circles, then the maximum number of points winnable by $\alpha$ would be 4 - thus, the VC dimension of rectangular classification sets is 4.

Restoring our the mathematical notation, we denote $\mathcal{X} = \mathbb{R}^2$ our two-dimensional plane. $C$ is the subset of cardinality $|C| = d$ that the player $\alpha$ selects. And $\mathcal{H}$ is a class (a "set-of-sets") of the subsets of $\mathcal{X}$ that one should use as a classification boundary. Formally, the statement that the game above is winnable by $\alpha$ can be written as:

$$ \exists\;C\subset\mathcal{X}.|C|=d \Rightarrow\forall\; A\subset C\; \exists\; B\in\mathcal{H}\;. A = B\,\cap\,A $$

The maximal $d$ at which this statement is true would be the VC dimension. (I actually worked backwards from noticing the alternating quantifiers $\exists\,\forall\,\exists$ in the VC definition - which is typical in game playing, so I worked back from the definition to make the game above.)

Answer 2

Shattered set. First we need a concept of a shattered set. I'll work from a shattered set example in Wikipedia adjusting it to your notation.

The statement that $\mathcal{H}$ shatters $C$ means that for every subset $A \subset C$ there is a set $B\in\mathcal{H}$ such that $B$ "separates" $A$ from $C \backslash A$. Writing this formally:

$$\text{shatters}(\mathcal{H},C) = \forall A \subset C\; \exists B\in\mathcal{H}\;.\;A = B\,\cap A $$

As an example consider the set $C$ of four points on $\mathcal{X} = \mathbb{R}^2$:

$$C = \left\{(0,0); (0,1); (1,0); (1,1)\right\}$$

And the classification class $\mathcal{H}$ being all possible 2D discs on $\mathcal{X} =\mathbb{R}^2$. (Notice that people use the world "class" here, because we are dealing with "set-of-sets" stuff and that might get tricky). Note that a disk can be represented as the set of all points inside the circle.

Now, it turns out that this $\mathcal{H}$ doesn't shatter $C$. The counterexample would be the subset $A$ of "diagonal" points:

$$A = \left\{(0,0); (1,1)\right\} \subset C$$

There is no 2D disk $B\in\mathcal{H}$ (in the context of learning theory, an element/set of the hypothesis class is a hypothesis, which can also be viewed as a function) that satisfies $A = B\,\cap A$. Intuitively, this means that you cannot use a 2D disk to classify your pair of points $A$ from the rest of the set $C$.

The VC dimension of $\mathcal{H}$ is the maximal cardinality $d$ of the set $C$ that it can shatter. For $d=3$, we can provide tree points $C'$ for which we can easily find all discs that cover all eight possible subsets of $C'$:

$$C' = \left\{(0,0); (0,1); (1,0)\right\}$$

Above we've shown that for a particular set $C$ of $d=4$ points $\text{shatters}(\mathcal{H}, C)$ is false. But we need to prove that it is false for all 4-point sets. To prove this, we consider a convex hull of an arbitrary set of four points $C = \left\{a;b;c;d\right\}$. In general position, the convex hull is either a triangle or a quad:

In the case of a triangle, we choose the outermost three points as a counterexample set $A$. So, with this (labeling) configuration, you cannot find a disk that covers (i.e. classifies) the outermost three points correctly while excluding the point inside the triangle. In the case of a quad, we choose the pair on the longest diagonal. If any three points lay on a single line, then we choose the pair of outermost points.

This sketches a proof that no $d=4$ point set can be shattered by $\mathcal{H}$, but we've shown that there is a $d=3$ set $C'$ that can be. Concluding that $VCdim(\mathcal{H}) = 3$

Another example is considered on the next page (pg. 71) of the book you've referenced. It again considers 2D plane $\mathcal{X} =\mathbb{R}^2$ and the classification class $\mathcal{H}$ is all possible axis-aligned rectangles. Authors show a configuration $C$ of four points that can be shattered by $\mathcal{H}$ on the left of figure 6.1. And then provide a proof that no $d=5$ points can be shattered by axis-aligned rectangles. Concluding that VC dimension of their $\mathcal{H}$ is four.

Hope these examples help. (BTW, note that, it seems that Deep Learning has quite bad VC dimension but it still works somehow - which is rather puzzling).

Answer 3

This may be lacking some rigour, but this is how I have explained it in the past:

The VC Dimension is the maximum number of inputs such that for any subset of these inputs, it is possible for the model to classify the subset as true and the rest as false.

I am aware that this definition still uses the term subset, but in my experience even people who are not familiar with set theory understand the concept of a subset.

The part about this that tends to confuse most people is the notion of a subset unable to be induced by a model. This can be nicely illustrated by picking a really simply hypothesis, such as a closed interval, and showing how it cannot express non-contiguous positive inputs, or using a linear classifier and showing how it cannot express XOR.