Observations on bagging

Bagging is a device intended for reducing the prediction error of learning algorithms. In its simplest form, bagging draws bootstrap samples from the training sample, ap-plies the learning algorithm to each bootstrap sample, and then averages the resulting prediction rules. We investigate bagging in a simplified situation: the prediction rule produced by a learning algorithm is replaced by a simple real-valued statistic of i.i.d. data. We extend the definition of bagging from statistics (defined on samples) to statistical functionals (defined on distributions), and we study the von Mises expansion of bagged statistical functionals. We show that a bagged functional is smooth in the sense that the von Mises expansion is finite of length 1 + resample size M. The resample size may be different from the original sample size N; it acts as a smoothing parameter, where smaller M means more smoothing. We then study the effects of bagging on U-statistics. U-statistics of high order can describe complex dependencies, and yet they admit a rigorous asymptotic analysis. We show that bagging U-statistics often but not always decreases variance, whereas it always increases bias. The most striking finding, however, is an equivalence between bagging based on re-sampling with and without replacement: the respective resample sizes Mwith = αwithN and Mw/o = αw/oN produce very similar bagged statistics if αwith = αw/o/(1 − αw/o). While our derivation is limited to U-statistics, the equivalence seems to be universal. We illustrate this point in simulations where bagging is applied to cart trees