%% This LaTeX-file was created by <jl> Sun Apr 28 08:12:46 2002
%% 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{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{dfd}

{\par\centering True Error Bounds for (Stochastic) Neural Networks\par}

{\par\centering John Langford and Rich Caruana\par}


\lyxnewslide{adf}

{\par\centering Neural Networks\par}

Very amorphous \( \Rightarrow  \) very loose bounds

\begin{enumerate}
\item New approach: PAC-Bayes (McAllester)
\item Constructing Stochastic Neural Networks
\item Results
\end{enumerate}

\lyxnewslide{as}

{\par\centering Lingo\par}

\begin{enumerate}
\item \( S \) = \( m \) examples drawn iid from \( D \) on \( X\times Y \)
\item hypothesis = \( h:X\rightarrow Y \)
\item ``true'' error = \( e(h)=\Pr _{D}(h(x)\neq y) \)
\item empirical error = \( \hat{e}(h)=\Pr _{S}(h(x)\neq y) \)
\end{enumerate}

\lyxnewslide{adf}

{\par\centering PAC-Bayes: \( \forall P\sim h \), with probability \( 1-\delta  \):\par}


\[
\forall Q:\, \, E_{Q}e(h)<E_{Q}\hat{e}(h)+\sqrt{\frac{\textrm{KL}(Q||P)+\ln \frac{2m}{\delta }}{2m-1}}\]


\begin{enumerate}
\item P = ``Prior'' distribution over \( h \)
\item Q = ``Posterior'' distribution over \( h \)
\item KL\( (Q||P) \) = KL divergence = \( E_{Q}\ln \frac{q(x)}{p(x)} \)
\end{enumerate}

\lyxnewslide{dfda}

Reality:
\[
\forall Q:\, \, \textrm{KL}(E_{Q}\hat{e}(h)||E_{Q}e(h))<\frac{\textrm{KL}(Q||P)+\ln \frac{2m}{\delta }}{2m-1}\]



\lyxnewslide{adlk}

For neural networks, must:

\begin{enumerate}
\item Pick ``prior''
\item Pick ``posterior''
\item Evaluate \( E_{Q}\hat{e}(h) \)
\item Evaluate bound
\end{enumerate}

\lyxnewslide{dfa}

{\par\centering ``Prior''\par}

\begin{enumerate}
\item For every weight, \( w_{i} \): \( N(0,s) \) = gaussian with large variance
\item Reality: pick a mixture of gaussians.
\end{enumerate}

\lyxnewslide{dfd}

{\par\centering ``Posterior''\par}

\begin{enumerate}
\item Train Neural Network
\item For each \( w_{i} \) find sensitivity \( s_{i} \) 
\item For all \( w_{i} \), pick \( N(w_{i},s_{i}) \) 
\end{enumerate}

\lyxnewslide{adfd}

{\par\centering Evaluate \( E_{Q}\hat{e}(h) \)\par}

Repeat 500 times:

\begin{enumerate}
\item Pick random example
\item Pick random ``Posterior'' neural network
\item Evaluate
\end{enumerate}
Count errors. Bound \( E_{Q}\hat{e}(h) \)


\lyxnewslide{Ev}

{\par\centering Evaluate Bound\par}

\begin{enumerate}
\item Analytically calculate \( \textrm{KL}(Q||P) \).
\item binary search to find \( E_{Q}e(h) \) constraint.
\end{enumerate}

\lyxnewslide{df}

{\par\centering General form\par}

\begin{enumerate}
\item Pick ``prior'' (semigeneric)
\item Pick ``posterior'' (semigeneric)
\item Evaluate \( E_{Q}\hat{e}(h) \) (generic)
\item Evaluate bound (generic)
\end{enumerate}

\lyxnewslide{adfd}

{\par\centering Results\par}

\begin{enumerate}
\item Learning problem
\item Neural Net architecture
\item Comparison
\end{enumerate}

\lyxnewslide{dfd}

{\par\centering Learning Problem\par}

\begin{enumerate}
\item \( X=R^{25} \), \( Y=\{-1,1\} \)
\item Pick \( m=100 \) examples from \( D \):

\begin{enumerate}
\item Pick \( Y \) uniformly
\item Pick \( N(y,1) \)
\item Pick \( N(0,1)^{24} \)
\end{enumerate}
\end{enumerate}

\lyxnewslide{dafd}

{\par\centering Architecture\par}

\begin{itemize}
\item 2 hidden nodes, sigmoid activation
\item 1 output node, linear activation
\end{itemize}
Intentional architecture/problem mismatch


\lyxnewslide{fd}

{\par\centering Comparison\par}

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


\lyxnewslide{adf}

{\par\centering Close Comparison\par}

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


\lyxnewslide{dfs}

{\par\centering Conclusion\par}

\begin{enumerate}
\item Quantitative bounds for (Stochastic) Neural Networks
\item Improvable? (some slack exists)
\item SNN error relatable to NN error?
\item Generalizable? (Matthias Seeger)
\end{enumerate}
\end{document}
