We proved Sauer's Lemma (2.9.5) by proving, that for every hypothesis class H of finite VC- dimension d, and every subse

[answerhappygod]

We Proved Sauer S Lemma 2 9 5 By Proving That For Every Hypothesis Class H Of Finite Vc Dimension D And Every Subse 1 (69.47 KiB) Viewed 27 times

We proved Sauer's Lemma (2.9.5) by proving, that for every hypothesis class H of finite VC- dimension d, and every subset C = {c₁,, Cm} of X = R", we have: d |Hc|≤|{B C C : H shatters B}| ≤ Σ (™) i=0 Show that there are cases in which these inequalities can be replaced by strict inequalities. Namely, give an example, such that d |Hc| < |{B C C : H shatters B}| < Σ (7) i=0 Hint: Let n ≥ 3 and consider the class H = {sign (w, x) : w€ R¹}.