3
$\begingroup$

The adaboost algorithm is as follows:

$\mathbf{Input}$: sequence of m examples $<(x_1,y_1),...,(x_m,y_m)>$ with the labels $y_i \in Y = \{1,...,k\}$
weak learning algorithm WeakLearn
integer T specifying the number of iterations
$\mathbf{Initialize}$: $D_i(i) = \frac{1}{m}$ for all i
$\mathbf{Do}$ t = 1,2,...,T:
1. Call WeakLearn, providing it with distribution $D_t$
2. Get back a hypothesis $h_t : X \rightarrow Y$
3. Calculate the error of $\displaystyle h_t: \epsilon_t = \sum_{i:h_t(x_i)\neq y_i} D_i(i)$
If $\epsilon_t > 0.5$, then set $T = t - 1$ and abort loop.
4. $\displaystyle \beta_t = \frac{\epsilon_t}{1-\epsilon_t}$
5. Update distribution $D_t$ as $\displaystyle D_{t+1} = \frac{D_t(i)}{Z_t} \times \begin{cases} \beta_t, & \text{if $h_t(x_i) = y_i$} \\ 1, & \text{otherwise} \end{cases} $
where $Z_t$ is a normalization constant (chosen so that $D_{t+1}$ will be a distribution)

My confusion is regarding two steps:

  1. What does the notation for the error, $\epsilon_t$ mean? Does it mean add all the weights if there is a missclassification?

  2. What does the statement If $\epsilon_t > 0.5$, then set T = t - 1 and abort loop. mean? Is it stating to abort the leap (as in break) or do not count this as an iteration and continue to loop?

Some details: I am actually randomly choosing from $D_i$ based on the sample weights. The idea to generate a weak SVM classifier.

$\endgroup$
  • 1
    $\begingroup$ This is a fun question! (+1) $\endgroup$ – usεr11852 Mar 29 at 22:41
3
$\begingroup$
  1. As Lucas already said (+1), yes, your intuition is correct; that is the sum of the weighted error terms.
  2. This steps is indeed awkward for Adaboost, because it is not the Adaboost commonly used but actually the early version of what we call Adaboost algorithm, namely Adaboost.M1; it is presented in Freund & Schapire (1996) Experiments with a New Boosting Algorithm. Adaboost.M1 explicitly encoded what the authors describe as: "(...) Adaboost (...), theoretically can be used to significantly reduce the error of any learning algorithm that consistently generates classifiers whose performance is a little better than random guessing". Therefore as soon as $\epsilon_t > 0.5$, the iteration stopped.

Some further commentary on Point 2: As more people studied the algorithm it became clear that the break condition was unnecessary. The reproduction of Adaboost.M1, simply as Adaboost, in Friedman et al. (2000) Additive logistic regression: a statistical view of boosting does not include this "hot-fix"/break condition. If anything it was superfluous for Friedman et al.'s core notion that the: "AdaBoost algorithm (population version) builds an additive logistic regression model via Newton-like updates for minimizing $E(e^{-yF(x)})$". To that extent, the break condition in Adaboost.M1 became uninterpretable when we moved to LogitBoost, BrownBoost and other boosting variances. F&S obviously knew this; it is evident even in their 1996 paper; the algorithm Adaboost.M2 does not include any break conditions. As a final note, I think that the CV.SE thread Binary classifiers with accuracy < 50% in Adaboost? will also help one's understanding of the issue. It discusses why this break condition is indeed redundant; in short, we can naturally "flip" the signs of a "bad" classification result to get a "good" one.

$\endgroup$
  • $\begingroup$ Thank you, that made a lot of sense. Is it possible for the error to increase in the AdaBoost M1 implementation? $\endgroup$ – saad Mar 30 at 0:25
  • $\begingroup$ +1 That's really interesting! $\endgroup$ – Lucas Farias Mar 30 at 0:33
  • $\begingroup$ @saad: In probability the training error should not increase; if anything there is an additional early stopping condition to guarantee that. $\endgroup$ – usεr11852 Mar 30 at 0:51
  • $\begingroup$ @usεr11852 Thank you. Can you also explain how the normalization term, Zt, is computed? Zt, as I understand, is the a term that makes Dt into a distribution (i.e. a sum of 1). In that case, is Zt a sum of Zt or Zt+1? $\endgroup$ – saad Mar 30 at 5:40
  • $\begingroup$ Yes, $Z_t$ is used to make $D_t$ sum up to 1. $Z_t$ would be $\sum_i D_{t+1}(i)$. $\endgroup$ – usεr11852 Mar 30 at 9:31
2
$\begingroup$
  1. Yes. The notation $i:h(x_i) \neq y_i$ means you'll pick $i$'s that satisfy the given condition; in this case that the computed hypothesis does not correspond to the true value.
  2. This step looks weird when compared to other descriptions of this algorithm (this one (p. 58), for example). Specially when you consider that there are still steps to come after abortion, and that convergence would not be achieved this way.

I think there's something off. If you can provied the source, we can maybe check it further.

$\endgroup$
  • 1
    $\begingroup$ I can't figure out 2) either. $\endgroup$ – Matthew Drury Mar 29 at 16:03
  • 2
    $\begingroup$ @MatthewDrury It is the Adaboost.M1 formulation, mid to late 90's. It is a break; it tries to encapsulate the idea that the learner is better than chance. I might expand on this tonight! $\endgroup$ – usεr11852 Mar 29 at 18:36
  • $\begingroup$ Yah, I can see that it's saying "This weak lerner learned worse than a coin flip, so bail", but it's unclear to me how that is even possible. Would enjoy the expansion! $\endgroup$ – Matthew Drury Mar 29 at 20:13
  • $\begingroup$ @MatthewDrury: You are right, it is not possible. "Most of us" learned boosting in the context of Friedman et al. (2000) and Friedman (2001). Adaboost.M1 predates these by almost half a decade so our priors aren't exactly flat! $\endgroup$ – usεr11852 Mar 29 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.