An Empirical Comparison of Supervised Learning Algorithms

Rich Caruana [email protected]

Alexandru Niculescu-Mizil [email protected]

Department of Computer Science, Cornell University, Ithaca, NY 14853 USA

Abstract

A number of supervised learning methods

have been introduced in the last decade. Un-

fortunately, the last comprehensive empiri-

cal evaluation of supervised learning was the

boosted stumps. We also examine the effect

that calibrating the models via Platt Scaling

and Isotonic Regression has on their perfor-

mance. An important aspect of our study is

the use of a variety of performance criteria to

evaluate the learning methods.

1. Introduction

There are few comprehensive empirical studies com-

paring learning algorithms. STATLOG is perhaps the

best known study (King et al., 1995). STATLOG was

and different performance metrics are appropriate for

each domain. For example Precision/Recall measures

are used in information retrieval; medicine prefers

ROC area; Lift is appropriate for some marketing

tasks, etc. The different performance metrics measure

different tradeoffs in the predictions made by a clas-

sifier, and it is possible for learning methods to per-

form well on one metric, but be suboptimal on other

metrics. Because of this it is important to evaluate

algorithms on a broad set of performance metrics.

ing eight performance criteria. We evaluate the perfor-

mance of SVMs, neural nets, logistic regression, naive

bayes, memory-based learning, random forests, deci-

sion trees, bagged trees, boosted trees, and boosted

stumps on eleven binary classification problems using

a variety of performance metrics: accuracy, F-score,

Lift, ROC Area, average precision, precision/recall

break-even point, squared error, and cross-entropy.

For each algorithm we examine common variations,

and thoroughly explore the space of parameters. For

both before and after calibrating its predictions with

Platt Scaling and Isotonic Regression.

The empirical results are surprising. To preview: prior

to calibration, bagged trees, random forests, and neu-

ral nets give the best average performance across all

eight metrics and eleven test problems. Boosted trees,

however, are best if we restrict attention to the six

metrics that do not require probabilities. After cal-

ibration with Platt’s Method, boosted trees predict

better probabilities than all other methods and move

sion trees dramatically outperforms boosting weaker

stumps on most problems. On average, memory-based

learning, boosted stumps, single decision trees, logistic

regression, and naive bayes are not competitive with

the best methods. These generalizations, however, do

not always hold. For example, boosted stumps and

logistic regression, which perform poorly on average,

are the best models for some metrics on two of the test

problems.

summarizes the parameters used for each learning al-

gorithm, and may safely be skipped by readers who

are easily bored.

SVMs: we use the following kernels in SVMLight

(Joachims, 1999): linear, polynomial degree 2 & 3, ra-

dial with width {0.001,0.005,0.01,0.05,0.1,0.5,1,2}. We

also vary the regularization parameter by factors of ten

from 10

to 10

ANN we train neural nets with gradient descent

ridge (regularization) parameter by factors of 10 from

10

to 10

Naive Bayes (NB): we use Weka (Witten & Frank,

2005) and try all three of the Weka options for han-

dling continuous attributes: modeling them as a single

normal, modeling them with kernel estimation, or dis-

cretizing them using supervised discretization.

KNN: we use 26 values of K ranging from K = 1 to

Random Forests (RF): we tried both the Breiman-

Cutler and Weka implementations; Breiman-Cutler

yielded better results so we report those here. The

forests have 1024 trees. The size of the feature set

considered at each split is 1,2,4,6,8,12,16 or 20.

Decision trees (DT): we vary the splitting crite-

rion, pruning options, and smoothing (Laplacian or

Bayesian smoothing). We use all of the tree models

in Buntine’s IND package (Buntine & Caruana, 1991):

BAYES, ID3, CART, CART0, C4, MML, and SMML.

each type described above. With boosted trees

(BST-DT) we boost each tree type as well. Boost-

ing can overfit, so we consider boosted trees af-

