IEEE Geoscience and Remote Sensing Magazine - September 2015 - 91

The third tree ensemble algorithm, Gradient Boosted
Regression Trees (GBRT) [15], has a completely different
target as it aims to reduce bias. In this algorithm an ensemble of trees is also trained, but these are not unpruned
CART trees with small bias that are averaged to reduce variance as in the other methods. Instead these trees have a relatively small, predefined maximum depth (typically 3-8)
and high bias. Furthermore, they are not trained in parallel
but sequentially, and in every iteration the new tree to be
added targets explicitly the samples that are responsible for
the current remaining regression error. Due to its iterative
nature, the GBRT algorithm can approximate very complex
functions resulting in models with low bias. On the other
hand, the algorithm under certain conditions can be fragile
to noise and even more to outliers. Table 3 summarizes the
GBRT algorithm.
4.1. EffEct of hypEr-paramEtErs from a
bias-variancE pErspEctivE
Following the formal presentation of the three algorithms,
it is important to discuss the number of hyper-parameters
that can be tuned and their effect from a bias-variance point
of view. This is required in order to better understand the
tradeoffs available for each algorithm, as well as to explain
their behavior in the experimental section.
Starting from the Random Forest algorithm, the hyperparameters that mostly affect its performance are the number of features to use for doing node splits and the number of trees in the ensemble. Regarding the first one, as a
heuristic Breiman recommends k for classification and
k/3 for regression problems, where k is the total number
of features. If sufficient data are available the parameter
can be chosen using cross-validation, often resulting in a
(typically modest) improvement compared to the heuristic. Generally, a small number favors more aggressive variance reduction at the expense of more bias. Regarding the
number of trees, as a bagging variation RF benefits from
them without a danger of overfitting, although diminishing returns and computational costs are the limiting factors. Note that in some cases additional options that are
not part of the canonical Random Forest are provided, e.g.
enabling tree pruning (or setting a maximum tree depth)
can result in further variance reduction at the expense of
more bias. A similar effect of favoring more variance reduction can be achieved with setting the minimal samples
allowed per leaf. Note that if cross-validation is to be used
for defining more than one hyper-parameters, then nested
cross-validation is required.
The second case is the Extra Trees algorithm and since
it is inspired by the RF algorithm it is also characterized by
similar hyper-parameters (number of features to consider
for each node split, number of trees, maximum tree depth,
and minimal samples allowed per leaf). Due to the intrinsic mechanics of the algorithm, setting the parameters to
the same values as for RF will typically result in a model
that favors less variance at the expense of more bias.
september 2015

ieee Geoscience and remote sensing magazine

Table 3. The GradienT boosTed reGression
Trees alGoriThm.
Step 1.

Setting hyper-parameters. Set the hyper-parameters of
the GBRT algorithm, e.g., number of trees T, maximum
depth of the trees, and value of the feature set splitting
variable mtry

Step 2.

Training the decision trees.

◗ Set initial guess to the value of the dependent
variable.

◗ 'Upweight' examples that the existing model poorly
predicts.

◗ Compute the residuals based on the current model
rmi = y i - fm -1 (x i) where i refers to observations. It
should be noted that fm -1 refers to the sum of all
previous regression trees.
◗ Fit a regression tree (with a fixed depth) to the
residuals.
◗ For each terminal node of the tree, compute the
average residual. The average value is the estimate
for residuals that fall in the corresponding node.
◗ Add the regression tree of the residuals to the current best model fm .
Step 3.

Classifying. After the training is done and the algorithm
operates in classification mode, when a new input is
entered it is run down the final model fM (comprised
by all the trees) to generate the prediction.

Finally, the GBRT algorithm as a tree-based algorithm
is also having similar hyper-parameters, which however
often result in different behavior compared to the other algorithms. The first of these hyper-parameters is the number of trees: in contradistinction to RF and ET, a very large
number of trees can result to
overfitting (depending also
on the amount of training
Tuning of The hyperdata, noise level, etc.) while
parameTerS iS very
a very small number will
imporTanT eSpecially for
result to underfitting (both
gBrT, while random
of these effects appear due
to the iterative nature of the
foreST and exTra TreeS
algorithm). The maximum
are leSS affecTed.
tree depth is also a lot more
critical for GBRT, especially
for preventing overfitting.
Together with the number of trees and the portion of the
training set that is received by each tree, these three are
typically the hyper-parameters that mostly affect performance and need to be tuned by nested cross-validation.
Finally, hyper-parameters like the number of features
to consider for each node split and minimal samples allowed per leaf have the same effect as for the previous algorithms, favoring reduction of variance at the expense
of bias.
4.2. algorithm summary and bEst practicEs
Following the introduction of the algorithms and the description of their hyper-parameters, we summarize their
key properties in Table 4. The goal of this summary is on
one hand to capture the basic mechanics of the algorithms
91

Table of Contents for the Digital Edition of IEEE Geoscience and Remote Sensing Magazine - September 2015