Ensemble Learning Methods

Ensemble Learning Overview

• Ensemble methods involve training multiple models and combining them to improve accuracy
• Combining the models involves hard or soft voting

Hard Voting

• Individual classifiers vote for a class, with the majority winning
• For regression, each model's prediction is averaged for the final prediction

Soft Voting

• Classifiers provide a probability distribution over possible classes or a numerical prediction with certainty
• Predictions are weighted based on the classifier's importance, then summed or averaged
• The target label with the highest sum of weighted probabilities wins the vote

Why Use Ensemble Methods

• To reduce bias and variance
• Bias is a systematic deviation from the truth
• Variance is a model's sensitivity to peculiarities in the training data
• The bias-variance tradeoff aims to minimize both systematic and random errors
• Overall, it is desired to reduce bias and variance

Reducing Bias

• Using multiple classifiers can increase accuracy
• Consider a scenario with 3 independent classifiers, each having a 60% accuracy rate (a = 0.6)
• An ensemble classifier, which follows the majority among the three, can achieve higher accuracy

Reducing Variance

• Ensemble learning can reduce variance using multiple models
• If we have n models with the same variance σ², the average variance formula is expressed differently if models corelate or do not

Three Main Ensemble Learning Methods

• Bagging involves bootstrap aggregating, with classifiers trained independently in parallel ("averaging" classifiers)
• Boosting involves incrementally "adding" classifiers, with classifiers learned sequentially in an adaptive way
• Stacking combines predictions from previous models

Bagging (Bootstrap Aggregating)

• Creates k bootstrap samples (D1, D2,..., Dk)
• Trains distinct base classifiers (hᵢ) on each bootstrap sample Di, which are usually weaker learners of the same type
• Classifies new instances by averaging the classifier votes
• Introduces variation by using training subsamples and feature selection for each classifier

Bootstrap Sampling

• Given a set D containing m training examples, create Di by drawing m examples at random with replacement from D
• Approximately 63% of samples are distinct in each bootstrap

Random Forest

• Composed of a collection of trees
• Decision trees recursively partition samples based on Gini coefficient or information gain until a criterion is met
• Random Forest is composed of a collection of random trees
• There is variation on training subsamples and selecting among a subset of all features for each tree

Random Forest and Tree Bagging: Feature Selection

• Tree Bagging selects features at bootstrap sampling and over all features
• Random Forest searches best split in a subset of randomly selected features, where the number of features is the square root of n_features
• ExtraTrees: Extremely Randomized Trees use whole original samples, randomize the value to split

Scikit-learn Support

• Out-of-Bag (Oob) evaluation uses the remaining 37% of training instances to evaluate each predictor
• Feature importance is a weighted average across all trees measuring impurity reduction on average

Bagging Limitations

• Inefficient Bootstrap Sampling: Every example has = chance to be sampled, with no distinction between simple or difficult examples
• Inefficient Model Combination: Constant weight for each classifier, with no distinction between accurate or inaccurate classifiers

Improving Bagging Efficiency

• Better sampling strategy: Focus on difficult-to-classify examples which leads to Boosting
• Better combination strategy: Accurate model should be assigned larger weights, so use another machine learning model to combine the results which leads to Stacking

Boosting

• Additive model that compensates shortcomings of classifiers
• Adaptive Boosting (Adaboost) weights the data
• Gradient Boosting (Gradient Descent + Boosting) identifies shortcomings by gradients

Adaptive Boosting: Example

• Adaptively adjusts weights based on classification performance
• Instances classified incorrectly have increased weights
• Instances classified correctly have decreased weights
• Adaptive Boosting: Example Instances that are wrongly classified will have their weights are increased
• Instances that are correctly classified will have their weights decreased

AdaBoost Algorithm

• Given input x, where xᵢ ∈ X, and classification 𝑦𝑖 ∈ {−1, +1}
• All instances get an initial start up weight value
• Iteratively calculate new base learners using weighted instances set and compute the misclassification rate et
• Update instance weights for the new iteration with Dt+1(i) depending on instance importance

Gradient Boosting: Intuition

• It consists of an error-correction approach, fixes mistakes from previous classifiers

Gradient Boosting

• In regression form, the model minimizes the square loss
• Models are created that minimize square loss with the purpose to get closer to the true model

Gradient Boosting Algorithm Summary

• Utilizes additive model F = Σt ρtht
• Compensates shortcomings of existing models, adjusting with the factor F = F + ph, p = learning rate
• Identifies shortcomings with the negative gradients

Stacking

• Stacking is an ensemble learning technique using predictions from many models to build a new one
• Training can be broken down in two stages

1. Splitting into 2 sets for training + tests
2. Splitting training data into folds for K-fold cross-validation

Midterm Exam

• The midterm exam is April 3, with a mix of T/F and Multiple Choice questions
• Primarily closed book format