\documentclass{amsart}
\usepackage[T1]{fontenc}
\usepackage{graphics}

\makeatletter


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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}    
\newtheorem{thm}{Theorem}[section]
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\theoremstyle{plain}    
\newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering

\makeatother

\begin{document}


\title{(Not) Bounding the True Error}

\begin{abstract}
We present a new approach to bounding the true error rate of a
continuous valued classifier based upon PAC-Bayes bounds. The method
first constructs a distribution over classifiers by determining how
sensitive each parameter in the model is to noise.  This sensitivity
analysis allows a stochastic classifier with similar error rates to be
constructed.  The true error rate of the stochastic classifier can
then be tightly bounded using a PAC-Bayes bound.  In this paper we
demonstrate the method on artificial neural networks with results of a
\( 2-3 \) order of magnitude improvement vs. the best deterministic
neural net bounds.
\end{abstract}
\maketitle

\section{Introduction}

In machine learning it is important to know the true error rate a
classifier will achieve on future test cases. Estimating the true
error rate of a classifier from the training set can be suprisingly
difficult in some settings.  For example, all known bounds on the true
error rate of artificial neural networks tend to be extremely loose
and often result in the meaningless bound of ``the true error rate is
less than \( 1 \)''.

The method we propose in this paper is \emph{not} able to bound the
true error rate of a single neural network.  Instead, the method
produces a bound for a distribution of networks which we create by
analysing one neural network.  This approach proves to be much more
fruitful than trying to bound the true error rate of a single network.
We produce nontrivial bounds with less than \( 100 \) examples.  This
is a radical improvement over the best current approaches
\cite{Bartlett}\cite{Panchenko} which often require \( 1000 \), \(
10000 \), or more examples before producing a nontrivial bound on the
true error rate.

Our approach uses the PAC-Bayes bound \cite{PAC-Bayes}.  It can be
thought of as a redivision of the work between the experimenter and
the theoretician: we make the experimenter work harder so that the
theoretician's true error bound becomes much tighter. This ``extra
work'' on the part of the experimenter is significant, but tractable,
and the resulting bounds are \emph{much} tighter.

An alternate viewpoint is that the classification problem \emph{is}
finding a hypothesis with a low upper bound on the future error rate.
We present a post-processing phase for neural-net learning algorithms
which results in a classifier with a much lower upper bound on the
future error rate.  The post-processing can be used with any
artificial neural net trained with any optimization method.  It does
not require that the learning procedure be modified (or even re-run).

The extra work required is a post-processing step that finds a
``large'' distribution over classifiers, which has a small
\emph{average} empirical error rate. Given the average empirical error
rate, it is straightforward to apply the PAC-Bayes bound in order to
find a bound on the \emph{average} true error rate.  One way of
finding the large distribution over classifiers is by performing a
straightforward noise sensitivy analysis on the learned model.  The
noise model allows us to generate a distribution of classifiers with a
known, small, empirical error rate.

Why do we expect the PAC-Bayes bound to be a significant improvement
over standard covering number and VC bound approaches? There exist
learning problems for which the gap between the lower bound and the
PAC-Bayes upper bound are tight up to a difference of size \( O\left(
\frac{\ln m}{m}\right) \). This is superior to the guarantees which
can be made for typical covering number bounds where the gap is, at
best, known up to an (asymptotic) constant. The guarantee that
PAC-Bayes bounds are sometimes quite tight encourages us to apply them
here.

The next sections will:

\begin{enumerate}
\item Describe the bounds we will compare.
\item Describe our algorithm for constructing a distribution over neural networks.
\item Present experimental results.
\end{enumerate}

\section{Theoretical setup}

We will work in a standard supervised batch learning setting. This setting starts
with the assumption that all examples are drawn from some fixed (unknown) distribution,
\( D \), over (input, output) pairs, \( (x,y) \). The output \( y \) is drawn
from the space \( \{-1,1\} \) and the input space is arbitrary. The goal of
machine learning is to use a sample set \( S \) of \( m \) pairs to find a
classifier, \( h \), which maps the input space to the output space and has
a small true error, \( e(h)\equiv \Pr _{D}(h(x)\neq y) \). Since the distribution
\( D \) is unknown, the true error rate is not observable. However, we can
observe the empirical error rate, \( \hat{e}(h)\equiv \Pr _{S}(h(x)\neq y)=\frac{1}{m}\sum _{i=1}^{m}h(x_{i})\neq y_{i} \).

