Adaptive Boosting

back to notes

Bootstrap Estimation

  From Wikipedia: "Bootstrapping alludes to a German legend about a Baron Münchhausen, who was able to lift himself out of a swamp by pulling himself up by his own hair. In later versions he was using his own boot straps to pull himself out of the sea which gave rise to the term bootstrapping."
Bootstrapping here (Bradley Efron, 1979) comes from statistics and is used to estimate a parameter and its variance. It follows these steps:

• Draw n samples from a dataset D repeatedly
• Get estimates for each set of samples
• The final estimate is the average of all estimates

See also cross-validation and jackknife.

Bagging/Aggregate Bootstrapping/Bootstrap Aggregating

  Bagging is used to increase a classifier's stability, while reducing its variance. It follows these steps:

• Draw several times n samples from a dataset D, each time replacing them
• learn the classifier for each set of samples
• The final classification is the vote of all learned classes

Boosting (Shapire 1989)

  . It follows these steps:

• Draw n samples from a dataset D, and train C1
• Draw m samples from D with half of the samples those that were misclassified by C1, and train C2
• Select all samples that C1 and C2 disagree on, train C3
• vote between C1, C2 and C3 to get the final classification

AdaBoost (Freund, Schapire)

Adaboost stands for adaptive boosting.

Given:

   classified samples: (x_0,0,x_0,1,...x_0,n, c₀), (x_1,0,x_1,1,...x_1,n, c₁), ..., (x_N,0,x_N,1,...x_N,n, c_N)

   where the classes c_i are +1 or  -1    (i=1..N)

   initial weights are starting all equal:  w_0,i = 1/N    (i=1..N)

Algorithm:  for training iterations t (t=1..T) for all i classifiers (i=1..N):

   1) Get all the classes back from the classifiers: h_i     

   2) Calculate the error:  E = P(h_i!=c_i)

   3) Calculate alpha:

   4) Update the weights:

   5) Result: 

• Another short intro re. AdaBoost: MlNet/OIS explanation