%% This LaTeX-file was created by <jl> Fri Jul 11 18:22:24 2003
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[landscape,dvips]{slides}
\usepackage[T1]{fontenc}
\pagestyle{empty}
\usepackage{color}
\usepackage{graphics}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

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

\makeatother

\begin{document}


\lyxnewslide{adfaf}

{\par\centering A Tale of Two Bounds\par}

{\par\centering John Langford\par}

{\par\centering IBM Research\par}


\lyxnewslide{adfaf}

{\par\centering What is a bound?\par}

You have a classifier, \textcolor{blue}{\( c:X\rightarrow Y \)}.

You have some distribution \textcolor{blue}{\( D \)} over \textcolor{blue}{\( X\times Y \)}.

How often will the classifier err in the future?

\textcolor{blue}{
\[
e_{D}(c)=\Pr _{x,y\sim D}(c(x)\neq y)\]
}

A ``bound'' is an upper bound on the future error rate. 


\lyxnewslide{adfaf}

{\par\centering Types of Bounds\par}

\begin{enumerate}
\item Test set bounds (use 'uncontaminated' examples for bounding)
\item Train set bounds (use examples for training and bounding)
\end{enumerate}
This talk: train set bounds.


\lyxnewslide{adfaf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{training_set.eps}} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

{\par\centering A Brief History of Bounds\par}

\begin{enumerate}
\item \textcolor{magenta}{Test Set bound (aka Binomial confidence interval) ??}
\item VC bound (Vapnik and Chervonenkis, 1971)
\item \textcolor{magenta}{Compression Bound (Littlestone and Warmuth, 1986)}
\item Occam's Razor Bound (BEHW, 1987)
\item Margin Bounds (SFBL, 1998, Bartlett 1998)
\item \textcolor{magenta}{PAC-Bayes Bound (McAllester, 1999)}
\end{enumerate}

\lyxnewslide{adfaf}

{\par\centering Outline\par}

\begin{enumerate}
\item \textcolor{red}{PAC-Bayes Margin bound for SVMs}
\item Compression bound for SVMs
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering PAC-Bayes Bound\par}

\textcolor{blue}{\( P(c) \)}: distribution over classifiers 

\textcolor{blue}{\( Q(c) \)}: Training example dependent distribution over
classifiers

\textcolor{blue}{\( \hat{e}_{S}(c) \)} = error rate on sample set \( S \). 

For all \textcolor{blue}{\( P(c) \)}:

