Lecture 8 Ensemble methods

model errors can be characterized by three factors

• inherent randomness (noise)

• bias

• variance

model erros : inherent randomness

= noise

bayes error = lowest possible error taking into account inherent randomness

bayes error

lowest possible error taking into account the inherent randomness

when is a modeling procedure biased

if no matter how much training data we give it, the lowest practically possible error (the bayes rate) is never attained/

errors from bias arise due to erroneous assumptions in the learning algorithm

what is the modeling procedure’s variance

how much the prediction tends to vary across different datasets

a mdoellings procedure’s sensitivity to fluctuations in the training set

the bias-variance trade-off

• more complexity gives higher variance and lower bias

• complexity control : find ‘sweet spot’ where geenralization error is lowest

• → regularization (start with high-variance low-bias and regularize)

Q: characterize Decision Tree and logistic/linear regression in terms of bias/ variance

Linear/logistic regression : high bias method

DT : the more we split the less bias but the more variance (pruning)

ensemble methods : wisdom of the crowds

the average is almost always better than any expert individual

what does ensemble benefit more from (to imrpove performance)

from diverse models, with uncorrelated errors → we can make models different by for example using bootstrapping

bootstrapping

to effectively achieve models that make different errors, the samples used to develop these models should be as different as possible

→ bootstrapping : sampling with replacement

→ contains around 63,2% original records in each sample (if # boostrap goed to n)

what does ensemble learning do

it combines multiple ase models (weak learners) to form a powerful ‘ensemble model (strong learner)

what is a weak learner

a model that performs relativerly poorly, but better than random chance, with too high variance, or too high bias

homogeneous ensemble metods

utilize the same base learning algorithm

→ usually decision trees

• bagging

• random forest

• boosting

heterogeneous ensemble methods

utilize different base learning algorithms

(are more difficult to do)

hard majority voting

class output by each model = 1 vote, sum and assign class with most votes (equal to the mode of the class outputs)

soft majority voting

average the (weighted) probabilities returned by the base learner, assign the class with the highest average probability

bagging

focus on reducing variance of high variance base learners (DT when unpruned very high variance)

hyperparameters : N = nymber of trees

Bootstrap Aggregation (bagging)

• take N bootstras from the original data sample (you can tune N via validatio set)

• build a classifier (DT) for each bootstrap

• for classification : a new observation is classifier by letting all N classifiers vote (weighted) majority voting scheme, ties resulved arbitrarily-

• for regression : prediction is the average of the outcome of the various regression Trees

→ individual classifiers are learned independently; no pruning, final estimate : simple majority voting

bagging : probability of specific observation being sampled :

constant and equal for all observations

bagging adavantages

• since bootstraps and models are independent, models can be trained in parallel

• reduced variance by averaging

bagging disadvantages

• considered less powerful than other ensemble methods

• interpretability

random forest

lots of very diverse high variance and low bias tress combine to generate a low bias low variance forest

hyperparameters :

• N number of trees

• m = number of variables used to calculate the best split at each node < M = # input features

grow N trees as follows

• create a bootstrap sample (usually the same siez as the original training set)

• at each node randomly choose m features and calculate the best split (instead of calculating the information gain for everything, you only alclate it for one subset randomly)

• each tree is grown to the largest extent possible, no pruning

majority vote determines final predictions

random forest compared to bagging

random forest has more variance reduction due to averaging over more diverse tress (due to random feature subset splitting)

random forest are used for

classification and regression variants

the error rate of random forests depends on

• the correlation between any two trees in the forest. increasing the correlation increases the forest error rate

• the strength of each individual tree in the forest. A tree with a low error rate is a strong classifier. Increase the strength of the individual trees decreases the forest error rate

reducing m (=number of variables used to calculate the best split at each node)

random forest advantages

• models can be trained independently and in parallel

• reduces variance by averaging (but chooses higher variance indivdual trees (feature subsampling at each split) )

• gives measure of feature importance (compares splits between when certain features are allowed to be used and when not, and that says how important the feature us)

• very good classifocation performance with very limited required tuning, also for large datasets

• → usually more powerful than bagging due to random sibset of splitting at each node

random forest disadvantages

interpretability

boosting

iterative porcedure where in each round

• observations currently misclassified are made more important → by increasing weight (bootstrap sampling rate or in loss function)

both classification and regression (similar to bagging)

boosting : Adaboost

most well-known boosting algorithm

hyperparameter : T (nuymber of trees/ rounds)

set uniform weigts for all obseravtions

then for T rounds

• create a bootstrap sample based on the weights

• train a classifier on the sample and apply it on the original training set

• records that are wrongly classifier will have their weights increased

• records that are classified correclty will have their weights decreased

final prediction : majority vote

boosting advantages

number of rounds (models) is the only parameter to tune

reduces bias

fast, simple and easy to program

boosting disadvantages

increases variance - bossting can have a risk of overfitting to the hard (=noisy) examples in the data

interpretability

sequential : high dependency between ensemble elements

alternative to boosting

gradient boosting

• implments tree boosting whereby a tree in the ensemble is fit to the residual of the prediction from the earlier trees

stacking method

used to combine different types of models : base learners → heterogeneous ensembling method

prediction of base learners are used as imput for a meta learner

the base learners use the original dataset as input

the meta learner used the output of the base learners as input

the meta model learns to weight the contributions of the base learners to minimize error

→ ideally reduces both variance and bias

(ignores models that work very bad)

stacking advantages

• flexible way to combine heterogeneous models

• can sometimes reduce both bias and variance

stacking disadvantages

• hard to analyse theoretically

• a lot of work to train and optimize different member classifier

is rarely used

what is not required for tree-based ensembles

no normalization or encoding required (handling of missing values depends on the algorithm-

ensemble methods are supervised or unsupervised learning ?

supervised learning methods

neural networks are relatively old, but recent boom with deep learning, why the boom ?

• big data

• hardware

• software

artificial neural networks

collection of connected computational units (neurons) arranged in interconnected layers

very powerful and flexible

very popular for both supervised and unsupervised learning

state of the art across many complex domains, mainly based on unstructured data

artificial neural networks are very powerful and flexible

• more layers / neurons → more capacity / complexity

• specialized archotectures