–
Lecture
Ensemble methods
1
Which technique is better?
Many techniques
SVM
K-nearest neighbours
Logistic regression
HMM
Neural networks
Which one we should pick?
Which will perform better?
2
Ensemble Learning
Each learning technique yields a different hypothesis
None of these are perfect hypothesis
Can we combine several imperfect hypothesis to produce a
better hypothesis?
Hopefully
Example: Selection of Candidates by voting
An individual often make mistakes, but majority less likely to make
mistakes
Example: A committee combines the experts’ opinion and make
a decision
An individual may have partial knowledge, but when combining the
knowledge of a pool of experts leads to better decision
3
Ensemble Learning
Ensemble learning select a collection (ensemble) of
hypotheses and combine their predictions.
When combing multiple independent and diverse decisions each
of which is at least more accurate than random guessing,
random errors cancel each other out, correct decisions are
reinforced.
Example:
generate 50 different decision trees from the same or different
training set and have them vote on the best classification for a new
example.
Motivation:
reduce the error rate. Hope is that it will become much more
unlikely that the ensemble of will misclassify an example.
4
Ensemble Learning
Another way of thinking about ensemble learning:
way of enlarging the hypothesis space, i.e., the
ensemble itself is a hypothesis and the new hypothesis
space is the set of all possible ensembles constructible
form hypotheses of the original space.
Increasing power of ensemble learning:
Three linear threshold hypothesis
(positive examples on the non-shaded side);
Ensemble classifies as positive any example classified
positively be all three. The resulting triangular region hypothesis
is not expressible in the original hypothesis space.
Linear separator to Polytope
5
Ensemble learning
[Link] 6
Why does it work?
Intuition
combining diverse, independent opinions in human decision-
making as a protective mechanism (e.g. stock portfolio)
Uncorrelated error reduction
Suppose we have 5 completely independent classifiers for majority
voting
If accuracy is 70% for each
10 (.7^3)(.3^2)+5(.7^4)(.3)+(.7^5)
83.7% majority vote accuracy
101 such classifiers
99.9% majority vote accuracy
7
7
Why does it work?
Some unknown distribution
Model 1 Model 6
Model 3 Model 5
Model 2 Model 4
Ensemble gives the global picture! 8
Why does it work?
Overcome limitations of single hypothesis
The target function may not be implementable with
individual classifiers, but may be approximated by model
averaging
Decision Tree Model Averaging 9
Learning Ensembles
Learn multiple alternative definitions of a concept using
different training data or different learning algorithms.
Combine decisions of multiple definitions, e.g. using
weighted voting.
Training Data
Step 1 : Create
multiple data sets
Data1 Data2 Data m
Learner1 Learner2 Learner m
Step 2 : Build multiple
models Model1 Model2 Model m
Step 3 : Combine Model Combiner Final Model
classifiers
10
Homogenous Ensembles
Use a single, arbitrary learning algorithm but manipulate
training data to make it learn multiple models.
Data1 Data2 … Data m
Learner1 = Learner2 = … = Learner m
Different methods for changing training data:
Bagging: Resample training data
Boosting: Reweight training data
DECORATE: Add additional artificial training data
11
Bagging
Ensemble of Hypothesis
Instance
Classification
P1 P2
P4 X Majority {P1(X), P2(X), P3(X), P4(X), P5(X)}
P3 P5
Classification is wrong only if 3 out of 5 hypothesis is
wrong
12
Parallel Ensemble Learning(Bagging)
Bagging, is a machine learning ensemble meta-algorithm intended
to improve the strength and accuracy of machine learning
algorithms used in classification and regression purpose. It
additionally diminishes fluctuation of data(variance)and help to
from over-fitting.
Parallel ensemble methods where the base learners are generated
in parallel
Algorithms : Random Forest, Bagged Decision Trees, Extra Trees
13
Bagging (bootstrap aggregating)
Create ensembles by repeatedly randomly resampling the
training data (Brieman, 1996).
Given a training set of size n, create m samples of size n
by drawing n examples from the original data, with
replacement.
Combine the m resulting models using simple majority
vote.
Decreases error by decreasing the variance in the results
due to unstable learners, algorithms (like decision trees)
whose output can change dramatically when the training
data is slightly changed.
14
Advantages of Bagging
Easy to implement
Reduces variance - strong beneficial effect on high
variance classifiers
As the prediction is an average of many classifiers, you
obtain a mean score and variance. Latter can be
interpreted as the uncertainty of the prediction.
Bagging provides an unbiased estimate of the test error,
(out-of-bag error)
15
Bagging- Final Points
Works well if the base classifiers are unstable
Increased accuracy because it reduces variance as
compared to any individual classifier
Multiple models can be learned in parallel
16
Weighted majority
However
In practice, hypothesis may not be independent
Some hypothesis may perform better than others
Can take weighted majority
Decrease weight of correlated hypotheses
Increase weight of good hypotheses
17
Boosting
Popular ensemble technique
Computes a weighted majority
Can “boost” a “weak learner”
Operates on a weighted training set
18
Sequential Ensemble learning (Boosting) :
Boosting, is a machine learning ensemble meta-algorithm
for principally reducing bias, and furthermore variance in
supervised learning, and a group of machine learning
algorithms that convert weak learner to string ones.
Sequential ensemble methods where the base learners are
generated sequentially.
Example : Adaboost, Stochastic Gradient Boosting
19
Issues in Ensembles
Parallelism in Ensembles: Bagging is easily
parallelized, Boosting is not.
Variants of Boosting to handle noisy data.
How “weak” should a base-learner for Boosting
be?
What is the theoretical explanation of boosting’s
ability to improve generalization?
Exactly how does the diversity of ensembles
affect their generalization performance.
Combining Boosting and Bagging.
20
Issues in Ensembles
Can generate multiple classifiers by
Resampling training data
Reweighting training data
Varying learning parameters
Varying feature set
Boosting can’t be run in parallel and is very
sensitive to noise, but (in the absence of noise)
seems very insensitive to overfitting
Ability of ensemble methods to reduce variance
depends on independence of learned classifiers
21
21