3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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