Adaboost Notation Confusion

Question

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.

Answer 1

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.

Answer 2

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.