%% 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}
 }

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

\lyxnewslide{dfd}

\begin{center}Practical Prediction Theory\end{center}

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

\begin{center}IBM Research\end{center}


\lyxnewslide{sla}

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

\begin{enumerate}
\item Get (input, class label) pairs from unknown function
\item Guess 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}
Sample Complexity = the study of prediction ability, assuming indepedence.


\lyxnewslide{adfa}

\begin{center}Why Study Sample Complexity?\end{center}

\begin{enumerate}
\item Methods for using more examples
\item To gain insight into learning
\end{enumerate}

\lyxnewslide{adfa}

\begin{center}Methods for using more examples\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}
Sample complexity approaches allow us to 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 criteria? Why are
large margin good? What other algorithms are likely to yield good
results?
\end{enumerate}

\lyxnewslide{dafa}

\begin{center}Outline\end{center}

\begin{enumerate}
\item The Basic Model
\item The Test Set Bound
\item Occam's Razor Bound
\item PAC-Bayes Bound
\item Sample Compression 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}

There exists a distribution $D(x,y)$ and all samples are drawn independently
from $D$.

\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}\]
} 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(c(x)\neq y)\]
} = {}``train error'', {}``test error'', or {}``observed error'',
depending on context.

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


\lyxnewslide{adfa}

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

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

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


= probability of $k$ heads in $m$ flips of a coin with bias $c_{D}$.


\lyxnewslide{df}

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


\lyxnewslide{adfaf}

We use the cumulative:

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


\lyxnewslide{adfa}

Actually, we use the pivot of the cumulative since we care about confidence
intervals.

\[
\overline{\textrm{Bin}}(\frac{k}{m},\delta)=\max\{ p:\textrm{Bin}(\frac{k}{m},c_{D})\geq\delta\}\]


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


\lyxnewslide{adfa}

\begin{center}Outline\end{center}

\begin{enumerate}
\item The Basic Model
\item The Test Set Bound
\item Occam's Razor Bound
\item PAC-Bayes Bound
\item Sample Compression Bound
\end{enumerate}

\lyxnewslide{adfaf}

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}
What does Sample Complexity say about this method?


\lyxnewslide{adafd}

Theorem: For all classifiers, $c$, 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: (by contradiction). 

Assume $\textrm{Bin}(\frac{k}{m},c_{D})\geq\delta$ (which is true
with probability $1-\delta$). 

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

Next: proof by pictures


\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 the bound mean?\end{center}

Corollary: For all classifiers, $c$, 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, \[
\overline{\textrm{Bin}}\left(\hat{c}_{S},\delta\right)\leq\hat{c}_{S}+\sqrt{\frac{\ln\frac{1}{\delta}}{2m}}\]


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


\lyxnewslide{ad}

\begin{center}Comparsion: Empirical {}``confidence'' intervals\end{center}

$k$= number of test errors, $m=$ number of examples

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

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

pick bound = $\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{enumerate}
\item empirical confidence intervals are too pessimistic
\item empirical confidence intervals are 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}Outline\end{center}

\begin{enumerate}
\item The Basic Model
\item The Test Set Bound
\item Occam's Razor Bound
\item PAC-Bayes Bound
\item Sample Compression Bound
\end{enumerate}

\lyxnewslide{adll}

\begin{center}Occam's Razor bounds\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{afda }

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


\lyxnewslide{dad}

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

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


Compare with test set bound: $\delta\rightarrow\delta P(c)$.


\lyxnewslide{adfa}

