2
$\begingroup$

In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, etc.

All proofs first derive a lower bound, and then show an upper bound. However, why not just derive the upper bound since the definition of VC dimension only cares about the "largest" set that can be shattered by hypothesis set $\mathcal{H}$? Since all examples ends up with a lower bound matching the upper bound, is the lower bound just helpful/useful to set a target when trying to show an upper bound?

Reference: From page 41 of this book pdf version https://pdfs.semanticscholar.org/e923/9469aba4bccf3e36d1c27894721e8dbefc44.pdf

$\endgroup$

1 Answer 1

3
$\begingroup$

Lets use the quotes from the book.

To give an upper bound, we need to prove that no set $S$ of cardinality $d + 1$ can be shattered by $H$

By doing this, we are proving that $\text{VCdim}(H) < d+1$, but it does not necessarily mean $\text{VCdim}(H) = d$. For example, we may go for an easier-to-prove failure like sets with $2d+1$ members, and consequently prove $\text{VCdim}(H) < 2d+1$, although we know $\text{VCdim}(H) = d$. Therefore:

To give a lower bound $d$ for $\text{VCdim}(H)$, it suffices to show that a set $S$ of cardinality $d$ can be shattered by $H$

We need to prove the lower bound as well to show that $d \le \text{VCdim}(H) < d+1$, which implies $\text{VCdim}(H) = d$. The last equality means that for each size $1$ to $d$, $H$ can shatter at least one set $S$ with that size.

Note that for the $2d+1$ example, we will fail to prove $2d \le \text{VCdim}(H)$, therefore $\text{VCdim}(H) \neq 2d$, and consequently we must try to prove a smaller (probably harder to prove) upper bound $d+1$.

$\endgroup$
2
  • $\begingroup$ Thank you!! Now I understand I had some misunderstandings of the equations. $\endgroup$ Apr 12, 2019 at 14:04
  • $\begingroup$ @MLstudent My pleasure! Glad I could help. $\endgroup$
    – Esmailian
    Apr 12, 2019 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.