ter 2,4,8,16,32,64,128,256,512,1024 and 2048 steps

of boosting. With boosted stumps (BST-

STMP) we boost single level decision trees gener-

ated with 5 different splitting criteria, each boosted for

2,4,8,16,32,64,128,256,512,1024,2048,4096,8192 steps.

With LOGREG, ANN, SVM and KNN we scale at-

tributes to 0 mean 1 std. With DT, RF, NB, BAG-

slac 59 5000 25000 50%

only restriction it makes is that the mapping function

be isotonic (monotonically increasing). A standard al-

gorithm for Isotonic Regression that finds a piecewise

constant solution in linear time, is the pair-adjacent

violators (PAV) algorithm (Ayer et al., 1955).

To calibrate models, we use the same 1000 points val-

idation set that will be used for model selection.

2.5. Data Sets

We compare the algorithms on 11 binary classifica-

remaining 25 letters as negative, yielding a very unbal-

anced problem. LETTER.p2 uses letters A-M as posi-

tives and the rest as negatives, yielding a well balanced

problem. HS is the IndianPine92 data set (Gualtieri

et al., 1999) where the difficult class Soybean-mintill is

the positive class. SLAC is a problem from the Stan-

ford Linear Accelerator. MEDIS and MG are medical

data sets. COD, BACT, and CALHOUS are three of

the datasets used in (Perlich et al., 2003). ADULT,

COD, and BACT contain nominal attributes. For

3. Performances by Metric

For each test problem we randomly select 5000 cases

for training and use the rest of the cases as a large

final test set. We use 5-fold cross validation on the

before computing the three probability metrics.) A

“PLT” or “ISO” in the second column indicates that

the model predictions were scaled after the model was

trained using Platt Scaling or Isotonic Regression, re-

spectively. These scaling methods were discussed in

ignore the last column, OPT-SEL. This column will

be discussed later in this section.

In the table, the algorithm with the best performance

on each metric is boldfaced. Other algorithm’s whose

performance is not statistically distinguishable from

the best algorithm at p = 0.05 using paired t-tests on

the 5 trials are *’ed.

Entries in the table that are

neither bold nor starred indicate performance that is

experiment-wise p-value that takes into account the num-

ber of tests performed, but the strong correlations between

performances on different metrics, and on calibrated and

uncalibrated models, makes this problematic as well, so we

decided to keep it simple. Most of the differences in the ta-

ble are significant well beyond p = 0.05. Doing the t-tests

at p = 0.01 adds few additional stars to the table.

Note that it is possible for the difference between the

scores 0.90 and 0.89 to be statistically significant, and yet

or without calibration, the poorest performing models

are naive bayes, logistic regression, and decision trees.

Memory-based methods (e.g. KNN) are remarkably

unaffected by calibration, but exhibit mediocre overall

performance. Boosted stumps, even after calibration,

also have mediocre performance, and do not perform

nearly as well as boosted full trees.

Looking at individual metrics, boosted trees, which

have poor squared error and cross-entropy prior to cal-

ibration, dominate the other algorithms on these met-

dering metrics: area under the ROC, average precision,

and the precision/recall break-even point.

forests and bagged trees have similar performance as

boosted trees on these metrics. The neural nets and

SVMs also order cases extremely well.

On metrics that compare predictions to a thresh-

old: accuracy, F-score, and Lift, the best models are

calibrated or uncalibrated random forests, calibrated

boosted trees, and bagged trees with or without cali-

by cheating and looking at the final test sets. The

means in this column represent the best performance

that could be achieved with each learning method if

model selection were done optimally. We present these

numbers because parameter optimization is more crit-

ical (and more difficult) with some algorithms than

with others. For example, bagging works well with

most decision tree types and requires little tuning, but

neural nets and SVMs require careful parameter selec-

tion. As expected, the mean normalized scores in the

that may affect performance on the ordering metrics.

Table 2. Normalized scores for each learning algorithm by metric (average over eleven problems)

