In Defense of One-Vs-All Classification

Ryan RifkinAldebaro Klautau

article2004JMLR2,079 citations

Demonstrates through rigorous empirical evaluations and theoretical analysis that simple one-vs-all multiclass strategies match the accuracy of far more complex methods when using well-tuned regularized binary classifiers.

Listen

Organizations deploying machine learning must regularly categorize data into three or more distinct classes, a problem known as multiclass classification. Over the past decade, substantial engineering effort and academic research have been directed toward creating sophisticated techniques to replace the simple, traditional "one-versus-all" (OVA) approach—a method that trains one binary classifier per class to distinguish that class from all others. Advocates of newer alternatives, such as error-correcting codes and complex single-machine optimization frameworks, have claimed superior accuracy over OVA. However, these complex architectures introduce significant algorithmic overhead and implementation risk, raising the question of whether the additional engineering cost is truly justified in practice.

This article evaluates whether complex multiclass frameworks actually outperform the simple OVA architecture when underlying binary algorithms are properly regularized and tuned. The authors set out to demonstrate that the primary determinant of multiclass performance is the quality and tuning of the underlying binary learners, not the combination scheme itself, thereby defending OVA as an equally accurate and practical default.

To test this hypothesis, the authors conducted controlled empirical benchmarks and rigorous mathematical analysis. The empirical evaluation examined ten benchmark datasets spanning diverse domains, focusing specifically on datasets where prior studies reported large performance advantages for complex methods. The researchers systematically trained and compared well-tuned binary algorithms—primarily support vector machines (SVMs) and regularized least-squares classification (RLSC) using Gaussian kernels—across five output coding schemes: OVA, all-pairs (all-versus-all), complete, dense random, and sparse random codes. Hyperparameters were tuned via cross-validation without test-set contamination. To assess credibility beyond raw percentage points, the authors employed bootstrap statistical procedures to establish 90% confidence intervals for performance differences and tracked exact prediction agreement between methods.

The findings show that when binary classifiers are properly tuned, the purported accuracy advantages of complex multiclass methods largely disappear. Across nearly all datasets, OVA achieved classification accuracy essentially indistinguishable from all-pairs, dense, sparse, and complete coding schemes, with differences typically contained within narrow confidence intervals encompassing zero. For instance, on standard datasets such as "satimage" and "yeast," where earlier literature claimed error-correcting codes cut error rates by half or more relative to OVA, the well-tuned OVA implementation achieved error rates of 7.80% and 40.30%, matching or slightly exceeding alternative configurations. Furthermore, different multiclass schemes exhibited extremely high prediction agreement (often exceeding 95%), demonstrating that residual classification errors stem from inherently ambiguous data points rather than flaws in the OVA combination logic. Theoretical analysis of RLSC proved that for class-symmetric coding matrices, continuous loss-based decoding produces decision boundaries that are mathematically identical to those of the simple OVA scheme.

These results carry immediate practical implications for systems architecture, technical debt, and resource allocation. They indicate that past claims favoring complex multiclass designs were largely artifacts of poorly tuned or weak base classifiers, whose uncorrelated errors temporarily benefited from error-correcting redundancy. Strong, well-tuned binary classifiers produce highly correlated errors, eliminating the theoretical advantages of elaborate combination schemes. Consequently, engineering teams can achieve state-of-the-art accuracy without taking on the development complexity, debugging overhead, and fragile codebases associated with single-machine multiclass formulations.

For technology leaders and practitioners, the primary recommendation is to adopt the conceptually straightforward OVA framework as the standard baseline for multiclass problems. Development teams should focus engineering time on optimizing binary model hyperparameters (such as kernel and regularization settings) and feature quality rather than implementing complex error-correcting matrices. If computational speed is a primary operational constraint during training, practitioners may consider all-pairs approaches, which train many smaller models on subsets of data and can train faster on specific large-scale workloads. Conversely, where runtime inference latency and memory footprints dominate, OVA remains highly competitive because it requires evaluating fewer classifiers.

