Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers

Erin L. AllweinRob SchapireY. Singer

article2000JMLR1,699 citations

Unifies standard multiclass-to-binary reductions under a single framework by introducing margin- and loss-based decoding techniques backed by rigorous error bounds for algorithms like AdaBoost and support vector machines.

Listen

Many real-world machine learning systems, such as optical character recognition, speech processing, and medical diagnosis, require categorizing data into one of several potential classes. While many high-performance algorithms excel at distinguishing between two classes, directly applying them to complex multiclass problems remains challenging. Practitioners routinely decompose multiclass tasks into collections of simpler two-class problems, but existing reduction strategies—such as one-against-all, pairwise comparisons, and error-correcting output codes—have historically lacked a single, cohesive theoretical framework.

The article establishes a unifying mathematical framework that connects all major reduction strategies for margin-based classifiers, which measure prediction confidence alongside binary class assignment. The authors evaluate this framework across theoretical bounds and empirical benchmarks to demonstrate how best to decompose multiclass problems and recombine binary predictions.

The authors conducted formal mathematical analyses alongside empirical testing on synthetic data and thirteen real-world benchmark datasets from the UCI repository. The empirical evaluations compared two primary decoding strategies—traditional Hamming decoding, which uses binary agreement, and loss-based decoding, which incorporates prediction confidence and specific training loss functions—across algorithms including Support Vector Machines and AdaBoost.

The findings demonstrate three key insights. First, loss-based decoding consistently outperforms Hamming decoding, often cutting error rates substantially (for example, reducing error from 50.4% down to 27.8% on the satellite image dataset when using Support Vector Machines). Second, the widely adopted one-against-all reduction is markedly inferior when paired with Support Vector Machines, frequently exhibiting severe performance deficits (such as a 72.9% error rate on yeast classification versus roughly 40% for alternative codes). Third, while error-correcting output codes provide substantial theoretical error tolerance, there is an inherent trade-off: codes with large separation between classes can generate individually harder binary subproblems, meaning no single coding scheme dominates universally across all data domains.

These results indicate that organizational machine learning workflows should avoid defaulting to standard one-against-all reductions or simple sign-based decoding rules. Incorporating prediction confidence through loss-based decoding significantly improves classification reliability and model performance without modifying the underlying binary algorithms, directly lowering misclassification risks and operational failure rates.

Engineering and data science teams should transition existing multiclass classification pipelines to use loss-based decoding rather than simple Hamming matching. For Support Vector Machine models, teams should immediately replace one-against-all schemes with all-pairs, dense random, or sparse output codes. Because overall accuracy depends on the specific dataset, practitioners should benchmark candidate output codes during model validation rather than relying on a one-size-fits-all approach.

The confidence in these conclusions is high, supported by rigorous loss bounds and consistent experimental validations across multiple baseline learners. However, the study's scope is bounded by the computational cost of scaling very large codes (such as complete or all-pairs matrices) to problems with dozens of categories, as well as the implementation constraints of base algorithms on large datasets with missing features.

AT&T Labs—Research Southwest Research Institute The Hebrew University of Jerusalem adaptive boosting coding scheme computational efficiency multiclass learning margin classifiers binary margin-based learning

Allwein et al (2000).pdf

Paper: Solving Multiclass Learning Problems via Error-Correcting Output Codes, Thomas G. Dietterich et al. (1994). This foundational paper introduced error-correcting output codes (ECOC) for decomposing multiclass problems into binary tasks using Hamming decoding, which the source directly analyzes and improves upon with margin- and loss-based decoding.
Paper: Boosting the margin: A new explanation for the effectiveness of voting methods, Robert E. Schapire et al. (1997). It formalizes margin theory and generalization bounds for voting and ensemble methods, providing the conceptual groundwork for the source's margin-based analysis of multiclass reductions.
Paper: Large Margin DAGs for Multiclass Classification, John Platt et al. (1999). It explores directed acyclic graphs for multiclass support vector machine reductions, illustrating key trade-offs in pairwise margin classification that motivate the unified framework.
Paper: A training algorithm for optimal margin classifiers, Bernhard E. Boser et al. (1992). It provides the foundational mathematical formulation for optimal margin classification and support vector optimization upon which margin-based reduction schemes are built.
Paper: Support-vector networks, Corinna Cortes et al. (1995). It introduces standard binary support vector machines, the primary margin-based base classifier evaluated in the source's multiclass reduction framework.