Now that the basic quantities of interest are defined, we will first present
a modern neural network bound, the best PAC-Bayes bound, and then describe how
we construct the distribution necessary to apply the PAC-Bayes bound.


\subsection{Neural Network bound}

We will compare with a specialization of a bound \cite{Panchenko} on the true
error rate of a neural network. This bound is described in terms of the following
parameters:

\begin{enumerate}
\item A margin, \( \gamma  \).
\item A function \( \phi  \) defined by \( \phi (x)=1 \) if \( x<0 \), \( \phi (x)=0 \)
if \( x>1 \), and linear in between.
\item \( A_{i} \), a bound on the weights in the \( i \)th layer of the neural network
\item \( L_{i} \), a Lipshitz condition which holds for the \( i \)th layer of the
neural network.
\item \( d \) is the size of the input space.
\end{enumerate}
With these parameters defined, we get the following bound.

\begin{thm}
(2 layer feed-forward Neural Network true error bound)

\[
\Pr _{D}\left( \exists h\in H:\, \, e(h)>\inf _{\gamma }\,\,b(\gamma )\right) \leq \delta \]
where \( b(\gamma )=\frac{1}{m}\sum \phi \left( \frac{yh(x)}{\gamma }\right) +\frac{2\sqrt{2\pi }}{\gamma }32\sqrt{\frac{d+1}{m}}L_{1}L_{2}A_{1}A_{2}+\frac{\sqrt{\frac{1}{2}\ln \frac{2}{\delta }}+2}{\sqrt{m}} \)
\end{thm}
\begin{proof}
Given in \cite{Panchenko}. 
\end{proof}
The theorem is actually only given up to a universal constant. ``\( 32 \)''
might be the right choice, but this is not proved. The neural network true error
bound above is (perhaps) the tightest known bound for general feed-forward neural
networks and so it is the natural bound to compare with.

The 2 layer feed-forward bound is not easily applied in a tight manner because
we can't calculate a priori what our weight bound \( A_{i} \) should be. This
can be patched up using the principle of structural risk minimization. In particular,
we can prove the bound for \( A_{1}=\alpha ^{j} \) where \( j \) is some non-negative
integer. If the bound for the \( j \)th theorem holds with probability \( \frac{4}{\pi ^{2}}\frac{\delta }{j^{2}} \),
then it will hold for all theorems with probability \( \delta  \), since
\[
\sum _{j=1}^{\infty }\frac{1}{j^{2}}=\frac{\pi ^{2}}{4}\]
Applying the approach to the values of both \( A_{1} \) and \( A_{2} \), we
get the following theorem:

\begin{thm}
(2 layer feed-forward Neural Network true error bound)

\[
\Pr _{D}\left( \exists h\in H:\, \, e(h)>\inf _{\gamma jk}\,\,b(\gamma ,j,k)\right) \leq \delta \]
where \( b(\gamma ,j,k)=\frac{1}{m}\sum \phi \left( \frac{yh(x)}{\gamma }\right) +\frac{2\sqrt{2\pi }}{\gamma }32\sqrt{\frac{d+1}{m}}L_{1}L_{2}\alpha ^{j}\beta ^{k}+\frac{\sqrt{\frac{1}{2}\ln \frac{16j^{2}k^{2}}{\delta \pi ^{4}}}+2}{\sqrt{m}} \)
\end{thm}
\begin{proof}
Apply the union bound to all possible values of \( j \) and \( k \) as discussed
above.
\end{proof}
In practice, we will use \( \alpha =\beta =1.1 \). 


\subsection{PAC-Bayes bound}

Our approach will be to instead use a PAC-Bayes bound. We will use a simple
refinement \cite{LS} of the original bound \cite[PAC-Bayes]{}. First, we will
need to define a couple parameters of the theorem.

