%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[landscape,english,dvips]{slides}
\usepackage[T1]{fontenc}
\pagestyle{empty}
\usepackage{color}
\usepackage{graphicx}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Bold symbol macro for standard LaTeX users
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \newcounter{slidetype}
 \setcounter{slidetype}{0}
 \newif\ifLyXsNoCenter
 \LyXsNoCenterfalse
 \newcommand{\noslidecentering}{
    \LyXsNoCentertrue%
 }
 \newcommand{\slidecentering}{
    \LyXsNoCenterfalse%
 }
 \newcommand{\lyxendslide}[1]{
    \ifLyXsNoCenter%
         \vfill%
    \fi%
    \ifcase \value{slidetype}%
         \or % no action for 0
         \end{slide} \or%
         \end{overlay} \or%
         \end{note}%
    \fi%
    \setcounter{slidetype}{0}
\visible
 }
 \AtEndDocument{\lyxendslide{.}}
 \newcommand{\lyxnewslide}[1]{
    \lyxendslide{.}
    \setcounter{slidetype}{1}
    \begin{slide}
 }
 \newcommand{\lyxinvisible}[1]{
    \invisible
 }

\usepackage{babel}
\makeatother
\begin{document}

\lyxnewslide{dfd}

\begin{center}The Test Set Bound and the Occam's Razor Bound\end{center}

\begin{center}John Langford\end{center}

\begin{center}TTI-Chicago\end{center}


\lyxnewslide{sla}

\begin{center}The Classification Problem:\end{center}

\begin{enumerate}
\item Get (input, class label) pairs from unknown function
\item Find the unknown function
\item ... to minimize errors on future inputs
\end{enumerate}

\lyxnewslide{al}

\includegraphics[%
  width=0.60\textwidth,
  angle=270]{learning_example.ps}


\lyxnewslide{ads}

\includegraphics[%
  width=0.60\textwidth,
  angle=270]{fit.ps}


\lyxnewslide{aldda;}

\includegraphics[%
  width=0.60\textwidth,
  angle=270]{future_fit.ps}


\lyxnewslide{adfa}

\begin{center}Learning = Prediction ability\end{center}

\begin{itemize}
\item We can't expect any prediction ability, in general.
\item We can expect prediction ability, if examples come independently,
sometimes.
\end{itemize}
Here we study prediction ability, assuming indepedence.


\lyxnewslide{adfa}

\begin{center}Why study prediction theory?\end{center}

\begin{enumerate}
\item Better methods for learning and verifying predictive ability
\item To gain insight into learning.
\end{enumerate}

\lyxnewslide{adfa}

\begin{center}Better Methods for Learning \& Verification\end{center}

Standard technique:

\begin{enumerate}
\item Divide samples into train and test set
\item Train on train set
\item Test on test set
\end{enumerate}
We can do better.


\lyxnewslide{adfa}

\begin{center}To gain insight into learning\end{center}

\begin{enumerate}
\item Overfitting: sample complexity quantifies overfitting.
\item Learning algorithm design: What is a good pruning criterion? Why are
large margins good? What other algorithms are likely to yield good
results?
\end{enumerate}

\lyxnewslide{dafa}

\begin{center}Outline\end{center}

\begin{enumerate}
\item \textcolor{red}{The Basic Model}
\item The Test Set Bound
\item Occam's Razor Bound
\end{enumerate}

\lyxnewslide{da}

\begin{center}Model: Definitions\end{center}

\textcolor{blue}{$X$} = input space

\textcolor{blue}{$Y=\{0,1\}$} = output space

\textcolor{blue}{$c:X\rightarrow Y$} = classifier


\lyxnewslide{daf}

\begin{center}Model: Basic Assumption\end{center}

All samples are drawn independently from some unknown distribution
\textcolor{blue}{$D(x,y)$}.

\textcolor{blue}{$S=(x,y)^{m}\sim D^{m}$} is a sample set.


\lyxnewslide{adfaf}

\begin{center}Model: Derived quantities\end{center}

The thing we want to know:\textcolor{blue}{\[
c_{D}\equiv\Pr_{x,y\sim D}(c(x)\neq y)=\textrm{true error}\]
}


\lyxinvisible{}

{}``train error'', {}``test error'', or {}``observed error'',
depending on context.

(note: we identify the set $S$ with the uniform distribution on $S$)


\lyxnewslide{adfaf}

\begin{center}Model: Derived quantities\end{center}

