I'm learning machine learning. VC dimension is a good way to measure the complexity of hypothesis class for binary classifier and has a very good intuitive explanation from shattering.
When we discuss multi-class problems, we will use Natarajan dimension.
I know that both dimensions are based on the "shattering" concept.
When we discuss VC-dimension, shattering means $H$ have all the behaviors on a set of size less than $VCdim(H)$. That is:
Let $C=(c_1,\dots,c_d)$ be a shattered set by $H$. Denote the restriction of $H$ to $C$ by $H_c$. $$H_c = \{(h(c_1),\dots,h(c_d)):h\in H\}$$ Then $$|H_c| = 2^d$$ However, according to the definition of shattering on Page 403 of the book "Understanding Machine Learning: from theory to algorithms"(You can click the link to download the book.), the multiclass version of "shattering" is as follows:
We say a that a set $C\subset X$ is shattered by $H$ if there exist 2 functions $f_0,f_1\colon C\to [k]$ such that
for every $x\in C$, $f_0(x) \ne f_1(x)$.
for every $B\subset C$, there exists a function $h\in H$ such that
$$\forall x\in B, h(x)=f_0(x)\ and\ \forall x\in C \backslash B, h(x) = f_1(x)$$
Here, $H$ does not have all the behaviors on a set of size less than the Natarajan dimension. That is,
$$|H_c| \ne k^d$$ when $k>2$.
How do you understand the definition of the multiclass version of shattering, especially this point?
