%% 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{\lyxnewoverlay}[1]{
    \lyxendslide{.}
    \setcounter{slidetype}{2}
    \begin{overlay}
 }
 \newcommand{\lyxinvisible}[1]{
    \invisible
 }

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

\lyxnewslide{daf}

\begin{center}Label Compression implies Verifiable Learning\end{center}

\begin{center}Avrim Blum and John Langford\end{center}


\lyxnewslide{adfa}

Theorem: (Occam's Razor Bound) Small description length for classifier
$\Rightarrow$ verifiable learning

\includegraphics[%
  scale=1.5]{occam_game.eps}


\lyxnewslide{df}

Theorem: (Occam's Razor Bound) Small description length for classifier
$\Rightarrow$ verifiable learning

\includegraphics[%
  scale=1.5]{occam_game2.eps}


\lyxnewslide{df}

Theorem: (Occam's Razor Bound) Small description length for classifier
$\Rightarrow$ verifiable learning

\includegraphics[%
  scale=1.5]{occam_game3.eps}

Restated: Small number of bits transmitted $\Rightarrow$verifiable
learning

Is this true in general?


\lyxnewslide{adf}

\begin{center}Outline\end{center}

\begin{enumerate}
\item Main Result: Label compression $\Rightarrow$ Verifiable learning
\item Secondary note: {}``all'' bounds $\Rightarrow$ Label compression
\end{enumerate}

\lyxnewslide{da}

\begin{center}Basic Definitions\end{center}

$X$= input space

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

$c:X\rightarrow Y$ = classifier

$D(x,y)$ = distribution over $x$ and $y$

$S=(x,y)^{m}\sim D^{m}$ = sample set

$e_{D}(c)\equiv\Pr_{x,y\sim D}(c(x)\neq y)$ = {}``true error''

$\hat{e}_{S}(c)\equiv\Pr_{x,y\sim U(S)}(c(x)\neq y)$ = {}``train
error''


\lyxnewslide{adf}

\begin{center}The compression game\end{center}

\vspace{0.3cm}
\begin{center}\includegraphics{../game.eps}\end{center}
\vspace{0.3cm}

How many bits are used to send the labels to Bob?


\lyxnewslide{adfa}

\begin{center}New definitions\end{center}

Learning algorithm is transductive: 

$S$ = train set

$S'$ = unlabeled test set

$m=|S|$

$n=|S'|$

$\sigma:X^{m+n}\rightarrow Y^{m+n}$ = transductive classifier


\lyxnewslide{adfa}

\begin{center}PAC-MDL Bound\end{center}
\vspace{0.3cm}

Theorem: (PAC-MDL Bound) $\forall P(\sigma)$, for all but $\delta$
draws of $S,S'\sim D^{m+n}$:

\[
\forall\sigma:\,\,\hat{e}_{S}(\sigma)>0\textrm{ or }\hat{e}_{S'}(\sigma)\leq\frac{\ln\frac{1}{P(\sigma)}+\ln\frac{1}{\delta}}{n\ln\left(1+\frac{m}{n}\right)}\]



\lyxnewslide{adfa}

\begin{center}New Stuff: The proof\end{center}
\vspace{0.3cm}

Fix $X^{m+n}$. Let $\pi(m,n)$ = uniform distributions over partitions 

\[
\forall x^{m+n},y^{m}\forall\sigma\,\,\,\Pr_{S,S'\sim\pi(m,n)}(0\,\textrm{train and }t\textrm{ test errors})=\frac{\left(\begin{array}{c}
n\\
t\end{array}\right)}{\left(\begin{array}{c}
m+n\\
t\end{array}\right)}\]


\[
\forall x^{m+n},y^{m}\forall\sigma\,\,\,\Pr_{S,S'\sim\pi(m,n)}\left(0\,\textrm{train and }\frac{\left(\begin{array}{c}
n\\
t\end{array}\right)}{\left(\begin{array}{c}
m+n\\
t\end{array}\right)}\leq\delta P(\sigma)\right)\leq\delta P(\sigma)\]



\lyxnewslide{adfaf}

\begin{center}New Stuff: Proof II\end{center}

\[
\forall x^{m+n},y^{m}\,\,\,\Pr_{S,S'\sim\pi(m,n)}\left(\exists\sigma\,\,\,0\,\textrm{train and }\frac{\left(\begin{array}{c}
n\\
t\end{array}\right)}{\left(\begin{array}{c}
m+n\\
t\end{array}\right)}\leq\delta P(\sigma)\right)\leq\delta\]
\[
\Pr_{S,S'\sim D^{m+n}}\left(\exists\sigma\,\,\,0\,\textrm{train and }\frac{\left(\begin{array}{c}
n\\
t\end{array}\right)}{\left(\begin{array}{c}
m+n\\
t\end{array}\right)}\leq\delta P(\sigma)\right)\leq\delta\]
\[
\Pr_{S,S'\sim D^{m+n}}\left(\forall\sigma\,\,\,1\,\textrm{or more train or }\frac{\left(\begin{array}{c}
n\\
t\end{array}\right)}{\left(\begin{array}{c}
m+n\\
t\end{array}\right)}\geq\delta P(\sigma)\right)\geq1-\delta\]



\lyxnewslide{adfa}

\begin{center}New Stuff: Proof End\end{center}

Appeal to algebra and approximation.


\lyxnewslide{adf}

\begin{center}Outline\end{center}

\begin{enumerate}
\item Main Result: Label compression $\Rightarrow$ Verifiable learning
\item Secondary note: {}``all'' bounds $\Rightarrow$ Label compression
\end{enumerate}

\lyxnewslide{adf}

