Page cover image

#11: Ensemble Learning

  • 3 min

#11: Ensemble Learning content

Created
Topics
Bagging & Boosting

Bagging (Bootstrap Aggregating)

🎯
Reduce variance w/o increasing bias
Var(Xˉ)=Var(X)NVar(\bar X)=\frac{Var(X)}N : Averaging reduce variance
 
E.g. Cross Validation: give more stable error estimate by averaging multiple independent folds

Bootstrap Sampling

🎯
A method to sample from our sample data to simulate sampling from the population
  1. Use empirical distribution of our data to estimate the true unknown data-generating distribution
  1. Not all samples will be chosen and each could be chosen twice
  1. P(chosen) = 0.632

Classification Tree Example

Average the predictions over a collection of bootstrap samples

Setup & Training

Number of trees = BB
Bootstrap sample size = original sample size nn
Train each tree on each bootstrap sample

Making Predictions

  1. Plurality vote over the predictionsy^x0bagging =arg⁡max⁡k=1,…,K∑b=1BI(gbtree (x0)=k)\hat{y}_{x_{0}}^{\text {bagging }}=\arg \max _{k=1, \ldots, K} \sum_{b=1}^{B} I\left(g_{b}^{\text {tree }}\left(x_{0}\right)=k\right)
  1. Predict with the combined probabilitiesp^kbagging (x0)=1B∑i=1Bp^ki(x0) for k∈[1,K]Y^x0bagging =arg⁡max⁡k=1,…,Kp^kbagging (x0)\hat{p}_{k}^{\text {bagging }}\left(x_{0}\right)=\frac{1}{B} \sum_{i=1}^{B} \hat{p}_{k}^{i}\left(x_{0}\right) \quad \text { for } k\in[1,K]\\ \hat{Y}_{x_{0}}^{\text {bagging }}=\arg \max _{k=1, \ldots, K} \hat{p}_{k}^{\text {bagging }}\left(x_{0}\right)
    • More well behaved than 1.

Out-of-Bag (OOB) Error Estimation

OOB Samples: remaining 37.7%37.7\% sample not contained in each bootstrap samples
⇒ See as test data
  • Each sample is an OOB for B3\frac B 3 trees
  • Predict the response for the i-th observation
? When to record if a sample is OOB
 

Random Forests

💡
Decorrelates individual bagged trees by small tweaks

Random Feature Selection

💡
Essentially drop out a random subset of input features
At each node, select a random subset of mm predictors
Split along the best in the subset
In practice: m≈# input featuresm\approx\sqrt \text{\# input features}

Summary

notion image

Analysis

Random forests are better predictors than bagged trees
notion image

Boosting

💡
A sequential (iterative) process: Combine multiple week classifier to classify non-linearly-separable data
Weak learner: a classification model w/ accuracy little more than 50%
  • If use a strong learner, will 100% overfit
  1. Associate a weight to each training sample: wi=1nw_i=\frac 1 n
  1. Loop until convergence:
    1. Train the weak learner on a bootstrap sample of the weighted training set
    2. Increase wiw_i for misclassified sample ii; decrease otherwise

Prediction

DO a weighted majority voting on trained classifiers

Intuition

notion image

Adaboost

notion image
  • αr\alpha_r = weight for model rr
  • ϵr\epsilon_r = classification error for model rr
  • wr+1(i)w_{r+1}(i) weight of sample ii computed from model rr's classification errors

Gradient Boosting

💡
Fit a model on the residuals & add it to the origional

Intuition

Given a model non-perfect model F
  1. Cannot delete anything from model F
  1. Can only add additional model to F to get
    Fnew(xi)=F(xi)+h(xi)=yiF_{new}(x_i)=F(x_i)+h(x_i)=y_i by intuition
Use regression to find h(xi)=yi−F(xi)h(x_i)=y_i-F(x_i)

Procedure

Training set D′={(x1,[y1−F(x1)]),(x2,[y2−F(x2)]),…,(xn,[yn−F(xn])}\mathscr{D}^{\prime}=\left\{\left(x_{1},\left[y_{1}-F\left(x_{1}\right)\right]\right),\left(x_{2},\left[y_{2}-F\left(x_{2}\right)\right]\right), \ldots,\left(x_{n},\left[y_{n}-F\left(x_{n}\right]\right)\right\}\right.= residuals of the model
Train hh on D′\mathscr{D}^{\prime}
New Model = F+hF+h
Repeat until satisified

Theory: Relation to Gradients

Squared Loss function L(yi,F(xi))=(yi−F(xi))2L(y_i,F(x_i))=(y_i-F(x_i))^2
Minimize L=∑i=1nL(yi,F(xi))\mathscr L=\sum_{i=1}^nL(y_i,F(x_i)) wrt F(xi)F(x_i) gives
∂L∂F(xi)=∂∑i=jnL(yj,F(xj))∂F(xi)=∂L(yi,F(xi))∂F(xi)=−F(xi)−yi=−g(xi)\frac{\partial \mathscr{L}}{\partial F\left(x_{i}\right)}=\frac{\partial \sum_{i=j}^{n} L\left(y_{j}, F\left(x_{j}\right)\right)}{\partial F\left(x_{i}\right)}=\frac{\partial L\left(y_{i}, F\left(x_{i}\right)\right)}{\partial F\left(x_{i}\right)}=-F\left(x_{i}\right)-y_{i}=-g(x_i)
⇒ Residuals =−= -gradients

Update Rule

Ft+1(xi)=Ft(xi)+h(xi)=Ft(xi)+[yi−F(xi)]=Ft(xi)−∂L∂F(xi)θi=θi−η∂L∂θi\begin{aligned}F_{t+1}\left(x_{i}\right) &=F_{t}\left(x_{i}\right)+h\left(x_{i}\right) \\&=F_{t}\left(x_{i}\right)+\left[y_{i}-F\left(x_{i}\right)\right] \\&=F_{t}\left(x_{i}\right)-\frac{\partial \mathscr{L}}{\partial F\left(x_{i}\right)} \\\theta_{i} &=\theta_{i}-\eta \frac{\partial \mathscr{L}}{\partial \theta_{i}}\end{aligned}
Can use other loss function

Gradient Boosted Decision Trees (if time permits)