Properties of VC dimension

Question

I have some difficulties with understanding the notion of VC dimension.

The following is the number of question I want to answer.

Q: If there is a set $|S|=k$ such that hypothesis space $H$ doesn't shatter it, does it mean that $VC(H)<k$?

Yes. According to the definition if H doesn't shatter the set of size k, it doesn't shatter any possible set of size k, however here we have some set $S$, so there are might other set $S'$ of size $k$ which is shatter by $H$.

Q:if $H_1$ and $H_2$ are two hypothesis spaces and $H_1 \subseteq H_2$ then $VC(H_1) \leq VC(H_2)$?

Yes. Every hypothesis that belongs to $H_1$ are in $H_2$ so the shattered subset of $H_2$ is at least as of $H_1$.

Did I answer it correctly?

Answer 1

"According to the definition if H doesn't shatter the set of size k, it doesn't shatter any possible set of size k"

-> No, e.g. say your hypothesis space is all straight lines. Then there exist sets of 3 points that can be shattered using this model (any 3 points that are not collinear can be shattered), but some that cannot (3 collinear points).

$H$ = all straight lines:

Keep in mind that the VC dimension of a hypothesis set $H$ is the most points $H$ can shatter.

Your answer to the second question sounds good.

If you have difficulties with understanding the notion of VC dimension, I strongly recommend CalTech's free machine Learning online course by Yaser Abu-Mostafa Learning from Data (the first 7 lectures).

Answer 2

Well... but then there also exist sets of four points that can be shattered, e.g.

0 0

1 1

or

0 0

1 0

So what's the difference? You may say ok, but you can find a set of four points that cannot be shattered, but also in the case of three points you can do the same (three aligned points like 010).

I would put it like this. The VC dimension of a classification machine is larger or equal to n if at least an arrangement of n points exists that can be classified without errors for any labeling of the n points. It is equal to n if the sentence I have just written holds for every k from 2 to n but not for k = n+1.

Answer 3

I would answer your each question and try to reason your explanation for the same and then give my explanation.

Q1. If there is a set $|S|=k$ such that hypothesis space H doesn't shatter it, does it mean that $VC(H)<k$?

My answer: It only implies that $VC(H) \le k$. If VC-dimension of a concept class is $d$, then one should not be able to shatter any set of size greater than d i.e. $d+1$ and above. Since you could not shatter a set of size $k$, hence VC-dimension should only be $k-1$ or less.

Q2. if $H1$ and $H2$ are two hypothesis spaces and $H1⊆H2$ then $VC(H1)≤VC(H2)$?

Myanswer: Your answer and explaination is absolutely correct for this one.