The conclusions should be interpreted within specific boundary conditions. The empirical findings reflect standard public benchmark datasets and assume that problem classes are mutually independent rather than organized into natural hierarchies. On small datasets with high class counts and substantial noise (such as the abalone dataset), all-pairs schemes showed modest accuracy advantages, suggesting caution when classifying overlapping or poorly separated distributions. Confidence in the central finding remains high: for well-formed classification tasks with independent classes, properly tuned OVA delivers performance on par with the most complex alternatives available.

Honda Research Institute University of California, San Diego multi-class classification support vector adaptive boosting Classi Data Classi Ers

Rifkin et al (2004).pdf

Paper: On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines, Koby Crammer et al. (2002). Introduces the direct multiclass Support Vector Machine formulation that serves as a primary point of comparison and target of critical re-examination in the defense of one-vs-all methods.
Paper: Solving Multiclass Learning Problems via Error-Correcting Output Codes, Thomas G. Dietterich et al. (1994). Pioneers error-correcting output codes for multiclass learning, which became a leading alternative framework evaluated alongside standard one-vs-all reduction strategies.
Paper: Support-vector networks, Corinna Cortes et al. (1995). Establishes standard binary support vector machines, which provide the foundational regularized base learners tuned and analyzed in the multiclass decomposition study.
Paper: Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms, Thomas G. Dietterich (1998). Provides the methodological and statistical testing standards necessary for rigorous empirical benchmarking of supervised learning algorithms across multiple datasets.
Paper: Choosing Multiple Parameters for Support Vector Machines, OLIVIER CHAPELLE et al. (2002). Demonstrates automated parameter tuning for support vector machines, underpinning the paper's central premise that properly tuned regularized binary classifiers eliminate performance gaps in one-vs-all schemes.

Paper: Statistical Comparisons of Classifiers over Multiple Data Sets, Janez Demšar (2006). Establishes non-parametric statistical testing frameworks that formalize and refine multi-dataset classifier benchmarking comparisons.
Paper: Classifier chains for multi-label classification, J. Read et al. (2009). Extends binary reduction strategies by chaining one-vs-all style binary classifiers to account for label dependencies in multi-label learning.
Paper: Do we need hundreds of classifiers to solve real world classification problems?, Manuel Fernández Delgado et al. (2014). Expands on large-scale empirical benchmarking across hundreds of classifiers to evaluate whether sophisticated learning methods genuinely outperform well-tuned standard baselines.
Paper: An empirical comparison of supervised learning algorithms, R. Caruana et al. (2006). Conducts extensive multi-metric benchmarking and probability calibration across supervised classifiers, following the empirical evaluation rigor championed in multiclass comparisons.
Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). Generalizes large-margin multiclass classification beyond independent binary reductions to complex, structured output spaces using cutting-plane optimization.
Paper: Sharing visual features for multiclass and multiview object detection, Antonio Torralba et al. (2007). Applies multiclass binary decomposition principles to vision tasks while introducing joint feature sharing to improve the efficiency of multiple one-vs-all style detectors.

Cover for In Defense of One-Vs-All Classification

Abstract

We consider the problem of multiclass classification. Our main thesis is that a simple “one-vs-all” scheme is as accurate as any other approach, assuming that the underlying binary classifiers are well-tuned regularized classifiers such as support vector machines. This thesis is interesting in that it disagrees with a large body of recent published work on multiclass classification. We support our position by means of a critical review of the existing literature, a substantial collection of carefully controlled experimental work, and theoretical arguments.

Topics

multi-class classification support vector adaptive boosting svm classification models binary classification problems

Keywords

Classi Data Classi Ers Classi Cation Data Sets Data Set One-Vs-All OVA Binary Classi Ers SVM

1. Introduction
2. Regularized Kernel Classifiers
3. Previous Work
3.1. Single Machine Approaches
3.1.1. Vapnik and Blanz, Weston and Watkins
3.1.2. Lee, Lin and Wahba
3.1.3. Bredensteiner and Bennett
3.1.4. Crammer and Singer
3.1.5. Summary
3.2. Error-Correcting Coding Approaches
3.2.1. Dietterich and Bakiri
3.2.2. Allwein, Schapire and Singer
3.2.3. Crammer and Singer
3.2.4. Fürnkranz
3.2.5. Platt, Cristianini and Shawe-Taylor
3.2.6. Hsu and Lin
3.2.7. Summary
4. Experimental Work
4.1. Experimental Protocol
4.2. Results
5. Multiclass Classification with RLSC: Theoretical Arguments
6. Discussion and Conclusions
Appendix A. A Simple Bootstrap Approach to Comparing Classifiers
Appendix B. Fürnkranz's Experiments Revisited
Appendix C. SVM and RLSC Parameter Settings
References

