0
$\begingroup$

Let $X$ be a finite domain and $k$ a number such that $k\le|X|$. Consider the hypothesis class

$$ H:=\{h:|\{x\in X:h(x)=1\}|\le k\text{ or }|\{x\in X:h(x)=0\}|\le k\}. $$

Find the VC dimension of $H$.

$\endgroup$
3
  • $\begingroup$ Is this a binary classification problem, where you're proposing some Boolean hypothesis over $x$ ? Would you like to describe the VC dimension of a simpler $h'$ which assigns 1 to at most $k$ points, and hence 0 to at least $|X| - k$ points? Perhaps an even simpler $h''$ which assigns 1 to exactly $k$ points? $\endgroup$
    – J_H
    Mar 25 at 18:12
  • $\begingroup$ What have you tried? (Do you have any sets that are shattered, hence a lower bound on the dimension; or an argument for an upper bound, by saying that no set of a large size is shattered?) $\endgroup$
    – Ben Reiniger
    Apr 14 at 16:34
  • $\begingroup$ See related questions datascience.stackexchange.com/q/114918/55122 and datascience.stackexchange.com/q/117796/55122 $\endgroup$
    – Ben Reiniger
    Apr 14 at 16:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.