PaperlayerView exact revision on arXiv

Source-linked AI summary

Comparison of 14 different families of classification algorithms on 115 binary datasets

Jacques Wainer

arXiv:1606.00930v1cs.LGcs.CV

TL;DR

Broad classifier comparisons need family-level evidence and criteria distinguishing statistically significant differences from practically important ones. The study uses cross-validated hyperparameter selection and evaluates classifier performance with held-out error rates and execution-time measurements. Random forest, gradient boosting, and RBF SVM are the strongest classifiers without important error-rate differences, while RBF SVM is faster in training and combined training plus testing time.

  • Problem

    Broad classifier comparisons need family-level evidence and criteria distinguishing statistically significant differences from practically important ones.

  • Method

    The study uses cross-validated hyperparameter selection and evaluates classifier performance with held-out error rates and execution-time measurements.

  • Results

    Random forest, gradient boosting, and RBF SVM are the strongest classifiers without important error-rate differences, while RBF SVM is faster in training and combined training plus testing time.

  • Takeaways & Limitations

    Differences below 0.0112 in error rate should generally be treated as practically irrelevant, and the three leading classifiers are likely interchangeable in accuracy within this scope.

  • Takeaways & Limitations

    Timing conclusions are limited because the study uses standard R implementations whose development status may favor SVM over newer random-forest and gradient-boosting implementations.

Abstract

from arXiv · show

We tested 14 very different classification algorithms (random forest, gradient boosting machines, SVM - linear, polynomial, and RBF - 1-hidden-layer neural nets, extreme learning machines, k-nearest neighbors and a bagging of knn, naive Bayes, learning vector quantization, elastic net logistic regression, sparse linear discriminant analysis, and a boosting of linear classifiers) on 115 real life binary datasets. We followed the Demsar analysis and found that the three best classifiers (random forest, gbm and RBF SVM) are not significantly different from each other. We also discuss that a change of less then 0.0112 in the error rate should be considered as an irrelevant change, and used a Bayesian ANOVA analysis to conclude that with high probability the differences between these three classifiers is not of practical consequence. We also verified the execution time of "standard implementations" of these algorithms and concluded that RBF SVM is the fastest (significantly so) both in training time and in training plus testing time.

1 Introduction

The paper revisits broad classifier comparisons by evaluating algorithm families on binary datasets with more careful tuning, principled significance analysis, and execution-time measurements.

  • Motivation and scope: Practitioners have limited resources, time, and expertise, making broad empirical comparisons useful for prioritizing algorithms to test.The authors likewise argue that researchers can focus development on more promising algorithm families.
  • Motivation and scope: The study addresses limitations in prior comparisons by converting datasets to binary problems, reducing comparisons to algorithm families, and adding gradient boosting machines.These changes aim to make family-level rankings more useful for practitioners and researchers.
  • Methodological extensions: The authors perform more careful hyperparameter searches while limiting training steps so algorithms receive comparable tuning effort.The prior study’s 179 programs required reliance on default hyperparameters, which could produce suboptimal results.
  • Methodological extensions: The analysis combines the full Demsar procedure with Bayesian ANOVA to distinguish statistical significance from practical significance.The authors define thresholds below which error-rate differences are practically irrelevant.
  • Methodological extensions: The study also measures standard implementation costs so practitioners can balance expected accuracy against execution time.These measurements may encourage faster implementations of strong algorithms.

2 Data and Methods

The experiments compare 14 diverse classifiers on 115 transformed binary datasets, using repeated cross-validation for hyperparameter selection and held-out subset evaluation.

  • 2.2 Datasets: The dataset collection starts from 121 preprocessed UCI datasets; six datasets with fewer than 100 observations are removed, leaving 115.Large datasets use subsets for hyperparameter search but full subsets for final training and testing.
  • 2.3 Algorithms: The comparison includes 14 classifiers spanning random forests, boosting, SVM kernels, neural networks, nearest neighbors, Bayesian methods, discriminant analysis, and regularized linear models.The design emphasizes diverse algorithm families rather than many implementations of the same algorithm.
  • 2.3 Algorithms: The SVM family is represented separately by linear, polynomial, and RBF kernels, while random forest and gradient boosting each contribute one implementation.Other included methods comprise naive Bayes, learning vector quantization, k-nearest neighbors, bagged k-nearest neighbors, and neural-network variants.
  • 2.4 Hyperparameters ranges: Hyperparameter searches use algorithm-specific ranges, including random-forest tree counts from 500 to 3000 and regularization paths computed by glmnet.The number of trees is treated as a free hyperparameter because multiple tested values can be evaluated from one trained forest.

