Bias-Corrected Bootstrap and Model Uncertainty

Harald Steck, Tommi S. JaakkolaNeurIPS 2003 · OpenReview

Introduction

The bootstrap method is a staple in statistics for estimating the uncertainty of a model. In the context of graphical models—where the goal is to learn the web of dependencies between variables—researchers often use bootstrap samples to determine which edges appear consistently. However, this process inherently biases results toward overly complex structures.

Because bootstrap samples are created by resampling with replacement, they contain duplicate data points that do not exist in the original distribution. This "spurious discreteness" tricks standard scoring functions, such as the Bayesian Information Criterion (BIC) or Akaike Information Criterion (AIC), into perceiving more structure in the data than actually exists. Consequently, the learned models contain too many edges, leading to overconfidence in dependencies that may merely be artifacts of the resampling process.

The Bias-Correction Method

To address this overestimation, the authors derive a leading-order bias correction by connecting the maximum likelihood score of a graphical model to the plug-in estimator for entropy.

  1. Entropy Bias: The plug-in estimator for entropy tends to underestimate true entropy. The bootstrap bias for entropy is approximately $\frac{1}{2N}(|X| - 1)$.
  2. The "One-Half" Rule: Extending this to scoring functions like BIC, the bias induced by the bootstrap is approximately $\frac{1}{2}|\theta|$, where $|\theta|$ is the number of independent parameters (model complexity). Interestingly, while training error underestimates test error by the full AIC penalty, the bootstrap's "hallucinated" structure bias is exactly half of that amount.
  3. Correction: To correct for this, the authors propose amending the scoring function applied to bootstrap samples by subtracting this bias term. This effectively adds a penalty equal to half of the AIC penalty to the bootstrap scores.

Experimental Results

The proposed correction was evaluated on two primary datasets:

  • ALARM Network: A classic synthetic Bayesian network representing a medical diagnostic system (37 variables, 46 edges), providing a known ground truth.
  • Yeast Pheromone Response Data: A real-world gene-expression dataset (33 variables, 320 data points), representing the noisy, limited-data scenarios where the bootstrap is most commonly used.

The results demonstrate a significant reduction in spurious complexity. Naive bootstrap shifts the distribution toward models that are significantly more complex than those learned from the original data.

Edge count comparison across datasets

As shown in the table above, in the ALARM network ($N=300$), the original data suggested approximately 41 edges. The naive bootstrap inflated this to ~49 edges. The bias-corrected bootstrap (boot BC) successfully brought this back down to ~40.7 edges, aligning closely with the original data. The effect was even more dramatic in the noisy yeast pheromone data: the naive bootstrap estimated ~135.7 edges (massive overfitting), while the bias-corrected version estimated ~57.8 edges, much closer to the ~63 edges found in the reference data.

Furthermore, without correction, the bootstrap can make an edge appear "certain" (e.g., appearing in 90%+ of samples) when it is actually quite uncertain.

Scatter plots comparing edge confidences

Scatter plots comparing edge confidences reveal that the bias-corrected bootstrap provides confidence levels that are far more consistent with the original data than the naive approach, successfully mitigating overconfidence in spurious edges.

Limitations and Future Work

While highly effective, the correction is based on a second-order Taylor expansion (leading-order in $N$). It is not a perfect fix for extremely small datasets where higher-order terms might become significant. Additionally, the experiments utilized the K2 algorithm and local search with simulated annealing; while the bias is largely independent of the search strategy, different algorithms might interact with the bias in unique ways. Finally, the paper notes that the "delete-d jackknife" method also shows low bias, but its meaningfulness for estimating model variability remains an open topic for future exploration.

Summary updated

Abstract

The bootstrap has become a popular method for exploring model (structure) uncertainty. Our experiments with artificial and real- world data demonstrate that the graphs learned from bootstrap samples can be severely biased towards too complex graphical mod- els. Accounting for this bias is hence essential, e.g., when explor- ing model uncertainty. We find that this bias is intimately tied to (well-known) spurious dependences induced by the bootstrap. The leading-order bias-correction equals one half of Akaike’s penalty for model complexity. We demonstrate the effect of this simple bias-correction in our experiments. We also relate this bias to the bias of the plug-in estimator for entropy, as well as to the differ- ence between the expected test and training errors of a graphical model, which asymptotically equals Akaike’s penalty (rather than one half).
BibTeX
@inproceedings{steck2003bias,
  author = {Harald Steck and Tommi S. Jaakkola},
  title = {{Bias-Corrected Bootstrap and Model Uncertainty}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2003},
  url = {https://openreview.net/forum?id=HJZ8PPWdbr},
}
Figure