Paper: In Defense of One-Vs-All Classification, Ryan Rifkin et al. (2004). This work directly re-evaluates and critiques the source's conclusions regarding multiclass coding schemes, demonstrating that well-tuned one-versus-all classifiers can rival complex error-correcting codes.
Paper: On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines, Koby Crammer et al. (2002). It formulates direct, single-optimization multiclass kernel machines as an alternative to binary decomposition and output coding schemes.
Paper: Transforming classifier scores into accurate multiclass probability estimates, Bianca Zadrozny et al. (2002). It extends output coding and pairwise reduction architectures by incorporating calibrated probability estimation into multiclass decision making.
Paper: Probability Estimates for Multi-class Classification by Pairwise Coupling, Tingyao Wu et al. (2003). It builds upon pairwise coupling schemes to derive stable, efficient multiclass probability estimates from binary margin classifiers.
Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). It generalizes large-margin multiclass formulation principles to complex, interdependent, and structured output prediction spaces.
Paper: Classifier chains for multi-label classification, Jesse Read et al. (2009). It expands problem-transformation and reduction strategies beyond flat multiclass settings to multi-label classification using classifier chains.

Cover for Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers

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.

Topics

adaptive boosting coding scheme computational efficiency engineering model validation optical character recognition pair-wise comparison speech processing support vector synthetic data

Keywords

multiclass learning margin classifiers binary margin-based learning support vector machines Hamming decoding generalization error

2. Margin-based Learning Algorithms
3. Output Coding for Multiclass Problems
4. Analysis of the Training Error
5. Analysis of Generalization Error for Boosting with Loss-based Decoding
6. Experiments
Acknowledgment
References

Knowls

Knowl 1 — Ternary Coding Matrix Framework for Multiclass Reductions
model/method
A general framework reduces a $k$ -class supervised learning problem, where instances $x \in \mathcal{X}$ have labels $y \in \mathcal{Y} = \{1, \dots, k\}$ , to $\ell$ binary classification problems using a ternary coding matrix

$M \in \{-1, 0, +1\}^{k \times \ell}$

Each column $s \in \{1, \dots, \ell\}$ defines a binary problem over the training set $(x_1, y_1), \dots, (x_m, y_m)$ : examples with $M(y_i, s) = +1$ are treated as positive ( $+1$ ), examples with $M(y_i, s) = -1$ are treated as negative ( $-1$ ), and examples with $M(y_i, s) = 0$ are omitted from training for that column. A binary margin-based learning algorithm $\mathcal{A}$ generates binary hypotheses $f_s : \mathcal{X} \to \mathbb{R}$ for each $s$ , either by being invoked $\ell$ times on the individual sub-problems (the multi-call variant) or by being invoked once on instances augmented with the column index $((x_i, s), M(y_i, s))$ for all non-zero entries (the single-call variant).

This framework unifies standard multiclass reductions:
- One-against-all: $M \in \{-1, +1\}^{k \times k}$ with $+1$ along the diagonal and $-1$ everywhere else.
- All-pairs: $M \in \{-1, 0, +1\}^{k \times \binom{k}{2}}$ , where each column corresponds to an unordered pair $(r_1, r_2)$ , having $+1$ in row $r_1$ , $-1$ in row $r_2$ , and $0$ in all remaining rows.
- Complete binary codes: $M \in \{-1, +1\}^{k \times (2^{k-1}-1)}$ , containing columns for all non-trivial binary partitions of the $k$ classes.
- Dense random codes: $M \in \{-1, +1\}^{k \times \ell}$ , where each entry is chosen uniformly at random from $\{-1, +1\}$ .
- Sparse random codes: $M \in \{-1, 0, +1\}^{k \times \ell}$ , where each entry is independently sampled such that $\operatorname{Pr}[M(r, s) = 0] = 1/2$ , and $\operatorname{Pr}[M(r, s) = +1] = \operatorname{Pr}[M(r, s) = -1] = 1/4$ .
Knowl 2 — Loss-Based Decoding for Margin Classifiers
model/method
Let $f(x) = (f_1(x), \dots, f_\ell(x)) \in \mathbb{R}^\ell$ be the vector of real-valued predictions generated by $\ell$ binary margin classifiers trained using a coding matrix $M \in \{-1, 0, +1\}^{k \times \ell}$ . To classify a new instance $x$ , the predicted label $\hat{y} \in \{1, \dots, k\}$ is chosen to minimize a distance metric between the matrix rows $M(r)$ and $f(x)$ :

