Reducing multiclass to binary: a unifying approach for margin classifiers

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

552 citations recorded by the source corpus.

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.

Subfields: General Health Professions, Philosophy

View Paper: https://www.semanticscholar.org/paper/47df961a226c16a65f16d9ab204f49bdd755e537

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In General Health Professions

In Philosophy

Citations in the corpus

Chunking with Support Vector Machines (2001, methodology): “For example, Dietterich and Bakiri(Dietterich and Bakiri, 1995) and Allwein(Allwein et al., 2000) introduce a unifying framework for solving the multiclass problem we want to keep consistency with Inside/Start (B/I/O) representation. by reducing them into binary models.”
A comparative study on content-based music genre classification (2003, unknown): “In practice, the choice of reduction method from multi-class to binary is problem-dependent and not a trivial task and it is fair to say that there is probably no method generally outperforms the others [1].”
On the Learnability and Design of Output Codes for Multiclass Problems (2002, methodology): “Several family of codes have been suggested and tested so far, such as, comparing each class against the rest, comparing all pairs of classes [11, 2], random codes [8, 19, 2 ], exhaustive codes [8, 2], and linear error correcting codes [8].”
Automatic Tagging of Arabic Text: From Raw Text to Base Phrase Chunks (2004, methodology): “Thereby, we address them using the same SVM experimental setup which comprises a standard SVM as a multiclass classifier (Allwein et al., 2000).”
Multi-group support vector machines with measurement costs: A biobjective approach (2008, methodology): “Margin can be seen as a value that is zero when 30 there are misclassified objects and otherwise it measures the confidence in the 31 prediction, [1].”
A Comprehensive Survey of Loss Functions in Machine Learning (2020, background): “It should be noted that binary classification can be extended to multi-classification according to one-vs-rest, one-vs-one [26, 27] and so on [28–32].”
Distributional Word Clusters vs. Words for Text Categorization (2003, methodology): “Joachims (1998b) used an SVM classifier for a multi-labeled categorization of Reuters without feature selection, and achieved a break-even point of 86.4%.”
The Boosting Approach to Machine Learning An Overview (2003, methodology): “Schapire and Singer [70] and Allwein, Schapire and Singer [2] give yet another method of combining boosting with errorcorrecting output codes.”
Analysing the classification of imbalanced data-sets with multiple classes: Binarization techniques and ad-hoc approaches (2013, methodology): “In this situation, we can proceed by transforming the original multiple-class problem into binary subsets, which are easier to discriminate, via a class binarization technique [3,13,25].”
Round Robin Classification (2002, methodology): “Allwein et al. (2000) criticize this simple Hamming decoding and suggest the use of loss-based decoding techniques that take into account the conﬁdence of the base learner into its own predictions.”
Nonlinear Models Using Dirichlet Process Mixtures (2007, methodology): “When the number of classes in a classification problem was bigger than two, LSVM and RBF-SVM used the all-vs-all scheme as suggested by Allwein et al. (2000), Fürnkranz (2002), and Hsu and Lin (2002).”
Recent Advances of Large-Scale Linear Classification (2012, methodology): “Studies that broadly discussed various approaches of decomposition include, for example, [48], [49].”
Multicategory Support Vector Machines, Theory, and Application to the Classiﬁcation of Microarray Data and Satellite Radiance Data (2002, background): “Allwein, Schapire, and Singer (2000) proposed a unifying framework to study the solution of multiclass problems obtained by multiple binary classi ers of certain types (see also Crammer and Singer 2000).”
Multi-class Classification without Multi-class Labels (2019, methodology): “Supervised learning and problem reduction: Allwein et al. (2000) presents a unifying framework for multi-class classification by reducing it to multiple binary problems.”
Probability Estimates for Multi-class Classification by Pairwise Coupling (2003, methodology): “Though the main purpose of this section is to compare different probability estimates, here we check the accuracy of another multi-class classification method: exponential lossbased decoding by Allwein et al. (2001). In the pairwise setting, if f̂ij ∈ R is the two-class hypothesis so that f̂ij > 0 (”
Transforming classifier scores into accurate multiclass probability estimates (2002, methodology): “For many domains, however, using more sophisticated code matrices can yield better results, at least in terms of error rate [1].”