<p>VC-dimension has multiple multiclass extensions:
pseudo dimension, Natarajan dimension, graph dimension.
See here for example:
<a href="http://math.huji.ac.il/~amitd/multiclass.pdf" rel="nofollow">http://math.huji.ac.il/~amitd/multiclass.pdf</a>
<a href="http://jmlr.org/papers/volume8/guermeur07a/guermeur07a.pdf" rel="nofollow">http://jmlr.org/papers/volume8/guermeur07a/guermeur07a.pdf</a></p>

<p>There are also extensions to continuous-valued functions (fat-shattering dimension):
<a href="http://users.cecs.anu.edu.au/~williams/papers/P53.pdf" rel="nofollow">http://users.cecs.anu.edu.au/~williams/papers/P53.pdf</a></p>

CC BY-SA 3.0
2014-12-01T09:17:34.700Z
2014-12-01T09:17:34.700Z
Aryeh
<p>So far, I've only encountered the VC-dim for binary classifiers. I'm interested to learn how this notion can be extended to the multi-class case. Are there expressions that provide bounds on the out-of-sample error based on the VC-dim for multi-category classifiers? The learning machines I am interested in are: SVMs, Neural Networks, AdaBoost and k-Nearest neighbors. Thanks.</p>

<machine-learning><vc-dimension><svm>
Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?
srx
# Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?

(Asked by: username_0 on 2014-11-30)

So far, I've only encountered the VC-dim for binary classifiers. I'm interested to learn how this notion can be extended to the multi-class case. Are there expressions that provide bounds on the out-of-sample error based on the VC-dim for multi-category classifiers? The learning machines I am interested in are: SVMs, Neural Networks, AdaBoost and k-Nearest neighbors. Thanks.

**Tags:** machine-learning, vc-dimension, svm

---

## 1 answers

### Answer by username_1 on 2014-12-01. Score: 4 | Accepted answer

VC-dimension has multiple multiclass extensions:
pseudo dimension, Natarajan dimension, graph dimension.
See here for example:
<http://math.huji.ac.il/~amitd/multiclass.pdf>
<http://jmlr.org/papers/volume8/guermeur07a/guermeur07a.pdf>

There are also extensions to continuous-valued functions (fat-shattering dimension):
<http://users.cecs.anu.edu.au/~williams/papers/P53.pdf>


---

