Ensembles

Question 1

Two characteristics of good ensembles

Answer 1

1. Individual models should be strong

2. The correlation between the models in the ensemble should be weak (diversity)

Question 2

What is bagging?

Answer 2

• Trains N models in parallel using bootstrapped data samples, from an overall training set
• Aggregates using majority voting
• Bootstrapped aggregating = bagging

Question 3

Bayes Optimal Ensemble

Answer 3

• An ensemble of all hypotheses in the hypothesis space
• On average, no other ensemble can outperform it
• not possible to practically implement
• Tom Mitchell book (1997)

Question 4

What some practical approaches to ensembling?

Answer 4

1. Bagging
2. Random Forests
3. Boosting
4. Gradient Boosting
5. Stacking

Question 5

Subagging

Answer 5

Bagging, but where we sample without replacement

• Used in large datasets where we want to create bootstrap samples that are smaller than the original dataset

Question 6

What type of learning algorithms are suited to bagging?

Answer 6

• Decision Trees
• DTs are very sensitive to changes and so small changes in a dataset can result in a different feature being selected to split the dataset at the root, or high up in the tree and this can have a ripple effect throughout the subtrees under this node

Question 7

What is subspace sampling?

Answer 7

• A bootstrap sample only uses a randomly selected subset of the descriptive features in the dataset
• Encourages further diversity of the trees within the ensemble
• Has the advantage of reducing training time for each tree

Question 8

Random Forests

Answer 8

= Bagging + Subspace sampling

Question 9

Advantages of Bagging over Boosting

Answer 9

1. Simpler to implement + parallelize
2. Ease of use
3. Reduced training time

However, Caruana et al. (2008) showed that boosted DT ensembles performed best for datasets < 4000 desc. features.
> 4000 descriptive features -> random forests (based on bagging) performed better
> Boosted ensembles may be prone to overfitting and in domains with large numbers of features, overfitting becomes a serious probelm

Question 10

Costs of using ensembles

Answer 10

1. Increased model complexity

2. Increasing learning

Question 11

What types of algorithms does Bagging work well for?

Answer 11

Unstable algos - algos whose output classifier undergoes major changes in response to small changes in the training data

Question 12

Examples of unstable classifiers

Answer 12

DTs, NNs and rule-learning algos are all unstable

Question 13

Examples of stable classifiers

Answer 13

• Linear regression
• Nearest neighbour
• Linear threshold algorithm

Question 14

Bootstrap replicate

Answer 14

Training set created from bagging procedure

Contains on average 63.2% of the original training set, with several training examples appearing multiple times (Diettrich paper)

Question 15

Methods for manipulating training datasets

Answer 15

1. Bagging
2. K-fold cross-validation (ensembles constructed in this way are called ‘cross-validation committees’)
3. Boosting

Question 16

AdaBoost

Answer 16

Freund & Schapire (1995-8)

• manipulates the training examples to generate multiple hypotheses
• maintains a set of weights over the the training examples
• Effect of the change in weights is to place more weight on training examples that were misclassified by h(l) and less weight on examples that were correctly classified
• In subsequent iterations, therefore, Adaboost constructs progressively more difficult learning problems
• final classifier is constructed by a weighted vote of the individual classifiers. Each classifier is weighted (by w(l)) according to its accuracy on the weighted training set that it was trained on
• can be viewed as trying to maximise the margin (confidence of accuracy) on the training data
• constructs each new DT to eliminate ‘residual errors’ that have not been properly handled by the weighted vote of the previously-constructed trees.
• thus, it is directly trying to optimise the weighted vote
  and is therefore making a direct attack on the representational problem
• directly optimising an ensemble can increase the rik of overfitting
• in high-noise cases, Adaboost puts a large amount of weight on the mislabelled examples and this leads to it overfitting badly

Question 17

Bagging vs AdaBoost

Answer 17

Diettrich paper: AdaBoost typically outperforms Bagging but when 20% artificial classification noise was added, AdaBoost overfit the data badly while Bagging did very well in the presence of noise.

Question 18

Why doesn’t Adaboost overfit more often?

Answer 18

• Stage-wise nature of AdaBoost
• In each iteration, it reweights the training examples, constructs a new hypothesis, and chooses a weight for that hypothesis.
• HOWEVER, it never backs up and modifies the previous choices of hypotheses or weights that it has made to compensate for this new hypothesis

Question 19

What is an ensemble?

Answer 19

A prediction model that is composed of a set of models

Question 20

What is the motivation behind ensembles?

Answer 20

• A committee of experts working together on a problem are more likely to solve it successfully than a single expert working alone
• however, should still avoid GROUPTHINK (i.e. each model should make predictions independently of the other models in the ensemble)

Question 21