$\hat{y} = \arg\min_{r \in \{1, \dots, k\}} d(M(r), f(x))$

Two decoding distance metrics are formulated:
1. Loss-based decoding: Incorporates both the confidence magnitudes of $f_s(x)$ and the specific loss function $L : \mathbb{R} \to [0, \infty)$ minimized during binary training by defining the distance as the total loss under candidate class $r$ (with $L(0)$ assigned when $M(r, s) = 0$ ):
$d_L(M(r), f(x)) = \sum_{s=1}^\ell L(M(r, s) f_s(x))$

$\hat{y} = \arg\min_{r \in \{1, \dots, k\}} d_L(M(r), f(x))$
1. Hamming decoding: Evaluates only the discrete sign agreement between predictions and matrix entries, assigning a penalty of $1/2$ if either $M(r, s) = 0$ or $f_s(x) = 0$ :
$d_H(M(r), f(x)) = \sum_{s=1}^\ell \frac{1 - \operatorname{sign}(M(r, s) f_s(x))}{2}$

$\hat{y} = \arg\min_{r \in \{1, \dots, k\}} d_H(M(r), f(x))$

where $\operatorname{sign}(z) = +1$ if $z > 0$ , $-1$ if $z < 0$ , and $0$ if $z = 0$ .
Knowl 3 — Ternary Distance Metric and Minimum Separation of Coding Matrices
definition
For two row vectors $u, v \in \{-1, 0, +1\}^\ell$ , the generalized Hamming distance $\Delta(u, v)$ is defined as:

$\Delta(u, v) = \sum_{s=1}^\ell \begin{cases} 0 & \text{if } u_s = v_s \land u_s \neq 0 \land v_s \neq 0 \\ 1 & \text{if } u_s \neq v_s \land u_s \neq 0 \land v_s \neq 0 \\ 1/2 & \text{if } u_s = 0 \lor v_s = 0 \end{cases} = \sum_{s=1}^\ell \frac{1 - u_s v_s}{2} = \frac{\ell - u \cdot v}{2}$

The minimum separation $\rho$ between distinct rows of a coding matrix $M \in \{-1, 0, +1\}^{k \times \ell}$ is:

$\rho = \min_{r_1 \neq r_2} \Delta(M(r_1), M(r_2))$

For standard matrices with $k$ classes:
- One-against-all code ( $M \in \{-1, +1\}^{k \times k}$ ): $\rho = 2$ .
- All-pairs code ( $M \in \{-1, 0, +1\}^{k \times \binom{k}{2}}$ ): $\rho = \frac{\binom{k}{2} - 1}{2} + 1 = \frac{k(k-1)}{4} + \frac{1}{2}$ .
- Complete code ( $M \in \{-1, +1\}^{k \times (2^{k-1}-1)}$ ): $\rho = 2^{k-2}$ .
- Random dense or sparse codes of length $\ell$ : the expected distance between any pair of distinct rows is $\mathbb{E}[\Delta(M(r_1), M(r_2))] = \ell / 2$ .
Knowl 4 — Multiclass Empirical Loss Bound for Loss-Based Decoding
theoretical result
Let $(x_1, y_1), \dots, (x_m, y_m)$ be a training set with $y_i \in \mathcal{Y} = \{1, \dots, k\}$ , and let $M \in \{-1, 0, +1\}^{k \times \ell}$ be a coding matrix with minimum row distance $\rho = \min_{r_1 \neq r_2} \Delta(M(r_1), M(r_2))$ . Let $L : \mathbb{R} \to [0, \infty)$ be a margin-based loss function satisfying

$\frac{L(z) + L(-z)}{2} \ge L(0) > 0 \quad \forall z \in \mathbb{R}$

(a property satisfied by convex losses such as exponential $e^{-z}$ , hinge $(1-z)_+$ , logistic $\log(1+e^{-2z})$ , and squared error $(1-z)^2$ ).

Let $\varepsilon$ denote the average binary loss across all $m$ examples and $\ell$ columns:

$\varepsilon = \frac{1}{m\ell} \sum_{i=1}^m \sum_{s=1}^\ell L(M(y_i, s) f_s(x_i))$

Then the multiclass training error under loss-based decoding is bounded by:

