Weak learners

Trees may be weak learners

• Trees use to be sensitive to small changes in training data which lead to very different tree structure.
• This implies predictions are highly variable
• This may be explained because they are greedy algorithms making locally optimal decisions at each node without considering the global optimal solution.
  • This can lead to suboptimal splits and ultimately a weaker predictive performance.

There’s room for improvement

• In many situations trees may be a good option (e.g. for simplicity and interpretability)

• But there are issues that, if solved, may improve performance.

• It is to be noted, too, that these problems are not unique to trees.

  • Other simple models such as linear regression may be considered as weakl learners in may situations.

The bias-variance trade-off

• When we try to improve weak learners we need to deal with the bias-variance trade-off.

The bias-variance trade-off

How to deal with such trade-off

• How can a model be made less variable or less biased without this increasing its bias or variance?

• There are distinct appraches to deal with this problem

  • Regularization,
  • Feature engineering,
  • Model selection
  • Ensemble learning

Ensemble learners

• Ensemble learning takes a distinct based on “the wisdom of crowds”.

• Predictors, also called, ensembles are built by fitting repeated (weak learners) models on the same data and combining them to form a single result.

• As a general rule, ensemble learners tend to improve the results obtained with the weak learners they are made of.

Ensemble methods

• If we rely on how they deal with the bias-variance trade-off we can consider distinct groups of ensemble methods:

  • Bagging

  • Boosting

  • Hybrid learners

Emnsemble methods cheatsheet

Boosting & Stacking

• Boosting or Stacking combine distinct predictors to yield a model with an increasingly smaller error, and so reduce the bias.

• They differ on if do the combination

  • sequentially (1) or

  • using a meta-model (2) .

Hybrid Techniques

• Hybrid techniques combine approaches in order to deal with both variance and bias.

• The approach should be clear from their name:

  • Gradient Boosted Trees with Bagging

  • Stacked bagging

Bagging: bootstrap aggregation

• Decision trees suffer from high variance when compared with other methods such as linear regression, especially when \(n/p\) is moderately large.

• Given that this is intrinsic to trees, Breiman (1996) sugested to build multiple trees derived from the same dataset and, somehow, average them.

Averaging decreases variance

• Bagging relies, informally, on the idea that:

  • given \(X\sim F()\), s.t. \(Var_F(X)=\sigma^2\),
  • given a s.r.s. \(X_1, ..., X_n\) from \(F\) then
  • if \(\overline{X}=\frac{1}{N}\sum_{i=1}^n X_i\) then \(var_F(\overline{X})=\sigma^2/n\).

• That is, relying on the sample mean instead of on simple observations, decreases variance by a factor of \(n\).

• BTW this idea is still (approximately) valid for more general statistics where the CLT applies.

BAGGING: Bootstrap Aggregation

• Breiman (1996) combined the ideas of:
  • Averaging provides decreased variance estimates,
  • Bootstrap provides multiple (re)samples.
• He suggested: bootstrap aggregating :
  • Take resamples from the original training dataset
  • Learn the model on each bootstrapped training set to get a prediction \(\hat f^{*b}(x)\).
  • Average \(\hat f^{*b}(x)\) to obtain improved prediction/classification.

Bagging prediction/classifier

• For regression (trees) the bagged estimate is the average prediction at \(x\) from these \(B\) trees. \[ \hat f_{bag}(x)=\frac 1B \sum_{b=1}^B \hat f^{*b}(x) \]

• For classification (trees) the bagged classifier selects the class with the most “votes” from the \(B\) trees: \[ \hat G_{bag}(x) = \arg \max_k \hat f_{bag}(x). \]

Resampling based estimators

• The bootstrap was introduced as a way to provide standard error estimators.
• When used to compute \(\hat f_{bag}(x)\) or \(\hat G_{bag}(x)\), as described above, it provides direct estimators of a characteristic, not of their standard errors.
• However, the bagging process can also provide resampling based estimates of the precision of these estimators.

Out-Of-Bag observations

• Every time a resample is taken with replacement, some observations are omitted, due to the multiple occurring of others.

• These out-of-bag (OOB) observations can be used to build an estimate of prediction error.

Illustration of OOB EE

Source: https://www.baeldung.com/cs/random-forests-out-of-bag-error

Bagging - Prepare data

# Prepare "clean" dataset from raw data
ames <- AmesHousing::make_ames()
# Scale response variable to improve readability
ames$Sale_Price <- ames$Sale_Price/1000
# Split in test/training
set.seed(123)
train <- sample(1:nrow(ames), nrow(ames)/2)
# split <- rsample::initial_split(ames, prop = 0.7, 
#                        strata = "Sale_Price")
ames_train  <- ames[train,]
ames_test   <- ames[-train,]

