In ensemble learning, an agent takes a number of learners and combines their predictions to make a prediction for the ensemble. The algorithms being combined are called base-level algorithms. Random forests are an example of an ensemble method, where the base-level algorithm is decision tree, and the predictions from the individual trees are averaged or are used to vote for a prediction.

In boosting, there is a sequence of learners in which each one learns from the errors of the previous ones. The features of a boosting algorithm are:

• •

  There is a sequence of base learners (that can be different from each other or the same as each other), such as small decision trees, or (squashed) linear functions

• •

  Each learner is trained to fit the examples that the previous learners did not fit well

• •

  The final prediction is a mix (e.g., sum, weighted average or mode) of the predictions of each learner.

The base learners can be weak learners, in that they do not need to be very good; they just need to better than random. These weak learners are then boosted to be components in the ensemble that performs better than any of them.

A simple boosting algorithm is functional gradient boosting which can be used for regression, as follows. The final prediction, as a function of the inputs, is the sum

where $p_0(X)$ is an initial prediction, say the mean, and each $d_i$ is the difference from the previous prediction. Let the $i$th prediction be $p_i(X)=p_0(X)+d_1(X)+\mathrm{\dots }+d_i(X)$. Then $p_i(X)=p_{i-1}(X)+d_i(X)$. Each $d_i$ is constructed so that the error of $p_i$ is minimal, given that $p_{i-1}$ is fixed. At each stage, the base learner learns $d_i$ to minimize

The $i$th learner can learn $d_i(e)$ to best fit $Y_i(e)-p_{i-1}(e)$. This is equivalent to learning from a modified data set, where the previous prediction is subtracted from the actual value of the training set. In this way, each learner is made to correct the errors of the previous prediction.

The algorithm is shown in Figure 7.19. Each $p_i$ is a function that, given an example, returns a prediction for that example. $E_i$ is a new set of examples, where for each $e\in Es$, the latest prediction, $p_{i-1}(e)$, is subtracted from the value of the target feature $Y(e)$. The new learner is therefore learning from the errors of the old learner. Note that $E_i$ does not need to be stored; the examples in $E_i$ can be generated as needed. The function $d_i$ is computed by applying the base learner to the examples $E_i$.