Knowls

Knowl 1 — Equivalence of Class-Symmetric Zero-Free Output Codes and One-Vs-All under Regularized Least Squares Classification
theoretical result
When Regularized Least Squares Classification (RLSC) is used as the underlying binary learner with square loss $V(f(x), y) = (y - f(x))^2$ , training an error-correcting output code (ECOC) matrix $M \in \{-1, +1\}^{N \times F}$ with no zero entries does not require training new classifiers. Because the RLSC weight vector is a linear function of the label vector, the continuous output of the $i$ -th binary classifier on input $x$ is given by $f_i(x) = \sum_{j=1}^N M_{ji} f^j(x)$ , where $f^j(x)$ is the prediction of the $j$ -th standard One-Vs-All (OVA) classifier.

Using loss-based decoding with the square loss $L(y f(x)) = (1 - y f(x))^2$ , the multiclass prediction for an input $x$ selects the class $r \in \{1, \dots, N\}$ minimizing total loss:

$f(x) = \arg\min_{r \in \{1, \dots, N\}} \sum_{i=1}^F L(M_{ri} f_i(x)) = \arg\min_{r \in \{1, \dots, N\}} \left( -F f^r(x) + \sum_{j \neq r} D_{rj} f^j(x) \right)$

where $D_{rj} \equiv -\sum_{i=1}^F M_{ir} M_{ij}$ .

A coding matrix $M$ is defined as class-symmetric if $D_{rj} = D^*$ is constant for all pairs $r \neq j$ . This condition holds for both the standard OVA matrix and the complete code matrix containing all valid binary column combinations. For any class-symmetric coding matrix where $D^* > -F$ (no duplicate rows):

$f(x) = \arg\min_{r \in \{1, \dots, N\}} \left( -F f^r(x) + D^* \sum_{j \neq r} f^j(x) \right) = \arg\max_{r \in \{1, \dots, N\}} f^r(x)$

Thus, when RLSC is used as the base learner for any class-symmetric zero-free coding scheme, loss-based decoding produces classification decisions identical to the standard One-Vs-All maximum-output decision rule.
Knowl 2 — Asymptotic Bayes Optimality of One-Vs-All Regularized Least Squares Classification
theoretical result
For binary classification with square loss $V(f(x), y) = (y - f(x))^2$ , the asymptotic minimizer of the expected loss functional (as sample size $\ell \to \infty$ and regularization parameter $\lambda \to 0$ ) is:

$f(x) = \frac{(p(x))^{1/2} - (1 - p(x))^{1/2}}{(p(x))^{1/2} + (1 - p(x))^{1/2}}$

where $p(x) = P(y = 1 \mid x)$ is the posterior probability of the positive class.

In an $N$ -class One-Vs-All (OVA) multiclass classification setting using regularized least squares classifiers, each class $i \in \{1, \dots, N\}$ has an asymptotic discrimination function $f_i(x) = R(p_i(x))$ , where $p_i(x) = P(y = i \mid x)$ and:

$R(p) = \frac{p^{1/2} - (1 - p)^{1/2}}{p^{1/2} + (1 - p)^{1/2}}$

The derivative of $R(p)$ with respect to $p$ on $(0, 1)$ is:

$\frac{dR}{dp} = \frac{\left(\frac{1-p}{p}\right)^{1/2} + \left(\frac{p}{1-p}\right)^{1/2}}{\left(p^{1/2} + (1-p)^{1/2}\right)^2} > 0$