\begin{enumerate}
\item \( Q \) is a distribution over the hypotheses which can be found in an example
dependent manner.
\item \( P \) is a distribution over the hypotheses which is chosen a priori - without
dependence on the examples.
\item \( e_{Q}(h)=E_{h\sim Q}e(h) \) is the true error rate of the stochastic hypothesis
which, in any evaluation, draws a hypothesis \( h \) from \( Q \), and outputs
\( h(x) \).
\item \( \hat{e}_{Q}(h)=E_{h\sim Q}\hat{e}(h) \) is the average empirical error rate
of the same stochastic hypothesis. 
\end{enumerate}
Now, we are ready to state the theorem.

\begin{thm}
(PAC-Bayes Relative Entropy Bound) \label{PBRE}For all priors, \( P \),
\[
\Pr _{D}\left( \exists Q:\, \, \textrm{KL}(\hat{e}_{Q}(h)||e_{Q}(h))\geq \frac{\textrm{KL}(Q||P)+\ln \frac{2m}{\delta }}{m-1}\right) \leq \delta \]
where \( \textrm{KL}(Q||P)=\int _{h}q(h)\ln \frac{q(h)}{p(h)}dh \) is the Kullback-Leibler
divergence between the distributions \( Q \) and \( P \) and \( \textrm{KL}(\hat{e}_{Q}(h)||e_{Q}(h)) \)
is the KL divergence between a coin of bias \( \hat{e}_{Q}(h) \) and a coin
of bias \( e_{Q}(h) \).
\end{thm}
\begin{proof}
Given in \cite{LS}.
\end{proof}
We will want to specialize this theorem for application to a neural network.
In order to make this specialization, we will make an arbitrary choice of the
``prior''. In particular, our ``prior'' will be zero on all neural net structures
other than the one we train. Since the weights in the network are real valued,
we will choose a multidimensional gaussian over the weights which parameterize
the neural networks defined on our structure. In particular, the multidimensional
gaussian will have a mean \( 0 \) and a variance in each dimension of \( b^{2} \).

The optimal value of \( b \) is unknown and dependent on the learning problem
so we will wish to parameterize it in an example dependent manner. We can do
this using the same trick as for the original neural net bound. Essentially,
we prove several bounds which are tighter then necessary, then we use the union
bound to prove that all bounds hold simultaneously with probability at least
\( 1-\delta  \). 

Now, assume that our ``posterior'' \( Q \) is also defined by a multidimensional
gaussian with the mean and variance in each dimension defined by \( w_{i} \)
and \( s_{i}^{2} \). Then, we can specialize to the following corollary:

\begin{cor}
(PAC-Bayes for Neural Networks) Let \( k \) be the number of weights in a neural
net, \( w_{i} \) be the \( i \)th weight and \( s_{i} \) be the variance
of the \( i \)th weight. Then, we have
\begin{equation}
\label{big_bound}
\Pr _{D}\left( \exists Q:\, \, \textrm{KL}(\hat{e}_{Q}(h)||e_{Q}(h))\geq \inf _{j}\frac{\sum _{i=1}^{k}[\ln \frac{cb^{j}}{s_{i}}+\frac{s_{i}^{2}+w_{i}^{2}}{c^{2}b^{2j}}-1]+\ln \frac{8j^{2}m}{\pi ^{2}\delta }}{m-1}\right) \leq \delta 
\end{equation}

\end{cor}
\begin{proof}
Analytic calculation of the KL divergence between two multidimensional Gaussians
and the union bound applied for each value of \( j \).
\end{proof}
We will choose \( b=1.1 \) and \( c=0.2 \) as reasonable default values.

One more step is necessary in order to apply this bound. The essential difficulty
is evaluting \( \hat{e}_{Q}(h) \). This quantity is observable although calculating
it to high precision is difficult. We will avoid the need for a direct evaluation
by a monte carlo evaluation and a bound on the tail of the monte carlo evaluation.
Let \( \hat{e}_{\hat{Q}}(h)=\Pr _{\hat{Q},S}(h(x)\neq y) \) be the observed
rate of failur of a random hypothesis on a random example. Then, the following
simple bound holds:

