5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

"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:

enter image description here

enter image description here

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.