Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $[k]$.

Denote the Natarajan dimension of $H$ by $Ndim(H)$. Hope you can give me an intuitive proof of the following lemma .

$|H|\le |X|^{Ndim(H)}\cdot k^{2Ndim(H)}$

The lemma is in the book "Understanding Machine Learning: from theory to algorithms". You just search keywords "Lemma 29.4".


You can check Natarajan, On learning sets and functions or Haussler and Long, A generalization of Sauer's lemma.

  • $\begingroup$ Thank you. But those proofs are very complex, making me really sleepy. Could you give me an intuitive proof? $\endgroup$
    – Ben
    Nov 23 '19 at 0:16
  • $\begingroup$ If you don’t like proofs, you can just accept the validity of the statement. I don’t expect there to be simpler proofs around of the lemma. $\endgroup$ Nov 23 '19 at 7:45

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.