PaperlayerView exact revision on arXiv

Source-linked AI summary

Confidence Intervals for Random Forests: The Jackknife and the Infinitesimal Jackknife

Stefan Wager, Trevor Hastie, Bradley Efron

arXiv:1311.4555v2stat.MLstat.COstat.ME

TL;DR

Variance estimation for bagged predictors and random forests is complicated by sampling variability and Monte Carlo noise from finite bootstrap ensembles. The paper develops bias-corrected jackknife and IJ methods, finds that IJ needs 1.7 times fewer replicates than jackknife for a given accuracy, and studies the estimators' sampling behavior.

  • Problem

    Estimating the sampling variance of bagged predictors from pre-existing bootstrap replicates must account for both sampling noise and finite-bootstrap Monte Carlo noise.

  • Method

    The paper studies jackknife-after-bootstrap and infinitesimal jackknife estimators, develops bias corrections, and derives a formula for the IJ estimator's sampling variance.

  • Results

    The IJ requires 1.7 times fewer bootstrap replicates than the jackknife for a given accuracy, while averaging their estimates can often reduce sampling bias.

  • Takeaways & Limitations

    These methods provide practical standard-error estimates for bagged predictors and random forests using the bootstrap replicates already used to form predictions.

  • Takeaways & Limitations

    A formal and general understanding of the relative biases of the limiting jackknife and IJ estimators remains open because the analysis relies on a heuristic approximation.

Abstract

from arXiv · show

We study the variability of predictions made by bagged learners and random forests, and show how to estimate standard errors for these methods. Our work builds on variance estimates for bagging proposed by Efron (1992, 2012) that are based on the jackknife and the infinitesimal jackknife (IJ). In practice, bagged predictors are computed using a finite number B of bootstrap replicates, and working with a large B can be computationally expensive. Direct applications of jackknife and IJ estimators to bagging require B on the order of n^{1.5} bootstrap replicates to converge, where n is the size of the training set. We propose improved versions that only require B on the order of n replicates. Moreover, we show that the IJ estimator requires 1.7 times less bootstrap replicates than the jackknife to achieve a given accuracy. Finally, we study the sampling distributions of the jackknife and IJ variance estimates themselves. We illustrate our findings with multiple experiments and simulation studies.

1. Introduction

The paper develops practical variance and standard-error estimates for bagged predictors and random forests using pre-existing bootstrap replicates. It analyzes both sampling and finite-bootstrap Monte Carlo noise, proposing corrections and comparing jackknife and IJ efficiency.

  • Motivation: The paper estimates the variance of bagged predictors and random forests using jackknife-after-bootstrap and infinitesimal jackknife methods.The estimates use bootstrap replicates already generated for the bagged prediction, requiring moderate computational overhead.
  • Random-forest examples: Random-forest error bars estimate how predictions may change under a new training set, while differing error-bar sizes indicate differing predictive confidence.The Auto MPG example also suggests residual noise not explained by the available predictor variables.
  • Sources of noise: Finite bootstrap replicates introduce Monte Carlo noise in addition to sampling noise, complicating variance estimation.The paper studies both sources of variability and their effects on jackknife and IJ estimates.
  • Main results: 1.7 times fewer bootstrap replicates are needed by the IJ than by the jackknife to achieve a given accuracy.The paper attributes this efficiency to the IJ's lower Monte Carlo variance and also develops bias-corrected estimators.
  • Main results: The paper compares the sampling biases of the jackknife and IJ and finds evidence that averaging their variance estimates can be close to unbiased.The jackknife shows upward sampling bias, whereas the IJ can show downward bias when Monte Carlo effects disappear.

2. Estimating the Variance of Bagged Predictors

The paper develops jackknife and infinitesimal jackknife estimates of the sampling variance of bagged predictors, including random forests, using the bootstrap replicates already computed for prediction. It analyzes finite-bootstrap effects and introduces bias corrections that reduce the required number of replicates while improving stability.

  • Core estimators: The main result is variance estimates for bagged predictors that can be computed from the same bootstrap replicates used to form predictions.Random forests are treated as a special class of bagged predictors.
  • Finite-B effects: Bagged predictions combine sampling noise with Monte Carlo noise from using a finite number B of bootstrap replicates.The paper studies both sources because finite-B effects can distort variance estimates.
  • Finite-B effects: The jackknife and IJ can badly overestimate sampling variance when B is small, so the paper develops bias-corrected versions.The corrections address Monte Carlo bias arising when bootstrap noise is conflated with sampling noise.
  • Finite-B effects: B = Θ(n^1.5) replicates may be required by simple estimators, whereas the bias-corrected versions require only B = Θ(n) replicates.This reduces the bootstrap computation needed to bring Monte Carlo noise down to the level of inherent sampling noise.
  • Estimator comparison: 1.7 times fewer bootstrap replicates are required by the IJ than by the jackknife to achieve a given level of Monte Carlo error.The IJ also has lower Monte Carlo noise than the jackknife in the reported finite-B comparison.
  • Sampling behavior: The jackknife has upward sampling bias, the IJ can have downward bias, and their arithmetic mean is often closer to unbiased than either estimator alone.The paper also proposes a sampling-variance estimator for the IJ itself.

