1
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ There are several approach to generalize VC theory to the non-binary setting. None of them has all properties of VC dimension. The definition you state allows proving an analog of the Sauer–Shelah lemma, whereas under your proposed definition, there might not be any meaningful analog of the Sauer-Shelah lemma. $\endgroup$ – Yuval Filmus Nov 23 '19 at 10:12
  • $\begingroup$ I have updated the question. $\endgroup$ – Ben Nov 23 '19 at 11:12
  • $\begingroup$ Cross-posted: stats.stackexchange.com/q/436833/2921. Please do not post the same question on multiple sites. $\endgroup$ – D.W.♦ Nov 28 '19 at 3:51
  • $\begingroup$ I'm voting to close this question because it was cross-posted. $\endgroup$ – D.W.♦ Nov 28 '19 at 3:51