Adaboost is a powerful algorithm for predicting models. However, a major disadvantage is that Adaboost may lead to over-fit in the presence of noise. Freund, Y. & Schapire, R. E. (1997) proved that the training error of the ensemble is bounded by the following expression:
\begin{equation}\label{ada1}e_{ensemble}\le \prod_{t}2\cdot\sqrt{\epsilon_t\cdot(1-\epsilon_t)}
\end{equation}
where $\epsilon_t$ is the error rate of each base classifier $t$. If the error rate is less than 0.5, we can write $\epsilon_t=0.5-\gamma_t$, where $\gamma_t$ measures how much better the classifier is than random guessing (on binary problems). The bound on the training error of the ensemble becomes
\begin{equation}\label{ada2}
e_{ensemble}\le \prod_{t}\sqrt{1-4{\gamma_t}^2}\le e^{-2\sum_{t}{\gamma_t}^2}
\end{equation}
Thus if each base classifier is slightly better than random so that $\gamma_t>\gamma$ for some $\gamma>0$, then the training error drops exponentially fast. Nevertheless, because of its tendency to focus on training examples that are misclassified, Adaboost algorithm can be quite susceptible to over-fitting.
We will give a new simple proof of \ref{ada1} and \ref{ada2}; additionally, we try to explain why the parameter $$\alpha_t=\frac{1}{2}\cdot\log\frac{1-\epsilon_t}{\epsilon_t}$$ in boosting algorithm.
AdaBoost Algorithm:
Recall the boosting algorithm is:
Given $(x_1, y_1), (x_2, y_2), \cdots, (x_m, y_m)$, where $x_i\in X, y_i\in Y=\{-1, +1\}$.
Initialize $$D_1(i)=\frac{1}{m}$$ For $t=1, 2, \ldots, T$: Train weak learner using distribution $D_t$.
Get weak hypothesis $h_t: X\rightarrow \{-1, +1\}$ with error \[\epsilon_t=\Pr_{i\sim D_t}[h_t (x_i)\ne y_i]\] If $\epsilon_i >0.5$, then the weights $D_t (i)$ are reverted back to their original uniform values $\frac{1}{m}$.
Choose
\begin{equation}\label{boost3}
\alpha_t=\frac{1}{2}\cdot \log\frac{1-\epsilon_t}{\epsilon_t}
\end{equation}
Update:
\begin{equation}\label{boost4}
D_{t+1}(i)=\frac{D_{t}(i)}{Z_t}\times
\left\{\begin{array}{c c}
e^{-\alpha_t} & \quad \textrm{if $h_t(x_i)=y_i$}\\
e^{\alpha_t} & \quad \textrm{if $h_t(x_i)\ne y_i$}
\end{array} \right.
\end{equation}
where $Z_t$ is a normalization factor.
Output the final hypothesis: \[H(x)=\text{sign}\left(\sum_{t=1}^{T}\alpha_t\cdot h_t(x)\right)\]