3 Statistical procedures

The study combines Demsar’s frequentist procedure with Bayesian analysis to compare classifiers while distinguishing statistical differences from practically irrelevant error changes. It also defines computational-cost measures and ranks execution times using mean ranks and Demsar testing.

  • 3.1 Demsar procedure: Demsar procedure: a Friedman test screens for overall differences, followed by Nemenyi pairwise comparisons when the overall p-value is below 0.05.The Nemenyi test applies the appropriate multiple-comparison correction when comparing all algorithms.
  • 3.2 Bayesian comparison of multiple groups: Bayesian ANOVA estimates posterior distributions for algorithm effects and pairwise differences, including the probability that differences fall within a practically irrelevant region.The model treats classification algorithm and dataset as factors and assumes no interaction component.
  • 3.3 Threshold of irrelevance: The irrelevance threshold is defined empirically as the lower of two proposed measures based on expected error changes across samples or between cross-validation and held-out testing.Both proposals use a futility perspective rather than theoretical considerations.
  • 3.4 Computational costs: Computational cost includes training plus testing time and hyperparameter-search time normalized by the number of tested combinations.Execution times are ranked by dataset using mean ranks and compared with the Demsar procedure.

4 Results

Across the benchmark, random forest ranked first, followed by Gaussian-kernel SVM and gradient boosting machines, while the top three were not statistically distinguishable. Bayesian analysis further indicated that their error-rate differences were usually practically irrelevant, and SVM with a radial kernel was fastest per hyperparameter.

  • 4.1 Error rates of the different algorithms: Random forest had the best mean rank, followed by Gaussian-kernel SVM and gradient boosting machines.The three worst mean-ranked algorithms were boosting of linear classifiers, naive Bayes, and L1-regularized LDA, although the authors caution that hyperparameter choices may explain some poor performance.
  • 4.2 Demsar procedure: The Nemenyi analysis found no statistically significant differences among random forest, radial-kernel SVM, and gradient boosting machines, whereas nnet differed significantly from each.The pairwise p-values among the top three were all above 0.05; this does not by itself establish equivalence.
  • 4.3 Irrelevance thresholds: 0.0112 was adopted as the error-rate threshold below which differences were considered irrelevant.The threshold was the lower of two comparable measures, each a little over 1%.
  • 4.4 Bayesian ANOVA analysis: Probabilities of 0.83 to 0.64 placed the top-three error-rate differences within the irrelevance range, supporting practical equivalence.The evidence for equivalence was strongest for random forest versus radial-kernel SVM and weaker for gradient boosting machine comparisons.
  • 4.5 Computational costs of the algorithms: Radial-kernel SVM was significantly faster than every other algorithm on per-hyperparameter cost.Its per-hyperparameter cost was especially low despite a dataset-independent hyperparameter grid; random forest could become less viable when separate tree-count training is required.

5 Discussion

