How Accurate Are Bootstrap Error Estimates in Small Samples? Exact Inclusion Probabilities and a Comparison of .632, .632+ and Cross-Validation on Four Benchmark Data Sets

Machine learning models trained on small data sets need honest estimates of their error. The bootstrap .632 and .632+ estimators were designed for that. I prove that the probability that a given point appears in a bootstrap sample, one minus (1 minus 1 over n) to the power n, falls to 1 minus 1 over e, about 0.632, and I derive the exact mean and variance of the number of distinct points in a bootstrap sample. I then compare five estimators against the true error of each fitted model, measured on held-out data, in 4,800 subsamples of 40 or 100 points from four UCI data sets (banknote, breast cancer, ionosphere, sonar), with one-nearest-neighbour and logistic classifiers. The .632+ estimator has the lowest average root mean squared error (0.0465, against about 0.051 for the others). Ten-fold cross-validation is almost unbiased (mean absolute bias 0.004) but no more accurate than the bootstrap estimators. The .632 estimator underestimates error by about 3 points on average for both classifiers and by up to 8.6 points, and the leave-one-out bootstrap overestimates it. All estimators track the expected error, not the error of the particular model: the correlation between the cross-validation estimate and the true error averages minus 0.12 across the 16 cells.