Bagging - Build bag of trees

library(randomForest)
set.seed(12543)
bag.Ames <- randomForest(Sale_Price ~ ., 
                         data = ames_train, 
                         mtry = ncol(ames_train-1), 
                         ntree = 100,
                         importance = TRUE)

Bagging - Results

show(bag.Ames )

Call:
 randomForest(formula = Sale_Price ~ ., data = ames_train, mtry = ncol(ames_train -      1), ntree = 100, importance = TRUE) 
               Type of random forest: regression
                     Number of trees: 100
No. of variables tried at each split: 80

          Mean of squared residuals: 771498315
                    % Var explained: 87.89

Bagging - Prediction and accuracy

yhat.bag <- predict(bag.Ames, newdata = ames_test)
MSE= mean((yhat.bag -ames_test$Sale_Price)^2)
plot(yhat.bag, ames_test$Sale_Price, main=c("MSE= ", MSE))
abline(0, 1)

Bagging - Prediction and accuracy

Interpetability: The “achiles heel”

• Trees may have a straightforward interpretation,
  • Plotting the tree provides information about
    • which variables are important
    • how they act on the prediction
• Ensembles are less intuitive because
  • there is no consensus tree.
  • not clear which variables are most important.

Feature importance from Trees

• To measure feature importance, the reduction in the loss function (e.g., SSE) attributed to each variable at each split is tabulated.

• The total reduction in the loss function across all splits by a variable are summed up and used as the total feature importance.

Feature importance for Ensembles

• Variable importance measures can be extended to an ensemble simply by adding up variable importance over all trees built.

Random forests: decorrelating predictors

• Bagged trees, based on re-samples (of the same sample) tend to be highly correlated.
• Leo Breimann, again, introduced a modification to bagging, he called Random forests, that aims at decorrelating trees as follows:
  • When growing a tree from one bootstrap sample,
  • At each split use only a randomly selected subset of predictors.

Split variable randomization

• While growing a decision tree, during the bagging process,

• Random forests perform split-variable randomization:

  • each time a split is to be performed,
  • the search for the split variable is limited to a random subset of \(m_{try}\) of the original \(p\) features.

Random forests

Source: AIML.com research

How many variables per split?

• \(m\) can be chosen using cross-validation, but
• The usual recommendation for random selection of variables at each split has been studied by simulation:
  • For regression default value is \(m=p/3\)
  • For classification default value is \(m=\sqrt{p}\).
• If \(m=p\), we have bagging instead of RF.

Random forest algorithm (1)

RF Algorithm, from ch. 11 in (Boehmke and Greenwell 2020)

Random forest algorithm (2)

Out-of-the box performance

• Random forests tend to provide very good out-of-the-box performance, that is:
  • Although several hyperparameters can be tuned,
  • Default values tend to produce good results.
• Moreover, among the more popular machine learning algorithms, RFs have the least variability in their prediction accuracy when tuning (Probst, Wright, and Boulesteix 2019).

Out of the box performance

• A random forest trained with all hyperparameters set to their default values can yield an OOB RMSE that is better than many other classifiers, with or without tuning.
• This combined with good stability and ease-of-use has made it the option of choice for many problems.

Out of the box performance example

# number of features
n_features <- length(setdiff(names(ames_train), "Sale_Price"))

# train a default random forest model
ames_rf1 <- ranger(
  Sale_Price ~ ., 
  data = ames_train,
  mtry = floor(n_features / 3),
  respect.unordered.factors = "order",
  seed = 123
)

# get OOB RMSE
(default_rmse <- sqrt(ames_rf1$prediction.error))
## [1] 24859.27

1. Number of trees

2. Number of features (\(m_{try}\)).

3. Complexity of each tree.

4. Sampling scheme.

5. Splitting rule

• Default splitting rules favor features with many splits, potentially biasing towards certain variable types.
• Conditional inference trees offer an alternative to reduce bias, but may not always improve predictive accuracy and have longer training times.
• Randomized splitting rules, like extremely randomized trees (which draw split points completely randomly), improve computational efficiency but may not enhance predictive accuracy and can even reduce it.

Tuning hyperparameters

• RF are a good example of a common situachion in ML:
  • As the number of parameter increases,
  • finding their optimal values requires more effort
  • and can even become computationally unfeasible.
• As more complex algorithms with greater number of hyperparameters are introduced tuning strategies should also be considered.

Tuning strategies

Random forests in bioinformatics

• Random forests have been thoroughly used in Bioinformatics (Boulesteix et al. 2012).
• Bioinformatics data are often high dimensional with
  • dozens or (less often) hundreds of samples/individuals
  • thousands (or hundreds of thousands) of variables.

Application of Random forests

