Reducing multiclass to binary: A unifying approach for margin classifiers

Erin L. Allwein, Robert E. Schapire, Yoram Singer

Research output: Contribution to journalArticle

1156 Scopus citations

Abstract

We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning algorithm. The proposed framework unifies some of the most popular approaches in which each class is compared against all others, or in which all pairs of classes are compared to each other, or in which output codes with error-correcting properties are used. We propose a general method for combining the classifiers generated on the binary problems, and we prove a general empirical multiclass loss bound given the empirical loss of the individual binary learning algorithms. The scheme and the corresponding bounds apply to many popular classification learning algorithms including support-vector machines, AdaBoost, regression, logistic regression and decision-tree algorithms. We also give a multiclass generalization error analysis for general output codes with AdaBoost as the binary learner. Experimental results with SVM and AdaBoost show that our scheme provides a viable alternative to the most commonly used multiclass algorithms.

Original languageEnglish (US)
Pages (from-to)113-141
Number of pages29
JournalJournal of Machine Learning Research
Volume1
Issue number2
StatePublished - Mar 1 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Reducing multiclass to binary: A unifying approach for margin classifiers'. Together they form a unique fingerprint.

  • Cite this