The thing we want to know:\textcolor{blue}{\[
c_{D}\equiv\Pr_{x,y\sim D}(c(x)\neq y)=\textrm{true error}\]
}The thing we have:\textcolor{blue}{\[
\hat{c}_{S}\equiv\Pr_{x,y\sim S}(c(x)\neq y)=\frac{1}{m}\sum_{i=1}^{m}I\left[c(x)\neq y\right]\]
} = {}``train error'', {}``test error'', or {}``observed error'',
depending on context.

(note: we identify the set $S$ with the uniform distribution on $S$)


\lyxnewslide{adfa}

\begin{center}Model: Basic Observations\end{center}

Q: What is the distribution of \textcolor{blue}{$\hat{c}_{S}$}?

A: A Binomial. \textcolor{blue}{\[
\Pr_{S\sim D^{m}}\left(\left.\hat{c}_{S}=\frac{k}{m}\right|c_{D}\right)=\left(\begin{array}{c}
m\\
k\end{array}\right)c_{D}^{k}(1-c_{D})^{m-k}\]
}

= probability of \textcolor{blue}{$k$} heads (errors) in \textcolor{blue}{$m$}
flips of a coin with bias \textcolor{blue}{$c_{D}$}.


\lyxnewslide{df}

\includegraphics[%
  scale=1.75,
  angle=270]{binomials.ps}


\lyxnewslide{adfaf}

\begin{center}Model: basic quantities\end{center}

We use the cumulative:\textcolor{blue}{\[
\begin{array}{ccc}
\textrm{Bin}\left(\frac{k}{m},c_{D}\right) & = & \Pr_{S\sim D^{m}}\left(\left.\hat{c}_{S}\leq\frac{k}{m}\right|c_{D}\right)\\
 & = & \sum_{i=0}^{k}\left(\begin{array}{c}
m\\
i\end{array}\right)c_{D}^{i}(1-c_{D})^{m-i}\end{array}\]
}= probability of observing \textcolor{blue}{$k$} or fewer {}``heads''
(errors) with \textcolor{blue}{$m$} coins. 


\lyxnewslide{adfa}

\begin{center}Model: basic quantities\end{center}

Need confidence intervals $\Rightarrow$ use the pivot of the cumulative
instead

\textcolor{blue}{\[
\overline{\textrm{Bin}}\left(\frac{k}{m},\delta\right)=\max\left\{ p:\textrm{Bin}\left(\frac{k}{m},p\right)\geq\delta\right\} \]
}

= the largest true error such that the probability of observing \textcolor{blue}{$k$}
or fewer {}``heads'' (errors) is at least \textcolor{blue}{$\delta$}.


\lyxnewslide{adfa}

\begin{center}Outline\end{center}

\begin{enumerate}
\item The Basic Model
\item \textcolor{red}{The Test Set Bound}
\item Occam's Razor Bound
\end{enumerate}

\lyxnewslide{adfaf}

\begin{center}Test Set Bound: Setting\end{center}

Standard technique: 

\begin{enumerate}
\item Cut the data into train set and test set
\item Train on the train set
\item Test on the test set
\end{enumerate}

\lyxnewslide{adafd}

\begin{center}Test Set Bound: Theorem\end{center}

Theorem: (\textcolor{red}{Test Set Bound}) \textcolor{blue}{For all
classifiers $c$, for all $D$, for all $\delta\in(0,1]$:\[
\Pr_{S\sim D^{m}}\left(c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta\right)\right)\geq1-\delta\]
}

World's easiest proof: 

With probability \textcolor{blue}{$1-\delta$}, \textcolor{blue}{$\textrm{Bin}\left(\frac{k}{m},c_{D}\right)\geq\delta$} 

Then by definition, \textcolor{blue}{$\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta\right)\geq c_{D}$}


\lyxnewslide{daf}

\includegraphics[%
  scale=1.75,
  angle=270]{cut_binomials.ps}


\lyxnewslide{ada}

\includegraphics[%
  scale=1.75,
  angle=270]{consistent_cut_binomials.ps}


\lyxnewslide{adfaf}

\begin{center}\includegraphics[%
  scale=1.75,
  angle=270]{worst_cut.ps}\end{center}


\lyxnewslide{adfaf}

\begin{center}Test Set Bound Notes\end{center}

Perfectly tight: There exist true error rates achieving the bound

Lower bound of the same form.

Primary use: verification of succesful learning


\lyxnewslide{adfa}

\begin{center}What does Test Set Bound mean?\end{center}

Corollary: \textcolor{blue}{For all classifiers $c$, for all $D$,
for all $\delta\in(0,1]$:\[
\Pr_{S\sim D^{m}}\left(c_{D}\leq\hat{c}_{S}+\sqrt{\frac{\ln\frac{1}{\delta}}{2m}}\right)\geq1-\delta\]
}

