bootstrap aggregating, or bagging, to tree learners. Given a training set = , ..., with responses = , ..., , bagging repeatedly (B times) selects a random sample with replacement of the training set and fits trees to these samples: For = 1, ..., : Sample, with replacement, training examples from , ; call these , . Train a classification or regression tree on , . After training, predictions for unseen samples can be made by averaging the predictions from all the individual regression trees on : or by taking the in the case of classification trees. This bootstrapping procedure leads to better model performance because it decreases the variance of the model, without increasing the bias. This means that while the predictions of a single tree are highly sensitive to noise in its training set, the average of many trees is not, as long as the trees are not correlated. Simply training many trees on a single training set would give strongly correlated trees (or even the same tree many times, if the training algorithm is deterministic); bootstrap sampling is a way of de-correlating the trees by showing them different training sets. Additionally, an estimate of the uncertainty of the prediction can be made as the standard deviation of the predictions from all the individual regression trees on : The number of samples/trees, , is a free parameter. Typically, a few hundred to several thousand trees are used, depending on the size and nature of the training set. An optimal number of trees can be found using cross-validation, or by observing the out-of-bag error: the mean prediction error on each training sample , using only the trees that did not have in their bootstrap sample. The training and test error tend to level off after some number of trees have been fit. From bagging to random forests The above procedure describes the original bagging algorithm for trees. Random forests also include another type of bagging scheme: they use a modified tree learning algorithm that selects, at each candidate split in the learning process, a random subset of the features. This process is sometimes called "feature bagging". The reason for doing this is the correlation of the trees in an ordinary bootstrap sample: if one or a few features are very strong predictors for the response variable (target output), these features will be selected in many of the trees, causing