CS 2750 Machine Learning

Lecture 23

Ensemble methods.
Bagging and Boosting

Milos Hauskrecht
milos@[Link]
5329 Sennott Square

CS 2750 Machine Learning

Administrative announcements
• Term projects:
– Reports due on Wednesday, April 21, 2004 at 12:30pm.
– Presentations on Wednesday, April 21, 2004 at 12:30pm.
• Quiz
– Wednesday, April 14, 2003
– Closed book
– Short (~30 minutes)
– Main ideas of methods covered after the midterm
• EM, Dimensionality reduction, Clustering, Decision trees,
Mixtures of experts, Bagging and Boosting, Reinforcement
learning.

CS 2750 Machine Learning

1
 Ensemble methods
• Mixture of experts
– Multiple ‘base’ models (classifiers, regressors), each covers
a different part (region) of the input space
• Committee machines:
– Multiple ‘base’ models (classifiers, regressors), each covers
the complete input space
– Each base model is trained on a slightly different train set
– Combine predictions of all models to produce the output
• Goal: Improve the accuracy of the ‘base’ model
– Methods:
• Bagging
• Boosting
• Stacking (not covered)
CS 2750 Machine Learning

Bagging (Bootstrap Aggregating)

• Given:
– Training set of N examples
– A class of learning models (e.g. decision trees, neural
networks, …)
• Method:
– Train multiple (k) models on different samples (data splits)
and average their predictions
– Predict (test) by averaging the results of k models
• Goal:
– Improve the accuracy of one model by using its multiple
copies
– Average of misclassification errors on different data splits
gives a better estimate of the predictive ability of a learning
method
CS 2750 Machine Learning

2
 Bagging algorithm
• Training
– In each iteration t, t=1,…T
• Randomly sample with replacement N samples from the
training set
• Train a chosen “base model” (e.g. neural network,
decision tree) on the samples
• Test
– For each test example
• Start all trained base models
• Predict by combining results of all T trained models:
– Regression: averaging
– Classification: a majority vote

CS 2750 Machine Learning

Simple Majority Voting

Test examples
H1

H2

H3

Final

Class “yes”
Class “no”

CS 2750 Machine Learning

3
 Analysis of Bagging
• Expected error= Bias+Variance
– Expected error is the expected discrepancy between the
estimated and true function

E [( fˆ ( X ) − E [ f ( X )]) ] 2

– Bias is squared discrepancy between averaged

estimated and true function

(E [ fˆ ( X )]− E [ f ( X )]) 2

– Variance is expected divergence of the estimated

function vs. its average value

[( [
E fˆ ( X ) − E fˆ ( X )]) 2 ]
CS 2750 Machine Learning

When Bagging works?

Under-fitting and over-fitting

• Under-fitting:
– High bias (models are not
accurate)
– Small variance (smaller
influence of examples in the
training set)
• Over-fitting:
– Small bias (models flexible
enough to fit well to training
data)
– Large variance (models
depend very much on the
training set)

CS 2750 Machine Learning

4
 Averaging decreases variance
• Example
– Assume we measure a random variable x with a N(µ,σ2)
distribution
– If only one measurement x1 is done,
• The expected mean of the measurement is µ
• Variance is Var(x1)=σ2
– If random variable x is measured K times (x1,x2,…xk) and
the value is estimated as: (x1+x2+…+xk)/K,
• Mean of the estimate is still µ
• But, variance is smaller:
– [Var(x1)+…Var(xk)]/K2=Kσ2 / K2 = σ2/K
• Observe: Bagging is a kind of averaging!
CS 2750 Machine Learning

When Bagging works

• Main property of Bagging (proof omitted)

– Bagging decreases variance of the base model without
changing the bias!!!
– Why? averaging!
• Bagging typically helps
– When applied with an over-fitted base model
• High dependency on actual training data
• It does not help much
– High bias. When the base model is robust to the
changes in the training data (due to sampling)

CS 2750 Machine Learning

5
 Boosting. Theoretical foundations.
• PAC: Probably Approximately Correct framework
– (ε-δ) solution
• PAC learning:
– Learning with the pre-specified accuracy ε and
confidence δ
– the probability that the misclassification error is larger
than ε is smaller than δ
P ( ME ( c ) > ε ) ≤ δ
• Accuracy (ε ): Percent of correctly classified samples in test
• Confidence (δ ): The probability that in one experiment some
accuracy will be achieved

CS 2750 Machine Learning

PAC Learnability
Strong (PAC) learnability:
• There exists a learning algorithm that efficiently learns the
classification with a pre-specified accuracy and confidence
Strong (PAC) learner:
• A learning algorithm P that given an arbitrary
– classification error ε (<1/2), and
– confidence δ (<1/2)
• Outputs a classifier
– With a classification accuracy > (1-ε)
– A confidence probability > (1- δ)
– And runs in time polynomial in 1/ δ, 1/ε
• Implies: number of samples N is polynomial in 1/ δ, 1/ε
CS 2750 Machine Learning

6
 Weak Learner

Weak learner:
• A learning algorithm (learner) W
– Providing classification accuracy >1-εo
– With probability >1- δo
• For some fixed and uncontrollable
– classification error εo (<1/2)
– confidence δo (<1/2)
And this on an arbitrary distribution of data entries

CS 2750 Machine Learning

Weak learnability=Strong (PAC) learnability