Proof: Use the Chernoff approximation, \textcolor{blue}{\[
\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta\right)\leq\hat{c}_{S}+\sqrt{\frac{\ln\frac{1}{\delta}}{2m}}\]
}

Note: NOT tight when \textcolor{blue}{$\hat{c}_{S}$} near \textcolor{blue}{$0$}
(our goal!)


\lyxnewslide{adfa}

\begin{center}Test Set Bound: Example\end{center}

Suppose $\delta=0.1$

Suppose $m=100$

Suppose $\hat{c}_{S}=\frac{38}{100}$

Square root Chernoff bound: $\Rightarrow c_{D}\in[0.26,0.50]$

Exact calculation $\Rightarrow c_{D}\in[0.30,0.47]$


\lyxnewslide{ad}

\begin{center}Test Set Bound Comparison: Empirical {}``confidence''
intervals\end{center}

\textcolor{blue}{$k$} = number of test errors, \textcolor{blue}{$m$}
= number of examples

\textcolor{blue}{$\mu=\frac{k}{m}$ }

\textcolor{blue}{$\sigma^{2}=\frac{1}{m-1}\frac{1}{m}\sum_{i=1}^{m}\left(\mu-I\left[c(x_{i})\neq y_{i}\right]\right)^{2}=\frac{\mu(1-\mu)}{m-1}$} 

pick bound = \textcolor{blue}{$\frac{k}{m}+2\sigma$ }

How do they compare? 


\lyxnewslide{adfa}

\includegraphics[%
  scale=1.75,
  angle=270]{test_vs_two_sigma.ps}


\lyxnewslide{adfa}

\begin{center}Test Set Bound vs Empirical Confidence Interval\end{center}

\begin{enumerate}
\item empirical confidence intervals are sometimes pessimistic
\item empirical confidence intervals are sometimes optimistic
\item the test set bound always works
\end{enumerate}

\lyxnewslide{adfa}

\begin{center}Interpretation: Interactive Proof of Learning\end{center}

\vspace{0.3cm}
\begin{center}\includegraphics[%
  width=0.90\columnwidth]{test_set.eps}\end{center}


\lyxnewslide{adfa}

\begin{center}$K$-fold Cross Validation\end{center}

Divide $m$ examples into $K$ subsets. 

Repat $K$ times: Train on $K-1$ subsets, test on heldout subset.

Not well understood theoretically.

Best Result: Confidence interval smaller than a test set of size $\frac{m}{K}$.

$\Rightarrow$ leave-one-out cross validation very prone to overfitting.

$\Rightarrow$ Some people fool themselves with overconfidence in
Cross Validation.


\lyxnewslide{adfa}

\begin{center}Outline\end{center}

\begin{enumerate}
\item The Basic Model
\item The Test Set Bound
\item \textcolor{red}{Occam's Razor Bound}
\end{enumerate}

\lyxnewslide{adfa}

\begin{center}Training Set Bounds in General\end{center}

\begin{itemize}
\item Sometimes the holdout set is \emph{critical} for learning.
\item Sometimes we want bounds to guide learning
\end{itemize}
$\Rightarrow$Train set bounds

Occam's Razor bound is the simplest train set bound.


\lyxnewslide{adfaf}

\begin{center}A note on Practicality\end{center}

Many Train set bounds are not practical: They are too loose.

\begin{enumerate}
\item VC dimension bounds
\item Fat-shattering dimension bounds
\item Covering number bounds
\end{enumerate}
We do not cover these here: the emphasis is on (in practice) tight
bounds.

Despite lack of tightness, these other bounds can motivate learning
algorithms.


\lyxnewslide{afda }

\includegraphics[%
  width=1.0\columnwidth]{training_set.eps}


\lyxnewslide{dad}

\begin{center}Occam's Razor Bound\end{center}

Theorem: (\textcolor{red}{Occam's Razor Bound}) \textcolor{blue}{For
all {}``priors'' $P(c)$ over the classifiers $c$, for all $D$,
for all $\delta\in(0,1]$:\[
\Pr_{S\sim D^{m}}\left(\forall c:\,\, c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P\left(c\right)\right)\right)\geq1-\delta\]
}

Compare with test set bound: \textcolor{blue}{$\delta\rightarrow\delta P(c)$}.


\lyxnewslide{adfa}

\begin{center}Occam's Razor Bound: Proof\end{center}

Test set bound $\Rightarrow$\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)\geq1-\delta P(c)\]
}


\lyxinvisible{}