\begin{thm}
(Sample Convergence Bound) For all distributions, \( Q \), for all sample sets
\( S \),
\[
\Pr _{Q}\left( \textrm{KL}(\hat{e}_{\hat{Q}}(h)||\hat{e}_{Q}(h))\geq \frac{\ln \frac{2}{\delta }}{n}\right) \leq \delta \]
where \( n \) is the number of evaluations of the stochastic hypothesis.
\end{thm}
\begin{proof}
This is simply an application of the Chernoff Relative Entropy bound for the
tail of a Binomial. Here, a ``head'' occurs when an error is observed and
the expected error rate is \( \hat{e}_{Q}(h) \).
\end{proof}
In order to calculate a bound on the expected true error rate, we will first
bound the expected empirical error rate with confidence \( \frac{\delta }{2} \)
then bound the expected true error rate, \( e_{Q}(h) \), using the bound on
expected empirical error rate \( \hat{e}_{Q}(h) \) with confidence \( \frac{\delta }{2} \).


\subsection{Distribution Construction algorithm}

One critical step is missing in the description: How do we calculate the multidimensional
gaussian, \( Q \)? The variance of the gaussian needs to be dependent on each
weight in order to achieve a tight bound because we want any ``meaningless''
weights to not contribute significantly to the overall complexity. We use a
simple greedy algorithm to find the appropriate variance in each dimension.

\begin{enumerate}
\item Train a neural net on the examples
\item For every weight, \( w_{i} \), search for the variance, \( s_{i}^{2} \), which
reduces the empirical accuracy of the trained network by \( 5\% \) while holding
all other weights fixed.
\item The stochastic neural network defined by \( \{w_{i},\, \, s_{i}^{2}\} \) will
generally have a too-large empirical error. Therefore, we calculate a global
multiplier \( \lambda <1 \) such that the stochastic neural network defined
by \( \{w_{i},\, \, \lambda s_{i}^{2}\} \) decreases the empirical accuracy
by only \( 5\% \).
\item Then, we evaluate the empirical error rate of the resulting stochastic neural
net with many (\( 1000 \)) samples.
\end{enumerate}

\section{Experimental Results}

How well can we bound the true error rate of a stochastic neural network? The
answer is \emph{much} better than we can bound the true error rate of a neural
network. 

Our experimental results take place on a synthetic dataset which has 25 input
dimensions and one output dimension. Most of these dimensions are useless -
simply random numbers drawn from a \( N(0,1) \) Gaussian. One of the 25 input
dimensions is dependent on the label. First, the label \( y \) is drawn uniformly
from \( \{-1,1\} \), then the special dimension is drawn from a \( N(y,1) \)
Gaussian. Note that this learning problem can not be learned perfectly because
some examples will be drawn from the tail of the gaussian resulting in the special
dimension being an incomplete estimator.

The ``ideal'' neural net to use in solving this problem is a single node perceptron.
We will instead use a 2 layer neural net with 2 hidden nodes. This overly large
neural net will result in the potential for significant overfitting which makes
the bound prediction problem interesting. It is also somewhat more ``realistic''
if the neural net structure does not exactly fit the learning problem as is
typical in real-world problems. 

All of our datasets will use just \( 100 \) examples. Constructing a nonvacuous
bound for a continuous hypothesis space at \( 100 \) examples is quite challenging
as indicated by figure \ref{bound_vs_epoch}. Conventional bounds are hopelessly
loose while the stochastic neural network bound is still not as tight as we
might desire.

\begin{figure}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{bound_vs_epoch.ps}}} \par}


