Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
Harald Steck, Tommi Jaakkola
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).