\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\usepackage{color}

\usepackage{amsmath}                    %for math fonts
\usepackage{amsxtra}                    %for math fonts
\usepackage{amstext}                    %for math fonts
\usepackage{amssymb}                    %for math fonts
\usepackage{latexsym}                   %for math fonts
\usepackage{dsfont}                     %for math fonts
\usepackage{color}
\usepackage{graphicx}                   %for using DIA graphics (.eps files)


\newcommand{\mQ}{{\mathrm Q}}
\newcommand{\mX}{{\mathrm X}}
\newcommand{\mH}{{\mathrm H}}
\newcommand{\mI}{{\mathrm I}}
\newcommand{\mY}{{\mathrm Y}}
\newcommand{\mU}{{\mathrm U}}
\newcommand{\mS}{{\mathrm S}}
\newcommand{\mA}{{\mathrm A}}
\newcommand{\mB}{{\mathrm B}}
\newcommand{\mG}{{\mathrm G}}
\newcommand{\mE}{{\mathrm E}}
\newcommand{\mD}{{\mathrm D}}
\newcommand{\mC}{{\mathrm C}}
\newcommand{\mT}{{\mathrm T}}
\newcommand{\mPr}{{\mathrm Pr}}
\newcommand{\mVar}{{\mathrm Var}}
\newcommand{\mEX}{{\mE[\mX]}}
\newcommand{\mVX}{{\mVar(\mX)}}
\newcommand {\lra}{\longrightarrow}
%\newcommand {\b[}{\big[}
%\newcommand {\b]}{\big]}
\newcommand{\f}{\frac}
\newcommand{\vep}{\varepsilon}


\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}
\newtheorem{note}[theorem]{Note}
\newcommand{\RETURN}{{\bf return}}
\newcommand{\Adv}{{\rm Adv}}

\lecture{12}{June 10, 2009}{Ronitt Rubinfeld}{efrat bank, Guy Harari, Yehudit Hasson }

%%%% body goes in here %%%%


\section{Introduction}
In this lecture we prove that a "weak" PAC learning algorithm implies a "strong" PAC learning algorithm. Recall the definition that was given in previous lectures for PAC:
\begin{define}
  An algorithm $\mathcal{A}$ (\textbf{``strongly''}) PAC learns a concept class
  $ \ \mathcal{C}$ if~
  $\forall c \in \mathcal{C},
  \forall \ \mbox{distribution } \mathcal{D},
  \forall \vep >0$,
  with probability greater or equal $\f{3}{4}$ ,
  given examples of $c$ which are chosen according to the distribution $\mathcal{D}$,
  $\mathsf{A}$ outputs $h$ such that
  \begin{equation}
    \Pr_{\mathcal{D}}[h(x) \ne c(x)] \le \vep.
  \end{equation}
\end{define}
\begin{remark}
  \begin{itemize}
  \item Note that in previous lecture the parameter $\delta$ was introduced, and the requirement was that with probability greater or equal $1-\delta$ $\mathcal{A}$ output a "good" hypothesis. In homework we have shown that it is enough to consider the case of $\delta=3/4$, and results for general delta can be achieved via amplification.
  \item In previous lectures the distribution $\mathcal{D}$ was chosen to be the uniform distribution. In fact, any distribution may be used.
  \end{itemize}
\end{remark}

\begin{define}
  An algorithm $\mathcal{A}$ {\color{red}\textbf{weakly}} PAC learns a concept class
  $\mathcal{C}$ if~
  $\ \forall c \in \mathcal{C},
  {\color{red}\mathbf{ \ \exists \gamma > 0}} \ \mbox{such that }
   \ \forall  \ \mbox{distribution } \mathcal{D}$,
  with probability $\ge \f{3}{4}$,
  given examples of $c$ which are chosen according to the distribution $\mathcal{D}$,
  $\mathcal{A}$ outputs $h$ such that
  \begin{equation}
    \Pr_{\mathcal{D}}[h(x) \ne c(x)] \le {\color{red}\mathbf{ \frac{1}{2} - \frac{\gamma}{2}}}.
  \end{equation}
\end{define}
\begin{itemize}
  \item The term $\frac{\gamma}{2}$ is called the \textbf{\emph{advantage}} of $\mathcal{A}$.
  \item We will consider functions $c \in \mC$ such that $c:\{\pm1\}^n\lra\{\pm1\}$
\end{itemize}

The main result prove in this lecture is:
\begin{theorem}
  If a concept class $\mathcal{C}$ can be weakly learned, then $\mathcal{C}$ can be strongly learned.
\end{theorem}

\section{The Algorithm}