• Random forests provide robust classifiers for:
  • Distinguishing cancer from non cancer,
  • Predicting tumor type in cancer of unknown origin,
  • Selecting variables (SNPs) in Genome Wide Association Studies…
• Some variation of Random forests are used only for variable selection

Bagging vs Boosting

Source: Ensemble Learning: Bagging & Boosting

So what is Boosting

• Idea: create a model that is better than any of its individual components by combining their strengths and compensating for their weaknesses.

  • Multiple weak models are trained sequentially.

  • Each new model is trained to improve the errors made by the previous model.

• The final model is a weighted combination of all the models where the weights are determined by the accuracy of each model.

Historical background

• The boosting technique was proposed by Robert Schapire (Schapire 1989) and Yoav Freund in the 1990s.

• They introduced AdaBoost, the first widely-used Boosting algorithm.

  • It achieved significant success in various applications, including face detection and handwriting recognition.

• Other Boosting algorithms have become popular: Gradient Boosting, XGBoost, and LightGBM.

Adaboost

• AdaBoost (Adaptive Boosting) is a direct implementation of the “boosting” idea.

• It trains models sequentially, new models focusing on correcting the errors of the previous ones.

• Final Decision is made by combining models, giving more influence to the most reliable ones through

  • A weighted majority vote (classification) or

  • Weighted sum (regression).

Running Adaboost

• Adaboost proceeds iteratively by, at each iteration:

  • Fit the weak learner using initial weights.

  • Predict and identify misclassified observations.

  • Update observation weights:

    • decrease for correctly classified

    • increase for misclassified.

  • Assign a learner weight to the weak learner based on its accuracy.

• The final prediction is a weighted combination of all weak learners.

Adaboost Architecture

Source: Ensemble Learning: Bagging & Boosting

Adaboost applications

source: Evaluating the AdaBoost Algorithm for Biometric-Based Face Recognition

Adaboost has limitations

• Adaboost was a breakthrough algorithm that significantly improved the accuracy of ML models.

• However, Adaboost has its limitations.

  • It does not handle continuous variables very well.

  • Can be sensitive to noisy data and outliers,

  • May not perform well with complex datasets.

  • Its performance can reach a “plateau”: it will no longer improve after a certain number of iterations.

• In order to deal with some of these drawbacks different variants of boosting have been proposed.

Gradient Boosting

• Developed to overcome the limitations of Adaboost.

• Takes a different approach that can be linked with Optimization by Gradient Descent.

• Several advantages over Adaboost

  • Can handle continuous variables much better,

  • It is more robust to noisy data and outliers.

  • Can handle complex datasets and

  • Can continue to improve its accuracy even after Adaboost’s performance has “plateaued”.

Gradient boosting architechture

Source: Ensemble Learning: Bagging & Boosting

Relation with Gradient Descent

• Gradient Boosting can be seen as an extension of Gradient Descent, a popular optimization algorithm used to find the minimum of a function.

  • In Gradient Descent, the weights of the model are updated in the opposite direction of the gradient of the cost function.

  • In Gradient Boosting, the new model is trained on the negative gradient of the loss function, which is equivalent to minimizing the loss function in the direction of steepest descent.

Gradient Boosting Variations

• Multiple extensions from Gradient Boosting.

• XGBoost

  • Optimized implementation that uses regularization to control overfitting and provide better accuracy.
  • Won many competitions.

• LightGBM

  • Relies on a technique to reduce the number of samples used in each iteration.
  • Faster training, good for large datasets.

Boosting applications

• Fraud Detection

• Image and Speech Recognition

• Anomaly Detection

• Medical Diagnosis

• Amazon’s recommendation engine

• Models that predict protein structures from amino acid sequences

• Pattern identification in fMRI brain scans.

Advantages of Boosting

• Boosting, like other Ensemble methods, improves the accuracy of weak learners and achieve better predictive performance than individual models.

• Boosting also reduces overfitting by improving the generalization ability of models.

• Available in many flavors,

• Can be parallelized

• Strong experience in Real world applications and industry.

Limitations of Boosting

• Can be computationally expensive, especially when dealing with large datasets and complex models.

• Can be sensitive to noisy data and outliers,

• May not work well with certain types of data distributions.

• Not so good as “out-of-the-box”: Requires careful tuning of hyperparameters to achieve optimal performance, which can be time-consuming and challenging.

Boosting application with R and Python

• Many R packages implement the many variations of boosting:

  • ada,

  • adabag,

  • mboost,

  • gbm,

  • xgboost

  • An interesting option is to rely on the caret package which allows to run the distinct methods with a common interface.

• Inpython we usually rely on scikit-learn libraries although there are many alternative implementations

  • Scikit-learn ensemble
  • https://python-course.eu/machine-learning/boosting-algorithm-in-python.php

The bootstrap