Because $R(p)$ is strictly increasing on $[0, 1]$ , $p_i(x) > p_j(x)$ implies $f_i(x) > f_j(x)$ . Consequently, the OVA prediction $\arg\max_{i \in \{1, \dots, N\}} f_i(x)$ chooses $\arg\max_i p_i(x)$ and converges asymptotically to the Bayes-optimal multiclass classifier. Unlike OVA Support Vector Machines with hinge loss—which can produce negative outputs across all classes when $\max_i p_i(x) < 0.5$ —OVA with square loss requires no sum-to-zero constraint or single-machine coupling to guarantee asymptotic Bayes consistency.
Knowl 3 — Bootstrap Confidence Interval Procedure for Comparing Paired Classifiers
algorithm
To evaluate whether the difference in error rates between two classification models $A$ and $B$ evaluated on the same test set of size $\ell$ is statistically significant and to estimate the magnitude of that difference, a non-parametric bootstrap procedure is applied to the paired classification outcomes.
Input: Paired predictions and ground truth for $\ell$ test examples: ${(y_k, \hat{y}_k^A, \hat{y}_k^B)}_{k=1}^\ell$ , confidence level $k \in (0, 100)$ (e.g., $k = 90$ ), number of bootstrap replications $B$ (e.g., $B = 10000$ )
Output: Sample error difference $\Delta$ and $k\%$ bootstrap confidence interval $[q_{\text{low}}, q_{\text{high}}]$
Count occurrences of the four joint outcome events across the test set:
   $n_{CC}$ : count of examples where both $A$ and $B$ are correct
   $n_{II}$ : count of examples where both $A$ and $B$ are incorrect
   $n_{CI}$ : count of examples where $A$ is correct and $B$ is incorrect
   $n_{IC}$ : count of examples where $B$ is correct and $A$ is incorrect
Compute empirical joint probabilities:
   $p_{CC} \leftarrow n_{CC} / \ell$
   $p_{II} \leftarrow n_{II} / \ell$
   $p_{CI} \leftarrow n_{CI} / \ell$
   $p_{IC} \leftarrow n_{IC} / \ell$
Compute observed error rate difference: $\Delta \leftarrow (n_{IC} - n_{CI}) / \ell$
for $b \leftarrow 1$ to $B$ do
  Sample $(m_{CC}, m_{II}, m_{CI}, m_{IC})$ from $\text{Multinomial}(\ell, (p_{CC}, p_{II}, p_{CI}, p_{IC}))$
  Compute replication difference: $\delta_b \leftarrow (m_{IC} - m_{CI}) / \ell$
Sort bootstrap differences $\{\delta_b\}_{b=1}^B$ in ascending order
$q_{\text{low}} \leftarrow \text{percentile}(\{\delta_b\}, (100 - k) / 2)$
$q_{\text{high}} \leftarrow \text{percentile}(\{\delta_b\}, (100 + k) / 2)$
return $\Delta, [q_{\text{low}}, q_{\text{high}}]$
Unlike McNemar's test, which depends only on the discordant counts $n_{CI}$ and $n_{IC}$ and provides only a binary hypothesis rejection decision, this bootstrap test incorporates the total test size and mutual agreement rate ( $n_{CC} + n_{II}$ ) to construct a confidence interval for the effect size.
Knowl 4 — Empirical Parity of One-Vs-All and Output Coding Schemes with Tuned Gaussian SVMs
empirical result
Across benchmark multiclass datasets from the UCI repository (including soybean-large, letter, satimage, optdigits, glass, car, spectrometer, yeast, and page-blocks), One-Vs-All (OVA) Support Vector Machines (SVMs) achieve classification error rates that are statistically indistinguishable from or comparable to All-Vs-All (AVA), Dense random codes (DEN), Sparse random codes (SPA), and Complete codes (COM), provided that the Gaussian RBF kernel parameter $\gamma$ and regularization constant $C$ are tuned via cross-validation.

On the majority of datasets, the 90% bootstrap confidence intervals for the pairwise difference in error rate between OVA and the alternative coding schemes include zero. Classifier agreement rates between OVA and the alternative methods typically range from 85% to over 99%. Only on abalone (a 29-class problem with baseline error of 84% where all models achieve $>72\%$ error) and spectrometer (48 classes, 531 examples) does AVA show an advantage over OVA. On standard, well-separable datasets, the empirical differences between multiclass combination schemes disappear when strong binary learners are used.