\subsection{The Intuition}
The main idea is to run the weak-learning algorithm first with the uniform distribution (though it does not matter what is the initial distribution) in order to get an hypothesis $h_1$. Then, we would like \textbf{not} to choose the "good" examples again, meaning to give them a small probability, and to run the algorithm again with the new examples to get another hypothesis $h_2$. Next, we would like to somehow combine between the two output functions. A natural way would be to give the examples that were "good" for both $h_1$ and $h_2$ a low probability, and give the "bad" examples a higher one. We will refer to this process as "filtering". The following figure illustrates the main idea of the algorithm.

\begin{figure}[h]
    \begin{center}
        \includegraphics[angle=0, width=15cm]{graph.eps}
    \end{center}
    \caption{ Flow of the algorithm }
    \label{fig:star}
\end{figure}

\subsection{The Algorithm}
Given a weak learner $\mathsf{WL}$, a distribution $\mathcal{D}$, a concept
 $f:\{\pm1\}^n\lra \{\pm1\}$ and parameters $\vep$ and $\gamma$, the algorithm
goes as follows: (We illustrate the case for the
uniform distribution. Note that the algorithm can be easily modified
to any initial distribution although we are not showing it here.)

\begin{tabbing}
  $\mathsf{\textbf{Stage \ 0 - Initialization:}}$ \\
  \qquad \quad Set distribution $\mathcal{D}_0 \longleftarrow \mathcal{D} (= \mathcal{U})$ \\
  \qquad \quad Use $\mathsf{WL}$ to generate (with high probability) an hypothesis $c_1$ such that $\Pr_{\mathcal{D}_0}[f(x)=c_1(x)] \ge \frac{1}{2} + \frac{\gamma}{2}$\\\\
  $\mathsf{\textbf{Stage \ i:}}$\\
  \qquad \quad (1) Construct $\mathcal{D}_i$ via the \textbf{filtering mechanism}\\
  \qquad \quad (2) Run $\mathsf{WL}$ with examples from $\mathcal{D}_i$ to get hypothesis 
 $c_{i+1}$ such that $\Pr_{\mathcal{D}_i}[f(x)=c_{i+1}(x)] \ge \frac{1}{2} + \frac{\gamma}{2}$ \\
  \qquad \quad (3) If $\Pr_{\mathcal{D}_i}[f(x)=Maj(c_1,...,c_{i+1})] \geq 1-\vep$ output Maj$(c_1,...,c_{i+1})$\\\\
  $\mathsf{\textbf{After} \ T=O(\f{1}{{\gamma}^2{\vep}^2}) \ \textbf{steps:}}$\\
  \qquad \quad output c=Maj$(c_1,...,c_T)$
\end{tabbing}

\begin{tabbing}
  $\mathsf{\textbf{Filtering procedure:}}$ \\
  \qquad Given $(x,f(x))$ chosen according to the distribution $D_0$:\\
  \qquad \quad If $\mbox{Maj}(c_1,\ldots,c_i)$ is wrong on $x$, keep $x$\\
  \qquad \quad If \# of $c_i$'s right - \# of $c_i$'s wrong $\geq \frac{1}{\vep \gamma}$, throw $x$ away \\
  \qquad \quad Else \# of $c_i$'s right - \# of $c_i$'s wrong = $\frac{\alpha} {\vep \gamma}$, for some $0<\alpha<1$, keep $x$ with probability $1-\alpha$
\end{tabbing}

\begin{remark}
  \begin{itemize}
  \item We need to add the condition that if the filtering process takes too long, i.e. $O(\frac{1}{\varepsilon})$, stop early and output Maj$(c_1,...,c_j)$. This is correct since if one cannot find examples, i.e. all (or most) examples should be tossed, this means that the error must be small and the algorithm may stop.
  \item Until $i$ is about $\gamma \vep$ none of the examples is being tossed.
  \item If $x$ is tossed at some stage, it can still appear with some probability in one of the following stages.
  \end{itemize}
\end{remark}

