Constraint Classification: A New Approach to Multiclass Classification
Abstract
In this paper, we present a newviewof multiclass classification and introduce the constraint classification problem, a generalization that captures many flavors of multiclass classification. We provide the first optimal, distribution independent bounds for many multiclass learning algorithms, including winner-take-all (WTA). Based on our view, we present a learning algorithm that learns via a single linear classifier in high dimension. In addition to the distribution independent bounds, we provide a simple margin-based analysis improving generalization bounds for linear multiclass support vector machines.
Cite
Text
Har-Peled et al. "Constraint Classification: A New Approach to Multiclass Classification." International Conference on Algorithmic Learning Theory, 2002. doi:10.1007/3-540-36169-3_29Markdown
[Har-Peled et al. "Constraint Classification: A New Approach to Multiclass Classification." International Conference on Algorithmic Learning Theory, 2002.](https://mlanthology.org/alt/2002/harpeled2002alt-constraint/) doi:10.1007/3-540-36169-3_29BibTeX
@inproceedings{harpeled2002alt-constraint,
title = {{Constraint Classification: A New Approach to Multiclass Classification}},
author = {Har-Peled, Sariel and Roth, Dan and Zimak, Dav},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2002},
pages = {365-379},
doi = {10.1007/3-540-36169-3_29},
url = {https://mlanthology.org/alt/2002/harpeled2002alt-constraint/}
}