\scriptsize{
\begin{flushleft}

{\bfseries ALGORITHM AdaBoost.M1}\\
\bigskip
\bigskip
{\bfseries Input:}
\begin{itemize}
\item sequence of N examples $<(x_1,y_1),...,(X_N,y_N)>$ with labels $y_i \in Y = \{1,...,K\}$ 
\item distribution $D$ over the examples 
\item weak learner algorithm
\item integer T specifying the number of iterations
\end{itemize}
\bigskip
{\bfseries Initialize} the weight vector: $w_i^1 = D(i)$ for $i = 1,...,N$.\\
\bigskip
\bigskip
{\bfseries DO for} $t = 1,2,...,T$
\begin{enumerate}
\item Set
$$
 {\pv}^t  = \frac{ {\wv}^t }{\sum_{i=1}^N w_i^t}
 $$
 \item
 Call weak learner, providing it with the distribution ${\pv}^t$; get back the hypothesis $h_t: X \rightarrow Y$.
 \item
 Calculate the error of $h_t: e_t = \sum_{i=1}^N p_i^t\vdash h_t(x_i) \neq y_i \dashv$.
 \item
 Set $\beta_t = \frac{e_t}{1-e_t}$.
 \item
 Set the new weights vector to be 
 $$
 w_i^{t+1} = w_i^t \beta_t^{1 - \vdash h_t(x_i) \neq y_i \dashv}
 $$
 \end{enumerate}
 {\bfseries Output} the hypothesis
 $$
 h_f(x) = arg \max_{y\in Y} \sum_{t=1}^T (log \frac{1}{\beta_t})\vdash h_t(x_i) = y_i \dashv
 $$
 
\end{flushleft} 
}