Two defining characteristics of ensembles

Answer 21

1. Use a modified version of dataset

2. Aggregates predictions from many models

Question 22

How can ensembles lead to good predictions from base learners that are only marginally better than random guessing?

Answer 22

• Given a large population of independent models, an ensemble can be very accurate even if the individual models in the ensemble perform only marginally better than random guessing

Question 23

What are the 2 standard approaches to ensembling?

Answer 23

1. Bagging

2. Boosting

Question 24

Bagging

Answer 24

Bootstrap aggregation

Question 25

Bagging

Answer 25

Each model in the ensemble is trained on a random sample of the dataset

• each random sample is the same size as the original dataset (unless subagging is used)
• sampling with replacement is used

Question 26

Boosting

Answer 26

Each new model added to an ensemble is biased to pay more attention to instances that previous models misclassified

Question 27

How does boosting work?

Answer 27

By incrementally adapting the dataset used to train the models

• uses a weighted dataset
• each instance has an associated weight (w(i) >= 0)
• weights are initially set to 1/n (n=number of examples)
• these weights are used as a distribution over which the dataset is sampled to create a replicated training set
• number of times that an instance is replicated is proportional to its weight

Question 28

How does boosting work?

Answer 28

Iteratively creating models and adding them to the ensemble

Question 29

When do the iterations stop in boosting?

Answer 29

• predefined number of models have been added

- model’s accuracy dips below 0.5

Question 30

Assumptions of boosting algorithm

Answer 30

1. Accuracy of models > 0.5

2. Assumes it’s a binary classification problem

Question 31

What are the boosting algorithm steps?

Answer 31

1. Induces a model using the weighted dataset and calculates the total error, E, in the set of predictions made by the model for the instances in the training set. The E value is calculated by summing the weights of the training instances for which the predictions by the model are incorrect.
2. Increases weights for instances misclassified by the model: w[i] = w[i] * (1 / (2 *E))
3. Decreases the weights for the instances classified correctly by the model: w[i] = w[i] * (1 / (2*(1-E))
4. Calculates a confidence factor, such that alpha increases as E decreases. alpha = (0.5) * log((1-E)/E)

Question 32

What are the bagging algorithm steps?

Answer 32

1. Train N models in parallel using bootstrapped data samples from an overall training set
2. Aggregates using majority voting

Question 33

Why do we sample with replacement in bagging?

Answer 33

It results in duplicates within each of the bootstrap samples and consequently every bootstrap sample will be missing some instances too

• every bootstrap sample will be different, and so every model will be different

Question 34

Disadvantages of ensembles

Answer 34

1. Increased learning

2. Model complexity

Question 35

Pros of Bagging

Answer 35

1. Simpler to implement and parallelize

=> Ease of use and reduced training time

Question 36

Evidence of ensembles

Answer 36

Caruana and Niculescu-Mizil (2006) found that bagging and boosting were the best performers out of 7 predictor types

Caruana et al. (2008) - boosted DTs were best performing model of those tested for datasets <4k descriptive features. For more than 4k features, RFs were better as boosting led to overfitting

Question 37

Summary of Leo Breiman (1996) paper on ‘Bagging Predictors’

Answer 37

Bagging Predictors,
1996, Leo Breiman

bagging can push a good but unstable procedure towards optimality.
It can degrade the performance of stable procedures.

Question 38

Gradient Boosting

Answer 38

• Extension of Boosting
• Iteratively train up ensemble
• Train models to predict residuals

e.g. XGBoost

Question 39

How is Gradient Boosting similar to AdaBoost?

Answer 39

Creates an ensemble model by iteratively adding learners (similar to Ada)

Question 40

How is Gradient Boosting different to Adaboost?

Answer 40

More aggressive - fitting each model directly to the errors of the ensemble (up to the current iteration) rather than a weighted dataset which is more subtle

Question 41

How does Gradient Boosting work?

Answer 41

Best model to fit would be the model that predicts the difference between the old model’s prediction and the true prediction

t[i] - M(n-1)d[i]

• Uses gradient descent to reduce J (error in predictions)

Question 42

Where does the gradient in Gradient Boosting come from?

Answer 42

Because we treat the residuals as the negative gradients of the loss function

Under the hood, we’re doing gradient descent on the error surface

Question 43

Key idea of stacking

Answer 43

Stacking ensembles use a machine learning model to combine the outputs of the base models in an ensemble

Using the predictions of the base models as features at the stacked layer

Can be more effective than simple majority voting or weighted voting

Very common - heterogenous ensembles

Common to use k-folds to generate the stacked level training set

Requires new datasets to be generated for the stack layer

Question 44

Cons of Stacking

Answer 44

Produces small gains for lots of extra complexity