3. Random Forest Experiments

The paper applies jackknife-based variance estimation to random forests and uses it to interpret how feature subsampling affects prediction stability, bias, and variance. Across the experiments, intermediate values of m often provide the best balance, while the variance reflects both individual-tree variability and tree correlation.

  • Variance estimation: Random forests are treated as bagged predictors with randomized base learners, so the bagging variance formulas and bias corrections apply directly.The auxiliary randomization adds diversity without changing the limiting correlations relevant to the variance estimates.
  • Variance estimation: The IJ-U estimator uses the bootstrap replicates already used to form the random forest prediction.The authors implemented IJ-U for random forests on top of the R package randomForest.
  • E-mail Spam Example: 95.1%, 95.2% and 94.7% are the test-set accuracies for m = 5, 19 and 57, respectively, with m = 5 or 19 appearing best.Here m = 57 corresponds to a bagged tree, whereas m = 5 strongly constrains splitting-variable choices.
  • E-mail Spam Example: m = 57 appears unstable, with high IJ-U standard errors suggesting predictions could change substantially with more training data.The authors interpret this pattern as possible overfitting and potential improvement with additional data.
  • E-mail Spam Example: m = 5 produces remarkably stable predictions, with almost all standard errors below 0.1, but its cautious probabilities suggest bias limits classification.The m = 19 forest generally makes more extreme predictions than m = 5 on the same e-mails, consistent with a better bias-variance balance.
  • California Housing Example: m = 4 minimizes mean sampling variance while m = 5 minimizes MSE on California housing, making values around 4 or 5 optimal by both criteria.The variance is U-shaped because large m increases tree correlation, while very small m increases the variance of individual trees.

4. Controlling Monte Carlo Error

The section analyzes Monte Carlo error in jackknife and IJ variance estimates caused by finite bootstrap replicates. It develops bias corrections, compares estimator stability and replicate requirements, and validates the results empirically and theoretically.

  • Monte Carlo error comparison: The jackknife requires 1.7 times more bootstrap replicates than the IJ to control Monte Carlo noise at a given level.With B replicates, IJ errors are on the same scale as jackknife errors with 1.7 · B replicates.
  • IJ behavior: The Monte Carlo MSE of the IJ depends mainly on the bootstrap variance of the base learner, so computational difficulty varies with that variance.The IJ bias grows linearly with the variance of the original estimator being bagged.
  • Monte Carlo error comparison: B = Θ(n) bootstrap iterations control Monte Carlo variance, but uncorrected estimators require B = Θ(n^1.5) to reduce bias to O(n^-0.5).The Monte Carlo MSE is often dominated by bias, especially for large n.
  • Bias correction: Bias-corrected J-U and IJ-U estimators remove Monte Carlo bias without noticeably increasing variance and need only B = Θ(n) replicates for MSE of order 1/n.The correction uses the bootstrap estimate of the base learner's variance; U denotes unbiased.
  • Empirical validation: For fixed B, jackknife estimates are less stable than IJ estimates, while both uncorrected methods are badly biased at small B.In the cholesterol example, the bias-corrected estimators appear to fix the bias without introducing instability.
  • Empirical validation: Theoretical formulas give a credible account of the relative merits of jackknife and IJ estimators in the numerical comparison.Figure 7 compares observed Monte Carlo bias and variance ratios with theoretical approximations.

5. Sampling Distribution of Variance Estimates

The section analyzes the sampling variability and bias of jackknife and IJ variance estimates, separating finite-bootstrap Monte Carlo effects from data-sampling effects. It derives an IJ sampling-variance formula and finds that averaging jackknife and IJ estimates can reduce bias, while the IJ can have lower overall mean squared error.

  • Sampling variance: The limiting analysis sends B to infinity to isolate sampling error from Monte Carlo error in jackknife and IJ variance estimates.The section studies the estimators’ sampling properties when bootstrap-replicate noise is absent.
  • Sampling variance: The IJ estimator’s sampling variance is approximated by a sum of independent first-order contributions from the observations.The approximation relies on independently drawn data and a plug-in estimate because the underlying distribution F is unknown.
  • Sampling variance: The IJ estimate’s coefficient of variation is fairly low on the cholesterol data, suggesting stable variance estimates in that example.The reported formula can nevertheless require many bootstrap replicates to stabilize and has upward Monte Carlo bias.
  • Sampling bias: Both estimators recover the first-order variance term on average, but the jackknife weights higher-order terms increasingly while the IJ drops them.This difference explains why their sampling biases can have opposite directions.
  • Sampling bias: In the n = 25 bagged-tree experiment, the mean of the jackknife and IJ estimates was nearly unbiased for the true variance.For the prostate cancer example, the jackknife stabilized at 0.093 and the IJ at 0.067, making 0.08 their arithmetic mean.
  • Simulation evidence: The bias-corrected IJ has systematically lower variance and can achieve lower overall mean squared error than the bias-corrected jackknife.The simulations report an exception for the “Noisy AND” experiment and leave a formal general bias analysis open.

