|
NeuroCOLT
Technical Report NC-TR-94-022
Sample Sizes for
Sigmoidal Neural Networks
John
Shawe-Taylor
Department of Computer Science
Royal Holloway University of London
Abstract
This paper applies the theory of Probably Approximately Correct (PAC)
learning to feedforward neural networks with sigmoidal activation
functions. Despite the best known upper bound on the VC dimension
of such networks being $O((WN)^2)$, for $W$ parameters and $N$ computational
nodes, it is shown that the asymptotic bound on the sample size required
for learning with increasing accuracy $1 - \epsilon$ and decreasing
probability of failure $\delta$ is $$O((1/\epsilon)(W\log(1/\epsilon)
+ (WN)^2 + \log(1/\delta)).$$ For practical values of $\epsilon$ and
$\delta$ the formula obtained for the sample sizes is a factor $2\log(2e/\epsilon)$
smaller than a naive use of the VC dimension result would give. Similar
results are obtained for learning where the hypothesis is only guaranteed
to correctly classify a given proportion of the training sample. The
results are formulated in general terms and show that for many learning
classes defined by smooth functions thresholded at the output, the
sample size for a class with VC-dimension $d$ and $\ell$ parameters
is $O((1/\epsilon)(\ell\log(1/\epsilon) + o(\log(1/\epsilon))d + \log(1/\delta))$.
Download Compressed
Postscript
|