How do you prove the Natarajan's Lemma intuitively?

Question

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".

Answer 1

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