Boosting

Articoli di approfondimento

Boosting

Il Boosting è un metodo generale per la creazione di un modello di previsione complesso che utilizza componenti di costruzione semplici chiamati weak learner.
Quessto algoritmo inizia a fittare un weak learner sul training data.
Successivamente il weak learner viene nuovamente adattato, ma dando più peso (importanza) alle osservazioni adattate male/non classificate.
Questo processo viene ripetuto finché non viene raggiunta una regola di arresto.

In questo capitolo andremo ad analizzare tre tipi di algoritmi: * boosting with squared error loss (L2-boosting) utilizza alberi di regressione come weak learners


L2-boosting algoritmo per alberi di classificazione

L2-boosting costruisce con gli alberi di regressione un modello adattando ripetutamente ad un albero di regressione ai residuals. Questo è diverso dalle Random Forest perché ogni albero sta cercando di correggere gli errori commessi dall’insieme di alberi precedentemente coltivati


  1. Inizializzo \(\hat{f}(x)= \bar{y}\) and \(r_i = y_i - \bar{y}\) for \(i=1,\ldots,n\)

  2. Facciamo un ciclo For per \(b=1,2,\ldots, B\) e ripetiamo:

    • Fittiamo un albero \(\hat{f}^b\) con \(d\) splits su dati \((x_1,r_1),\ldots, (x_n,r_n)\)
    • Aggiorniamo \(\hat{f}\) aggiungendo una versione del nuovo albero: \[\hat{f}(x) \leftarrow \hat{f}(x) + \lambda \hat{f}^b(x)\]
    • Aggiorniamo i residui: \[r_i \leftarrow r_i - \lambda \hat{f}^b(x_i)\]

  3. L’output del modello è: \[\hat{f}(x) = \bar{y}+ \sum_{b=1}^{B} \lambda \hat{f}^b(x)\]

Parametri di tuning per il boosting:

library(rpart)

rm(list=ls())
set.seed(123)
n = 100
x=sort(runif(n)*2*pi)
y=sin(x)+rnorm(n, sd=0.5)
plot(y~x)
curve(sin(x), min(x),max(x), col="red", add=T)

Qui sotto c'è una applicazione che mostra come i tre paratri influenzano lo sviluppo dell'algoritmo (questa applicazione è stata fatta con la versione graduita di shinyapp quindi mi scuso per eventuali disagi fornisco anche il codice .Rmd cosi da poter agevolare la visualizzazione: codice.Rmd)

ESEMPIO 

rm(list=ls())
# data import
als <- read.table("http://web.stanford.edu/~hastie/CASI_files/DATA/ALS.txt",header=TRUE)
# split into training and test
train = als[als$testset==F,-1]
n = nrow(train)
test = als[als$testset==T,-1]
m = nrow(test)

Usiamo la funzione gbm() per fittare il modello boosting sui dati ALS impostando:

# library gbm
  library(gbm)
set.seed(123)

# tuning parameters
d = 4
nu = 0.02
B = 500
K = 10

# boosted regression trees fit
fit <- gbm(dFRS ~ ., 
              distribution = "gaussian",
              data = train,
              n.trees = B,
              interaction.depth = d,
              shrinkage = nu,
              bag.fraction = 1, 
              cv.folds= K)

print(fit)
## gbm(formula = dFRS ~ ., distribution = "gaussian", data = train, 
  ##     n.trees = B, interaction.depth = d, shrinkage = nu, bag.fraction = 1, 
  ##     cv.folds = K)
  ## A gradient boosted model with gaussian loss function.
  ## 500 iterations were performed.
  ## The best cross-validation iteration was 292.
  ## There were 369 predictors of which 136 had non-zero influence.
# predictions at each step b
  yhats = sapply(1:B, function(b) predict(fit, newdata = test, n.trees = b))

# test MSE at each step b
MSEs = apply(yhats, 2, function(yhat) mean( (test$dFRS - yhat)^2))
plot(1:B, MSEs, xlab="Number of trees", ylab="test MSE", type="l")

which.min(MSEs)
## [1] 188
# bstop
bstop = gbm.perf(fit, method="cv")

##                                           var   rel.inf
## Onset.Delta                       Onset.Delta 30.443296
## alsfrs.score.slope         alsfrs.score.slope  6.051237
## mean.slope.svc.liters   mean.slope.svc.liters  3.774028
## mean.slope.weight           mean.slope.weight  3.098220
## last.slope.weight           last.slope.weight  3.003234
## last.alsfrs.score           last.alsfrs.score  2.939656
## last.slope.bp.systolic last.slope.bp.systolic  2.691271
## mean.slope.fvc.liters   mean.slope.fvc.liters  2.058366
## mean.speech                       mean.speech  2.033955
## max.dressing                     max.dressing  2.012729
# fitted functions
plot(fit, i.var="Onset.Delta", n.trees=bstop)

plot(fit, i.var="last.slope.weight", n.trees=bstop)

Adaboost

L’algoritmo AdaBoost.M1 algorithm (Freund and Schapire, 1997), è stato sviluppato per problemi di classificazione binaria \(Y \in \{-1,1\}\) e utilizza alberi di classificazione come weak learners.



1. Inizializzo i pesi delle osservazioni pari a \(w_i=1/n, i=1,\ldots,n\)

  1. Creo un ciclo For per \(b=1,\ldots,B\) e ripeto:

    • Costruisco alberi di classificazione \(\hat{C}^{b}\) sul training set utilizzando i pesi \(w_i\) (come farei in un bootstrap parametrico)
    • Calcolo i nuovi pesi sfruttando gli errori commessi nella classificazione precedente \(\hat{C}^{b}\) \[\mathrm{Err}^{b} = \frac{\sum_{i=1}^{n}w_i I\{ y_i \neq \hat{C}^{b}(x_i) \}}{\sum_{i=1}^{n}w_i}\]
  1. Gli output dell’algoritmo sono \(\hat{C}^{B}(x) = \mathrm{sign}( \sum_{b=1}^B \alpha^{b} \hat{C}^{b}(x) )\)

Gradient boosting algorithm (gbm)

  1. Partiamo imponendo \(\hat{f}^0(x)=0\), e impostiamo \(B\) e il parametro di restringimento (shrinkage parameter) \(\lambda>0\) come abbiamo fatto negli algoritmi precedenti

  2. Creo ciclo For per \(b=1,\ldots,B\) e ripeto i seguenti steps:

    1. Calcoliamo il gradiente negativo della funzione di perdita (pointwise negative gradient of the loss function) per ogni punti fittati \[r_i = -\frac{\partial L(y_i,f_i)}{\partial f_i}\left|_{f_i=\hat{f}^{b-1}(x_i)}\right., \quad i=1,\ldots,n\]

    2. Approssimiamo qeusti valori attraverso un albero \(g\) con una profondità \(d\): \[(x_1,r_1),\ldots,(x_n,r_n)\rightarrow \hat{g}(x)\]

    3. Aggiorniamo i dati dello step precedente del ciclo \[\hat{f}^b(x) = \hat{f}^{b-1}(x) + \lambda \hat{g}(x)\]

  3. L’output alla fine dei ciclo è \(\hat{f}^b(x), b=1,\ldots,B\)

Loss functions

Si può notare che la funzione di perdità di Laplace non è differenziabile quando \(y=f(x)\); i valori negtivi del gradiente vengono posti uguali a 0.