Formulation Bagging Boosting
Chapter 9
Ensemble Learning
supplementary slides to
Machine Learning Fundamentals
c
Hui Jiang 2020
published by Cambridge University Press
August 2020
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Outline
1 Formulation of Ensemble Learning
2 Bagging
3 Boosting
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Ensemble Learning
ensemble learning: combine multiple base models that are
learned separately for the same task
how to choose base models?
◦ neural networks, linear models, decision trees, etc.
how to learn base models to ensure the diversity?
◦ re-sampling the training set, re-weighting training samples, etc.
how to combine base models optimally?
◦ bagging, boosting, stacking
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Decision Trees (I)
a popular non-parametric model for
regression or classification tasks
a tree-structured model:
◦ each non-terminal node is associated
with a binary question regarding an
input feature element xi and a threshold
tj , e.g. xi ≤ tj
◦ each leaf node represents a homogeneous
region Rl in the input space
each decision tree represents a particular
partition of the input space
decision trees are a highly interpretable
machine learning method
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Decision Trees (II)
fit a simple model to all y values in each x y
region Rl ML model
◦ regression: use a constant cl for each Rl
◦ classification: assign all x in each Rl to y = f¯(x)
one particular class
approximate the unknown target function
by a piece-wise constant function
X
y = f (x) = cl I(x ∈ Rl )
l
where
1 if x ∈ Rl
I(x ∈ Rl ) =
0 otherwise
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Decision Trees for Regression
a training set: D = (x(n) , y (n) ) n = 1, 2, · · · , N
construct the loss functional using a loss function l(·):
1
PN 1
PN 2
L(f ; D) = N n=1 l y (n) , f (x(n) ) = N n=1 y (n) − f (x(n) )
computationally infeasible to find the best partition to
minimize the above loss
use the greedy algorithm to recursively find an optimal split
x∗i ≤ t∗j at a time
h X 2 X 2 i
x∗i , t∗j = arg min y (n) − c∗l y (n) − c∗r
+
xi ,tj
x(n) ∈Dl x(n) ∈Dr
where
(n) (n)
Dl = (x(n) , y (n) ) xi ≤ tj , Dr = (x(n) , y (n) ) xi > tj ,
and c∗l and c∗r are the centroids of Dl and Dr
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Decision Trees for Classification
classification
problem involving K classes,
i.e. ω1 , ω2 , · · · , ωK
plk (k = 1, 2, · · · , K): the portion of class
k among all training samples assigned to
leaf node l representing Rl
1 X
plk = I(y (n) = ωk )
Nl
x(n) ∈Rl ◦ misclassification error:
1
P (n)
Nl x (n) ∈R l
I(y 6=
all input x in each region Rl is assigned ωkl∗ ) = 1 − plkl∗
to the majority class ◦ Gini index: 1 − K
P 2
k=1 plk
kl∗ = arg maxk plk ◦ entropy:
− K
P
the criteria for the best split {x∗i , t∗j } k=1 plk log(plk )
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Bagging and Random Forests
bagging stands for bootstrap aggregating
bootstrapping (sampling with replacement) a training set into
M subsets
use M bootstrap subsets to independently learn M models
combine M models by averaging or majority-voting
random forests: use decision trees as base models in bagging
◦ row sampling
◦ column sampling
◦ sub-optimal splitting
random forests are much more powerful than decision trees
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Boosting: Outline
1 Gradient Boosting
2 AdaBoost
3 Gradient Tree Boosting
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Boosting
consider an additive model for ensemble learning
Fm (x) = w1 f1 (x) + w2 f2 (x) + · · · + wm fm (x)
each base model fm (x) ∈ H, then Fm (x) ∈ lin(H) ⊇ H
ensemble learning: ⇐⇒ functional minimization
N
X
Fm (x) = arg min l f (xn ), yn
f ∈ lin(H)
n=1
boosting: a sequential learning strategy to add a new base
model to improve the current ensemble
Fm (x) = Fm−1 (x) + wm fm (x)
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Gradient Boosting
gradient boosting: estimate the new base
model along the direction of the gradient
at the current ensemble Fm−1 :
∂l f (x), y
∆
∇l Fm−1 (x) =
∂f
f =Fm−1
project the gradient into H: N
∆ 1 X
hf, gi = f (xi )g(xi )
fm = arg max f, −∇l Fm−1 (x) N i=1
f ∈H
estimate the optimal weight:
PN
wm = arg minw n=1 l Fm−1 (xn ) + w fm (xn ), yn
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
AdaBoost (I)
apply gradient boosting to binary classification problems
H: all binary functions, i.e. ∀f ∈ H, f (x) ∈ {−1, +1}
the exponential loss function: l F (x), y = e −yF (x)
given a training set: D = (x1 , y1 ), (x2 , y2 ), · · · , (xN , yN ) ,
where xn ∈ Rd and yn ∈ {−1, +1}
the functional gradient:
∆ ∂l f (x), y
∇l Fm−1 (x) = = −y e−yFm−1 (x)
∂f
f =Fm−1
project into H:
fm = arg max f, −∇l Fm−1 (x)
f ∈H
N
1 X
= arg max yn f (xn )e−yn Fm−1 (xn )
f ∈H N n=1
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
AdaBoost (II)
(m) ∆
denote αn = exp(−yn Fm−1 xn ) :
X X
fm = arg max αn(m) − αn(m)
f ∈H
yn =f (xn ) yn 6=f (xn )
N
X X
= arg max αn(m) − 2 αn(m)
f ∈H
n=1 yn 6=f (xn )
X
= arg min αn(m)
f ∈H
yn 6=f (xn )
(m)
(m) ∆ αn
normalize all weights as ᾱn = PN (m) , we have
n=1 αn
X
fm = arg min ᾱn(m)
f ∈H
yn 6=f (xn )
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
AdaBoost (III)
estimate fm to minimize the weighted classification error:
X
m = ᾱn(m) (0 ≤ m ≤ 1)
yn 6=fm (xn )
replace the 0-1 loss function with a weighted loss function,
(m)
where ᾱn is treated as the loss if (xn , yn ) is misclassified
estimate the optimal weight:
N
X
wm = arg min e−yn Fm−1 (xn )+w fm (xn )
w
n=1
P (m)
ᾱn
1 yn =fm (xn ) 1 1 − m
=⇒ wm = ln (m)
= ln
2 2 m
P
yn 6=fm (xn ) ᾱn
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
AdaBoost (IV)
AdaBoost algorithm
input: (x1 , y1 ), · · · , (xN , yN ) , where xn ∈ Rd and yn ∈ {−1, +1}
output: an ensemble model Fm (x)
m = 1 and F0 (x) = 0
(1)
initialize ᾱn = N1 for all n = 1, 2, · · · , N
while not converged do P (m)
learn a binary classifier fm (x) to minimize m = yn 6=fm (xn ) ᾱn
estimate ensemble weight: wm = 21 ln 1− m
m
add to ensemble: Fm (x) = Fm−1 (x) + wm fm (x)
(m) −yn wm fm (xn )
(m+1) ᾱn e
update ᾱn = PN (m) −yn wm fm (xn ) for all n = 1, 2, · · · , N
n=1 ᾱn e
m=m+1
end while
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
AdaBoost (V)
Theorem
If AdaBoost generates m base models with errors 1 , 2 , · · · , m ,
the error of the ensemble model Fm (x) is bounded as:
m p
Y
ε ≤ 2m t (1 − t )
t=1
combine many weak classifiers towards a strong classifier, i.e.
ε → 0 as m → ∞ if all t 6= 12 (better than random guessing)
generalize well into unseen samples since it improves the
margin distribution of training samples
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Gradient Tree Boosting (I)
apply gradient boosting to regression problems
H: all decision trees
use the square error as the loss functional:
2
l f (x), y = 12 f (x) − y
the functional gradient: ∇l Fm−1 (x) = Fm−1 (x) − y
given a training set: D = (x1 , y1 ), (x2 , y2 ), · · · , (xN , yN )
project it to minimize:
2
fm = arg min
f + ∇l Fm−1 (x)
f ∈H
N
X 2
= arg min f (xn ) − yn − Fm−1 (xn )
f ∈H
n=1
| {z }
residual
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Gradient Tree Boosting (II)
gradient tree boosting: build a decision tree fm to
approximate the residuals, i.e. yn − Fm−1 (xn ), for all n
X
y = fm (x) = cml I(x ∈ Rml )
l
where cml is the mean of all residuals in the region Rml
a.k.a. gradient boosting machine (GBM), gradient boosted
regression tree (GBRT)
use a pre-set ”shrinkage” parameter ν as the weight:
Fm (x) = Fm−1 (x) + ν fm (x)
also applicable to multi-class classification problems
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
Formulation Bagging Boosting
Gradient Tree Boosting (III)
Gradient Tree Boosting
input: (x1 , y1 ), (x2 , y2 ), · · · , (xN , yN )
output: an ensemble model Fm (x)
fit a regression tree f0 (x) to (x1 , y1 ), (x2 , y2 ), · · · , (xN , yN )
F0 (x) = ν f0 (x)
m=1
while not converged do
compute the negative gradients as pseudo outputs:
ỹn = −∇l Fm−1 (xn) for all n = 1, 2, · · · , N
fit a regression tree fm (x) to (x1 , ỹ1 ), · · · , (xN , ỹN )
Fm (x) = Fm−1 (x) + νfm (x)
m=m+1
end while
supplementary slides to Machine Learning Fundamentals
c
Hui Jiang 2020 published by Cambridge University Press
Chapter 9