\caption{\label{bound_vs_epoch}We plot the true error bounds for the neural network
and the stochastic neural network. Note that a true error bound of ``100''
implies that at least \protect\( 100^{2}\protect \) more examples are required
in order to make a nonvacuous bound.}
\end{figure}
The comparison between the neural network bound and the stochastic neural network
bound is not quite ``fair'' due to the form of the bound. In particular, the
stochastic neural network bound can never return a value greater then ``\( 1 \)''
which implies that when the bound is near the value of ``\( 1 \)'', it is
difficult to judge how rapidly extra examples will improve the stochastic neural
network bound. We can judge the sample complexity of the stochastic bound by
plotting the value of the numerator in \ref{big_bound}. Figure \ref{complexity_vs_epoch}
plots the complexity versus training epoch. 

\begin{figure}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{complexity.ps}}} \par}


\caption{\label{complexity_vs_epoch} We plot the ``complexity'' (numerator of \ref{big_bound})
vs. training epoch. Note that the complexity increases with more training as
expected and stays below \protect\( 100\protect \), implying nonvacuous bounds
on a training set of size \protect\( 100\protect \).}
\end{figure}
The stochastic bound is a radical improvement on the neural network bound but
it is not yet a perfectly tight bound. Given that we do not have a perfectly
tight bound, one important consideration arises: does the minimum of the stochastic
bound predict the minimum of the ``real'' bound (as predicted by a large holdout
dataset). In general, the stochastic bound depends upon the complexity which
increases with the training epoch and the training error which decreases with
the epoch. For this particular problem, we observe that the minimum bound (of
\( 0.48 \)) is achieved at approximately one epoch, the epoch of minimum true
error on a holdout set.

All of the previous graphs were constructed by (approximately) choosing a stochastic
neural network which has an empirical error rate \( 5\% \) worse than the empirical
error rate of the neural network. Is this optimal? In general, the ``optimal''
choice of the extra error rate depends upon the learning problem. Since the
PAC-Bayes Relative Entropy bound \ref{PBRE} holds for all distributions, we
are free to optimize the choice of distribution in anyway we desire. Figure
\ref{q_opt} shows the resulting bound for different choices of \( q \). The
bound has a minimum at \( 0.03 \) extra error. Also note that the complexity
always decreases with increasing error rate so the existence of a minimum implies
that the increased empirical error rate is significant for the calculation of
the true error bound.

\begin{figure}
{\par\centering \resizebox*{0.9\columnwidth}{!}{\rotatebox{270}{\includegraphics{error_vs_bound.ps}}} \par}


\caption{\label{q_opt}Plot of the Stochastic NN bound for ``posterior'' distributions
chosen according to the extra error they introduce.}
\end{figure}



\section{Conclusion}

We have introduced a bound on the true error rate of a stochastic Neural Net
derived from a PAC-Bayes bound. The stochastic Neural Net bound results in a
radically tighter (\( 2-3 \) orders of magnitude) bound on the true error rate
of a classifier while increasing the empirical error rate only a small amount. 

Although, the Stochastic Neural Net bound is not completely tight, it
is not vacuous with just \( 100 \) examples and the minima of the
bound weakly predicts the point where overtraining occurs.

The results with a synthetic data set are extremely promising -- the
bounds are \emph{orders of magnitude} better.  Our next step will be
to test the method on a few ``real world'' datasets to insure that the
bounds remain tight. In addition, there remain many opportunities for
improving the application of the bound.  For example, it is possible
that shifting the weights as well as finding a maximum acceptable
variance will result in a tighter bound. Also, we have not taken into
account symmetries within the network which allow for a tighter bound
calculation.

\begin{thebibliography}{1}
\bibitem{LS}John Langford and Matthias Seeger, ``Bounds for Averaging Classifiers.'' CMU
tech report, 2001.
\bibitem{PAC-Bayes}David McAllester, ``Some PAC-Bayes bounds'', COLT1999.
\bibitem{Bartlett}Peter Bartlett, ``The Sample Complexity of Pattern Classification with Neural
Networks: The Size of the Weights is More Important than the Size of the Network'',
IEEE Transactions on Information Theory, Vol. 44, No. 2, March 1998.
\bibitem{Panchenko}V. Koltchinskii and D. Panchenko, ``Empirical Margin Distributions and Bounding
the Generalization Error of Combined Classifiers'' http://citeseer.nj.nec.com/386416.html
\end{thebibliography}
\end{document}
