#This file was created by <jl> Sun Apr 28 09:21:51 2002
#LyX 1.0 (C) 1995-1999 Matthias Ettrich and the LyX Team
\lyxformat 2.15
\textclass slides
\options dvips
\language default
\inputencoding default
\fontscheme default
\graphics default
\paperfontsize default
\spacing single 
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 0
\paperorientation landscape
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle empty

\layout Slide

dfd
\layout Standard
\align center 
True Error Bounds for (Stochastic) Neural Networks
\layout Standard
\align center 
John Langford and Rich Caruana
\layout Slide

adf
\layout Standard
\align center 
Neural Networks
\layout Standard

Very amorphous 
\begin_inset Formula \( \Rightarrow  \)
\end_inset 

 very loose bounds
\layout Enumerate

New approach: PAC-Bayes (McAllester)
\layout Enumerate

Constructing Stochastic Neural Networks
\layout Enumerate

Results
\layout Slide

as
\layout Standard
\align center 
Lingo
\layout Enumerate


\begin_inset Formula \( S \)
\end_inset 

 = 
\begin_inset Formula \( m \)
\end_inset 

 examples drawn iid from 
\begin_inset Formula \( D \)
\end_inset 

 on 
\begin_inset Formula \( X\times Y \)
\end_inset 


\layout Enumerate

hypothesis = 
\begin_inset Formula \( h:X\rightarrow Y \)
\end_inset 


\layout Enumerate


\begin_inset Quotes eld
\end_inset 

true
\begin_inset Quotes erd
\end_inset 

 error = 
\begin_inset Formula \( e_{D}(h)=\Pr _{D}(h(x)\neq y) \)
\end_inset 


\layout Enumerate

empirical error = 
\begin_inset Formula \( \hat{e}_{S}(h)=\Pr _{S}(h(x)\neq y) \)
\end_inset 


\layout Slide

affa
\layout Standard
\align center 
PAC-Bayes Lingo
\layout Enumerate

P = 
\begin_inset Quotes eld
\end_inset 

Prior
\begin_inset Quotes erd
\end_inset 

 distribution over 
\begin_inset Formula \( h \)
\end_inset 


\layout Enumerate

Q = 
\begin_inset Quotes eld
\end_inset 

Posterior
\begin_inset Quotes erd
\end_inset 

 distribution over 
\begin_inset Formula \( h \)
\end_inset 


\layout Enumerate


\begin_inset Formula \( \hat{e}_{Q,S}=E_{h\sim Q}\hat{e}_{S}(h) \)
\end_inset 

 = average empirical error
\layout Enumerate


\begin_inset Formula \( e_{Q,D}=E_{h\sim Q}e_{D}(h) \)
\end_inset 

 = average true error
\layout Slide

dfda
\layout Standard
\align center 
PAC-Bayes
\layout Standard


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

\end_inset 


\layout Standard


\begin_inset Formula \( \textrm{KL}(Q||P) \)
\end_inset 

 = KL divergence = 
\begin_inset Formula \( E_{Q}\ln \frac{q(x)}{p(x)} \)
\end_inset 


\layout Standard

For 
\begin_inset Formula \( \hat{e}_{Q,S}<e_{Q,D} \)
\end_inset 

: 
\begin_inset Formula 
\[
\textrm{KL}(\hat{e}_{Q,S}||e_{Q,D})=\hat{e}_{Q,S}\ln \frac{\hat{e}_{Q,S}}{e_{Q,D}}+(1-\hat{e}_{Q,S})\ln \frac{(1-\hat{e}_{Q,S})}{(1-e_{Q,D})}\]

\end_inset 

 
\layout Slide

adlk
\layout Standard

For neural networks, must:
\layout Enumerate

Pick 
\begin_inset Quotes eld
\end_inset 

prior
\begin_inset Quotes erd
\end_inset 


\layout Enumerate

Pick 
\begin_inset Quotes eld
\end_inset 

posterior
\begin_inset Quotes erd
\end_inset 


\layout Enumerate

Evaluate 
\begin_inset Formula \( \hat{e}_{Q,S} \)
\end_inset 


\layout Enumerate

Evaluate bound
\layout Slide

dfa
\layout Standard
\align center 

\begin_inset Quotes eld
\end_inset 

Prior
\begin_inset Quotes erd
\end_inset 


\layout Enumerate

For every weight, 
\begin_inset Formula \( w_{i} \)
\end_inset 

: 
\begin_inset Formula \( N(0,s) \)
\end_inset 

 = gaussian with large variance
\layout Enumerate

Reality: pick a mixture of gaussians.
\layout Slide

dfd
\layout Standard
\align center 

\begin_inset Quotes eld
\end_inset 

Posterior
\begin_inset Quotes erd
\end_inset 


\layout Enumerate

Train Neural Network
\layout Enumerate

For each 
\begin_inset Formula \( w_{i} \)
\end_inset 

 find sensitivity 
\begin_inset Formula \( s_{i} \)
\end_inset 

 
\layout Enumerate

For all 
\begin_inset Formula \( w_{i} \)
\end_inset 

, pick 
\begin_inset Formula \( N(w_{i},s_{i}) \)
\end_inset 

 
\layout Slide