$\frac{1}{m} \sum_{i=1}^m [[\hat{y}_i \neq y_i]] \le \frac{\ell \varepsilon}{\rho L(0)}$

When explicitly parameterized by the fraction of ignored pairs $q = \frac{|\{(i, s) : M(y_i, s) = 0\}|}{m\ell}$ and the average binary loss restricted to non-ignored pairs $\bar{\varepsilon} = \frac{1}{m\ell(1-q)} \sum_{(i, s) : M(y_i, s) \neq 0} L(M(y_i, s) f_s(x_i))$ , the training error bound becomes:

$\text{Training Error} \le \frac{\ell}{\rho} \left( q + (1 - q) \frac{\bar{\varepsilon}}{L(0)} \right)$
Knowl 5 — Multiclass Empirical Loss Bound for Hamming Decoding
theoretical result
Let $f_1, \dots, f_\ell$ be binary hypotheses trained on $(x_1, y_1), \dots, (x_m, y_m)$ with $y_i \in \{1, \dots, k\}$ using coding matrix $M \in \{-1, 0, +1\}^{k \times \ell}$ having minimum row distance $\rho = \min_{r_1 \neq r_2} \Delta(M(r_1), M(r_2))$ .
1. In terms of discrete binary classification mistakes, the multiclass training error under Hamming decoding is bounded by:
$\text{Training Error} \le \frac{1}{\rho m} \sum_{i=1}^m \sum_{s=1}^\ell \frac{1 - \operatorname{sign}(M(y_i, s) f_s(x_i))}{2}$
1. For any margin loss $L : \mathbb{R} \to [0, \infty)$ satisfying $L(z) \ge L(0) > 0$ for all $z < 0$ , let $\varepsilon = \frac{1}{m\ell} \sum_{i=1}^m \sum_{s=1}^\ell L(M(y_i, s) f_s(x_i))$ be the average binary loss. The multiclass training error under Hamming decoding satisfies:
$\text{Training Error} \le \frac{2\ell \varepsilon}{\rho L(0)}$

(which is a factor of 2 looser than the bound for loss-based decoding).
1. In terms of the fraction of ignored pairs $q$ and the binary misclassification rate restricted to non-ignored pairs $\bar{\epsilon} = \frac{1}{m\ell(1-q)} \sum_{(i,s) : M(y_i, s) \neq 0} [[M(y_i, s) \neq \operatorname{sign}(f_s(x_i))]]$ , the bound is:
$\text{Training Error} \le \frac{\ell}{\rho} \left( q + 2(1 - q) \bar{\epsilon} \right)$
Knowl 6 — AdaBoost.MO Algorithm with Ternary Output Codes
algorithm
AdaBoost.MO trains a multiclass classifier using a ternary coding matrix $M \in \{-1, 0, +1\}^{k \times \ell}$ and a binary base learner by maintaining a distribution $D_t$ over the $m \times \ell$ training example-column pairs. At each round $t$ , a base hypothesis $h_t : \mathcal{X} \times \{1, \dots, \ell\} \to \{-1, +1\}$ is learned, its weighted binary training error $\epsilon_t$ is computed, hypothesis weight $\alpha_t$ is assigned, and the distribution $D_{t+1}$ is updated multiplicatively. The final prediction combines base hypotheses across rounds via loss-based decoding using the exponential loss function.
Input: Training examples $((x_1, y_1), \dots, (x_m, y_m))$ with $x_i \in \mathcal{X}$ and $y_i \in \mathcal{Y} = \{1, \dots, k\}$
Input: Coding matrix $M \in \{-1, 0, +1\}^{k \times \ell}$
Input: Number of boosting rounds $T$
Input: Base learning algorithm
Initialize distribution $D_1(i, s) = \frac{1}{m\ell}$ for all $i \in \{1, \dots, m\}$ and $s \in \{1, \dots, \ell\}$
for $t = 1$ to $T$ :
    Train base learner on $((x_i, s), M(y_i, s))$ using distribution $D_t$ to get base hypothesis $h_t : \mathcal{X} \times \{1, \dots, \ell\} \to \{-1, +1\}$
    Compute weighted binary error: $\epsilon_t = \sum_{i=1}^m \sum_{s=1}^\ell D_t(i, s) [[ M(y_i, s) \neq h_t(x_i, s) ] ]$
    Set hypothesis weight: $\alpha_t = \frac{1}{2} \ln\left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$
    Compute normalization factor: $Z_t = 2 \sqrt{\epsilon_t (1 - \epsilon_t)}$
    for each $i \in \{1, \dots, m\}$ and $s \in \{1, \dots, \ell\}$ :
        Update distribution: $D_{t+1}(i, s) = \frac{D_t(i, s) \exp(-\alpha_t M(y_i, s) h_t(x_i, s))}{Z_t}$