Knowl 5 — Kernel Tuning Sensitivity in Multiclass ECOC vs. One-Vs-All SVM Evaluations

data/table

Prior published claims asserting that One-Vs-All (OVA) SVMs are systematically inferior to Error-Correcting Output Codes (ECOC) and All-Vs-All (AVA) schemes (such as in Allwein et al., 2000) relied on fixed degree-4 polynomial kernels without independent hyperparameter tuning. When Gaussian RBF kernels are used and the kernel parameter $\gamma$ and regularization constant $C$ are tuned via 10-fold cross-validation on the training set, overall test error rates decrease substantially and the performance gap between OVA and other output coding schemes vanishes.

Dataset and Evaluation Setup	OVA (%)	AVA (%)	COM (%)	DEN (%)	SPA (%)
Satimage (Allwein et al., degree-4 polynomial)	40.9	27.8	13.9	14.3	13.3
Satimage (Tuned Gaussian RBF kernel)	8.2	7.8	7.8	7.7	8.9
Yeast (Allwein et al., degree-4 polynomial)	72.9	40.9	40.4	39.7	47.2
Yeast (Tuned Gaussian RBF kernel)	40.3	41.0	40.3	40.1	38.6

The apparent superiority of ECOC over OVA in earlier literature was an artifact of weak base classifiers whose errors were sufficiently decorrelated to benefit from error-correction. When binary classifiers are well-tuned, their errors become highly correlated, eliminating the advantage of redundant coding.

Knowl 6 — Performance Comparison of OVA SVMs against Round-Robin Rule Induction
empirical result
Prior studies demonstrating that pairwise round-robin (All-Vs-All) classification substantially outperforms One-Vs-All (OVA) classification (Fürnkranz, 2002) used the rule-induction learner Ripper ( $R^3$ ) as the binary base classifier. When compared on the same UCI benchmark datasets, a One-Vs-All Support Vector Machine (OVA SVM) with a cross-validation-tuned Gaussian RBF kernel matches or substantially outperforms round-robin Ripper across 8 of 10 datasets.

Specifically, OVA SVM produces lower error rates on soybean-large (5.85% vs. 13.3%), letter (2.75% vs. 7.7%), satimage (7.80% vs. 12.2%), optdigits (2.73% vs. 7.5%), and car (1.50% vs. 2.8%). Ripper achieves lower error rates only on abalone (74.1% vs. 79.69%) and spectrometer (51.2% vs. 53.67%), which have high baseline errors and small sample-to-class ratios. Combining weaker learners using pairwise or error-correcting schemes does not exceed the performance achieved by combining strong, well-tuned regularized kernel classifiers in a simple OVA architecture.
Knowl 7 — Empirical Classification Equivalence of Regularized Least Squares and Support Vector Machines
empirical result
Regularized Least Squares Classification (RLSC), which solves the linear system $(K + \lambda \ell I)c = y$ corresponding to square loss $V(f(x), y) = (y - f(x))^2$ , yields multiclass classification accuracies comparable to Support Vector Machines (which optimize the hinge loss) when using Gaussian RBF kernels with tuned parameters $\gamma$ and $\lambda$ .