\textcolor{blue}{
\[
\Pr _{S\sim D^{m}}\left( \forall Q(c):\,\,\,\textrm{KL}(E_{c\sim Q}\hat{e}_{S}(c)||E_{c\sim Q}e_{D}(c))\leq \frac{\textrm{KL}(Q||P)+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta \]
}

\textcolor{blue}{\( m= \) number of examples}

\textcolor{blue}{\( \textrm{KL}(q||p)=q\ln \frac{q}{p}+(1-q)\ln \frac{1-q}{1-p} \)}
and \textcolor{blue}{\( \textrm{KL}(Q||P)=E_{c\sim Q}\ln \frac{Q(c)}{P(c)} \)}


\lyxnewslide{adf}

{\par\centering Specialize to weighted sum classifiers\par}

Consider:\textcolor{blue}{
\[
c(x)=\textrm{sign}\left( \sum _{i=1}^{n}w_{i}x_{i}\right) \]
}

Margin = \textcolor{blue}{\( \gamma (x,y)=y\sum _{i}w_{i}x_{i} \)}

\vspace{0.3cm}
{\par\centering \includegraphics{margin.eps} \par}
\vspace{0.3cm}


\lyxnewslide{adfaf}

{\par\centering PAC-Bayes Margin Bound (NIPS2002)\par}

\textcolor{blue}{
\[
\Pr _{S\sim D^{m}}\left( \forall Q_{\mu ,w}:\,\,\,\textrm{KL}(E_{c\sim Q}\hat{e}(c)||E_{c\sim Q}e_{D}(c))\leq \frac{\ln \frac{1}{\bar{F}(\mu )}+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta \]
}

\textcolor{blue}{\( P=N(0,1)^{n} \)} = isotropic normal

\textcolor{blue}{\( Q=N(0,1)^{n-1}\times R_{\mu } \)} 

\textcolor{blue}{\( \bar{F}(\mu )=1-\int _{-\infty }^{\mu }\frac{1}{\sqrt{2\pi }}e^{-\frac{x^{2}}{2}}dx \)}
= cumulative of the normal

\textcolor{blue}{\( R_{\mu }(x)=\frac{I(x>\mu )}{\sqrt{2\pi }\bar{F}(\mu )}e^{-\frac{x^{2}}{2}} \)}
= renormalized normal tail


\lyxnewslide{adfa}

{\par\centering A few things to note\par}

\textcolor{blue}{\( Q_{\mu ,w} \)} = \( N(0,1) \) in all directions perpendicular
to \( w \).

\textcolor{blue}{\( \epsilon \equiv E_{x,y\sim S}\bar{F}\left( \frac{yx_{||}}{x_{\perp }}\mu \right) \geq E_{c\sim Q}\hat{e}(c) \)}

which implies:

\textcolor{blue}{
\[
\Pr _{S\sim D^{m}}\left( \forall Q_{\mu ,w}:\,\,\,\textrm{KL}(\epsilon ||E_{c\sim Q}e_{D}(c))\leq \frac{\ln \frac{1}{\bar{F}(\mu )}+\ln \frac{m+1}{\delta }}{m}\right) \geq 1-\delta \]
}


\lyxnewslide{adfaf}

{\par\centering The Margin Bound for Support Vector Machines\par}

Kernelize bound (Herbrich and Graepel 2001) \textcolor{blue}{\( \gamma (x,y)=\frac{y(w\cdot x)}{\sqrt{w\cdot w}\sqrt{x\cdot x}} \)
\[
\epsilon =E_{x,y\sim U(S)}\bar{F}\left( \frac{\gamma }{1-\gamma ^{2}}\mu \right) \]
} \textcolor{blue}{
\[
c(x)=\textrm{sign}\left( \sum _{i=1}^{m}\alpha _{i}k(x_{i},x)\right) \]
}

\( k \) is a kernel \textcolor{blue}{\( \Rightarrow k(x_{i},x)=\Phi (x_{i})\cdot \Phi (x) \)}
where \( \Phi  \) is some projection into another space. 

\textcolor{blue}{\( w=\sum _{i=1}^{m}\alpha _{i}\Phi (x_{i}) \)}, \textcolor{blue}{\( w\cdot x=\sum ^{m}_{i=1}\alpha _{i}k(x_{i},x) \)},
\textcolor{blue}{\( x\cdot x=k(x,x) \)}, \textcolor{blue}{\( w\cdot w=\sum _{i,j}\alpha _{i}\alpha _{j}k(x_{i},x_{j}) \)} 


\lyxnewslide{adfa}

{\par\centering Dataset/Learning details\par}

Use ``radial basis function'' kernel, \textcolor{blue}{\( K(x_{1},x_{2})=e^{-\gamma ||x_{1}-x_{2}||^{2}} \)}

8 datasets from UCI database, picked for pure numerical features

7:3 Train:Test split (except ``adult'' which is to large)

145 to 1428 examples

Everything implemented as a postprocessor for SVMlight.


\lyxnewslide{adf}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{test.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{test_and_margin.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{test_vs_margin.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{adfaf}

{\par\centering What about optimizing?\par}

Use the gradient:

\textcolor{blue}{
\[
\frac{\partial \bar{e}}{\partial \alpha _{i}}=\frac{\ln \frac{\bar{e}(1-\hat{e})}{\hat{e}(1-\bar{e})}}{\frac{\bar{e}-\hat{e}}{\bar{e}(1-\bar{e})}}\frac{\partial \epsilon }{\partial \alpha _{i}}\]
\[
\frac{\partial \epsilon }{\partial \alpha _{i}}=-\mu E_{x,y\sim S}f\left( \frac{\gamma }{\sqrt{1-\gamma ^{2}}}\mu \right) \frac{1}{(1-\gamma ^{2})^{\frac{3}{2}}}\frac{\partial \gamma }{\partial \alpha _{i}}\]
\[
\frac{\partial \gamma }{\partial \alpha _{i}}=\frac{yk(x,x_{i})}{\sqrt{w\cdot w}\sqrt{k(x,x)}}-y_{i}\gamma \gamma _{i}\sqrt{k(x_{i},x_{i})}\]
}

In practice, about x10 slower than SVMlight.


\lyxnewslide{adfa}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{margin_opt.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{adfaf}

{\par\centering Outline\par}

\begin{enumerate}
\item PAC-Bayes Margin bound for SVMs
\item \textcolor{red}{Compression bound for SVMs}
\end{enumerate}

\lyxnewslide{adfa}

{\par\centering The Sample Compression Bound\par}

Suppose we knew in advance that the learning algorithm will not depend upon
some subset of the examples. 

Then, the ``undependent'' subset acts like a test set and gives us a test
set bound.

Let \textcolor{blue}{\( \textrm{Bin}(m,k,p)=\sum _{i=0}^{k}{m\choose i}p^{i}(1-p)^{m-i} \)}
= cumulative of Binomial

Let \textcolor{blue}{\( S' \)} = ``undependent subset''

\textcolor{blue}{
\[
\Pr _{S\sim D^{m}}\left( e_{D}(c)\leq \textrm{argmax}\left\{ p:\textrm{Bin}(|S'|,|S'|\hat{e}_{S'}(c),p)\geq \delta \right\} \right) \geq 1-\delta \]
}


\lyxnewslide{adfa}

{\par\centering The Sample Compression Bound II\par}

Problem: We don't know \textcolor{blue}{\( S' \)} in advance.

Solution: Assign \textcolor{blue}{\( \frac{\delta }{m{m\choose k}} \)} confidence
to any subset of size \textcolor{blue}{\( k \)}. Note: \textcolor{blue}{
\[
\sum _{k=1}^{m}\sum _{|S'|=k}\frac{\delta }{m{m\choose k}}=\delta \]
}Also note: \textcolor{blue}{\( \Pr (A\textrm{ or }B)\leq \Pr (A)+\Pr (B) \)}.
Apply repeatedly to get that \textcolor{blue}{with probability \( 1-\delta  \):
\[
\forall S':\,\,\,e_{D}(c)\leq \textrm{argmax}\left\{ p:\textrm{Bin}(|S'|,|S'|\hat{e}_{S'}(c),p)\geq \frac{\delta }{m{m\choose |S'|\hat{e}_{S'}(c)}}\right\} \]
}


\lyxnewslide{adfa}

{\par\centering Sample Compression Bound application\par}

A support Vector machine only depends upon support vectors. Nonsupport vectors
are ``undependent''. 

\( \Rightarrow  \) Use performance on the nonsupport vector training set.


\lyxnewslide{adfa}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{test_and_compress.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{adfa}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{test_vs_compression.ps}}} \par}
\vspace{0.3cm}


\lyxnewslide{adaf}

{\par\centering What about Optimizing?\par}

SVMlight has an option '-i 1' = throw out the inconsistent examples and retrain. 

\( \Rightarrow  \) much fewer support vectors

\( \Rightarrow  \) more errors in the ``undependent'' set


\lyxnewslide{adfa}

\vspace{0.3cm}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{compress_opt.ps}}} \par}


\lyxnewslide{adfad}

{\par\centering Conclusion\par}

\begin{enumerate}
\item PAC-Bayes Margin bound is good enough to provide useful information for SVMs.

\begin{enumerate}
\item May be worth combining with test set bound for combined train-test bound
\item Approach probably works for Maximum Entropy classifiers
\end{enumerate}
\item Compression bound does not work as well for SVMs.

\begin{enumerate}
\item Maybe works well for Relevance Vector Machine?
\item Maybe more direct sparsity optimization is fruitful?
\end{enumerate}
\end{enumerate}
\end{document}
