I am reading an overview of AdaBoost written by Schapire, which calculates the upper bound of the training error in Eq. (5), section 3. In fact, it states that

$$\prod_{t}Z_t=\prod_{t}\left[2\sqrt{\epsilon_t(1-\epsilon_t)}\right]$$ with $$ \begin{align} Z_t=&\sum_{i}D_t(i)\exp(-\alpha_ty_ih_t(x_i))\\ \alpha_t=&\frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t} \end{align} $$ where $t$ denotes the iteration times, $i$ the index of data points, $h_t$ the classifier selected at the $t$th round, $\alpha_t$ the weight of $h_t$, and $D_t$ satisfies $$D_{t+1}(i)=\frac{D_t(i)\exp(-\alpha_ty_ih_t(x_i))}{Z_t}$$

In order to simplify $\prod_{t}Z_t$, I've tried: $$ \begin{align} Z_t=&\sum_{i}D_t(i)\exp(-\alpha_ty_ih_t(x_i))\\ =&\sum_{i}D_t(i)\left(\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\right)^{-y_ih_t(x_i)}\\ =&\sum_{y_i\ne h_t(i)}D_t(i)\left(\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}\right)+\sum_{y_i= h_t(i)}D_t(i)\left(\sqrt{\frac{\epsilon_t}{1-\epsilon_t}}\right) \end{align} $$

But I don't what to do next. Can anyone give hints?


Recall that: $$ \epsilon_t = \sum_{y_i\neq h_t(i)}{D_t(i)} \qquad 1 - \epsilon_t = \sum_{y_i = h_t(i)}{D_t(i)} $$ That should get you to the result.

  • $\begingroup$ Oh yes, that's it. I should blame myself. $\endgroup$ – ziyuang Dec 7 '11 at 19:02

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.