In One-Vs-All (OVA) multiclass evaluations across benchmark datasets, RLSC and SVM achieve very similar error rates:
- soybean-large: RLSC 6.12%, SVM 5.85%
- satimage: RLSC 7.90%, SVM 7.80%
- optdigits: RLSC 2.50%, SVM 2.73%
- glass: RLSC 31.30%, SVM 30.84%
- spectrometer: RLSC 52.30%, SVM 53.67%
- yeast: RLSC 40.00%, SVM 40.30%
- page-blocks: RLSC 3.25%, SVM 3.40%
In nearly all cases, the 90% bootstrap confidence interval for the error difference between RLSC and SVM contains zero, demonstrating that the choice of loss function between square loss and hinge loss has negligible impact on generalization accuracy for well-tuned regularized kernel classifiers.
Knowl 8 — Computational and Complexity Trade-Offs in Multiclass SVM Architectures
model/method
Multiclass classification architectures using Support Vector Machines exhibit distinct training and inference computational trade-offs:
- One-Vs-All (OVA) trains $N$ binary SVMs on all $\ell$ training samples. Because SVM training algorithms scale superlinearly with training size (roughly $\mathcal{O}(\ell^2)$ to $\mathcal{O}(\ell^3)$ ), training $N$ separate classifiers on the full dataset is often slower than pairwise training for large sample sizes $\ell$ .
- All-Vs-All (AVA / All-Pairs) trains $\binom{N}{2} = \frac{N(N-1)}{2}$ binary classifiers, but each classifier is trained only on the subset of data from two classes (average size $2\ell / N$ ). Despite the quadratic number of classifiers, AVA often trains substantially faster on large datasets due to the superlinear scaling of SVM solvers.
- Single-Machine Multiclass SVMs (e.g., Weston-Watkins, Crammer-Singer) optimize $N$ functions simultaneously by solving a single quadratic programming problem with $\mathcal{O}(N\ell)$ variables and complex coupled constraints, making decomposition methods less effective and training significantly slower than OVA or AVA.
- Testing Complexity: For OVA and AVA, evaluation requires computing kernel products against unique support vectors across models. The Directed Acyclic Graph (DAG) SVM evaluates only $N-1$ pairwise classifiers per test point via tournament elimination, reducing testing time relative to standard AVA while achieving equivalent test accuracy.
Knowl 9 — Assumption of Class Independence and Flat Target Categories
assumption
The conclusion that One-Vs-All (OVA) multiclass classification achieves accuracy on par with single-machine and error-correcting code approaches assumes that the $N$ target classes are flat and mutually independent, without an intrinsic taxonomic hierarchy or structured inter-class relationship.

If target classes exhibit known semantic hierarchies or non-uniform inter-class proximities (where instances of class $A$ are systematically more similar to class $B$ than to class $C$ ), particularly in data regimes with limited training examples per class, algorithms designed to exploit structured relationships among classes may outperform standard unlinked OVA binary decompositions.

Coverage note — Omitted detailed mathematical derivations of existing single-machine multiclass SVM formulations (Weston & Watkins; Lee, Lin & Wahba; Bredensteiner & Bennett; Crammer & Singer) and exact hyperparameter tables (Tables 16-19), as they represent prior work or implementation configurations rather than standalone contributed knowledge.

References