• Assume there exists a weak learner
– it is better that a random guess (50 %) with confidence
higher than 50 % on any data distribution
• Question:
– Is problem also PAC-learnable?
– Can we generate an algorithm P that achieves an arbitrary
(ε-δ) accuracy?
• Why is important?
– Usual classification methods (decision trees, neural nets),
have specified, but uncontrollable performances.
– Can we improve performance to achieve pre-specified
accuracy (confidence)?

CS 2750 Machine Learning

7
 Weak=Strong learnability!!!

• Proof due to R. Schapire

An arbitrary (ε-δ) improvement is possible

Idea: combine multiple weak learners together

– Weak learner W with confidence δo and maximal error εo
– It is possible:
• To improve (boost) the confidence
• To improve (boost) the accuracy
by training different weak learners on slightly different
datasets

CS 2750 Machine Learning

Boosting accuracy
Training
Distribution samples Learners
H1

H2

H3

Correct classification
Wrong classification
H1 and H2 classify differently
CS 2750 Machine Learning

8
 Boosting accuracy
• Training
– Sample randomly from the distribution of examples
– Train hypothesis [Link] the sample
– Evaluate accuracy of H1 on the distribution
– Sample randomly such that for the half of samples H1.
provides correct, and for another half, incorrect results;
Train hypothesis H2.
– Train H3 on samples from the distribution where H1 and
H2 classify differently
• Test
– For each example, decide according to the majority vote
of H1, H2 and H3

CS 2750 Machine Learning

Theorem
• If each hypothesis has an error εo, the final classifier has
error < g(εo) =3 εo2- 2εo3
• Accuracy improved !!!!
• Apply recursively to get to the target accuracy !!!

CS 2750 Machine Learning

9
 Theoretical Boosting algorithm
• Similarly to boosting the accuracy we can boost the confidence
at some restricted accuracy cost
• The key result: we can improve both the accuracy and
confidence

• Problems with the theoretical algorithm

– A good (better than 50 %) classifier on all data problems
– We cannot properly sample from data-distribution
– Method requires large training set

• Solution to the sampling problem:

– Boosting by sampling
• AdaBoost algorithm and variants
CS 2750 Machine Learning

AdaBoost
• AdaBoost: boosting by sampling

• Classification (Freund, Schapire; 1996)

– AdaBoost.M1 (two-class problem)
– AdaBoost.M2 (multiple-class problem)

• Regression (Drucker; 1997)

– AdaBoostR

CS 2750 Machine Learning

10
 AdaBoost
• Given:
– A training set of N examples (attributes + class label pairs)
– A “base” learning model (e.g. a decision tree, a neural
network)
• Training stage:
– Train a sequence of T “base” models on T different sampling
distributions defined upon the training set (D)
– A sample distribution Dt for building the model t is
constructed by modifying the sampling distribution Dt-1 from
the (t-1)th step.
• Examples classified incorrectly in the previous step
receive higher weights in the new data (attempts to cover
misclassified samples)
• Application (classification) stage:
– Classify according to the weighted majority of classifiers
CS 2750 Machine Learning

AdaBoost training
Distribution Learn Test
.
Training D1 Model 1 Errors 1
data

D2
Model 2 Errors 2

DT Model T Errors T

CS 2750 Machine Learning

11
 AdaBoost algorithm
Training (step t)
• Sampling Distribution D t
D t ( i ) - a probability that example i from the original
training dataset is selected
D 1 ( i ) = 1 / N for the first step (t=1)
• Take K samples from the training set according to D t
• Train a classifier ht on the samples
• Calculate the error ε t of ht : ε t = ∑ D t (i )
i:h t ( x i ) ≠ y i
• Classifier weight: β t = ε t /( 1 − ε t )
• New sampling distribution
D t (i)  β t ht ( xi ) = y i
D t +1 (i ) = × 
Zt  1 otherwise
Norm. constant
CS 2750 Machine Learning

AdaBoost. Sampling Probabilities

Example: - Nonlinearly separable binary classification
- NN as week learners

CS 2750 Machine Learning

12
 AdaBoost: Sampling Probabilities

CS 2750 Machine Learning

AdaBoost classification
• We have T different classifiers h t
– weight wt of the classifier is proportional to its accuracy on
the training set
w t = log( 1 / β t ) = log ((1 − ε t ) / ε t )
β t = ε t /( 1 − ε t )
• Classification:
For every class j=0,1
• Compute the sum of weights w corresponding to ALL
classifiers that predict class j;
• Output class that correspond to the maximal sum of
weights (weighted majority)
h final (x ) = arg max
j
∑w
t :ht ( x ) = j
t

CS 2750 Machine Learning

13
 Two-Class example. Classification.

• Classifier 1 “yes” 0.7

• Classifier 2 “no” 0.3
• Classifier 3 “no” 0.2

• Weighted majority “yes”

0.7 - 0.5 = + 0.2
• The final choose is “yes” + 1

CS 2750 Machine Learning

What is boosting doing?

• Each classifier specializes on a particular subset of examples
• Algorithm is concentrating on “more and more difficult”
examples
• Boosting can:
– Reduce variance (the same as Bagging)
– But also to eliminate the effect of high bias of the weak
learner (unlike Bagging)
• Train versus test errors performance:
– Train errors can be driven close to 0
– But test errors do not show overfitting
• Proofs and theoretical explanations in readings

CS 2750 Machine Learning

14
 Boosting. Error performances

0.4
Training error
Test error
Single-learner error
0.35

0.3

0.25

0.2

0.15

0.1

0.05

0
0 2 4 6 8 10 12 14 16

CS 2750 Machine Learning

15