<p>The dimension characterizing multiclass learnability (i.e., the &quot;correct&quot; multiclass analog of VC-dimension) has recently been discovered:
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff:
A Characterization of Multiclass Learnability.
<a href="https://arxiv.org/abs/2203.01550" rel="nofollow noreferrer">https://arxiv.org/abs/2203.01550</a></p>

CC BY-SA 4.0
2022-07-14T21:29:23.797Z
2022-07-14T21:29:23.797Z
Aryeh
<p>Yes - I think you are looking for "multiclass VC dimension," and there are a couple different generalizations of VC dimension to multiclass classification.  A good <a href="http://mercurio.srv.dsi.unimi.it/~cesabian/Pubblicazioni/jcss-95.pdf">paper</a> on this is by Ben-David et al. ('95). In addition to proving learnability results, they give a nice history and references to previous extensions of VC dimension to the multiclass case.  Another perhaps relevant <a href="http://www.phillong.info/publications/sauer.pdf">work</a> by Haussler and Long ('95) generalizes Sauer's lemma to more general versions of VC dimension.</p>

CC BY-SA 2.5
2011-02-26T17:58:42.260Z
2011-02-26T18:10:25.817Z
2011-02-26T18:10:25.817Z
Lev Reyzin
<p>VC dimension is a measure of the complexity of classes of functions $f:X\rightarrow \{0,1\}$ that is closely tied to sample complexity. Fat shattering dimension is a generalization suited to richer ordered domains: i.e. $f:X\rightarrow \mathbb{R}$. Is there a standard generalization of VC-dimension suited to functions with discrete, unordered domains? i.e. $f:X\rightarrow K$ where $K$ is a finite set with no ordering on it.</p>

<reference-request><lg.learning><vc-dimension>
VC Dimension generalized to discrete, non-binary, unordered domains?
Aaron Roth
# VC Dimension generalized to discrete, non-binary, unordered domains?

(Asked by: username_0 on 2011-02-26)

VC dimension is a measure of the complexity of classes of functions $f:X\rightarrow \{0,1\}$ that is closely tied to sample complexity. Fat shattering dimension is a generalization suited to richer ordered domains: i.e. $f:X\rightarrow \mathbb{R}$. Is there a standard generalization of VC-dimension suited to functions with discrete, unordered domains? i.e. $f:X\rightarrow K$ where $K$ is a finite set with no ordering on it.

**Tags:** reference-request, lg.learning, vc-dimension


---

## 2 answers

### Answer by username_2 on 2011-02-26. Score: 10 | Accepted answer

Yes - I think you are looking for "multiclass VC dimension," and there are a couple different generalizations of VC dimension to multiclass classification. A good [paper](http://mercurio.srv.dsi.unimi.it/~cesabian/Pubblicazioni/jcss-95.pdf) on this is by Ben-David et al. ('95). In addition to proving learnability results, they give a nice history and references to previous extensions of VC dimension to the multiclass case. Another perhaps relevant [work](http://www.phillong.info/publications/sauer.pdf) by Haussler and Long ('95) generalizes Sauer's lemma to more general versions of VC dimension.


---

### Answer by username_1 on 2022-07-14. Score: 1

The dimension characterizing multiclass learnability (i.e., the "correct" multiclass analog of VC-dimension) has recently been discovered:
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff:
A Characterization of Multiclass Learnability.
<https://arxiv.org/abs/2203.01550>


---