1.E. L. Allwein, R. E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of Machine Learning Research, 1:113–141, 2000.
2.R. C. Bose and D. K. Ray-Chaudhuri. On a class of error-correcting binary group codes. Information and Control, 3:68–79, 1960.
3.B. E. Boser, I. M. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In D. Haussler, editor, 5th Annual ACM Workshop on COLT, pages 144–152, 1992.
4.O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499–526, 2002.
5.E. Bredensteiner and K. P. Bennett. Multicategory classification by support vector machines. In Computational Optimizations and Applications, volume 12, pages 53–79, 1999.
6.W. W. Cohen. Fast effective rule induction. In Proceedings of the Twelfth International Conference on Machine Learning, 1995.
7.R. Collobert and S. Bengio. SVMTorch: Support vector machines for large-scale regression problems. Journal of Machine Learning Research, 1:143–160, 2001.
8.K. Crammer and Y. Singer. Improved output coding for classification using continuous relaxation. In Proceedings of the Thirteenth Annual Conference on Neural Information Processing Systems, 2000a.
9.K. Crammer and Y. Singer. On the learnability and design of output codes for multiclass problems. In Computational Learning Theory, pages 35–46, 2000b.
10.K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-basd vector machines. Journal of Machine Learning Research, 2:265–292, 2001.
11.K. Crammer and Y. Singer. On the learnability and design of output codes for multiclass problems. Machine Learning, 47(2):201–233, 2002.
12.T. G. Dietterich. Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10(7):1895–1924, 1998.
13.T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, 1995.
14.B. Everitt. The analysis of contingency tables. Chapman and Hall, 1977.
15.Theodoros Evgeniou, Massimiliano Pontil, and T. Poggio. Regularization networks and support vector machines. Advances In Computational Mathematics, 13(1):1–50, 2000.
16.Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.
17.G. Fung and O. L. Mangasarian. Proximal support vector classifiers. In Provost and Srikant, editors, Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 77–86. ACM, 2001a.
18.G. Fung and O. L. Mangasarian. Proximal support vector machine classifiers. Technical report, Data Mining Institue, 2001b.
19.J. F¨urnkranz. Round robin classification. Journal of Machine Learning Research, 2:721–747, 2002.
20.C. F. Gauss. Theoria combinationis obsevationum erroribus minimis obnoxiae. Werke, 1823.
21.F. Girosi and T. Poggio. Networks and the best approximation property. Technical Report A.I. Memo No. 1164, C.B.C.L Paper No. 45, Massachusetts Institute of Technology, Artificial Intelligence Laboratory and Center for Biological and Computational Learning, Department of Brain and Cognitive Sciences, October 1989.
22.Y. Guermeur. Combining discriminant models with new multi-class svms. Pattern Analysis and Applications, 5(2):168–179, 2002.
23.T. Hastie and R. Tibshirani. Classification by pairwise coupling. The Annals of Statistics, 26(2):451–471, 1998.
24.C. Hsu and C. Lin. A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks, 13:415–425, 2002.
25.T. Joachims. Making large-scale SVM learning practical. Technical Report LS VIII-Report, Universit¨at Dortmund, 1998.
26.E. B. Kong and T. G. Dietterich. Why error-correcting output coding works with decision trees. Technical report, Department of Computer Science, Oregon State University, Corvallis, OR, 1995.
27.Y. Lee, Y. Lin, and G. Wahba. Multicategory support vector machines. Technical Report 1043, Department of Statistics, University of Wisconsin, 2001a.
28.Y. Lee, Y. Lin, and G. Wahba. Multicategory support vector machines. In Proceedings of the 33rd Symposium on the Interface, 2001b.
29.Y. Lin. Support vector machines and the Bayes rule in classification. Technical Report Technical Report Numberr 1014, Department of Statistics, University of Wisconsin, 1999.
30.Q. McNemar. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 12:153–157, 1947.
31.C. J. Merz and P. M. Murphy. UCI repository of machine learning databases. http://www.ics.uci.edu/ mlearn/MLRepository.html, 1998.
32.S. Mika, G. R¨atsch, J. Weston, B. Sch¨olkopf, and K.-R. M¨uller. Fisher discriminant analysis with kernels. In Hu, Larsen, Wilson, and Douglas, editors, Proceedings of the IEEE Workshop on Neural Networks for Signal Processing IX, pages 41–48, 1999.
33.E. Osuna. Support Vector Machines: Training and Applications. PhD thesis, Massachusetts Institute of Technology, 1998.
34.E. Osuna, R. Freund, and F. Girosi. Training support vector machines: an application to face detection. In Proceedings of the 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 130–136, Los Alamitos, CA, USA, June 1997. IEEE Computer Society Technical Committee on Pattern Analysis and Machine Intelligence, IEEE Computer Society.
35.J. C. Platt, N. Cristianini, and J. Shawe-Taylor. Large margin DAGs for multiclass classification. In Advances in Neural Information Processing Systems, volume 12, pages 547–553. MIT Press, 2000.
36.T. Poggio and F. Girosi. Networks for approximation and learning. Proceedings of the IEEE, 78(9):1481–1497, September 1990.
37.J. R. Quinlan. C4.5: Programs for Empirical Learning. Morgan Kaufmann, 1993.
38.R. M. Rifkin. Everything Old Is New Again: A Fresh Look at Historical Approaches to Machine Learning. PhD thesis, Massachusetts Institute of Technology, 2002.
39.C. Saunders, A. Gammerman, and V. Vovk. Ridge regression learning algorithm in dual variables. In Proceedings of the 15th International Conference on Machine Learning, 1998.
40.R. E. Schapire, Y. Freund, P. Bartlett, and W. S. Lee. Boosting the margin: a new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5): 1651–1686, 1998.
41.R. E. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336, 1999.
42.I. Sch¨onberg. Spline functions and the problem of graduation. Proceedings of the National Academy of Science, pages 947–950, 1964.
43.T. J. Sejnowski and C. R. Rosenberg. Parallel networks that learn to pronounce English text. Journal of Complex Systems, 1(1):145–168, 1987.
44.J. A. K. Suykens, L. Lukas, P. Van Dooren, B. De Moor, and J. Vandewalle. Least squares support vector machine classifiers: a large scale algorithm. In Proceedings of the European Conference on Circuit Theory and Design, 1999.
45.J. A. K. Suykens and J. Vandewalle. Least squares support vector machine classifiers. Neural Processing Letters, 9(3):293–300, 1999a.
46.J. A. K. Suykens and J. Vandewalle. Multiclass least squares support vector machines. In Proceedings of the International Joint Conference on Neural Networks, 1999b.
47.A. N. Tikhonov and V. Y. Arsenin. Solutions of Ill-posed Problems. W. H. Winston, 1977.
48.V. N. Vapnik. Statistical Learning Theory. John Wiley and Sons, 1998.
49.G. Wahba. Spline Models for Observational Data, volume 59 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 1990.
50.G. Wahba and G. Kimeldorf. Some results on Tchebycheffian spline functions. Journal of Mathematical Analysis Applications, 33(1):82–95, 1971.
51.J. Weston and C. Watkins. Multi-class support vector machines. Technical Report CSD-TR-98-04, Royal Holloway, University of London, Department of Computer Science, 1998.
52.I. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann, 1999.

