TY - JOUR
T1 - Constraint classification
T2 - A new approach to multiclass classification
AU - Har-Peled, Sariel
AU - Roth, Dan
AU - Zimak, Dav
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84869128840&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84869128840&partnerID=8YFLogxK
U2 - 10.1007/3-540-36169-3_29
DO - 10.1007/3-540-36169-3_29
M3 - Article
AN - SCOPUS:84869128840
VL - 2533
SP - 365
EP - 379
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SN - 0302-9743
ER -