Ten More Years of Error Rate Research
International Statistical ReviewPublished 1 December 2000
Rosa A. Schiavo, David J. Hand
Citations58
SJR quartileQ1
SJR score0.92
SNIP1.84
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper reviews the last ten years of error rate research, bringing up to date the reviews of Hand (1986a) and McLachlan (1987) and new approaches to error rate estimation have been developed.
Abstract
Summary The assessment of the performance of supervised classification rules by estimating their error rate (the proportion of objects misclassified) is an important area of work in statistical pattern recognition. This paper reviews the last ten years of error rate research, bringing up to date the reviews of Hand (1986a) and McLachlan (1987). Since those surveys were published, old estimators have been improved new estimators have been introduced, and new approaches to error rate estimation have been developed. Some of this work has led to deep insights into classification methodology and statistical modelling in general.
Keywords
Computer Science
An Introduction to the Bootstrap
39,744 Citations1994Bradley Efron, Robert Tibshirani
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
TechnometricsStatistical Learning Theory
26,913 Citations1999Yuhai Wu, Vladimir Vapnik
Presenting a method for determining the necessary and sufficient conditions for consistency of learning process, the author covers function estimates from small data pools, applying these estimations to real-life problems, and much more.
Data Mining and Knowledge DiscoveryA Tutorial on Support Vector Machines for Pattern Recognition
16,433 Citations1998Christopher J. C. Burges
There are several arguments which support the observed high accuracy of SVMs, which are reviewed and numerous examples and proofs of most of the key theorems are given.
Machine LearningBagging predictors
16,377 Citations1996Leo Breiman
Tests on real and simulated data sets using classification and regression trees and subset selection in linear regression show that bagging can give substantial gains in accuracy.
A study of cross-validation and bootstrap for accuracy estimation and model selection
10,733 Citations1995Ron Kohavi
The results indicate that for real-word datasets similar to the authors', the best method to use for model selection is ten fold stratified cross validation even if computation power allows using more folds.
Society for Industrial and Applied Mathematics eBooksThe Jackknife, the Bootstrap and Other Resampling Plans
7,903 Citations1982Bradley Efron
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Stochastic modelling and applied probabilityA Probabilistic Theory of Pattern Recognition
3,277 Citations1996Luc Devroye, László Györfi +1 more
The Bayes Error and Vapnik-Chervonenkis theory are applied as guide for empirical classifier selection on the basis of explicit specification and explicit enforcement of the maximum likelihood principle.
Communications of the ACMA theory of the learnable
3,268 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
The American StatisticianA Leisurely Look at the Bootstrap, the Jackknife, and Cross-Validation
2,963 Citations1983Bradley Efron, Gail Gong
Journal of the American Statistical AssociationDiscriminant Analysis and Statistical Pattern Recognition.
2,671 Citations1993Douglas M. Hawkins, Geoffrey J. McLachlan
Information science and statisticsEstimation of Dependences Based on Empirical Data
2,238 Citations2006Vladimir Vapnik
Journal of the American Statistical AssociationEstimating the Error Rate of a Prediction Rule: Improvement on Cross-Validation
2,161 Citations1983Bradley Efron
Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension
1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more
This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Information and ComputationBoosting a Weak Learning Algorithm by Majority
1,686 Citations1995Yoav Freund
An algorithm for improving the accuracy of algorithms for learning binary concepts by combining a large number of hypotheses, each of which is generated by training the given learning algorithm on a different set of examples, is presented.
Neural ComputationWhat Size Net Gives Valid Generalization?
1,555 Citations1989Eric B. Baum, David Haussler
It is shown that if m O(W/ ∊ log N/∊) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 ∊/2 of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 2 ∊ of future test examples drawn from the same distribution.
TechnometricsEstimation of Error Rates in Discriminant Analysis
1,495 Citations1968Peter A. Lachenbruch, M. R. Mickey
Several methods of estimating error rates in Discriminant Analysis are evaluated by sampling methods, finding the two methods in most common use to be significantly poorer than some new methods that are proposed.
IEEE Transactions on Information TheoryThe sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network
1,187 Citations1998Peter L. Bartlett
Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights.
TechnometricsConstruction and Assessment of Classification Rules
625 Citations1999Mark R. Wade, David J. Hand
Basic Ideas Introduction Constructing Rules Fisher's LDA and Other Methods Based on Covariance Matrices Recursive Partitioning Methods Nonparametric Smoothing Methods Practical Issues Some Special Problems Some Illustrative Applications.
Cambridge University Press eBooksNeural Network Learning
580 Citations1999Martin Anthony, Peter L. Bartlett
QUT ePrints (Queensland University of Technology)Boosting the margin: A new explanation for the effectiveness of voting methods
578 Citations1997Robert E. Schapire, Yoav Freund +2 more
IEEE Transactions on Information TheoryStructural risk minimization over data-dependent hierarchies
527 Citations1998John Shawe‐Taylor, Peter L. Bartlett +2 more
A result is presented that allows one to trade off errors on the training sample against improved generalization performance, and a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets.
An empirical comparison of pattern recognition, neural nets, and machine learning classification methods
470 Citations1989Sholom M. Weiss, Ioannis Kapouleas
For these problems, which have relatively few hypotheses and features, the machine learning procedures for rule induction or tree induction clearly performed best.
Computational learning theory
322 Citations1992Dana Angluin
The general AI meetings, AAAI and IJCAI, currently have a large number of papers devoted to learning, as do the neural net meetings, and the European meetings on Analogical and Inductive Inference and the AI machine learning communit y’s annual International Conference on Machine Learning.
IEEE Transactions on Information TheoryBibliography on estimation of misclassification
307 Citations1974Godfried Toussaint
Articles, books, and technical reports on the theoretical and experimental estimation of probability of misclassification are listed for the case of correctly labeled or preclassified training data.
OUT-OF-BAG ESTIMATION
279 Citations1996Leo Breiman
In bagging, predictors are constructed using bootstrap samples from the training set and then aggregated to form a bagged predictor, where estimated outputs instead of the observed outputs improves accuracy in regression trees.
Journal of the American Statistical AssociationCross-Validation, the Jackknife, and the Bootstrap: Excess Error Estimation in Forward Logistic Regression
236 Citations1986Gail Gong
Three estimates of the excess error are considered: cross-validation, the jackknife, and the bootstrap, for a moderately complicated prediction rule, involving a variable-selection procedure based on forward logistic regression.
IEEE Transactions on Information TheoryDistribution-free performance bounds for potential function rules
227 Citations1979Luc Devroye, T. Wagner
It is shown that the mean-square difference between the probability of error for the nde and its deleted estimate is bounded by A/ \sqrt{n} where A is an explicitly given constant depending only on M and the potential function.
The impact of changing populations on classifier performance
225 Citations1999Mark G. Kelly, David J. Hand +1 more
Examples of population drift are given, the nature of such population drift is examined, how the impact of population Drift depends on the chosen measure of classification performance, and a strategy for dynamically updating classification rules is proposed.
IEEE Transactions on Pattern Analysis and Machine IntelligenceBootstrap Techniques for Error Estimation
202 Citations1987Anil K. Jain, Richard C. Dubes +1 more
Results on the application of several bootstrap techniques in estimating the error rate of 1-NN and quadratic classifiers show that, in most cases, the confidence interval of a bootstrap estimator of classification error is smaller than that of the leave-one-out estimator.
Pattern RecognitionComparing classifiers when the misallocation costs are uncertain
172 Citations1999Niall M. Adams, David J. Hand
An alternative plot which is more revealing than an ROC plot is presented and a comparative index is described which allows one to take advantage of anything that may be known about the relative severity of the two kinds of misclassification.
Information and ComputationPredicting {0, 1}-Functions on Randomly Drawn Points
152 Citations1994David Haussler, N. Littlestone +1 more
IEEE Transactions on Information TheoryNonparametric estimation via empirical risk minimization
147 Citations1995Gábor Lugosi, K. Zeger
A general notion of universal consistency of nonparametric estimators is introduced that applies to regression estimation, conditional median estimation, curve fitting, pattern recognition, and learning concepts and distribution-free almost sure consistency of neural network estimates and generalized linear estimators are established.
Pattern RecognitionAdditive estimators for probabilities of correct classification
146 Citations1978Ned Glick
“Smooth” modification of the counting estimator, or sample success proportion, is recommended to reduce bias and variance while retaining robustness, and the “bootstrap” method of Efron can approximately correct an additive estimator's bias using an ancillary computer simulation.
Pattern Recognition LettersRecent advances in error rate estimation
132 Citations1986David J. Hand
Different types of error rates are described and the state of the art of error rate estimation at the time of Toussaint's survey is briefly summarised, and the two major advances, namely bootstrap and average conditional error rates estimation methods, and their extensions, are described in detail.
IEEE Transactions on Pattern Analysis and Machine IntelligenceBayes Error Estimation Using Parzen and k-NN Procedures
129 Citations1987Keinosuke Fukunaga, D.M. Hummels
It is shown that, by varying the decision threshold, many of the biases associated with the k-NN or Parzen density estimates may be compensated, and successful error estimation may be performed in spite of these biases.
IEEE Transactions on Information TheoryDistribution-free inequalities for the deleted and holdout error estimates
119 Citations1979Luc Devroye, T. Wagner
In the discrimination problem the random variable \theta, known to take values in {1,\ldots,M} , is estimated from the random vector X taking values in {\bfR}^{d} .
Algorithmic stability and sanity-check bounds for leave-one-out cross-validation
115 Citations1997Michael Kearns, Dana Ron
This article proves sanity-check bounds for the error of the leave-oneout cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate is not much worse than that of the training error estimate.
IEEE Transactions on Information TheoryNonparametric Bayes error estimation using unclassified samples
88 Citations1973Keinosuke Fukunaga, David Kessell
A pattern recognition system may be viewed as a decision rule which transforms measurements into class assignments and the Bayes error is the minimum achievable error, where the minimization is with respect to all decision rules.
IEEE Transactions on Pattern Analysis and Machine IntelligenceEstimation of classifier performance
76 Citations1989Keinosuke Fukunaga, R.R. Hayes
A unified and comprehensive approach to the analysis of classifier performance is presented and the theoretical analysis of the bootstrap method is presented for quadratic classifiers.
Neural ComputationHow Tight Are the Vapnik-Chervonenkis Bounds?
71 Citations1992David Cohn, Gerald Tesauro
It is found that, in some cases, the average generalization of neural networks trained on a variety of simple functions is significantly better than the VC bound: the approach to perfect performance is exponential in the number of examples m, rather than the 1/m result of the bound.
Journal of the Royal Statistical Society Series B (Statistical Methodology)On the Non-Parametric Estimation of Mixture Proportions
46 Citations1981Peter Hall
TechnometricsAn Evaluation of Smoothed Classification Error – Rate Estimators
43 Citations1985Steven Snapinn, James D. Knoke
Using the criterion of unconditional mean squared error, this particular smoothed estimator, called the NS method, appears to offer a reasonable alternative to existing nonparametric estimators.
IEEE Transactions on Neural NetworksGeneralization and PAC learning: some new results for the class of generalized single-layer networks
41 Citations1995Sean B. Holden, P. J. Rayner
It is shown that the use of self-structuring techniques for GSLNs may reduce the number of training examples sufficient to guarantee good generalization performance, and an explanation for the fact that GSLNs can require a relatively large number of weights is provided.
IEEE Transactions on Pattern Analysis and Machine IntelligenceSmall sample error rate estimation for k-NN classifiers
41 Citations1991Sabine Weiß
It is shown that each of the estimators has strengths and weaknesses for varying apparent and true error-rate situations and a combined estimator that corrects the leaving-one-out estimator (by combining bootstrap and cross-validation estimators) gives strong results over a broad range of situations.
BiometricsEstimation of Error Rates in Discriminant Analysis with Selection of Variables
35 Citations1989Steven Snapinn, James D. Knoke
This paper proposes a smoothed estimator that requires relatively little computation and which, on the basis of a Monte Carlo sampling study, is found to perform generally at least as well as the bootstrap method.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStatistical Properties of Error Estimators in Performance Assessment of Recognition Systems
31 Citations1982Josef Kittler, Pierre A. Devijver
In contrast to conventional methods of Bayes error estimation the unbiasedness of the R estimator for a given classifier can be obtained only at the price of an additional set of classified samples.
Estimating the accuracy of learned concepts
31 Citations1993Timothy L. Bailey, Charles Elkan
The experimental results contradict previous papers in statistics, which advocate the 632 bootstrap method as superior to cross-validation and suggest that conclusions based on cross- validation in previous machine learning papers are unreliable.
IEEE Transactions on Information TheoryOn the posterior-probability estimate of the error rate of nonparametric classification rules
28 Citations1994Gábor Lugosi, M. Pawlak
RePEc: Research Papers in EconomicsAn Efficient Method to Estimate Bagging's Generalization Error
28 Citations1996David H. Wolpert, William G. Macready
Error Rate Estimation in Discriminant Analysis: Recent Advances
26 Citations1987Geoffrey J. McLachlan
Australian Journal of StatisticsASSESSING ERROR RATE ESTIMATORS: THE LEAVE‐ONE‐OUT METHOD RECONSIDERED
26 Citations1997W. J. Krzanowski, David J. Hand
The leave-one-out estimator is investigated in a simulation study, both in absolute terms and in comparison with a popular bootstrap estimator, and appears to maintain superiority even when the criteria are adjusted.
Neural ComputationOn the Practical Applicability of VC Dimension Bounds
25 Citations1995Sean B. Holden, Mahesan Niranjan
The more recent Vapnik-Chervonenkis dimension-based bounds on sample complexity provide sample complexity predictions that are significantly more applicable in practice than those provided by earlier theories; however, it is found that these theories still have significant shortcomings.
BiometricsOn the Relationship between the F Test and the Overall Error Rate for Variable Selection in Two-Group Discriminant Analysis
22 Citations1980Geoffrey J. McLachlan
Neural Information Processing SystemsCan neural networks do better than the Vapnik-Chervonenkis bounds?
22 Citations1990David Cohn, Gerald Tesauro
A series of careful numerical experiments are described, which find that, in some cases, the average generalization is significantly better than the VC bound: the approach to perfect performance is exponential in the number of examples m, rather than the 1/m result of the bound.
Network Computation in Neural SystemsSample sizes for multiple-output threshold networks
20 Citations1991John Shawe‐Taylor, Martin Anthony
It is shown that the sample size for reliable learning can be bounded above by a quantity independent of the number of outputs of the network.
Estimating expected error rates of neural network classifiers in small sample size situations: a comparison of cross-validation and bootstrap
19 Citations2002N. Ueda, Ryoko Nakano
This paper applies a statistical resampling technique, called the bootstrap method, to this estimation problem and shows that the variance of the boot strap estimates can be smaller than those of the cross-validated estimates.
Journal of Statistical Computation and SimulationError-rate estimation in two-group discriminant analysis using the linear discriminant function
19 Citations1990S. Ganeshanandam, W. J. Krzanowski
Pattern RecognitionImproving k-nearest neighbor density and error estimates
19 Citations1993Ljubomir Buturović
Modified formulas for density estimator are proposed, based on the analysis of the bias and the variance expressions, and modified density estimators are then used for Bayes error estimation.
PAC-like upper bounds for the sample complexity of leave-one-out cross-validation
19 Citations1996Sean B. Holden
This paper addresses the following question: if the authors have n training examples what is the probability that the leave-one-out cross-validation estimate differs from the actual error probability by more than a constant c?
Strong Minimax Lower Bounds for Learning
17 Citations1998Abor Lugosi, Dana Ron
Communications in Statistics - Simulation and ComputationBias in error rate estimates in discriminant analysis when stepwise variable selection is employed
16 Citations1991Rutter carolyn, Flack Virgina +1 more
Network Computation in Neural SystemsSample sizes for multiple-output threshold networks
16 Citations1991John Shawe‐Taylor, Martin Anthony
Sample sizes for sigmoidal neural networks
15 Citations1995John Shawe‐Taylor
The theory of Probably Approximately Correct (PAC) learning is applied to feedforward neural networks with sigmoidal activation functions and it is shown that the asymptotic bound on the sample size required for learning with increasing accuracy 1 – c and decreasing probabllty of failure d is o((l/e)(wlog(l/c) + (WN)2 +log( l/6)),
Machine LearningStrong Minimax Lower Bounds for Learning
15 Citations1998András Antos, Gábor Lugosi
This paper shows that for several natural k-parameter concept classes, for any sequence of learning rules {gn}, there exists a fixed distribution of X and a fixed conceptC such that the expected error is larger than a constant timesk/n for infinitely manyn.
TechnometricsError-Rate Estimation in Multiple-Group Linear Discriminant Analysis
14 Citations1996David Hirst
Pattern RecognitionSmoothed additive estimators for non-error rates in multiple discriminant analysis
14 Citations1985Gerhard Tutz
In simulation experiments with normal, uniform and discrete distributions the smoothed additive estimators with fixed and variable smoothing parameter are compared to the leaving-one out method and the resubstitution method with respect to bias and variance.
Evaluating usefulness for dynamic classification
13 Citations1998Gholamreza Nakhaeizadeh, Charles Taylor +1 more
It is argued that usefulness can be used to improve the performance of classification rules, as well as to reduce their storage and derivation, in a dynamic setting, in which the distribution of at least one class is changing with time.
Journal of Computer and System SciencesCharacterizing Rational versus Exponential Learning Curves
11 Citations1997Dale Schuurmans
It is shown that somewhere dense chains always force rational convergence in the worst case, but exponential convergence can always be achieved for nowhere dense chains.
Journal of ClassificationA Monte Carlo study of the 632 bootstrap estimator of error rate
10 Citations1991Garrett M. Fitzmaurice, W. J. Krzanowski +1 more
There was no evidence to support the contention that the 632 bootstrap error rate estimator only performs well for a restricted range of true error rates, although the estimator's performance did vary with the true error rate.
SSRN Electronic JournalStrong Minimax Lower Bounds for Learning
10 Citations1997András Antos, Gábor Lugosi
Pattern RecognitionOn the asymptotic properties of smoothed estimators of the classification error rate
10 Citations1988M. Pawlak
The consistency of the estimate under very general conditions is established and asymptotic theory reveals that the relative deficiency of the counting estimate with respect to the smoothed one can tend to infinity as the sample size increases.
Communications in Statistics - Simulation and ComputationBootstrapped and smoothed classification error rate estimators
10 Citations1988Steven Snapinn, James D. Knoke
It is shown that the use of a bootstrap adjustment to reduce the bias of the NS method results in an estimator which combines the advantages of small bias with low variance, and is therefore preferable to existing resampling estimators.
Communications in Statistics - Simulation and ComputationBIAS in apparent classification rates in stepwise discriminant analysis
8 Citations1992Alvin C. Rencher
Pattern Recognition LettersAn optimal error rate estimator based on average conditional error rate: Asymptotic results
6 Citations1986David J. Hand
An asymptotically optimal distribution for choosing the classified sample with which to estimate the average conditional error rate is presented, which leads to an estimator with smaller asymPTotic variance than the standard form.
On the accuracy of a bootstrap estimate of the classification error
6 Citations2003Šarūnas Raudys
Analytical and simulation studies show that a variance of the bootstrap estimator discussed is lower than that of the commonly used leave-one-out estimator only when sample size is extremely small or when the classification error is large.
Pattern Recognition LettersA comparison of two average conditional error rate estimators
5 Citations1987Garrett M. Fitzmaurice, David J. Hand
It is shown how choice of a good metric in nearest neighbour estimates of posterior probability can lead to improved average conditional error rate estimates.
Computers & Mathematics with ApplicationsA shrunken leaving-one-out estimator of error rate
4 Citations1987David J. Hand
A new error rate estimator is presented based on shrinking the leaving-one-out estimate, and it is shown to perform very well.
Pattern RecognitionOn the minimum probability of error of classification with incomplete patterns
4 Citations1990Qiuming Zhu
The traditional decision theory is extended to the classifications with incomplete feature sets and shows that in case of classifying incomplete patterns, the Bayes classifier constructed on the marginal distributions of presented features also minimizes the probability of error.
Pattern RecognitionA nonparametric bound for the bayes error
3 Citations1995A. Ruiz-Jimeno
This paper presents a nonparametric upper bound on the Bayes wrror with a built-in statistical test and can be considered as an extension of the Kolmogorov-Smirnov test.
Computers & Mathematics with ApplicationsError rate estimation by mixture decomposition
1 Citations1987David J. Hand, Garrett M. Fitzmaurice
It is shown how error rate estimation may be viewed as a problem of mixture decomposition and the average conditional error rate approach to estimation and the effectiveness of one particular decomposition method by simulation is explored.
…