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.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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