Test set bound $\Rightarrow$\[
\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:\[
\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 ($\Pr(A\textrm{ or }B)\leq\Pr(A)+\Pr(B)$) repeatedly.\[
\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{sdfd}

\begin{center}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 = holdout bound, right bar = Occam's Razor Bound


\lyxnewslide{adfa}

\begin{center}Outline\end{center}

\begin{enumerate}
\item The Basic Model
\item The Test Set Bound
\item Occam's Razor Bound
\item PAC-Bayes Bound
\item Sample Compression Bound
\end{enumerate}

\lyxnewslide{adfaf}

\includegraphics[%
  scale=0.9]{pac-bayes.eps}


\lyxnewslide{afa}

average true error:\[
Q_{D}\equiv E_{c\sim Q}c_{D}\]
average train error:\[
\hat{Q}_{S}\equiv E_{c\sim Q}\hat{c}_{S}\]


Theorem: (PAC-Bayes Bound) For all {}``priors'' $P(c)$ over the
classifiers, $c$, for all $\delta\in(0,1]$:\[
\Pr_{S\sim D^{m}}\left(\forall Q(c):\,\,\textrm{KL}\left(\hat{Q}_{S}||Q_{D}\right)\leq\frac{\textrm{KL}(Q||P)+\ln\frac{m+1}{\delta}}{m}\right)\geq1-\delta\]
where: $\textrm{KL}(q||p)=q\ln\frac{q}{p}+(1-q)\ln\frac{1-q}{1-p}$
for $q<p$ 

$\textrm{KL}(Q||P)=E_{c\sim Q}\ln\frac{Q(c)}{P(c)}$


\lyxnewslide{adfa}

Lemma 1: For all $P(c)$, For all $\delta\in(0,1]$:\[
\Pr_{S\sim D^{m}}\left(E_{c\sim P}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}\leq\frac{m+1}{\delta}\right)\geq1-\delta\]


Proof: \[
\forall c\,\,\, E_{S\sim D^{m}}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}=\sum_{\frac{k}{m}}\Pr_{S\sim D^{m}}\left(\hat{c}_{S}=\frac{k}{m}\right)\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}=\frac{k}{m}\right)}=m+1\]
\[
\Rightarrow E_{S\sim D^{m}}E_{c\sim P}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}=m+1\]
Use the Markov inequality ($X\geq0$, $EX=\mu$, $\Rightarrow\Pr(X>\frac{\mu}{\delta})\leq\delta$):

\[
\forall P\,\,\Pr_{S\sim D^{m}}\left(E_{c\sim P}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}\leq\frac{m+1}{\delta}\right)\leq\delta\]



\lyxnewslide{daf}

Lemma 2: For all $Q(c)$: $\frac{E_{c\sim Q}\ln\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}}{m}\geq\textrm{KL}(\hat{Q}_{S}||Q_{D})$

Proof:$\frac{1}{m}E_{c\sim Q}\ln\frac{1}{\left(\begin{array}{c}
m\\
m\hat{c}_{S}\end{array}\right)c_{D}^{m\hat{c}_{S}}(1-c_{D})^{m(1-\hat{c}_{S})}}$

\vspace{-1.5cm}\[
=E_{c\sim Q}\left[\hat{c}_{S}\ln\frac{1}{c_{D}}+\left(1-\hat{c}_{S}\right)\ln\frac{1}{1-c_{D}}\right]-\frac{E_{c\sim Q}\ln\left(\begin{array}{c}
m\\
m\hat{c}_{S}\end{array}\right)}{m}\]
Jensen's inequality ($f$ concave $\Rightarrow$ $Ef(X)\geq f(EX)$):\[
E_{c\sim Q}\left[\hat{c}_{S}\ln\frac{1}{c_{D}}+\left(1-\hat{c}_{S}\right)\ln\frac{1}{1-c_{D}}\right]\geq\hat{Q}_{S}\ln\frac{1}{Q_{D}}+\left(1-\hat{Q}_{S}\right)\ln\frac{1}{1-Q_{D}}\]
\[
\frac{E_{c\sim Q}\ln\left(\begin{array}{c}
m\\
m\hat{c}_{S}\end{array}\right)}{m}\leq\frac{E_{c\sim Q}\ln e^{mH\left(\hat{c}_{S}\right)}}{m}=\frac{E_{c\sim Q}mH\left(\hat{c}_{S}\right)}{m}\leq H\left(\hat{Q}_{S}\right)\]
$\Rightarrow$lemma


\lyxnewslide{adfaf}

\begin{center}Proof (of PAC-Bayes bound)\end{center}

Let \[
P_{G}(c)=\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)E_{c\sim P}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}}P(c)\]
 \[
\Rightarrow0\leq\textrm{KL}(Q||P_{G})=E_{c\sim Q}\ln\frac{Q(c)}{P(c)}\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)E_{c\sim P}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}\]
\[
=\textrm{KL}(Q||P)-E_{c\sim Q}\ln\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}+\ln E_{c\sim P}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}\]
\[
\Rightarrow E_{c\sim Q}\ln\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}\leq\textrm{KL}(Q||P)+\ln E_{c\sim P}\frac{1}{\Pr_{S\sim D^{m}}\left(\hat{c}_{S}\right)}\]
+ Lemma 1\&2 $\Rightarrow$proof


