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.

• This is a fun question! (+1) Commented Mar 29, 2019 at 22:41

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.

• Thank you, that made a lot of sense. Is it possible for the error to increase in the AdaBoost M1 implementation?
Commented Mar 30, 2019 at 0:25
• +1 That's really interesting! Commented Mar 30, 2019 at 0:33
• @saad: In probability the training error should not increase; if anything there is an additional early stopping condition to guarantee that. Commented Mar 30, 2019 at 0:51
• @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?
• Yes, $Z_t$ is used to make $D_t$ sum up to 1. $Z_t$ would be $\sum_i D_{t+1}(i)$. Commented Mar 30, 2019 at 9:31
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.