Why was the VC dimension not defined for all configurations of $d$ points?

Question

Let's start with a typical definition of the VC dimension (as described in this book)

Definition $3.10$ (VC-dimension) The $V C$ -dimension of a hypothesis set $\mathcal{H}$ is the size of the largest set that can be shattered by $\mathcal{H}$ : $$ \operatorname{VCdim}(\mathcal{H})= \max \left\{m: \Pi_{\mathcal{H}}(m)=2^{m}\right\} $$

So, if there exists some set of size $d$ that $\mathcal{H}$ can shatter and it cannot shatter any set of size $d+1$, then the $\operatorname{VCdim}(\mathcal{H}) = d$.

Now, my question is: why would we be just interested in the existence of some set of size $d$ and not all sets of size $d$?

For instance, if you consider one of the typical examples that are used to illustrate the concept of the VC dimension, i.e. $\mathcal{H}$ is the set of all rectangles, then we can show that $\operatorname{VCdim}(\mathcal{H}) = d = 4$, given that there's a configuration of $d=4$ points that, for all possible labellings of those points, there's a hypothesis in $\mathcal{H}$ that correctly classifies those points. However, we can also easily show that, if the 4 points are collinear, there's some labelling of them (i.e. the 1st and 3rd are of colour $A$, while the 2nd and 4th are of colour $B \neq A$) that a rectangle cannot classify correctly.

So, the class of all rectangles can shatter some sets of points, but not all, so we would need another class of hypotheses to classify all sets of four points correctly. The VC dimension does not seem to provide any intuition on which set of classes would do the trick.

So, do you know why the VC dimension wasn't defined for all configurations of $d$ points? Was this just a need of Vapnik and Chervonenkis for the work they were developing (VC theory), or could have they defined it differently? So, if you know the rationale behind this specific definition, feel free to provide an answer. References to relevant work by Vapnik and Chervonenkis are also appreciated.

Answer 1

The measure that you are talking about actually has a name. It is called the "Popper dimension" -- it was introduced by Karl Popper in his "Logic of scientific discovery".

Popper's idea of falsifiability was, as Vladimir Vapnik himself admits, the inspiration behind their work on the VC dimension. The VC dimension of the hypothesis set $\mathcal{H}$ measures the "complexity" of the set by looking at how easy would it be to falsify it. The hypothesis sets with higher VC dimension should be harder to falsify. With limiting case of infinite VC dimension which is unfalsifiable for almost any data.

VC dimension and Popper dimension are different in exactly the way you are describing. This quote from the philosophy paper that Vapnik co-authored states it rather succinctly:

The VC-dimension is the largest number of points one can shatter, the Popper dimension is one less than the smallest number of points one can not shatter.

This paper goes on trying to reconcile the two definitions but I didn't find their exposition satisfactory (or even meaningful). I've found much more harsh take on this is in the "Learning from data" book (second edition, Section 4.7) :

Now we can contrast the VC dimension and Popper’s dimension, and conclude that Popper’s definition is not meaningful, as it does not lead to any useful conditions for generalization. In fact, for linear estimators the Popper’s dimension is at most 2, regardless of the problem dimensionality, as a set of hyperplanes cannot shatter three collinear points.

Which looks fair to me.

Answer 2

I would say, that meaning of VC dimension is at least a possibility to implement any function on the given number of points for some case, not an express any function on $n$ points.

Yes, you are right, that this definition, unfortunately, is not very useful in practice.

Say, family of functions $\text{sign}(\sin(ax))$ has infinite $\text{VC}$ dimension. There exists an infinite sequence $x_n$, such that by tuning the parameter $a$ one can implement any logical function $0 1 0 \ldots 1$ on these points. However, this doesn't make this class of functions an outstanding ML algorithm.