\lyxnewslide{adaf}

Is the PAC-Bayes bound tight enough to be useful? YES

Application: true error bounds for Support Vector Machines.

Classifier form:

\[
c(x)=\textrm{sign}\left(\vec{w}\cdot\vec{x}\right)\]



\lyxnewslide{adfaf}

\begin{center}PAC-Bayes Margin bound\end{center}

$\bar{F}(x)=\int_{x}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-x^{2}/2}$ =
cumulative distribution of a Gaussian

$Q(\vec{w},\mu)=N(\mu,1)\times N(0,1)^{n-1}$ where first direction
parallel to $\vec{w}$ 

$\gamma(\vec{x},y)=\frac{y\vec{w}\cdot\vec{x}}{||\vec{w}||||\vec{x}||}$
= normalized margin

$\hat{Q}(\vec{w},\mu)_{S}=E_{\vec{x},y\sim S}\bar{F}\left(\mu\gamma(\vec{x},y)\right)$
= stochastic error rate

Corollary: (PAC-Bayes Margin Bound) For all distributions $D$, for
all $\delta\in(0,1]$, we have: \[
\Pr_{S\sim D^{m}}\left(\forall\vec{w},\mu:\,\,\textrm{KL}\left(\hat{Q}(\vec{w},\mu)_{S}||Q(\vec{w},\mu)_{D}\right)\leq\frac{\frac{\mu^{2}}{2}+\ln\frac{m+1}{\delta}}{m}\right)\geq1-\delta\]



\lyxnewslide{adfa}

Proof: Set $P=N(0,1)^{n}$ 

$Q(\vec{w},\mu)=N(\mu,1)\times N(0,1)^{n-1}$ with first direction
parallal to $\vec{w}$

Gaussian $\Rightarrow$ coordinate system reorientable

\[
\Rightarrow\textrm{KL}(Q||P)=\textrm{KL}(N(0,1)^{n-1}||N(0,1)^{n-1})+\textrm{KL}(N(\mu,1)||N(0,1))\]
\[
=\frac{\mu^{2}}{2}\]



\lyxnewslide{adfa}

\includegraphics{pbmargin.eps}\[
\hat{Q}(\vec{w},\mu)_{S}=E_{\vec{x},y\sim S,\vec{w}^{'}\sim Q(\vec{w},\mu)}I\left(y\neq\textrm{sign}\left(\vec{w}^{'}\cdot\vec{x}\right)\right)\]
 \[
=E_{\vec{x},y\sim S}E_{w_{||}^{'}\sim N(\mu,1)}E_{w_{\perp}^{'}\sim N(0,1)}I\left(y(w_{||}^{'}x_{||}+w_{\perp}^{'}x_{\perp})\leq0\right)\]



\lyxnewslide{adfa}

\begin{center}PAC-Bayes Margin proof: the end\end{center}

\[
=E_{\vec{x},y\sim S}E_{z^{'}\sim N(0,1)}E_{w_{\perp}^{'}\sim N(0,1)}I\left(y\mu\leq-yz^{'}-yw_{\perp}^{'}\frac{x_{\perp}}{x_{||}}\right)\]
The sum of two Gaussians is a Gaussian $\Rightarrow$\[
=E_{\vec{x},y\sim S}E_{v\sim N\left(0,1+\frac{x_{\perp}^{2}}{x_{||}^{2}}\right)}I\left(y\mu\leq-yv\right)\]
\[
=E_{\vec{x},y\sim S}E_{v\sim N\left(0,\frac{1}{\gamma(\vec{x},y)^{2}}\right)}I\left(y\mu\leq-yv\right)\]
\[
=E_{\vec{x},y\sim S}\bar{F}\left(\mu\gamma(\vec{x},y)\right)\]



\lyxnewslide{adfa}

\begin{center}Application to SVM\end{center}

SVM classifier:\[
c(x)=\textrm{sign}\left(\sum_{i=1}^{m}\alpha_{i}k(x_{i},x)\right)\]