Table 3. Normalized scores of each learning algorithm by problem (averaged over eight metrics)

in the column for 2nd place, tells us that there is a

22.8% chance that boosted decision trees would have

placed 2nd in the table of results (instead of 1st) had

we selected other problems and/or metrics.

The bootstrap analysis complements the t-tests in Ta-

bles 2 and 3. The results suggest that if we had se-

lected other problems/metrics, there is a 58% chance

that boosted decision trees would still have ranked 1st

overall, and only a 4.2% chance of seeing them rank

lower than 3rd place. Random forests would come in

1st place 39% of the time, 2nd place 53% of the time,

with little chance (0.1%) of ranking below third place.

There is less than a 20% chance that a method other

after neural nets. The bootstrap analysis clearly shows

that MBL, boosted 1-level stumps, plain decision trees,

logistic regression, and naive bayes are not competitive

and metrics when trained on 5k samples.

6. Related Work

STATLOG is perhaps the best known study (King

et al., 1995). STATLOG was a very comprehensive

study when it was performed, but since then important

new learning algorithms have been introduced such as

evaluates nearly a dozen learning methods on a real

medical data set using both accuracy and an ROC-like

metric. Lim et al. (2000) perform an empirical com-

parison of decision trees and other classification meth-

ods using accuracy as the main criterion. Bauer and

Kohavi (1999) present an impressive empirical analy-

sis of ensemble methods such as bagging and boosting.

Perlich et al. (2003) conducts an empirical comparison

between decision trees and logistic regression. Provost

and Domingos (2003) examine the issue of predicting

probabilities with decision trees, including smoothed

and bagged trees. Provost and Fawcett (1997) discuss

the importance of evaluating learning algorithms on

metrics other than accuracy such as ROC.

ward neural nets have the best performance and are

competitive with some of the newer methods, particu-

larly if models will not be calibrated after training.

Calibration with either Platt’s method or Isotonic Re-

gression is remarkably effective at obtaining excellent

performance on the probability metrics from learning

algorithms that performed well on the ordering met-

rics. Calibration dramatically improves the perfor-

mance of boosted trees, SVMs, boosted stumps, and

Naive Bayes, and provides a small, but noticeable im-

uncalibrated bagged trees, calibrated SVMs, and un-

calibrated neural nets. The models that performed

poorest were naive bayes, logistic regression, decision

trees, and boosted stumps. Although some methods

clearly perform better or worse than other methods

problems and metrics. Even the best models some-

times perform poorly, and models with poor average

Acknowledgments

We thank F. Provost and C. Perlich for the BACT,

Bauer, E., & Kohavi, R. (1999). An empirical com-

Blake, C., & Merz, C. (1998). UCI repository of ma-

Breiman, L. (1996). Bagging predictors. Machine

Cooper, G. F., Aliferis, C. F., Ambrosino, R., Aronis,

Joachims, T. (1999). Making large-scale svm learning

King, R., Feng, C., & Shutherland, A. (1995). Statlog:

comparison of classification algorithms on large real-

world problems. Applied Artificial Intelligence, 9.

LeCun, Y., Jackel, L. D., Bottou, L., Brunot, A.,

Cortes, C., Denker, J. S., Drucker, H., Guyon, I.,

Muller, U. A., Sackinger, E., Simard, P., & Vapnik,

V. (1995). Comparison of learning algorithms for

handwritten digit recognition. International Con-

Niculescu-Mizil, A., & Caruana, R. (2005). Predicting

good probabilities with supervised learning. Proc.

Perlich, C., Provost, F., & Simonoff, J. S. (2003). Tree

induction vs. logistic regression: a learning-curve

analysis. J. Mach. Learn. Res., 4, 211–255.

Platt, J. (1999). Probabilistic outputs for support vec-

tor machines and comparison to regularized likeli-

hood methods. Adv. in Large Margin Classifiers.