1
$\begingroup$

Recently, I learnt about VC-dimension and how its boundedness assures PAC learnability on uncountable range spaces (let's assume that hypothesis class is the same as the family of concepts we want to learn).

My question is simple: What is/are the geometric intuition(s) behind the concept of VC dimension?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The VC dimension is a complexity measure for a family of boolean functions over some domain $\mathcal{X}$. Families who allow "richer" behavior have a higher VC dimension. Since $\mathcal{X}$ can be arbitrary, there isn't a general geometric interpretation.

However, if you think of $\mathcal{X}$ as $\mathbb{R}^d$, then you can think of binary functions as manifolds, whose boundary is what's separating positive and negative labels. Families with more "complex" boundaries have a high VC dimension, whereas simple manifolds do not, e.g. the dimension of linear separators is $O(d)$, while convex polygons (with unbounded number of edges) have infinite VC dimension. The more complex you allow the boundary to be, the more likely it is that you can find a large set for which you can agree with any labeling, by avoiding the negative labels in a "snake like" shape.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Suppose the range space is $(\mathbb{R}^d, \mathcal{M})$, where $\mathcal{M}$ is a family of manifolds. To each $M \in \mathcal{M}$ you are associating the canonical indicator function $\mathbb{1}_M$, right? $\endgroup$
    – LastIronStar
    Nov 12, 2017 at 10:01
  • $\begingroup$ Not every set is a manifold. Manifolds are mathematical objects with a precise definition, I used the term to trigger geometric intuition, and not in any precise sense. But in essence yes, I'm thinking of a sphere as the function which assigns positive labeling to points inside the sphere, and negative outside of it. $\endgroup$
    – Ariel
    Nov 12, 2017 at 11:35
  • $\begingroup$ yes, it conveys imagery but i still need to process everything you've said. $\endgroup$
    – LastIronStar
    Nov 12, 2017 at 13:13

Your Answer

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

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