$k$ is a kernel $\Rightarrow\exists\vec{\Phi}:\,\,\,\, k(x_{i},x)=\vec{\Phi}(x_{i})\cdot\vec{\Phi}(x)$
so:

$\vec{w}\cdot\vec{x}=\sum_{i=1}^{m}\alpha_{i}k(x_{i},x)$ 

$\vec{x}\cdot\vec{x}=k(x,x)$ 

$\vec{w}\cdot\vec{w}=\sum_{i,j}\alpha_{i}\alpha_{j}k(x_{i},x_{j})$\[
\Rightarrow\gamma(x,y)=\frac{\sum_{i=1}^{m}\alpha_{i}k(x_{i},x)}{\sqrt{k(x,x)\sum_{i,j=1,1}^{m,m}\alpha_{i}\alpha_{j}k(x_{i},x_{j})}}\]



\lyxnewslide{adfa}

\begin{center}PAC-Bayes Margin Bound Results\end{center}

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


\lyxnewslide{adfa}

\begin{center}Outline\end{center}

\begin{enumerate}
\item The Basic Model
\item The Test Set Bound
\item Occam's Razor Bound
\item PAC-Bayes Bound
\item Sample Compression Bound
\end{enumerate}

\lyxnewslide{afad}

\includegraphics{sample_compression.eps}


\lyxnewslide{adfa}

$A$ = learning algorithm

$S'\subseteq S$ = subset of training set. 

The idea: if we knew $S'$ in advance that $S-S'$ would act as a
test set. We don't know $S'$ in advance so the bound is looser.

Theorem: (Sample Compression Bound) For all $\delta\in(0,1]$, $D$,
$A$:\[
\Pr_{S\sim D^{m}}\left(\forall S'\subseteq S\,\,\,\textrm{with }c=A(S'):\,\,\, c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S-S'},\frac{\delta}{m{{m \choose |S'|}}}\right)\right)\geq1-\delta\]



\lyxnewslide{aadfa}

Proof: (Note that $S'$ is unambiguous before $S$ is drawn)\[
\forall S'\subseteq S\,\,\,\textrm{with }c=A(S'):\Pr_{S\sim D^{m}}\left(c_{D}\leq\overline{\textrm{Bin}}\left(\hat{c}_{S-S'},\frac{\delta}{m{{m \choose |S-S'|}}}\right)\right)\geq1-\frac{\delta}{m{{m \choose |S-S'|}}}\]
 Negate to get:

\[
\forall S'\subseteq S\,\,\,\textrm{with }c=A(S'):\Pr_{S\sim D^{m}}\left(c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S-S'},\frac{\delta}{m{{m \choose |S-S'|}}}\right)\right)<\frac{\delta}{m{{m \choose |S-S'|}}}\]
Use union bound ($\Pr(A\textrm{ or }B)\leq\Pr(A)+\Pr(B)$) over each
$S'$\[
\Rightarrow\Pr_{S\sim D^{m}}\left(\exists S'\subseteq S\,\,\,\textrm{with }c=A(S'):\,\,\, c_{D}>\overline{\textrm{Bin}}\left(\hat{c}_{S-S'},\frac{\delta}{m{{m \choose |S-S'|}}}\right)\right)<\delta\]


Negate again $\Rightarrow$ theorem


\lyxnewslide{adfa}

\begin{center}Application: Support Vector Machines\end{center}

If $S'$= set of support vectors than $A(S')=A(S)$.

How well does the sample compression bound work with a support vector
machine?


\lyxnewslide{adfa}

\includegraphics[%
  width=0.60\columnwidth,
  angle=270]{test_and_compress.ps}


\lyxnewslide{adfa}

Answer: Not so well. 

Why not? 

The SVM learning algorithm achieves 'incidental' sparsity rather than
optimizing for it explicitly (in contrast to the margin).

Note work by Mario Marchand and John Shawe-Taylor using Sample Compression
bound variant $\Rightarrow$ good quantitative results


\lyxnewslide{afaf}

\begin{center}Conclusion\end{center}

Use a confidence interval best for comparison. 

Amongst estimation methods, test set or K-fold cross validation are
reasonable.

Some code at:

http://www-2.cs.cmu.edu/\textasciitilde{}jcl/programs/bound/bound.html
\end{document}
