A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> 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 paper was first published in Russian as Вапник В. Н. and Червоненкис А. Я. О равномерноЙ сходимости частот появления событиЙ к их вероятностям. Теория вероятностеЙ и ее применения 16(2), 264–279 (1971). <s> BIB001 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> Abstract Two distribution-free upper bounds are given for the true error rate of a classifier, using the resubstitution error estimate. These bounds apply when the classifier is selected from a finite decision rule set. Both improve a bound proposed by Vapnik (1982). One of them is in a way optimal, while however presenting the disadvantage to be not analytic and requiring to be computed numerically for a given situation. A quantitative comparison of these bounds is provided, with realistic parameter values taken from classification trees and histogram discrimination rules. <s> BIB002 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> Preface * Introduction * The Bayes Error * Inequalities and alternatedistance measures * Linear discrimination * Nearest neighbor rules *Consistency * Slow rates of convergence Error estimation * The regularhistogram rule * Kernel rules Consistency of the k-nearest neighborrule * Vapnik-Chervonenkis theory * Combinatorial aspects of Vapnik-Chervonenkis theory * Lower bounds for empirical classifier selection* The maximum likelihood principle * Parametric classification *Generalized linear discrimination * Complexity regularization *Condensed and edited nearest neighbor rules * Tree classifiers * Data-dependent partitioning * Splitting the data * The resubstitutionestimate * Deleted estimates of the error probability * Automatickernel rules * Automatic nearest neighbor rules * Hypercubes anddiscrete spaces * Epsilon entropy and totally bounded sets * Uniformlaws of large numbers * Neural networks * Other error estimates *Feature extraction * Appendix * Notation * References * Index <s> BIB003 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> This paper concerns the use of real-valued functions for binary classification problems. Previous work in this area has concentrated on using as an error estimate the ‘resubstitution’ error (that is, the empirical error of a classifier on the training sample) or its derivatives. However, in practice, cross-validation and related techniques are more popular. Here, we devise new holdout and cross-validation estimators for the case where real-valued functions are used as classifiers, and we analyse theoretically the accuracy of these. <s> BIB004 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> The support-vector network is a new learning machine for two-group classification problems. The machine conceptually implements the following idea: input vectors are non-linearly mapped to a very high-dimension feature space. In this feature space a linear decision surface is constructed. Special properties of the decision surface ensures high generalization ability of the learning machine. The idea behind the support-vector network was previously implemented for the restricted case where the training data can be separated without errors. We here extend this result to non-separable training data. ::: ::: High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated. We also compare the performance of the support-vector network to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition. <s> BIB005 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> We study model selection strategies based on penalized empirical loss minimization. We point out a tight relationship between error estimation and data-based complexity penalization: any good error estimate may be converted into a data-based penalty function and the performance of the estimate is governed by the quality of the error estimate. We consider several penalty functions, involving error estimates on independent test data, empirical VC dimension, empirical VC entropy, and margin-based quantities. We also consider the maximal difference between the error on the first half of the training data and the second half, and the expected maximal discrepancy, a closely related capacity estimate that can be calculated by Monte Carlo integration. Maximal discrepancy penalty functions are appealing for pattern classification problems, since their computation is equivalent to empirical risk minimization over the training data with some labels flipped. <s> BIB006 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> In this chapter, we revise several methods for SVM model selection, deriving from different approaches: some of them build on practical lines of reasoning but are not fully justified by a theoretical point of view; on the other hand, some methods rely on rigorous theoretical work but are of little help when applied to real–world problems, because the underlying hypotheses cannot be verified or the result of their application is uninformative. Our objective is to sketch some light on these issues by carefully analyze the most well–known methods and test some of them on standard benchmarks to evaluate their effectiveness. <s> BIB007 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> In this paper, we review the k–Fold Cross Validation (KCV) technique, applied to the Support Vector Machine (SVM) classification algorithm. We compare several variations on the KCV technique: some of them are often used by practitioners, but without any theoretical justification, while others are less used but more rigorous in finding a correct classifier. The last ones allow to establish an upper– bound of the error rate of the SVM, which represent a way to guarantee, in a statistical sense, the reliability of the classifier and, therefore, turns out to be quite important in many real–world applications. Some experimental results on well–known benchmarking datasets allow to perform the comparison and support our claims. <s> BIB008 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> The Maximal Discrepancy (MD) is a powerful statistical method, which has been proposed for model selection and error estimation in classification problems. This approach is particularly attractive when dealing with small sample problems, since it avoids the use of a separate validation set. Unfortunately, the MD method requires a bounded loss function, which is usually avoided by most learning algorithms, including the Support Vector Machine (SVM), because it gives rise to a non-convex optimization problem. We derive in this work a new approach for rigorously applying the MD technique to the error estimation of the SVM and, at the same time, preserving the original SVM framework. <s> BIB009 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Introduction <s> In this paper, we focus the attention on one of the oldest problems in pattern recognition and machine learning: the estimation of the generalization error of a classifier through a test set. Despite this problem has been addressed for several decades, the last word has not yet been written, as new proposals continue to appear in the literature. Our objective is to survey and compare old and new techniques, in terms of quality of the estimation, easiness of use, and rigorousness of the approach. <s> BIB010
The main objective of supervised learning methods, like Neural Networks (NNs)  and Support Vector Machine (SVM) BIB005 , consists in estimating an input-output relationship by exploiting a set of patterns, named the training set. In general, the probability distribution originating the data is unknown and additional a priori information is seldom available, therefore this relationship must be inferred exclusively from the available data. A classifier is considered to be reliable and effective if it does not simply memorize the training samples, but if it can learn from them: in other words, a "good" trained model must be able to capture the underlying phenomenon characterizing the observed patterns and correctly predict the labels of new and previously unobserved inputs, if originated from the same distribution of the training set. This capacity is defined as the generalization ability of a classifier, while the misclassification rate on unseen patterns is known as the generalization error rate. Obviously, if we knew the probability distribution of the data, we could exactly compute the generalization error. However, in practice, statistical estimates are computed, instead, which consist in upper bounding the generalization error, in probability, according to some user-defined confidence. This approach is not only of theoretical interest, but of paramount importance in many application fields, such as, for example, forensic statistics  . The use of statistical upper bounds for measuring the generalization ability of a classifier has been extensively addressed, in recent years, by the Machine Learning community BIB006 BIB003 BIB001 BIB002 . Two main categories of methods exist to face this problem: in-sample and out-of-sample techniques  BIB007 . Insample procedures, such as the Maximal Discrepancy and the Rademacher Complexity BIB006 BIB009 , compute an estimation of the generalization error without exploiting a separate test set: in fact, the training set is used for both building the model and estimating the misclassification rate. Though providing new results and insights on the problem of error estimation and on the classification algorithms themselves, these methods aim at covering widely general cases and then result to be often inapplicable in practice  . In this work, instead, we focus on the more widespread out-of-sample methods BIB007  , where the generalization error is estimated by exploiting a separate test set, whose samples are independent of the training data. Many statistical results are available in the literature for this purpose: the objective of this paper is to survey -242 DOI 10.2478/jaiscr-2014-0016 some old and new ones and compare their performance under different conditions (e.g. by varying the amount of test data), in order to draw on and expand the analysis performed in BIB010 . Note that the test set approach can also be extended to resampling techniques BIB008 , as shown in the Appendix A of this paper in the case of the wellknown K-fold Cross Validation (KCV) BIB004 , where the procedure of splitting the original dataset into a training and a test set is iterated several times. As this and other resampling methods extract only a limited amount of samples, to be used as a test set, the identification of effective methods (i.e. tight generalization error bounds) becomes quite important in these cases as well.