0
$\begingroup$

Let $H$ be a family of classifiers such that $H=\{ h_{a,b} : a,b\in \mathbb{R}\}$ where $h_{a,b}(x,y)=1$ iff $x\geq a$ and $y\geq b$.

I've proved that for $C=\{m=(x,y)\}$, $H$ shatters $C$.

However, when I try to choose $$C=\{m_1=(x_1,y_1), m_2=(x_2,y_2)\}$$ such that (w.l.o.g) $x_1<x_2$ and $y_1<y_2$, there is no classifier $h\in H$ such that $h(m_1)=1$ and $h(m_2)=0$.

Does this mean the VCdim of $H$ is 1? or is there a way to configure some $h\in H$ such that $h(m_1)=1$ and $h(m_2)=0$?

$\endgroup$

1 Answer 1

0
$\begingroup$

You cannot assume w.l.o.g that $x_1<x_2$ and $y_1<y_2$. But you also don't need generality: you only need to find one set of 2 points that $H$ shatters to show that the VC dimension is at least 2.

$\endgroup$
6
  • $\begingroup$ Are you certain? the definition of shatters states that $H$ shatters $C$ if $|H_C|=2^{|C|}$ (contains all possible combinations). regarding what I'm trying to show, simply put that if we take 2 points in 2D $m_1 , m_2$ where $d(m_1) < d(m_2)$ ($m_1$ is closer to $(0,0)$ than $m_2$), there's no $h\in H$ thats able to categorize $h(m_1)=1$ and $h(m_2)=0$, doesnt this mean that $VCdim(H)=1$? $\endgroup$
    – Aishgadol
    Commented Mar 1 at 22:56
  • $\begingroup$ Yes. My answer doesn't yet try to show that any set is (or isn't) shattered; that requires showing that every labeling can be realized, but VC dimension just requires one set of the size that is shattered. // Try {(0,1),(1,0)}; I claim that this set of size 2 is shattered (and proving that takes four cases). $\endgroup$
    – Ben Reiniger
    Commented Mar 2 at 1:22
  • $\begingroup$ I see your point, than to show that $VCdim(H)=d$ I must show some group $C$ of points s.t. $|C|=d$ that $H$ shatters, but what about the $|C|=d+1$ part? must I show that for any $C$ of size $d+1$, $H$ doesnt shatter $C$? $\endgroup$
    – Aishgadol
    Commented Mar 2 at 12:05
  • $\begingroup$ @Aishgadol yes, that's it $\endgroup$
    – Ben Reiniger
    Commented Mar 2 at 13:12
  • $\begingroup$ I'm quite uncertain on how to prove that the $H$ cannot shatter $|C|=3$, I'm required to choose 3 arbitrary points, Yet i'm unsure on how to position them in order to show that theres not $h\in H$ which gives the correct assignment, care to direct me in this? $\endgroup$
    – Aishgadol
    Commented Mar 2 at 13:42

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.