%% 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}Practical Generalization Bounds\end{center}

\begin{center}Chicago 2005 Machine Learning Summer School\end{center}

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

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


\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
\item PAC-Bayes 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

\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 m\Pr_{x,y\sim S}(c(x)\neq y)=\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 \textcolor{blue}{$S$} with the uniform
distribution on \textcolor{blue}{$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}=k\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(m,k,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(m,k,\delta\right)=\max\left\{ p:\textrm{Bin}\left(m,k,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
\item PAC-Bayes 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}
What do sample complexity say about this method?


\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(m,\hat{c}_{S},\delta\right)\right)\geq1-\delta\]
}

World's easiest proof: (by contradiction). 

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

Then by definition, \textcolor{blue}{$\overline{\textrm{Bin}}\left(m,\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(\textrm{KL}\left(\frac{\hat{c}_{S}}{m}||c_{D}\right)\leq\frac{\ln\frac{1}{\delta}}{m}\right)\geq1-\delta\]
}where \textcolor{blue}{$\textrm{KL}(q||p)=q\ln\frac{q}{p}+(1-q)\ln\frac{1-q}{1-p}$
for $q<p$}

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\frac{\hat{c}_{S}}{m}+\sqrt{\frac{\ln\frac{1}{\delta}}{2m}}\right)\geq1-\delta\]
}

Proof: Use the Chernoff approximation. Full details in the notes.


\lyxnewslide{adfa}

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

Suppose \textcolor{blue}{$\delta=0.1$}

Suppose \textcolor{blue}{$m=100$}

Suppose \textcolor{blue}{$\hat{c}_{S}=2$}

Square root Chernoff bound: \textcolor{blue}{$\Rightarrow c_{D}\in[-0.102,0.142]$}

Exact calculation \textcolor{blue}{$\Rightarrow c_{D}\in[0.0045,0.0616]$} 


\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}\sum_{i=1}^{m}\left(\mu-I\left[c(x_{i})\neq y_{i}\right]\right)^{2}$} 

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 \textcolor{blue}{$m$} examples into \textcolor{blue}{$K$}
subsets. 

Repat \textcolor{blue}{$K$} times: Train on \textcolor{blue}{$K-1$}
subsets, test on heldout subset.

Not well understood theoretically. (Big open problem!)

Best Result: Confidence interval smaller than a test set of size \textcolor{blue}{$\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}
\item PAC-Bayes 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{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(m,\hat{c}_{S},\delta P\left(c\right)\right)\right)\geq1-\delta\]
}

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

Corollary: \textcolor{blue}{For all $P(c)$, for all $D$, for all
$\delta\in(0,1]$:}

\textcolor{blue}{\[
\Pr_{S\sim D^{m}}\left(c_{D}\leq\frac{\hat{c}_{S}}{m}+\sqrt{\frac{\ln\frac{1}{P(c)}+\ln\frac{1}{\delta}}{2m}}\right)\geq1-\delta\]
}


\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(m,\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(m,\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(m,\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(m,\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(m,\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(m,\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(m,\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(m,\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(m,\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(m,\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(m,\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(m,\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 \textcolor{blue}{$\delta=0.1$}

Suppose \textcolor{blue}{$m=100$}

Suppose \textcolor{blue}{$P(c)=0.1$}

Suppose \textcolor{blue}{$\hat{c}_{S}=2$}

Square root Chernoff \textcolor{blue}{$\Rightarrow c_{D}\in[-0.143,0.183]$}

Exact calculation \textcolor{blue}{$\Rightarrow c_{D}\in[0.001,0.089]$}


\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 = \textcolor{blue}{$\delta=0.1$}
\item Discrete problems from UCI database of Machine Learning problems.
\item \textcolor{blue}{$100\%$} of data used for training set bounds
\item \textcolor{blue}{$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{adfa}

\begin{center}Outline\end{center}

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

\lyxnewslide{adfaf}

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


\lyxnewslide{afa}

\begin{center}PAC-Bayes Bound: Basic quantities\end{center}

\textcolor{blue}{$Q_{D}\equiv E_{c\sim Q}[c_{D}]$} = average true
error

\textcolor{blue}{$\hat{Q}_{S}\equiv E_{c\sim Q}\left[\frac{\hat{c}_{S}}{m}\right]$}
= average train error


\lyxnewslide{adfa}

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

Theorem: (\textcolor{red}{PAC-Bayes 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 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: \textcolor{blue}{$\textrm{KL}(Q||P)=E_{c\sim Q}\ln\frac{Q(c)}{P(c)}$ }

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


\lyxnewslide{adfa}

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

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

Application: true error bounds for Support Vector Machines.

Classifier form:

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

Change the binary labels to $\{-1,1\}$ for the following.

Also note: Work by Matthias Seeger for Gaussian Processes.


\lyxnewslide{adfaf}

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

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

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

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

\textcolor{blue}{$\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: (\textcolor{red}{PAC-Bayes Margin Bound}) \textcolor{blue}{For
all distributions $D$, for all $\delta\in(0,1]$: \[
\Pr_{S\sim D^{m}}\left(\forall\vec{w},\mu>0:\,\,\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}

\begin{center}PAC-Bayes Margin Bound: Intuition\end{center}

\includegraphics{margin_intuition.eps}

Isotropic Gaussian prior and posterior


\lyxnewslide{adfa}

\begin{center}PAC-Bayes Margin Bound: Proof\end{center}

Start with PAC-Bayes bound:\textcolor{blue}{\normalsize \[
\forall P(c)\,\,\,\,\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\]
}Set \textcolor{blue}{$P=N(0,1)^{n}$} \textcolor{red}{}

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

Gaussian $\Rightarrow$ coordinate system reorientable\textcolor{blue}{\[
\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[%
  scale=0.9]{pbmargin.eps}\textcolor{blue}{\[
\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)\]
}

\vspace{-1cm}

Use properties of Gaussians to finish proof


\lyxnewslide{adfa}

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

\textcolor{blue}{\[
=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$\textcolor{blue}{\[
=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)\]
}$\Rightarrow$ Corollary


\lyxnewslide{adfa}

\begin{center}PAC-Bayes: Application to SVM\end{center}

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

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

\textcolor{blue}{$\vec{w}\cdot\vec{x}=\sum_{i=1}^{m}\alpha_{i}k(x_{i},x)$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vec{w}\cdot\vec{w}=\sum_{i,j}\alpha_{i}\alpha_{j}k(x_{i},x_{j})$\[
\Rightarrow\gamma(x,y)=\frac{y\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})}}\]
}

$\Rightarrow$ Margin bound applies to support vector machines.


\lyxnewslide{adfa}

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

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


\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 at:

http://hunch.net/\textasciitilde{}jl/projects/prediction\_bounds/bound/bound.html
\end{document}