\begin{center}Review: Occam's Razor \end{center}

Theorem: (Occam's Razor Bound \textcolor{red}{BEHW87}) $\forall P(c)$,
for all but $\delta$ $D^{m}(S)$:

\[
\forall c:\,\,\hat{e}_{S}(c)>0\textrm{ or }e_{D}(c)\leq\frac{\ln\frac{1}{P(c)}+\ln\frac{1}{\delta}}{m}\]



\lyxnewslide{adfa}

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

What is the communication language?


\lyxnewoverlay{daf}

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

$P(\sigma)=P(c)$

Pick $m=100$, $n=\infty$, $\delta P(c)=0.001$ and get:

\vspace{0.3cm}
\begin{center}\includegraphics[%
  angle=270]{../occam_vs_observable.ps}\end{center}
\vspace{0.3cm}


\lyxnewslide{adfa}

\begin{center}Review: PAC-Bayes \end{center}

Theorem: (PAC-Bayes Bound \textcolor{red}{M99}) $\forall P(c)$, for
all but $\delta$ $D^{m}(S)$:

\[
\forall Q(c):\,\,\, E_{Q(c)}\hat{e}_{S}(c)>0\textrm{ or }E_{Q(c)}e_{D}(c)\leq\frac{\textrm{KL}(Q||P)+\ln\frac{1}{\delta}}{m}\]



\lyxnewslide{adfa}

\begin{center}Connection: PAC-Bayes Bound\end{center}

What is the communication language?


\lyxinvisible{}

\[
\textrm{KL}(Q||P)=E_{c\sim Q}\ln\frac{Q(c)}{P(c)}=\ln\frac{1}{P(y^{m}|x^{m})}\]



\lyxnewoverlay{}

\begin{center}Connection: PAC-Bayes Bound\end{center}

Ideally: 

\[
P(y^{m}|x^{m})=\sum_{c:c^{m}(x^{m})=y^{m}}P(c)\]


\[
\textrm{KL}(Q||P)=E_{c\sim Q}\ln\frac{Q(c)}{P(c)}=\ln\frac{1}{P(y^{m}|x^{m})}\]


Reality: \[
P(y^{m+n}|x^{m+n})=\sum_{c:c^{m+n}(x^{m+n})=y^{m+n}}P(c)\]



\lyxnewslide{df}

\begin{center}Review: Compression\end{center}

$C(S)$ = {}``compression set'' = subset of examples that classifier
depends upon.

Theorem: (Compression Bound \textcolor{red}{LW89}) For all learning
algorithms $A$, For all but $\delta$ $D^{m}(S)$ let $c=A(C(S))$

\[
\hat{e}_{S-C(S)}(c)>0\textrm{ or }e_{D}(c)\leq\frac{\ln\left(\begin{array}{c}
m\\
|C(S)|\end{array}\right)+\ln\frac{m+1}{\delta}}{m-|C(S)|}\]



\lyxnewslide{adfa}

\begin{center}Connection: Compression Bound\end{center}

What is the communication language?
\vspace{0.3cm}


\lyxnewoverlay{dfa}

\begin{center}Connection: Compression Bound\end{center}

Ideally: $P(y^{m}|x^{m})=$ communication complexity of compression
set. \[
\ln P(y^{m}|x^{m})=\ln\left(\begin{array}{c}
m\\
|C(S)|\end{array}\right)+\ln(m+1)+|C(S)|\ln2\]


Reality: $P(y^{m}|x^{m})=$ communication complexity in train+test
set.

\[
\ln P(y^{m+n}|x^{m+n})=\ln\left(\begin{array}{c}
m+n\\
|C(S)|\end{array}\right)+\ln(m+n+1)+|C(S)|\ln2\]



\lyxnewslide{adfa}

\begin{center}Connection: Compression Bound II\end{center}

\vspace{0.3cm}
\begin{center}\includegraphics[%
  angle=270]{../compression_vs_observable.ps}\end{center}
\vspace{0.3cm}


\lyxnewslide{adfa}

\begin{center}Review: VC bound\end{center}

Theorem: (VC bound \textcolor{red}{VC71}) For all hypothesis spaces,
$H$, for all but $\delta$ $D^{m}(S)$, let $d=VC(H)$\[
\forall c\in H:\,\,\,\,\hat{e}_{S}(c)>0\textrm{ or }e_{D}(c)\leq2\frac{d\left(1+\ln\frac{2m}{d}\right)+\ln\frac{4}{\delta}}{m}\]



\lyxnewslide{adfa}

\begin{center}Connection: VC bound\end{center}
\vspace{0.3cm}

What is the communication language?


\lyxnewoverlay{afdaf}

\begin{center}Connection: VC bound\end{center}

$P(y^{m+n}|x^{m+n})=$uniform over all allowed possibilities $\geq\left(\frac{d}{em}\right)^{d}$

\vspace{0.3cm}
\begin{center}\includegraphics[%
  angle=270]{../vc.ps}\end{center}
\vspace{0.3cm}


\lyxnewslide{adfaafd}

\begin{center}Conclusion\end{center}

\begin{enumerate}
\item Applies to transduction and induction
\item (partial) Bound unification
\item Simple proof
\item Holds for all distributions, but the {}``worst case'' is conditioned
on the unlabeled data ($\Rightarrow$ remove bound slack)
\end{enumerate}

\lyxnewslide{adfa}

\begin{center}TODO\end{center}

\begin{enumerate}
\item Can we find an argument which uses exactly the PAC-Bayes and Compression
bound communication complexity?
\item What algorithms does this motivate?
\item Are any other obvious choices missing from the set of languages?\end{enumerate}

\end{document}
