2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.