Output: Multiclass classifier $H(x) = \arg\min_{y \in \mathcal{Y}} \sum_{s=1}^\ell \exp\left( -M(y, s) \sum_{t=1}^T \alpha_t h_t(x, s) \right)$
Knowl 7 — Multiclass Margin for Loss-Based Boosting Classifiers
definition
For a multiclass classifier trained via boosting with coding matrix $M \in \{-1, 0, +1\}^{k \times \ell}$ , let $\eta = \sum_{t=1}^T \alpha_t$ and let $f(x, s) = \frac{1}{\eta} \sum_{t=1}^T \alpha_t h_t(x, s) \in [-1, +1]$ denote the normalized ensemble prediction for column $s$ . The vote assigned to a candidate class $y \in \mathcal{Y}$ on instance $x$ is defined as:

$\nu(f, \eta, x, y) = -\frac{1}{\eta} \ln \left( \frac{1}{\ell} \sum_{s=1}^\ell e^{-\eta M(y, s) f(x, s)} \right)$

Because the transformation is strictly monotonic, the loss-based decoding decision rule is equivalent to $H(x) = \arg\max_{y \in \mathcal{Y}} \nu(f, \eta, x, y)$ , with $\nu(f, \eta, x, y) \in [-1, +1]$ .

The multiclass margin $M_{f, \eta}(x, y)$ of a labeled example $(x, y) \in \mathcal{X} \times \mathcal{Y}$ is defined as half the difference between the vote for the true label and the largest vote for any competing label:

$M_{f, \eta}(x, y) = \frac{1}{2} \left[ \nu(f, \eta, x, y) - \max_{r \neq y} \nu(f, \eta, x, r) \right]$

The margin satisfies $M_{f, \eta}(x, y) \in [-1, +1]$ , and $M_{f, \eta}(x, y) > 0$ if and only if $H(x)$ correctly classifies $(x, y)$ .
Knowl 8 — Generalization Error Bound for AdaBoost with Output Codes
theoretical result
Let $\mathcal{D}$ be a distribution over $\mathcal{X} \times \mathcal{Y}$ , and let $S$ be a sample of $m$ examples drawn i.i.d. from $\mathcal{D}$ . Let the base-classifier space $\mathcal{H}$ of functions mapping $\mathcal{X} \times \{1, \dots, \ell\} \to \{-1, +1\}$ have Vapnik-Chervonenkis (VC) dimension $d$ . Assume $m \ge d\ell \ge 1$ , where $\ell$ is the number of columns in coding matrix $M$ .

Then for any $\delta > 0$ , with probability at least $1 - \delta$ over the random choice of training sample $S$ , every weighted average function $f \in \operatorname{co}(\mathcal{H})$ and every $\eta > 0$ satisfies the following bound simultaneously for all margin thresholds $\theta > 0$ :

$\operatorname{Pr}_{\mathcal{D}}[M_{f, \eta}(x, y) \le 0] \le \operatorname{Pr}_S[M_{f, \eta}(x, y) \le \theta] + \mathcal{O}\left( \frac{1}{\sqrt{m}} \left( \frac{d \log^2(\ell m / d)}{\theta^2} + \log(1/\delta) \right)^{1/2} \right)$

This demonstrates that the multiclass generalization error is upper bounded in terms of the empirical distribution of training margins $M_{f, \eta}(x, y)$ , independently of the number of boosting rounds $T$ .
Knowl 9 — Exponential Margin Growth Bound for AdaBoost.MO
theoretical result
Let $M \in \{-1, +1\}^{k \times \ell}$ be a binary coding matrix without zeros having minimum row distance $\rho = \min_{r_1 \neq r_2} \Delta(M(r_1), M(r_2))$ . Suppose AdaBoost.MO produces base hypotheses with weighted binary errors $\epsilon_1, \dots, \epsilon_T$ on training set $S$ of size $m$ .

For any margin threshold $\theta \ge 0$ , the empirical fraction of training examples with margin at most $\theta$ is bounded by:

$\operatorname{Pr}_S[M_{f, \eta}(x, y) \le \theta] \le \frac{\ell}{\rho} \prod_{t=1}^T \left[ 2 \sqrt{\epsilon_t^{1-\theta} (1 - \epsilon_t)^{1+\theta}} \right]$

If the base learning algorithm generates hypotheses with an edge $\gamma > 0$ such that $\epsilon_t \le 1/2 - \gamma$ for all $t$ , the bound simplifies to:

$\operatorname{Pr}_S[M_{f, \eta}(x, y) \le \theta] \le \frac{\ell}{\rho} \left( \sqrt{(1 - 2\gamma)^{1-\theta} (1 + 2\gamma)^{1+\theta}} \right)^T$

For every $\theta < \gamma$ , the base of the exponent is strictly less than 1, implying that the fraction of training examples with margin below $\theta$ decreases exponentially to zero as the number of boosting rounds $T$ increases.

Knowl 10 — Empirical Error Rates Across Output Codes and Decoding Methods on UCI Benchmarks

data/table

Experiments evaluated five output code families (one-vs-all, complete, all-pairs, dense random, and sparse random) across multiclass UCI repository benchmarks using Support Vector Machines (polynomial kernel of degree 4) and AdaBoost (decision stumps). Decoding methods were tested using Hamming decoding versus loss-based decoding.

	Hamming Decoding					Loss-based Decoding
Problem	One-vs-all	Complete	All-Pairs	Dense	Sparse	One-vs-all	Complete	All-Pairs	Dense	Sparse
dermatology	4.2	3.6	3.1	3.6	2.5	3.3	3.6	3.6	3.9	3.1
satimage	40.9	14.3	50.4	15.0	27.4	40.9	13.9	27.8	14.3	13.3
glass	37.6	34.3	29.5	34.8	32.4	38.6	34.8	31.0	34.8	32.4
ecoli	15.8	14.2	13.9	15.2	14.2	16.1	13.6	13.3	14.8	14.8
pendigits	3.9	2.0	26.2	2.5	2.6	2.5	1.9	3.1	2.1	2.7
yeast	73.9	42.4	40.8	42.5	48.1	72.9	40.5	40.9	39.7	47.2
vowel	60.4	53.0	39.2	53.5	50.2	50.9	51.3	39.0	51.7	47.0
soybean	20.5	–	9.6	9.0	9.0	21.0	–	10.4	8.8	9.0

The test error percentages (evaluated by original split or 10-fold cross-validation) demonstrate two key empirical findings:

Loss-based decoding consistently outperforms or matches Hamming decoding across almost all datasets and codes. In extreme cases such as Satimage with All-Pairs under SVM, loss-based decoding achieves $27.8\%$ error compared to $50.4\%$ for Hamming decoding.
For SVM, the standard one-against-all code is substantially worse than complete, all-pairs, dense, or sparse codes (e.g., Yeast error is $72.9\%$ for one-vs-all vs. $39.7\%$ for dense random).

Coverage note — Omitted the 1-D synthetic threshold simulation details, AdaBoost with randomized predictions table (L1 decoding in Table 2), and the 5x5 pairwise error difference matrix figures (Figures 6 and 7), in favor of the core unifying theory, algorithms, margin-based generalization bounds, and primary benchmark results.

References

