3
$\begingroup$

The description of AdaBoost in Kevin Murphy's Machine Learning book (shown in a snapshot below) differs from the one in Wikipedia. I am trying to relate both definitions. Step by step, my questions are:

  1. What exactly is $\text{err}_m$ (step 4) supposed to capture below? Is this equivalent to the $\epsilon_t$ in Wikipedia's definition?

  2. Why isn't there a stopping rule in Kevin Murphy's method but there is one in Wikipedia's definition?

  3. There seems to be a typo in the parenthesis in the denominator, just in case - is it supposed to say the following?:

    $\text{err}_m = \frac{\sum_{i=1}^N w_{i,m} \mathbb{I}(\hat{y} \neq \phi(\mathbf{x_i)}}{\sum_{i=1}^N w_{i,m}} $

  4. Most importantly, Wikipedia provides the following criteria for choosing the weak learner and for stopping:

    $h_{t} = \underset{h_{t} \in \mathcal{H}}{\operatorname{argmax}} \; \left\vert 0.5 - \epsilon_{t}\right\vert$ where $\epsilon_{t} = \sum_{i=1}^{m} D_{t}(i)I(y_i \ne h_{t}(x_{i}))$

    $If \left\vert 0.5 - \epsilon_{t}\right\vert \leq \beta$, where $\beta$ is a previously chosen threshold, then stop.

    while Kevin's book defines the full algorithm as follows, and I don't see those two steps above in it:

enter image description here

$\endgroup$
2
$\begingroup$

1) The error, $err_{m}$, in step 4. captures the relative ratio of weighted prediction errors for each iterated pass, $m$, of the sequential learning algorithm ( $ 0 < err_{m} < 1$) . The errors are equivalent in both equations. You can see the weight distribution $D_{t}(i) = w_{i,t} / {\sum_{i=1}^m w_{i,t}}$. Only the chosen variable names are reversed ($m=t$, the iteration step in one case, and $m=N$ the number of observations in the other).

$\text{err}_m = \frac{\sum_{i=1}^N w_{i,m} \mathbb{I}(\hat{y} \neq \phi(\mathbf{x_i)}}{\sum_{i=1}^N w_{i,m}} = $

$\epsilon_{t} = \sum_{i=1}^{m} D_{t}(i)I(y_i \ne h_{t}(x_{i}))$

2) While the stopping rule is not shown in Kevin's algorithm, one of the theoretical requirements of the adaboost learner is to have weak learners slightly greater than chance. He does mention it in the text.

3) The unclosed parenthesis does appear to be a typo.

4) see 2)

$\endgroup$
  • $\begingroup$ Thanks. Are the $D_t(i)$ and the $w_{i,t}$ equivalent across both definitions? In Kevin's definition: I take that $\sum_{i=1}^N w_{i,m}$ does not need to equal 1, is that correct? In the Wikipedia definition the update rule is: $D_{t+1}(i) = \frac{ D_t(i) \exp(\alpha_t (2 I(y_i \ne h_{t}(x_{i})) - 1 )) }{\text{Denom}},$ where $\text{Denom}$ is, I quote, "the normalization factor ensuring that $D_{t+1}$ will be a probability distribution"... In other words, do the $w_{m,n}$ add up to 1 in Kevin's definition? and if not, is this a difference with respect to the definition in Wikipedia? $\endgroup$ – Josh Oct 28 '13 at 18:11
  • 1
    $\begingroup$ I see what you are saying. Since they do not explicitly show $D_{t}(i)$, it's likely they do the weight normalization in the update step. In that case, the $e_t$ term is just the total weighted error, prior to being normalized. The sum of the individual weights are not required to equal 1 in either example. I think what's important is that at some point the weights are normalized to guarantee a probability distribution for the next weight update. $\endgroup$ – pat Oct 28 '13 at 18:58

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.