Citation

MLA

Rifkin, R., and A. Klautau. “In Defense of One-Vs-All Classification”. Journal of Machine Learning Research, vol. 5, no. Jan, 2004, pp. 101–41, https://www.jmlr.org/papers/v5/rifkin04a.html.

APA

Rifkin, R., & Klautau, A. (2004). In Defense of One-Vs-All Classification. Journal of Machine Learning Research, 5(Jan), 101–141. https://www.jmlr.org/papers/v5/rifkin04a.html

Chicago

Rifkin, R., and A. Klautau. 2004. “In Defense of One-Vs-All Classification”. Journal of Machine Learning Research 5 (Jan): 101–41. https://www.jmlr.org/papers/v5/rifkin04a.html.

Harvard

Rifkin, R. and Klautau, A. (2004) “In Defense of One-Vs-All Classification”, Journal of Machine Learning Research, 5(Jan), pp. 101–141. Available at: https://www.jmlr.org/papers/v5/rifkin04a.html.

Vancouver

1. Rifkin R, Klautau A (2004) In Defense of One-Vs-All Classification. Journal of Machine Learning Research 5:101–141

BibTeX

@article{rifkin2004defense,
  title = {In Defense of One-Vs-All Classification},
  author = {Rifkin, Ryan and Klautau, Aldebaro},
  year = {2004},
  journal = {Journal of Machine Learning Research},
  volume = {5},
  number = {Jan},
  pages = {101-141},
  url = {https://www.jmlr.org/papers/v5/rifkin04a.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/

In Defense of One-Vs-All Classification

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Equivalence of Class-Symmetric Zero-Free Output Codes and One-Vs-All under Regularized Least Squares Classification

Knowl 2 — Asymptotic Bayes Optimality of One-Vs-All Regularized Least Squares Classification

Knowl 3 — Bootstrap Confidence Interval Procedure for Comparing Paired Classifiers

Knowl 4 — Empirical Parity of One-Vs-All and Output Coding Schemes with Tuned Gaussian SVMs

Knowl 5 — Kernel Tuning Sensitivity in Multiclass ECOC vs. One-Vs-All SVM Evaluations

Knowl 6 — Performance Comparison of OVA SVMs against Round-Robin Rule Induction

Knowl 7 — Empirical Classification Equivalence of Regularized Least Squares and Support Vector Machines

Knowl 8 — Computational and Complexity Trade-Offs in Multiclass SVM Architectures

Knowl 9 — Assumption of Class Independence and Flat Target Categories

References

Citation

BibTeX

Access the Paper