The discussion frames 0.0112 as an empirically derived practical-irrelevance threshold, while cautioning that conclusions depend on dataset scope, hyperparameter choices, model assumptions, and implementation timing. Within a stricter 0.0056 threshold, random forest and RBF SVM still have a 50% probability of practical equivalence.

  • Practical significance: 0.0112 is proposed as the median error-rate change expected when a classifier is trained and tested on different samples from the same population.The threshold is empirically derived from the 115 datasets rather than theoretically justified.
  • Bayesian analysis: The robust Bayesian model yields stronger practical-equivalence results because shrinkage allows algorithm coefficients to move closer together.The discussion contrasts this with a traditional Gaussian-prior Bayesian ANOVA model.
  • Comparison with prior work: The results broadly agree with prior evidence that random forest ranks best, while gradient boosting machines and RBF SVM also perform well.Gradient boosting machines were not included in Fernández-Delgado et al. (2014), limiting direct comparison for that algorithm.
  • Limits on this research: The conclusions should be generalized only to similar datasets because the study excludes very large, very sparse, high-dimensional, and nonbinary problems.The authors condition broader generalization on treating the UCI datasets as samples of real-life problems.
  • Future research: Hyperparameter choices may have unfairly ranked algorithms because useful value ranges are poorly studied for the compared methods.The authors identify hyperparameter selection as especially underdeveloped for random forests and gradient boosting machines.
  • Limits on this research: Timing results are limited because they compare standard R implementations whose development status and optimization differ across algorithms.Newer random-forest and gradient-boosting implementations, or incremental SVM solvers, could change the observed timing ranking.

6 Conclusion

The study identifies random forests, RBF SVM, and gradient boosting machines as the strongest classifiers, with no important error-rate differences among them. It proposes a 0.0112 practical-irrelevance threshold and Bayesian ANOVA as methodological tools for comparing algorithms.

  • Random forests, RBF SVM, and gradient boosting machines are the strongest classifiers, with likely no important error-rate differences among them.
  • RBF SVM is faster than random forests and gradient boosting machines for training and testing execution time.
  • 0.0112 is proposed as the threshold below which changes in error rate have no practical significance.
  • Bayesian ANOVA indicates that differences among the three top algorithms are very likely smaller than the practical-irrelevance threshold.

A Datasets

The dataset appendix records dataset size, feature and observation counts, positive-class proportions, and notes about binary conversion and large-dataset subsampling.

  • Dataset entries report size, feature count, observation count, and positive-class proportion.
  • Multivalued datasets were converted to binary problems using the procedure described in Section 2.
  • For large datasets, only 5000 observations were used to search for hyperparameters.
  • Tables 9 lists the datasets used in the study.

B Full p-value tables for the pairwise comparison of the 1-train-test and per hyperparameter costs

The appendix provides full pairwise p-value tables for training-test time and per-hyperparameter execution costs.

  • Table 10 contains the full p-value table for the 1-train-test time comparison.
  • Table 11 contains the full p-value table for per-hyperparameter execution times.

C Bayesian model verification

The Bayesian model is assessed against observed and generated error-rate distributions, with posterior predictive checks supporting its suitability despite a small fraction of negative generated values.

  • The observed error-rate distributions across algorithms and random datasets are presented with fitted Gaussian distributions.
  • The error-rate distributions are considered reasonably normal, supporting the assumptions of equations 2e and 2f.
  • Posterior predictive checking compares the true data with data generated from the model's posterior parameter distribution using χ2 discrepancy.
  • The posterior predictive probability is around 0.5, and the real data are among the most likely generated data, supporting model appropriateness.
  • 3% of generated data were negative, an aesthetically unpleasant property of the model output.

D Convergence of the MCMC

The MCMC convergence checks found potential scale reduction factors consistent with convergence and effective sample sizes indicating no high autocorrelation. The chains used 5000 burn-in steps, 5000 adaptive steps, and 100000 iterations across four chains.

  • The analysis used 5000 burn-in steps, 5000 adaptive steps, and 100000 iterations across four separate chains.
  • The Gelman–Rubin diagnostic compares variance within and between chains for the model variables.
  • Values between 1 and 1.1 indicate convergence of the MCMC iterations.
  • Effective sample sizes indicate no problem with high autocorrelation.

E Results with the robust Bayesian model

The robust Bayesian analysis presents pairwise probabilities that algorithm error-rate differences fall within the predefined irrelevance interval. Posterior predictive model verification was unavailable because the robust model's variance is undefined for its simulated Student-t degrees of freedom.

  • Posterior predictive checking could not verify the robust model because the χ2 discrepancy requires the data variance.
  • The Bayesian ANOVA reports probabilities that pairwise error-rate differences lie between -0.0112 and 0.0112 under the robust model.
  • The robust simulations used a Student-t distribution with 1.12 degrees of freedom, for which the variance is undefined below 2.
Loading 1606.00930v1…