• Bootstrap methods were introduced by Efron (1979) to estimate the standard error of a statistic.
• The success of the idea lied in that the procedure was presented as automatic, that is:
  • instead of having to do complex calculations,
  • it allowed to approximate them using computer simulation.
• Some called it the end of mathematical statistics.

Bootstrap Applications

• The bootstrap has been applied to almost any problem in Statistics.

  • Computing standard errors, Bias, Quantiles,
  • Building Confidence intervals,
  • Doing Significance tests, …

• We illustrate it with the simplest case: estimating the standard error of an estimator.

Empirical Distribution Function

The ECDF in R

x<- c(2,5,0,11,-1)
Fn <- ecdf(x)
knots(Fn)

[1] -1  0  2  5 11

cat("Fn(3) = ", Fn(3))

Fn(3) =  0.6

cat("Fn(-2) = ", Fn(-2))

Fn(-2) =  0

plot(Fn)

ECDF has good properties

• \(F_n (x)\) is a cumulative distribution function.

• \(F_n()\) is an important DF because it comes to be the best approximation that one can find for the theoretical (population) distribution function, that is: \[ F_n(x) \longrightarrow F(x), \text { uniformly in } x \text{ as } n \rightarrow \infty. \]

• This is stated in the Glivenko-Cantelli theorem also know as the Central Theorem of Statistics.

The Sample distribution function

Plug-in estimators

• Assume we want to estimate some parameter \(\theta\), that can be expressed as \(\theta (F)\), where \(F\) is the distribution function of each \(X_i\) in \((X_1,X_2,...,X_n)\).

• For example, \(\theta = E_F(X)=\theta (F)\).

• A natural way to estimate \(\theta(F)\) may be to rely on plug-in estimators, where \(F\) in \(\hat \theta (F)\) is substituted by some approximation (estimate) to \(F\).

Plug-in estimators

• A plug-in estimator is obtained by substituting \(F\) by an approximation to \(F\), call it \(\hat F\) in \(\theta(F)\): \[ \widehat {\theta (F)}=\theta(\hat{F}) \]
• Given that \(F_n\) is the best approximation to \(F\) a reasonable plug-in estimator is \(\theta(F_n)\).
• Common sample estimators are, indeed, plug-in estimators.

Some plug-in estimators

• Many estimators we usally work with are plug-in estimators.

Precision of an estimate

• An key point, when computing an estimator \(\hat \theta\) of a parameter \(\theta\), is how precise is \(\hat \theta\) as an estimator of \(\theta\)?

  • With the sample mean, \(\overline{X}\), the standard error estimation is immediate because the variance of the estimator is known: \(\sigma_\overline{X}=\frac{\sigma (X)}{\sqrt{n}}\)

  • So, a natural estimator of the standard error of \(\overline{X}\) is: \(\hat\sigma_\overline{X}=\frac{\hat{\sigma}(X)}{\sqrt{n}}\)

Standard error estimation

• Thus, a way to obtain a standard error estimator \(\widehat{\sigma}_{\widehat{\theta}}\) of an estimator \(\widehat{\theta}\) consists on replacing \(F\) with \(F_n\) in the ``population’’ standard error expression of \(\hat \theta\), \(\displaystyle{\sigma_{\hat \theta}= \sigma_{\hat \theta}(F)}\), whenever it is known.
• In a schematic form: \[ \sigma_{\hat \theta}= \sigma_{\hat \theta}(F) \Longrightarrow \sigma_{\hat \theta}(F_n)= \widehat{\sigma}_{\hat \theta}. \] That is, the process consists of “plugging-in” \(F_n\) in the (known) functional form, \(\sigma_{\hat \theta}(F)\) that defines \(\sigma_{\hat \theta}\)}.

The bootstrap (1)

• The previous approach, \(F\simeq F_n \Longrightarrow \sigma_{\hat \theta}(F) \simeq \sigma_{\hat \theta}(F_n)\) presents the obvious drawback that, when the functional form \(\sigma _{\hat{\theta}}(F)\) is unknown, it is not possible to carry out the substitution of \(F\) by \(F_n\).
• This is, for example, the case of standard error of the median or that of the correlation coefficient.

The bootstrap (2)

• The bootstrap method makes it possible to do the desired approximation: \[\hat{\sigma}_{\hat\theta} \simeq \sigma _{\hat\theta}(F_n)\] without having to to know the form of \(\sigma_{\hat\theta}(F)\).

• To do this,the bootstrap estimates, or directly approaches \(\sigma_{\hat{\theta}}(F_n)\) over the sample.

Bootstrap sampling (resampling)

• The bootstrap allows to estimate the standard error from samples of \(F_n\)

The resampling process

Resampling illustrated

Bootstrap Estimates of SE

Summary

From real world to bootstrap world: