Model-based boosting in R
Introduction to Gradient Boosting
Matthias Schmid
Institut f
ur Medizininformatik, Biometrie und Epidemiologie (IMBE)
Friedrich-Alexander-Universitat Erlangen-N
urnberg
Statistical Computing 2011
Introduction to Gradient Boosting
Aims and scope
Why boosting?
Definition and Properties of Gradient boosting
References
2/35
Introduction to Gradient Boosting
Aims and scope
Aims and scope
I
Consider a sample containing the values of a response variable Y
and the values of some predictor variables X = (X1 , . . . , Xp )>
Aim: Find the optimal function f (X) to predict Y
f (X) should have a nice structure, for example,
f (X)
f (X)
= 0 + 1 X1 + + p Xp
(GLM )
= 0 + f1 (X1 ) + + fp (Xp )
or
(GAM )
f should be interpretable
3/35
Introduction to Gradient Boosting
Aims and scope
Example 1 - Birth weight data
I
Prediction of birth weight by means of ultrasound measures
(Schild et al. 2008)
I
I
Outcome: birth weight (BW) in g
Predictor variables:
I
abdominal volume (volABDO)
biparietal diameter (BPD)
head circumference (HC)
other predictors (measured one week before delivery)
Data from n = 150 children with birth weight 1600g
Find f to predict BW
4/35
Introduction to Gradient Boosting
Aims and scope
Birth weight data (2)
I
Idea: Use 3D ultrasound measurements (left) in addition to
conventional 2D ultrasound measurements (right)
Sources: [Link], [Link]
Improve established formulas for weight prediction
5/35
Introduction to Gradient Boosting
Aims and scope
Example 2 - Breast cancer data
Data collected by the Netherlands Cancer Institute
(van de Vijver et al. 2002)
I 295 female patients younger than 53 years
I
Outcome: time to death after surgery (in years)
Predictor variables: microarray data (4919 genes) + 9 clinical
variables (age, tumor diameter, ...)
Select a small set of marker genes (sparse model)
Use clinical variables and marker genes to predict survival
6/35
Introduction to Gradient Boosting
Why boosting?
Classical modeling approaches
Classical approach to obtain predictions from birth weight data and
breast cancer data: Fit additive regression models (Gaussian
regression, Cox regression) using maximum likelihood (ML)
estimation
Example: Additive Gaussian model with smooth effects (represented
by P-splines) for birth weight data
f (X) = 0 + f1 (X1 ) + + fp (Xp )
7/35
Introduction to Gradient Boosting
Why boosting?
Problems with ML estimation
I
Predictor variables are highly correlated
Variable selection is of interest because of multicollinearity
(Do we really need 9 highly correlated predictor variables?)
I
In case of the breast cancer data: Maximum (partial) likelihood
estimates for Cox regression do not exist (there are 4928 predictor
variables but only 295 observations, p n)
Variable selection because of extreme multicollinearity
We want to have a sparse (interpretable) model including the
relevant predictor variables only
I
Conventional methods for variable selection (univariate, forward,
backward, etc.) are known to be instable and/or require the model
to be fitted multiple times.
8/35
Introduction to Gradient Boosting
Why boosting?
Boosting - General properties
I
Gradient boosting (boosting for short) is a fitting method to
minimize general types of risk functions w.r.t. a prediction
function f
Examples of risk functions: Squared error loss in Gaussian
regression, negative log likelihood loss
Boosting generally results in an additive prediction function, i.e.,
f (X) = 0 + f1 (X1 ) + + fp (Xp )
Prediction function is interpretable
If run until convergence, boosting can be regarded as an alternative
to conventional fitting methods (Fisher scoring, backfitting) for
generalized additive models.
9/35
Introduction to Gradient Boosting
Why boosting?
Why boosting?
In contrast to conventional fitting methods, ...
... boosting is applicable to many different risk functions (absolute
loss, quantile regression)
... boosting can be used to carry out variable selection during the
fitting process
No separation of model fitting and variable selection
... boosting is applicable even if p n
... boosting addresses multicollinearity problems (by shrinking effect
estimates towards zero)
... boosting optimizes prediction accuracy (w.r.t. the risk function)
10/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Gradient boosting - estimation problem
I
Consider a one-dimensional response variable Y and a
p-dimensional set of predictors X = (X1 , . . . , Xp )>
Aim: Estimation of
f := argmin E[(Y , f (X))] ,
f ()
where is a loss function that is assumed to be differentiable with
respect to a prediction function f (X)
I
Examples of loss functions:
I = (Y f (X))2 squared error loss in Gaussian regression
I
Negative log likelihood function of a statistical model
11/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Gradient boosting - estimation problem (2)
I
In practice, we usually have a set of realizations
X = (X1 , . . . , Xn ), Y = (Y1 , . . . , Yn ) of X and Y , respectively
Minimization of the empirical risk
n
R=
1X
(Yi , f (Xi ))
n i=1
with respect to f
n
Example: R =
1X
(Yi f (Xi ))2 corresponds to minimizing the
n i=1
expected squared error loss
12/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Naive functional gradient descent (FGD)
I
Idea: use gradient descent methods to minimize
R = R(f(1) , . . . , f(n) ) w.r.t. f(1) = f (X1 ), . . . , f(n) = f (Xn )
[0]
[0]
Start with offset values f(1) , . . . , f(n)
In iteration
[m]
f
(1)
..
.
[m]
f
(n)
m:
[m1]
R [m1]
(f(1) )
f
f(1)
(1)
..
..
=
+
.
.
[m1]
[m1]
fR
(
f(n) )
f(n)
(n)
where is a step length factor
Principle of steepest descent
13/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Naive functional gradient descent (2)
(Very) simple example: n = 2, Y1 = Y2 = 0, = squared error loss
1 2
2
R=
f(1) + f(2)
2
z = f1 + f2
3
14
10
10
12
12
14
16
0
1
2
16
f2
16
14
12
10
10
14
12
16
f1
14/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Naive functional gradient descent (3)
Increase m until the algorithm converges to some values
[m
]
[m
]
f stop , . . . , f stop
(1)
(n)
Problem with naive gradient descent:
I
I
No predictor variables involved
[m
]
[m
]
Structural relationship between f(1)stop , . . . , f(n)stop is ignored
[m]
[m]
(f Y1 , . . . , f Yn )
(1)
(n)
Predictions only for observed values Y1 , . . . , Yn
15/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Gradient Boosting
I
Solution: Estimate the negative gradient in each iteration
Estimation is performed by some base-learning procedure regressing
the negative gradient on the predictor variables
[m
]
[m
]
base-learning procedure ensures that f stop , . . . , f stop are
(1)
(n)
predictions from a statistical model depending on the predictor
variables
I
To do this, we specify a set of regression models (base-learners)
with the negative gradient as the dependent variable
In many applications, the set of base-learners will consist of p simple
regression models ( one base-learner for each of the p predictor
variables, component-wise gradient boosting)
16/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Gradient Boosting (2)
Functional gradient descent (FGD) boosting algorithm:
1. Initialize the n-dimensional vector f[0] with some offset values
(e.g., use a vector of zeroes). Set m = 0 and specify the set of
base-learners. Denote the number of base-learners by P .
(Y, f ) and
f
evaluate at f[m1] (Xi ), i = 1, . . . , n. This yields the negative
gradient vector
2. Increase m by 1. Compute the negative gradient
[m1]
U [m1] = (Ui
)i=1,...,n :=
(Y, f )
f
Y =Yi ,f =f[m1] (Xi ) i=1,...,n
..
.
17/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Gradient Boosting (3)
..
.
3. Estimate the negative gradient U [m1] by using the base-learners
(i.e., the P regression estimators) specified in Step 1.
This yields P vectors, where each vector is an estimate of the
negative gradient vector U [m1] .
Select the base-learner that fits U [m1] best ( min. SSE). Set
[m1] equal to the fitted values from the corresponding best
U
model.
..
.
18/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Gradient Boosting (4)
..
.
[m1] , where 0 < 1 is a real-valued
4. Update f[m] = f[m1] + U
step length factor.
5. Iterate Steps 2 - 4 until m = mstop .
I
The step length factor could be chosen adaptively. Usually, an
adaptive strategy does not improve the estimates of f but will only
lead to an increase in running time
choose small ( = 0.1) but fixed
19/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Schematic overview of Step 3 in iteration m
I
Component-wise gradient boosting with one base-learner for each
predictor variable:
U [m1] X1
U [m1] X2
..
.
U [m1] Xj
..
.
best-fitting base-learner
[m1]
U
U [m1] Xp
20/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m=0
m=0
0.00
0.05
0.05
0.10
0.00
0.05
Residuals
0.05
0.10
0.2
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
21/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m=1
m=1
0.00
0.05
0.05
0.10
0.00
0.05
Residuals
0.05
0.10
0.2
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
22/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m=2
m=2
0.05
0.05
0.00
0.05
Residuals
0.05
0.10
0.10
0.2
0.00
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
23/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m=3
m=3
0.05
0.05
0.00
0.05
Residuals
0.05
0.10
0.2
0.10
0.00
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
24/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m = 10
m = 10
0.05
0.05
0.00
0.05
0.00
0.05
0.10
Residuals
0.10
0.2
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
25/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m = 20
m = 20
0.05
0.05
0.00
0.05
Residuals
0.00
0.05
0.10
0.10
0.2
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
26/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m = 30
m = 30
0.05
0.05
0.00
0.05
Residuals
0.00
0.05
0.10
0.10
0.2
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
27/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Simple example
In case of Gaussian regression, gradient boosting is equivalent to
iteratively re-fitting the residuals of the model.
y = (0.5 0.9 e50 x ) x + 0.02
2
Residuals
0.10
0.10
m = 150
m = 150
0.05
0.00
0.05
0.05
Residuals
0.00
0.05
0.10
0.10
0.2
0.1
0.0
x
0.1
0.2
0.2
0.1
0.0
0.1
0.2
28/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Properties of gradient boosting
I
It is clear from Step 4 that the predictions of Y1 , . . . , Yn in
iteration mstop take the form of an additive function:
[0] + + U
[mstop 1]
f[mstop ] = f[0] + U
The structure of the prediction function depends on the choice of
the base-learners
I
For example, linear base-learners result in linear prediction
functions
Smooth base-learners result in additive prediction functions
with smooth components
f[mstop ] has a meaningful interpretation
29/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Gradient boosting with early stopping
I
Gradient boosting has a built-in mechanism for base-learner
selection in each iteration.
This mechanism will carry out variable selection.
I
Gradient boosting is applicable even if p > n.
In case p > n, it is usually desirable to select a small number of
informative predictor variables (sparse solution).
If m , the algorithm will select non-informative predictor
variables.
Overfitting can be avoided if the algorithm is stopped early, i.e.,
if mstop is considered as a tuning parameter of the algorithm
30/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Illustration of variable selection and early stopping
I
Very simple example: 3 predictor variables X1 , X2 , X3 ,
[m]
3 linear base-learners with coefficient estimates j , j = 1, 2, 3
Assume that mstop = 5
Assume that X1 was selected in the first, second and fifth iteration
Assume that X3 was selected in the third and forth iteration
f[mstop ]
[0] + U
[1] + U
[2] + U
[3] + U
[4]
f[0] + U
=
=
[0]
[1]
[2]
[3]
[4]
[0] + 1 X1 + 1 X1 + 3 X3 + 3 X3 + 1 X1
[0]
[1]
[4]
[2]
[3]
[0] + 1 + 1 + 1 X1 + 3 + 3 X3
[0] + 1 X1 + 3 X3
Linear prediction function
X2 is not included in the model (variable selection)
31/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
How should the stopping iteration be chosen?
I
Use cross-validation techniques to determine mstop
0.0
0.2
0.8
0.6
0.4
predictive risk
0.2
0.4
crossvalidated mstop
20
40
60
80
Number of boosting iterations
The stopping iteration is chosen such that it maximizes prediction
accuracy.
32/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Shrinkage
Early stopping will not only result in sparse solutions but will also
is
lead to shrunken effect estimates ( only a small fraction of U
added to the estimates in each iteration).
Shrinkage leads to a downward bias (in absolute value) but to a
smaller variance of the effect estimates (similar to Lasso or Ridge
regression).
Multicollinearity problems are addressed.
33/35
Introduction to Gradient Boosting
Definition and Properties of Gradient boosting
Further aspects
There are many types of boosting methods, e.g.,
I
tree-based boosting (AdaBoost, Freund & Schapire 1997)
likelihood-based boosting (Tutz & Binder 2006)
Here we consider gradient boosting
I
Flexible method to fit many types of statistical models in highand low-dimensional settings
Regularization of estimates via variable selection and shrinkage
Implemented in R package mboost (Hothorn et al. 2010, 2011)
34/35
Introduction to Gradient Boosting
References
References
Freund, Y. and R. Schapire (1997): A decision-theoretic generalization of on-line learning and an application to
boosting. Journal of Computer and System Sciences 55, 119-139.
Hothorn, T., P. B
uhlmann, T. Kneib, M. Schmid and B. Hofner (2010): Model-based boosting 2.0. Journal of
Machine Learning Research 11, 2109-2113.
Hothorn, T., P. B
uhlmann, T. Kneib, M. Schmid and B. Hofner (2011): mboost: Model-Based Boosting. R
package version 2.1-0. [Link]
Schild, R. L., M. Maringa, J. Siemer, B. Meurer, N. Hart, T. W. Goecke, M. Schmid, T. Hothorn and M. E.
Hansmann (2008). Weight estimation by three-dimensional ultrasound imaging in the small fetus. Ultrasound in
Obstetrics and Gynecology 32, 168-175.
Tutz, G. and H. Binder (2006): Generalized additive modelling with implicit variable selection by likelihood based
boosting. Biometrics 62, 961-971.
van de Vijver, M. J., Y. D. He, L. J. vant Veer, H. Dai, A. A. M. Hart, D. W. Voskuil et al. (2002). A
gene-expression signature as a predictor of survival in breast cancer. New England Journal of Medicine 347,
1999-2009.
35/35