6. Conclusion

The paper studies jackknife-after-bootstrap and IJ variance estimation for bagged predictors, proposes bias corrections, and derives a formula for IJ sampling variance. Experiments suggest that averaging the two estimators is often preferable from a sampling-bias perspective and provides useful insights for random forests.

  • The paper studies jackknife-after-bootstrap and IJ methods for estimating the variance of bagged predictors.
  • The authors propose bias-corrected versions after finding considerable Monte Carlo bias in both original estimators.
  • The paper provides a simple formula for the sampling variance of the IJ estimator.
  • The arithmetic mean of the jackknife and IJ estimators is often preferable to either original method from a sampling-bias perspective.
  • Experiments, including random forest examples, show how these methods can provide insights in realistic problems.

Appendix A. The Effect of Monte Carlo Noise on the Jackknife Estimator

The appendix analyzes finite-B Monte Carlo effects in the jackknife-after-bootstrap estimator. It explains why the estimator is upward biased with noisy bootstrap quantities and develops approximations for its bias and variance.

  • Finite-B analysis derives the Monte Carlo bias and variance of the jackknife-after-bootstrap variance estimate.
  • Bootstrap counts determine observation-specific quantities, with degenerate all-absent or all-present cases assigned a zero difference estimate.
  • The jackknife estimate is a sum of squares of noisy quantities, so finite-bootstrap noise creates upward bias.
  • As n and B grow, the relevant bootstrap-count expressions converge toward Gaussian limits and become uniformly integrable.
  • The appendix uses the central limit theorem to approximate the asymptotic Monte Carlo variance of the bootstrap differences.
  • The resulting simplifications use bootstrap estimates of base-learner variance that can be inspected on a random forest.

Appendix B. The IJ estimator and Hájek projections

The appendix connects the IJ estimator for bagged predictors to Hájek projections through an averaging-functional formulation. It also identifies the plug-in approximation needed for the connection and notes that this approximation can fail for counterexamples.

  • A bagged predictor can be expressed as an averaging functional applied to the empirical distribution of the observations.
  • The IJ estimate perturbs one observation’s empirical weight and uses the resulting change to estimate variance.
  • Samples from the empirical distribution are transformed into perturbed distributions by independently replacing observations with a selected data point.
  • For bagging, the plug-in approximation yields the sampling-variance expression used for the limiting IJ estimator.
  • The plug-in approximation can fail for constructed counterexamples, so general conditions guaranteeing its validity remain open.

Appendix C. Description of Experiments

The appendix details simulation designs and datasets used to evaluate variance estimates for bagged predictors and random forests. Experiments span synthetic regression settings, real-data examples, and multiple bootstrap configurations.

  • Real-data examples: Real-data experiments cover Auto MPG, California housing, prostate cancer, cholesterol, and e-mail spam datasets with regression or classification outcomes.The datasets range from 97 prostate-cancer subjects and 164 cholesterol subjects to 20,460 California neighborhoods and 4,601 e-mails.
  • Synthetic simulations: The main bagged-tree simulation uses 5-leaf regression trees, B = 10,000 bootstrap replicates, n = 500 observations, and 1,000 simulation runs.Data follow a step-function regression model with Gaussian noise.
  • Implementation details: Bootstrap replicate counts vary by experiment, including B = 40,000 for one random-forest fit, B = 1,000 for California housing, and B = 10,000 for Auto MPG.The Auto MPG variance uses the (bV_B−U)/2 estimator, while California housing uses random forests with eight features.
  • Synthetic simulations: A second tree simulation draws n = 25 points from a two-dimensional square and evaluates results over 2,000 simulation runs using B = 1,000 bootstrap replicates.The response is deterministically defined by whether the squared radius is at least one.
  • Evaluation procedure: Across simulations, a fixed test set is used while 100 training sets generate variance estimates at each test point, with Table 1 reporting average test-set performance.The test set contains 50 points except for Auto MPG, which uses its original test set of size 78.
Loading 1311.4555v2…