A Note on Extending Generalization Bounds for Binary Large-Margin Classifiers to Multiple Classes

Ürün Dogan, Tobias Glasmachers, Christian Igel

Abstract

A generic way to extend generalization bounds for binary large-margin classifiers to large-margin multi-category classifiers is presented. The simple proceeding leads to surprisingly tight bounds showing the same \(\tilde{O}(d^2)\) scaling in the number d of classes as state-of-the-art results. The approach is exemplified by extending a textbook bound based on Rademacher complexity, which leads to a multi-class bound depending on the sum of the margin violations of the classifier.
BibTeX
@inproceedings{dogan2012note,
  author = {Ürün Dogan and Tobias Glasmachers and Christian Igel},
  title = {{A Note on Extending Generalization Bounds for Binary Large-Margin Classifiers to Multiple Classes}},
  booktitle = {ECML/PKDD},
  year = {2012},
  doi = {10.1007/978-3-642-33460-3\_13},
}

Loading related content...

Figure