1.Bartlett, P. L. (1998). The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2), 525–536.
2.Breiman, L. (1997a). Arcing the edge. Tech. rep. 486, Statistics Department, University of California at Berkeley.
3.Breiman, L. (1997b). Prediction games and arcing classifiers. Tech. rep. 504, Statistics Department, University of California at Berkeley.
4.Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and Regression Trees. Wadsworth & Brooks.
5.Collins, M., Schapire, R. E., & Singer, Y. (2000). Logistic regression, AdaBoost and Bregman distances. In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory.
6.Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297.
7.Crammer, K., & Singer, Y. (2000). On the learnability and design of output codes for multiclass problems. In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory.
8.Csiszár, I., & Tusnády, G. (1984). Information geometry and alternating minimization procedures. Statistics and Decisions, Supplement Issue, 1, 205–237.
9.Della Pietra, S., Della Pietra, V., & Lafferty, J. (1997). Inducing features of random fields. IEEE Transactions Pattern Analysis and Machine Intelligence, 19(4), 1–13.
10.Dietterich, T. G., & Bakiri, G. (1995). Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2, 263–286.
11.Freund, Y. (1999). An adaptive version of the boost by majority algorithm. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pp. 102–113.
12.Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139.
13.Friedman, J., Hastie, T., & Tibshirani, R. (2000). Additive logistic regression: a statistical view of boosting. The Annals of Statistics, 38(2), 337–374.
14.Guruswami, V., & Sahai, A. (1999). Multiclass learning, boosting, and error-correcting codes. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pp. 145–155.
15.Hastie, T., & Tibshirani, R. (1998). Classification by pairwise coupling. The Annals of Statistics, 26(2), 451–471.
16.Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30.
17.Höffgen, K.-U., & Simon, H.-U. (1992). Robust trainability of single neurons. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, pp. 428–439.
18.Kearns, M., & Mansour, Y. (1996). On the boosting ability of top-down decision tree learning algorithms. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing.
19.Lafferty, J. (1999). Additive models, boosting and inference for generalized divergences. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, pp. 125–133.
20.Mason, L., Baxter, J., Bartlett, P., & Frean, M. (1999). Functional gradient techniques for combining hypotheses. In Smola, A. J., Bartlett, P. J., Schölkopf, B., & Schuurmans, D. (Eds.), Advances in Large Margin Classifiers. MIT Press.
21.Merz, C. J., & Murphy, P. M. (1998). UCI repository of machine learning databases. www.ics.uci.edu/~mlearn/MLRepository.html.
22.Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
23.Rätsch, G., Onoda, T., & Müller, K.-R. (to appear). Soft margins for AdaBoost. Machine Learning.
24.Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning internal representations by error propagation. In Rumelhart, D. E., & McClelland, J. L. (Eds.), Parallel Distributed Processing – Explorations in the Microstructure of Cognition, chap. 8, pp. 318–362. MIT Press.
25.Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5), 1651–1686.
26.Schapire, R. E., & Singer, Y. (1999). Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3), 297–336.
27.Schölkopf, B., Smola, A., Williamson, R., & Bartlett, P. (1998). New support vector algorithms. Tech. rep. NC2-TR-1998-053, NeuroColt2.
28.Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer.

Citation

MLA

Allwein, E. L., et al. “Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers”. Journal of Machine Learning Research, vol. 1, no. Dec, 2000, pp. 113–41, https://www.jmlr.org/papers/v1/allwein00a.html.

APA

Allwein, E. L., Schapire, R. E., & Singer, Y. (2000). Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers. Journal of Machine Learning Research, 1(Dec), 113–141. https://www.jmlr.org/papers/v1/allwein00a.html

Chicago

Allwein, E. L., R. E. Schapire, and Y. Singer. 2000. “Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers”. Journal of Machine Learning Research 1 (Dec): 113–41. https://www.jmlr.org/papers/v1/allwein00a.html.

Harvard

Allwein, E.L., Schapire, R.E. and Singer, Y. (2000) “Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers”, Journal of Machine Learning Research, 1(Dec), pp. 113–141. Available at: https://www.jmlr.org/papers/v1/allwein00a.html.

Vancouver

1. Allwein EL, Schapire RE, Singer Y (2000) Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers. Journal of Machine Learning Research 1:113–141

BibTeX

@article{allwein2000reducing,
  title = {Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers},
  author = {Allwein, Erin L. and Schapire, Robert E. and Singer, Yoram},
  year = {2000},
  journal = {Journal of Machine Learning Research},
  volume = {1},
  number = {Dec},
  pages = {113-141},
  url = {https://www.jmlr.org/papers/v1/allwein00a.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Ternary Coding Matrix Framework for Multiclass Reductions

Knowl 2 — Loss-Based Decoding for Margin Classifiers

Knowl 3 — Ternary Distance Metric and Minimum Separation of Coding Matrices

Knowl 4 — Multiclass Empirical Loss Bound for Loss-Based Decoding

Knowl 5 — Multiclass Empirical Loss Bound for Hamming Decoding

Knowl 6 — AdaBoost.MO Algorithm with Ternary Output Codes

Knowl 7 — Multiclass Margin for Loss-Based Boosting Classifiers

Knowl 8 — Generalization Error Bound for AdaBoost with Output Codes

Knowl 9 — Exponential Margin Growth Bound for AdaBoost.MO

Knowl 10 — Empirical Error Rates Across Output Codes and Decoding Methods on UCI Benchmarks

References

Citation

BibTeX

Access the Paper