6
$\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$

3 Answers 3

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$

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.

$\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.

Thinking the same thing in terms of dichotomies, a dichotomy in a set of n points is a way of dividing them into two groups, based on the labels or classifications assigned to each point. It does not relate to the physical arrangement of the points, but solely to their labeling. When a classifier like a perceptron can shatter a set of points, it can find boundaries to separate them according to every possible dichotomy.

In a 2D plane, a linear perceptron can shatter up to three points, regardless of how they are arranged. This means it can create boundaries for all possible label combinations. However, it cannot shatter all possible dichotomies of four points, even if you try to arrange it in the best possible way.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .