I have the following homework.

We proved Sauer's lemma by proving that for every class $H$ of finite VC-dimension $d$, and every subset $A$ of the domain,

$$ \left|\mathcal{H}_{A}\right| \leq |\{B \subseteq A: \mathcal{H} \text { shatters } B\} | \leq \sum_{i=0}^{d}\left(\begin{array}{c}{|A|} \\ {i}\end{array}\right) $$

Show that there are cases in which the previous two inequalities are strict (namely, the $\leq$ can be replaced by $<$) and cases in which they can be replaced by equalities. Demonstrate all four combinations of $=$ and $<$.

How can I solve this problem?


I am not good with math notations so I'll stick to language more.

The first equality holds when all hypotheses shattering a set of certain dimension (whose superset has not been shattered) are non overlapping with other hypotheses shattering similar sets.

Informally let' see with an example what this means. Let's say $\mathcal H = \{h_1, h_2,h_3, h_4, h_5, h_6\}$ and all have unique behaviours on $A$ which implies $|\mathcal H_A| = |\mathcal H|$. Now if $\{h_1, h_2,h_3, h_4\}$ shatters a subset $B_1$ of size $2$ then it also shatters all subsets of $B_1$ and number of subsets including $B_1$ itself of $B_1$ is $2^{|B_1|} = 4$ (in this case). Similarly, $\{h_5 h_6\}$ must shatter another subset $B_2$ with size $=1$ and using similar argument as before we get subsets $=2$. Which shows $2+4=6$ (i.e $B_1$ and $B_2$ and all its subsets form the RHS of the equation whose total number is $6$).

NOTE: This will also hold true for hypothesis having same behaviour on subset $A$ i.e if another hypothesis $h_7$ exist which give same output on $A$ as $h_6$. There will be no effect since the former derivation is based on $\mathcal H_A$ and not $\mathcal H$

The case during which $|\mathcal H_A| < |\{B \subseteq A: \mathcal{H} \text { shatters } B\} |$ , is when we have overlapping hypothesis i.e if certain hypothesis exists which helps in shattering $2$ different subsets none of which is subset of each other. Which means now if $\{h_1, h_2,h_3, h_4\}$ shatters some $B_1$ and $\{h_4, h_5\}$ with the overlap of $h_4$ shatters another hypothesis then this is the case $<$ will hold.

Now coming to the second part of the equation, we can see equality will hold when the hypothesis shatters all possible subsets of size $\leq d$. If we define a hypothesis as a set of points where the values is $1$ and $0$ otherwise, then we can verify this. Clearly, if $\mathcal H$ shatters all sets of size $\leq d$ then we can pick any set of size $i \leq d$, and total number of such sets will be $\sum_{i=0}^d \begin{array}{c}{|A|} \\ {i}\end{array}$. In all other cases $<$ will hold.

NOTE: A hypothesis class having VC dimension $d$ does not necessarily shatter all sets of size less $\leq d$ and hence the inequality. Check tis answer.

You can now play with the different scenarios to get $4$ cases as required, and as can be clearly seen the assumptions for equality in both the part of the equations are independent of each other. One deals with overlapping behaviour, while other deals with shattering of subsets $\leq d$. But note only under a certain condition will the equality hold on both sides, namely the hypothesis class shatters all possible subsets of size $d$ non overlappingly.

Sidenote: The first part of the equation can probably be proven by formal number theory, but I am not sure how.


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.