0
$\begingroup$

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.

$\endgroup$
1
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Unfortunately, this does not really answer my question, which is: why did VC define the VC dimension in this way? The answer can probably be found in the paper I am mentioning in the comment under my post above. $\endgroup$ – nbro May 20 at 9:21
  • $\begingroup$ @nbro they defined it in this way because they can obtain some analytical results about it. The definition, you are asking for is more useful, but seems like one has not succeeded to develop some generic theory for it $\endgroup$ – spiridon_the_sun_rotator May 20 at 9:27
  • $\begingroup$ Could you please point me to the relevant part of the mentioned paper or any other resource that discusses this, i.e. the why? I didn't read the mentioned paper, but after having skimmed through it, I noticed that it mentions the growth function. It's probably also a good idea for you to edit your answer so that you focus on answering my question (if you really know the answer). $\endgroup$ – nbro May 20 at 9:30
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks! I had already come across Popper before, but I didn't recall the Popper's dimension. I will try to read that paper by Vapnik that attempts to relate the VC dimension to the Popper's dimension, then I will come back to your answer to give you some feedback. $\endgroup$ – nbro May 21 at 0:07

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.