Negate to get:\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\delta P(c)\]
}Apply union bound: \textcolor{blue}{$\Pr(A\textrm{ or }B)\leq\Pr(A)+\Pr(B)$}
repeatedly.\textcolor{blue}{\[
\Pr_{S\sim D^{m}}\left(\exists c:\,\,\, c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\sum_{c}\delta P(c)=\delta\]
}Negate again to get proof.

Next: Graphical proof


\lyxnewslide{adfa}

\begin{center}Occam's Razor Bound: Proof\end{center}

Test set bound $\Rightarrow$\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)\geq1-\delta P(c)\]
}Negate to get:\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\delta P(c)\]
}


\lyxinvisible{}

Apply union bound: \textcolor{blue}{$\Pr(A\textrm{ or }B)\leq\Pr(A)+\Pr(B)$}
repeatedly.\textcolor{blue}{\[
\Pr_{S\sim D^{m}}\left(\exists c:\,\,\, c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\sum_{c}\delta P(c)=\delta\]
}Negate again to get proof.

Next: Graphical proof


\lyxnewslide{adfa}

\begin{center}Occam's Razor Bound: Proof\end{center}

Test set bound $\Rightarrow$\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)\geq1-\delta P(c)\]
}Negate to get:\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\delta P(c)\]
}Apply union bound: \textcolor{blue}{$\Pr(A\textrm{ or }B)\leq\Pr(A)+\Pr(B)$}
repeatedly.\textcolor{blue}{\[
\Pr_{S\sim D^{m}}\left(\exists c:\,\,\, c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\sum_{c}\delta P(c)=\delta\]
}


\lyxinvisible{}

Negate again to get proof.

Next: Graphical proof


\lyxnewslide{adfa}

\begin{center}Occam's Razor Bound: Proof\end{center}

Test set bound $\Rightarrow$\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)\geq1-\delta P(c)\]
}Negate to get:\textcolor{blue}{\[
\forall c\,\,\,\Pr_{S\sim D^{m}}\left(c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\delta P(c)\]
}Apply union bound: \textcolor{blue}{$\Pr(A\textrm{ or }B)\leq\Pr(A)+\Pr(B)$}
repeatedly.\textcolor{blue}{\[
\Pr_{S\sim D^{m}}\left(\exists c:\,\,\, c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta P(c)\right)\right)<\sum_{c}\delta P(c)=\delta\]
}Negate again to get proof.

Next: Graphical proof


\lyxnewslide{efa}

\vspace{-0.5cm}

\includegraphics[%
  width=0.50\textwidth,
  angle=270]{nonuniform_binomials.ps}

\vspace{-0.5cm}

Each classifier is a Binomial with a different size tail cut. 

\vspace{-0.5cm}

With high probability no error falls in any tail.


\lyxnewslide{dlsa}

\includegraphics[%
  width=0.50\textwidth,
  angle=270]{deep_cut_nonuniform_binomials.ps}

The chosen classifier has an unknown true error rate.


\lyxnewslide{dlsa}

\includegraphics[%
  width=0.50\textwidth,
  angle=270]{deep_cut_bound.ps}

Bound = the largest true error rate for which the observation is not
in the tail.


\lyxnewslide{adf}

\begin{center}Occam's Razor Bound: Example\end{center}

Suppose $\delta=0.1$

Suppose $m=100$

Suppose $P(c)=0.1$

Suppose $\hat{c}_{S}=\frac{38}{100}$

Square root Chernoff $\Rightarrow c_{D}\in[0.22,0.54]$

Exact calculation $\Rightarrow c_{D}\in[0,26,0.51]$


\lyxnewslide{sdfd}

\begin{center}Occam's Razor Bound Results Decision Trees\end{center}

\vspace{-0.25cm}

\begin{itemize}
\item ID3 decision tree + pruning
\item probability of failure = $\delta=0.1$
\item Discrete problems from UCI database of Machine Learning problems.
\item $100\%$ of data used for training set bounds
\item $80\%/20\%$ Train/Test split for test set bounds
\item Minimal selection bias 
\end{itemize}

\lyxnewslide{sfs}

\includegraphics[%
  width=0.50\columnwidth,
  angle=270]{test_vs_micro.ps}

\vspace{-0.5cm}

Left bar = test set bound, right bar = Occam's Razor Bound


\lyxnewslide{afaf}

\begin{center}Conclusion\end{center}

\begin{enumerate}
\item Use real confidence intervals to compare classifiers.
\item Test set bound very simple.
\item Train set bounds on the threshold of quantitatively useful.
\end{enumerate}
Code for bound calculation on the class web page.
\end{document}