\section{Preliminaries} \label{sec:notations}
Here are some notations and their properties:
\begin{enumerate}
  \item \(
      R_c(x) = \left\{ \begin{array}{c l}
          +1 & \mbox{if $f(x) = c(x)$} \\
          -1 & \mbox{o.w.}\\
      \end{array} \right. \)
    \quad gives $+1$ if (weak) hypothesis $c$ is right on example $x$
  \item $N_i(x) = \sum_{1 \le j \le i} R_{c_j}(x)$ \quad is the number
    of right $c$'s exceeding the wrong ones (i.e. \#right-\#wrong)
  \item \(
    M_i(x) = \left\{ \begin{array}{c l}
        1 & \mbox{if $N_i(x) \le 0$} \\
        0 & \mbox{if $N_i(x) \ge \frac{1}{\vep \gamma}$} \\
        1 - \vep \gamma N_i(x) & \mbox{o.w.}
      \end{array} \right. \)
    \quad \\is a ``Probabilty filter keeps sample x''- a ``measure'' which upper bounds the error of hypothesis $c=\mbox{Maj}(c_1,\ldots,c_i)$ on example $x$.
  \item $|M_i| = \sum_x M_i(x)$ \qquad is the total ``mass'' of all examples according to ``measure'' $M_i$.
  \item $D_{M_i}(x) = \frac{M_i(x)}{|M_i|}$ \qquad is a distribution over $x$
    given $M_i$.
  \item Observe that $error(c_{i+1})\equiv Pr_{x\in uniform}\left[c(x) \neq f(x)\right] \leq \frac{|M_i|}{2^n}$\\
  the error of concept class c is the number of inputs for which the majority gaves us a wrong answer and it's smaller than 
  $|M_i|$. (we noramlized it by the total number of inputs).     
  \item $\Adv_c(M) = \sum_x R_c(x)M(x)$ \qquad is the advantage of $c$ on $M$ which gives an indication on the number of inputs for which $c$ is correct. (Random guessing gives $0$.)
  \item $\Adv_c(M) \ge \gamma|M|$ iff $\Pr_{x \in D_M}[c(x)=f(x)] \ge \frac{1}{2} + \frac{\gamma}{2}$
  \item Note that if $\Pr_{x\in D_M}[c(x)=f(x)] \ge \frac{1}{2} + \frac{\gamma}{2}$ and $|M| \ge \vep2^n$, then $\Adv_c(M) \ge \vep \gamma 2^n $ 
  \label{item:adv}
\end{enumerate}

\section{Proof of correctness}

Let's define $A_i(x) = \sum_{0 \le j \le i-1} R_{c_{j+1}}(x)M_j(x)$ 

\begin{claim}\label{claim:Aix}$A_i(x)  \leq \frac{1}{\vep \gamma} + \frac{\vep \gamma}{2}\cdot i$
\end{claim}
Before proving this claim, we first use it to bound the maximum number
of iterations required by the boosting algorithm. Hence, if a concept
can be weakly PAC learned, then it can be (``strongly'') PAC learned.
\begin{claim}
  The maximum number of iterations required by the boosting algorithm is $i_0 \le \frac{2}{\gamma^2 \vep^2}$.
\end{claim}
\begin{proof}
  We prove the claim by showing that assuming the algorithm does not
  stop after $i_0+1$ stages, then $error(c_{i_0}) \geq \vep$ i.e. $\forall j |M_i|\geq \vep 2^n$
  and this leads to a contradiction.
   
  Suppose the claim is not true and $i_0 > \frac{2}{\gamma^2 \vep^2}$ then 
  we will consider the $2^n$ by $(i_0+1)$ dimensional matrix, where the rows are
	labelled by inputs and the columns by iteration number, and in which the entry corresponding to
	x,i contains $A_i(x)$.   We first bound the total sum of the entries of this matrix from below by showing
	that the total sum of each column is large.  The latter follows from Observation 8 above, which follows
	from the correctness of the weak learning algorithm and from the fact that the measure on which
	the algorithm errs is still large.   On the other hand, using the claim we can bound from above the
	total sum of the matrix by upper bounding the total sum of any row.  The claim, which we prove later,
	shows that after a number of iterations, there is a nontrivial upper bound on the number of  hypotheses (weighted
	by the corresponding measures) which  err on this input.   Note that if the majority of the hypotheses do
	well on an input, then its measure will go to zero, but later on, if too many of the newer hypotheses start to do badly
	on the same input, then its measure will become nonzero again.

  \begin{eqnarray}
    \sum_x A_{i_0+1}(x) & = & \sum_x \sum_{0 \le j \le i_0} R_{c_{j+1}}(x)M_j(x) \\
    & = & \sum_{0 \le j \le i_0} \underbrace{\sum_x R_{c_{j+1}}(x)M_j(x)}_{Adv_{c_{j+1}}(M_j(x))} \\
    & \ge & (i_0+1) \vep \gamma 2^n
  \end{eqnarray}

  Using Claim~\ref{claim:Aix} leads to an upper bound:
  \begin{eqnarray}
    \sum_x A_{i_0+1}(x) & \leq & \sum_x (\frac{1}{\vep \gamma} + \frac{\vep \gamma}{2}(i_0+1))\\
    & = & 2^n(\frac{1}{\vep \gamma} + \frac{\vep \gamma}{2}(i_0+1))
  \end{eqnarray}

  Using both bounds, $(i_0+1) \gamma 2^n \vep \le \sum_x
  A_{i_0+1}(x) < 2^n(\frac{1}{\vep \gamma} + \frac{\vep \gamma}{2}(i_0+1))
    \Rightarrow i_0 \leq \frac{2}{\gamma^2 \vep^2}-1$, we arrive at a
  contradiction.  So, the algorithm must run for $\frac{2}{\gamma^2
    \vep^2}$ iterations or less.
\end{proof}

\begin{fact}[The Elevator Principle] If one rides an elevator from the
  ground floor, then one ascends from the $k$-th to the $(k+1)$-th
  floor at most $1$ more time than one descends from the $(k+1)$-th to
  the $k$-th floor.  (Analogous argument holds when traveling from the
  ground floor to basements.)
\end{fact}

\begin{proofof}{Claim 2}
  The process of adding each term of $N_i(x)$ corresponds to an
  elevator ride with $R_{c_j}(x)$ dictating the direction and partial
  sum $N_j(x)$ denoting the current level.  The plan is to first match
  pairs of $R_{c{j+1}}(x)M_j(x)$ terms and obtain an upper bound of
  their sum using properties of function $M_j(x)$.  As for the
  unmatched pairs, we can bound the number of them (using the Elevator
  Argument) and also their sums. And so, an upper bound for $A_i(x)$ can
  be obtained.
  \paragraph{Matched Pairs}
  \begin{tabbing}
  For each $k \ge 0$,\\
  \quad match $j$ such that $N_j(x) = k$ and $N_{j+1}(x) = k+1$\\
  \quad with $j'$ such that $N_{j'}(x) = k+1$ and $N_{j'+1}(x) = k$
  \\(analogously match -k to -(k+1) with -(k+1) to -k)
  \end{tabbing}
  For each matched pair of terms corresponding to indices $a=j,b=j'$,
  the sum is\\ $\underbrace{R_{c_{a+1}}(x)}_{+1}
  \underbrace{M_a(x)}_{N_a(x)=k}+ \underbrace{R_{c_{b+1}}(x)}_{-1}
  \underbrace{M_b(x)}_{N_b(x)=k+1} = M_a(x)~-~M_b(x)$.
  \begin{tabbing}
    If \= $0 \le k \le \frac{1}{\vep \gamma}$ or $0 \le k+1 \le \frac{1}{\vep \gamma}$,~then\\
    \quad $M_a(x) - M_b(x) \le \vep \gamma$  (because $\frac{M_b(x) - M_a(x)}{k+1-k}$ is the slope of $M_i(x)$ which is $\ge -\vep \gamma$),\\
    else\\
    $(k<-1$ and $M_a(x)=M_b(x)=0)$ or $(k>\frac{1}{\vep \gamma}$ and $M_a(x)=M_b(x)=1)$ $\Rightarrow M_a(x) - M_b(x) = 0$

  \end{tabbing}
  Therefore, the total contribution of matched pairs is $\le 0.5\vep \gamma i$ (because
  $A_i(x)$ has $i$ pairs).

  \paragraph{Unmatched Terms}

  Notice that unmatched pairs are in the ``same direction'', i.e.\ all
  $R_{c_j}(x)$'s are either negative or positive.\\

  Suppose all $R_{c_j}(x)$'s are negative (i.e.\ $-1$), then their contribution to
  the sum is negative (because each term becomes $-M_j(x) \le 0$).  So
  they do not loosen the upper bound we already derived from matched
  pairs.

  Suppose all $R_{c_j}(x)$'s are positive (i.e.\ $+1$).  Then $N_j(x)
  \ge 0$, and so each term is $M_j(x) = 1-\vep \gamma N_j(x)$ if
  $N_j(x) \in [0, \frac{1}{\vep \gamma}]$ and $0$ otherwise.  The
  Elevator Lemma tells us that there is at most one unmatched $N_j(x)$
  for each integer value in the interval $[0, \frac{1}{\vep
    \gamma}]$, and so the total contribution of them (sum of a
  arithmetic series from $0$ to $1$ with $\frac{1}{\vep \gamma}$
  terms) is $\le \frac{1}{2\vep \gamma}$ $< \frac{1}{\vep
    \gamma}$\\

  Summing up the total contribution from both matched and unmatched terms gives\\
  $A_i(x) < \underbrace{\frac{1}{\vep \gamma}}_{unmatched} + \underbrace{\frac{\vep \gamma i}{2}}_{matched}$.

\end{proofof}

\end{document}

