Adaboost Algorithm

A boosting algorithm that minimizes 0-1 Loss

${ϵ}_t=\sum _n{w}_t(n)1(y_n\ne h_t(x_n))$

• Error (0-1 loss specifically) for the weight given to $h_t(\cdot )$, the weak (i.e. base) classifier for this epoch $t$ in the training cycle
• $n$ corresponds to a particular training example
• $w_t(n)$ is the weight for this epoch $t$ for a particular sample $n$
  • Set to $\frac{1}{n}$ for $t=1$

${\beta }_t=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$

• Contribution of $h_t$ to final classifier
• $-\infty$ for large ${ϵ}_t$
  • However, negative values for ${\beta }_t$ are always made positive by flipping the value of the weak classifier
• $0$ for ${ϵ}_t=\frac{1}{2}$, or when guessing randomly
• $1$ for ${ϵ}_t=\frac{1}{3}$
• $\infty$ for 0 ${ϵ}_t$

$w_{t+1}(n)\propto w_t(n)e^{-{\beta }_t{y}_n{h}_t(x_n)}$

• Updated weights. We compute this step $T$ times, or the number of epochs we’d like until we’ve minimized error

$h[x]=\text{sign}\left[\sum _{t=1}^T{\beta }_t{h}_t(x)\right]$

• Final classifier

Exponential Loss Minimization

$a_t(x)=a_{t-1}(x)+{\beta }_t{h}_t(x)$

• The Adaboost classifier for the current epoch equals the previous Adaboost classifier plus the current weighted base classifier
  
• Adaboost minimizes empirical risk of exponential loss

$w_t(n)=e^{-y_n{a}_{t-1}(x)}$

• The weight of the exponential loss of a particular weak classifier is the exponential loss of our previous Adaboost classifier
• $a_{t-1}(x)$ is the Adaboost classifier for epoch $t-1$

Training

• AdaboostTrain():
  • For each of $d$ features, sort data points for that feature value
    • This is the pre-sorting step and contributes $O(dN\log N)$ to the runtime
  • for $t$ in $T$:
    • $h_t(x):=$ decision stump threshold that minimizes error
      • Can be found in $O(dN)$ time by going for each of $d$ features, starting with the smallest threshold, calculating error, moving the threshold to the next datapoint as determined by our pre-sorting, updating the error in $O(1)$ time, and so on until we find the threshold that had the smallest error
    • ${ϵ}_t:=\sum _n{w}_t(n)1(y_n\ne h_t(x_n))$
    • ${\beta }_t:=\frac{1}{2}\ln \left(\frac{1-{ϵ}_t}{{ϵ}_t}\right)$
    • $w_{t+1}(n):=w_t(n)e^{-{\beta }_t{y}_n{h}_t(x_n)}$
• $h[x]=\text{sign}\left[\sum _{t=1}^T{\beta }_t{h}_t(x)\right]$

$O(dN\log N+dNT)$

• Training runtime using decision stumps as the base classifier