Bootstrap aggregating

Bootstrap aggregating, usually called bagging, is an ensemble meta-algorithm in machine learning that improves the stability and accuracy of classification and regression methods while reducing variance and overfitting. Given a training set of n examples, bagging draws several new training sets by sampling uniformly with replacement, so each one repeats some examples and leaves others out. For large n each such bootstrap sample holds about 63 percent of the distinct original examples, and the left-out examples form the out-of-bag set. A separate model is fitted to each bootstrap sample and the results are combined by averaging for regression or by voting for classification. Bagging helps unstable procedures such as neural networks and classification and regression trees, and can slightly harm stable methods such as k-nearest neighbors. It was proposed by Leo Breiman, who developed the idea in 1994 and coined the short name, building on the bootstrap of Bradley Efron.