# How do you prove the Natarajan's Lemma intuitively?

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

• – D.W. Nov 22 '19 at 5:13