adfd
\layout Standard
\align center 
Evaluate 
\begin_inset Formula \( \hat{e}_{Q,S}(h) \)
\end_inset 


\layout Standard

Repeat 500 times:
\layout Enumerate

Pick random example
\layout Enumerate

Pick random 
\begin_inset Quotes eld
\end_inset 

Posterior
\begin_inset Quotes erd
\end_inset 

 neural network
\layout Enumerate

Evaluate
\layout Standard

Count errors.
 Bound 
\begin_inset Formula \( \hat{e}_{Q,S}(h) \)
\end_inset 


\layout Slide

Ev
\layout Standard
\align center 
Evaluate Bound
\layout Enumerate

Analytically calculate 
\begin_inset Formula \( \textrm{KL}(Q||P) \)
\end_inset 

.
\layout Enumerate

binary search to find 
\begin_inset Formula \( e_{Q,D}(h) \)
\end_inset 

 constraint.
\layout Slide

df
\layout Standard
\align center 
General form
\layout Enumerate

Pick 
\begin_inset Quotes eld
\end_inset 

prior
\begin_inset Quotes erd
\end_inset 

 (semigeneric)
\layout Enumerate

Pick 
\begin_inset Quotes eld
\end_inset 

posterior
\begin_inset Quotes erd
\end_inset 

 (semigeneric)
\layout Enumerate

Evaluate 
\begin_inset Formula \( \hat{e}_{Q,S}(h) \)
\end_inset 

 (generic)
\layout Enumerate

Evaluate bound (generic)
\layout Slide

adfd
\layout Standard
\align center 
Results
\layout Enumerate

Learning problem
\layout Enumerate

Neural Net architecture
\layout Enumerate

Comparison
\layout Slide

dfd
\layout Standard
\align center 
Learning Problem
\layout Enumerate


\begin_inset Formula \( X=R^{25} \)
\end_inset 

, 
\begin_inset Formula \( Y=\{-1,1\} \)
\end_inset 


\layout Enumerate

Pick 
\begin_inset Formula \( m=100 \)
\end_inset 

 examples from 
\begin_inset Formula \( D \)
\end_inset 

:
\begin_deeper 
\layout Enumerate

Pick 
\begin_inset Formula \( Y \)
\end_inset 

 uniformly
\layout Enumerate

Pick 
\begin_inset Formula \( N(y,1) \)
\end_inset 


\layout Enumerate

Pick 
\begin_inset Formula \( N(0,1)^{24} \)
\end_inset 


\end_deeper 
\layout Slide

dafd
\layout Standard
\align center 
Architecture
\layout Itemize

2 hidden nodes, sigmoid activation
\layout Itemize

1 output node, linear activation
\layout Standard

Intentional architecture/problem mismatch
\layout Slide

fd
\layout Standard
\added_space_top 0.3cm \added_space_bottom 0.3cm \align center 

\begin_inset Figure size 267 187
file PAC-Bayes/g.100.full.ps
width 4 90
angle 270
flags 9

\end_inset 


\layout Slide

adf
\layout Standard
\added_space_top 0.3cm \added_space_bottom 0.3cm \align center 

\begin_inset Figure size 267 187
file eclipse_ps/g.100.ps
width 4 90
angle 270
flags 9

\end_inset 


\layout Slide

afa
\layout Standard
\added_space_top 0.3cm \added_space_bottom 0.3cm \align center 

\begin_inset Figure size 267 187
file eclipse_ps/g.200.ps
width 4 90
angle 270
flags 9

\end_inset 


\layout Slide

afa
\layout Standard
\added_space_top 0.3cm \added_space_bottom 0.3cm \align center 

\begin_inset Figure size 267 187
file eclipse_ps/g.500.ps
width 4 90
angle 270
flags 9

\end_inset 


\layout Slide

afaf
\layout Standard
\added_space_top 0.3cm \added_space_bottom 0.3cm \align center 

\begin_inset Figure size 267 187
file eclipse_ps/g.5000.ps
width 4 90
angle 270
flags 9

\end_inset 


\layout Slide

afaf
\layout Standard


\begin_inset Figure size 89 62
file eclipse_ps/a.100.ps
width 4 30
angle 270
flags 9

\end_inset 


\begin_inset Figure size 89 62
file eclipse_ps/a.200.ps
width 4 30
angle 270
flags 9

\end_inset 


\begin_inset Figure size 89 62
file eclipse_ps/a.500.ps
width 4 30
angle 270
flags 9

\end_inset 


\layout Standard


\begin_inset Figure size 89 62
file eclipse_ps/a.1000.ps
width 4 30
angle 270
flags 9

\end_inset 


\begin_inset Figure size 89 62
file eclipse_ps/a.2000.ps
width 4 30
angle 270
flags 9

\end_inset 


\begin_inset Figure size 89 62
file eclipse_ps/a.5000.ps
width 4 30
angle 270
flags 9

\end_inset 


\layout Slide

dfs
\layout Standard
\align center 
Conclusion
\layout Standard

Quantitative bounds for (Stochastic) Neural Networks
\layout Enumerate

Improvable? (some slack exists)
\layout Enumerate

SNN error relatable to NN error?
\layout Enumerate

Other applications? (Seeger, Gaussian Processes)
\layout Enumerate

Stochastic Gradient descent?
\the_end