# The upper bound of the training error of AdaBoost

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.