A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Scenario 1 -Results <s> We revisit the problem of interval estimation of a binomial proportion. The erratic behavior of the coverage probability of the stan- d ardWaldconfid ence interval has previously been remarkedon in the literature (Blyth andStill, Agresti andCoull, Santner andothers). We begin by showing that the chaotic coverage properties of the Waldinter- val are far more persistent than is appreciated. Furthermore, common textbook prescriptions regarding its safety are misleading and defective in several respects andcannot be trusted . This leads us to consideration of alternative intervals. A number of natural alternatives are presented, each with its motivation and con- text. Each interval is examinedfor its coverage probability andits length. Basedon this analysis, we recommendthe Wilson interval or the equal- tailedJeffreys prior interval for small n andthe interval suggestedin Agresti andCoull for larger n. We also provide an additional frequentist justification for use of the Jeffreys interval. <s> BIB001 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Scenario 1 -Results <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> BIB002
As a first step, we analyze the three generalization error bounds fixing the confidence level and the empirical misclassification rate, while varying the number of patterns in the test set. For this purpose, let us suppose to set δ = 5% and let us vary the cardinality of the test set X in the range n ∈ BIB002 200] , in accordance with the experiments performed elsewhere in the literature (e.g. see BIB001 ). Large datasets are not taken in account for two main reasons: -as n increases, the bounds tend to be characterized by a similar performance; -as we noted in the introduction, these bounds can also be exploited when applying the KCV procedure (see also Appendix A), where only small subsets of the dataset are available for testing purposes (e.g. 10% of the original dataset  ). Figs. 1 and 2 show the estimationsL (see Eq. (7)) for the three bounds in the case ofL n = 25% andL n = 0%, respectively. We note that: -WIL and CP give similarL values, even if it is worth observing that WIL is not rigorous and, then, there is no guarantee about the coverage probability of the bound; -NOR always outperforms WIL and CP, but, besides being non-rigorous, its error estimation is useless whenL n is small, as predicted by theory and as clearly shown in Fig. 2 (whereL = 0% ∀n using NOR). Now we fix n = 10 and n = 200 (the extreme values we used for the previous experiments) and we plot the trend ofL by varyingL n in the range of interest for classification problems [0%, 50%]. We observe that: -when n is small (Fig. 3) , CP results to be sometimes looser than the non-rigorous approaches NOR and WIL; -as n increases (Fig. 4) , the three bounds tend to predict similar values of L, as expected by theory (i.e. the binomial distribution can be safely approximated by a normal distribution). As CP is sometimes loose, it is interesting to compute the true coverage probability for the three bounds BIB001 , so to verify if the looseness is justified by rigorousness requirements. Different trends of C (L, n) are shown: -Figs. 5 and 6 present the coverage probability, when n is set, respectively, to 10 and 200 and L is varied in the range [0%, 50%]. CP is the only guaranteed bound, as expected, while both WIL and NOR, despite giving tighter estimates for L, are characterized by a coverage probability which sometimes falls below the nominal confidence (1 − δ = 95%), even when n is increased; -Figs. 7 and 8 present the coverage probability, when L is respectively set 4 to 1% and 25% and n is varied in the range BIB002 200] . As in the previous experiments, CP represents the only guaranteed bound, even if WIL results to be a valuable alternative, albeit non-rigorous, when either the true L is small or the nominal confidence boundary can be violated in practice. 