TL;DR
This paper introduces and evaluates "out-of-bag" (OOB) estimates for generalization error in bagging ensembles. While OOB estimates are computationally efficient, they tend to be overly optimistic. The authors propose and validate two correction methods to improve OOB estimates, with one showing significant promise for practical use.
What Problem Does This Paper Address?
When building machine learning models, especially complex ones like decision trees or neural networks, it's crucial to know how well they will perform on unseen data – this is called generalization error. A common way to estimate this is k-fold cross-validation, where the data is split multiple times. However, this can be computationally expensive, especially when training individual models is time-consuming. Bagging (Bootstrap Aggregating) is a technique that builds an ensemble of models by training each on a bootstrap sample of the data. A natural question arises: can we use the information already generated during bagging to estimate generalization error more efficiently? The paper tackles this by exploring the "out-of-bag" (OOB) estimate, which uses data points not included in a model's training set to evaluate that model. The core problem is that while OOB is fast, its accuracy and the confidence it provides in its estimates are questionable.
Methods
The paper's primary contribution is the investigation and improvement of out-of-bag (OOB) estimates for generalization error in bagging.
- Out-of-Bag (OOB) Estimation: For each predictor (model) trained on a bootstrap sample, its performance is evaluated on the data points omitted from that specific bootstrap sample. The OOB estimate for the entire ensemble is then derived from these individual OOB predictions. This avoids generating entirely new models, as is done in cross-validation.
- Test Error: To get a ground truth for comparison, a separate test set is used. The ensemble's predictions on this test set represent the empirical generalization error.
- Statistical Tests:
- Paired Difference t-test: Used to compare the average estimates of generalization error (OOB, corrected OOB, cross-validation) against the test error over 1000 trials. This tests for systematic bias.
- Two-Sample t-test: Used on each trial to assess if the estimate significantly differs from the test error. The frequency of "failures" (significant differences) in these tests helps evaluate the confidence intervals provided by the estimates.
- OOB Corrections:
- Test Error Correction: This method aims to correct the OOB estimate by considering the voting patterns of predictors on test examples. It simulates OOB voting by subsampling votes and uses statistical properties to estimate the expected error. However, this method is not practical for estimating generalization error on the training set itself, as it requires test data.
- Out-of-Bag Correction: This is a more practical approach that uses the OOB voting patterns on the training examples to estimate the distribution of "bagging" votes. It makes a heuristic assumption about the distribution of these votes to derive a corrected estimate.
Datasets
The authors used 10 two-class datasets from the UCI repository and the C4.5 distribution. These datasets were chosen for their suitability for two-class problems and their use in developing generalization error estimation methods. Specific datasets mentioned include:
- BA (UCI cylinder bands)
- CR (C4.5 credit card applications)
- FL (UCI solar flare)
- IO (UCI ionosphere)
- M1, M2, M3 (C4.5 monk datasets)
- PI (UCI Pima Indians diabetes)
- PR (UCI promoter gene sequence)
- SO (UCI sonar signals)
No new benchmarks were introduced; existing datasets were used for evaluation.
Key Insights and Ideas
- OOB is Fast, but Optimistic: The OOB estimate is computationally much cheaper than k-fold cross-validation because it reuses existing predictions. However, it tends to be overly optimistic, meaning it underestimates the true generalization error.
- Confidence Intervals are Misleading: Both OOB and standard 10-fold cross-validation often produce confidence intervals that are too narrow, giving a false sense of confidence in the accuracy of the error estimate. A supposedly 95% confidence interval might only be correct 90% or even 75% of the time.
- Corrections are Necessary: To make OOB estimates reliable, corrections are needed. The paper explores two types of corrections.
- Test Error Correction is Promising but Impractical: The "test error correction" method shows excellent results in terms of unbiasedness and good confidence intervals. However, its reliance on test data makes it unsuitable for estimating generalization error when only training data is available.
- Out-of-Bag Correction Offers a Practical Improvement: The "out-of-bag correction," which uses training data, is a significant improvement over the uncorrected OOB estimate. While not as perfect as the test error correction, it offers a much better balance of accuracy and practicality.
Key Results
- OOB vs. 10-Fold CV: On average, the OOB estimate differed from test error by 0.52%, and 10-fold CV by 0.25%. Both showed a tendency to overestimate test error.
- Confidence Interval Reliability: For both OOB and 10-fold CV, the two-sample t-test revealed overoptimistic confidence levels, with an average of 8-9% of trials failing the 95% confidence test.
- Test Error Correction: This correction resulted in an average difference of only 0.04% from test error and showed no significant bias on most datasets. Its confidence intervals were much more reliable.
- Out-of-Bag Correction: This correction yielded an average difference of -0.08% from test error. It was better than uncorrected OOB and 10-fold CV, and its confidence intervals were more reliable, though still not perfect.
- C4.5 Results: Similar trends were observed when using the C4.5 algorithm, with the test error correction outperforming other methods.
Limitations and Future Work
- Test Error Correction Impracticality: The authors acknowledge that the "test error correction" is not practical for real-world scenarios where generalization error is estimated on training data.
- Heuristic Nature of OOB Correction: The "out-of-bag correction" relies on a heuristic assumption about the distribution of bagging votes, which might limit its theoretical guarantees.
- Inflated Confidence Levels: Even with the OOB correction, confidence intervals can still be inflated, suggesting further research is needed.
- Future Research: The authors emphasize the need for further research to develop generalization error estimates with fully trusted confidence intervals. They also suggest exploring how these corrections might perform with different learning algorithms and ensemble methods.
Summary updated