|
NeuroCOLT
Technical Report NC-TR-95-002
Agnostic
PAC-Learning of Functions
on Analog Neural Nets
Wolfgang
Maass
Institute for Theoretical Computer Science
Technische Universitaet Graz, Klosterwiesgasse 32/2
A-8010 Graz
Austria
Abstract
We consider learning on multi-layer neural nets with piecewise polynomial
activation functions and a fixed number $k$ of numerical inputs. We
exhibit arbitrarily large network architectures for which efficient
and provably successful learning algorithms exist in the rather realistic
refinement of Valiant's model for probably approximately correct learning
(``PAC-learning'') where no a-priori assumptions are required about
the ``target function'' (agnostic learning), arbitrary noise is permitted
in the training sample, and the target outputs as well as the network
outputs may be arbitrary reals. The number of computation steps of
the learning algorithm LEARN that we construct is bounded by a polynomial
in the bit-length $n$ of the fixed number of input variables, in the
bound $s$ for the allowed bit-length of weights, in $\frac{1} {\varepsilon}$,
where $\varepsilon$ is some arbitrary given bound for the true error
of the neural net after training, and in $\frac{1}{\delta}$ where
${\delta}$ is some arbitrary given bound for the probability that
the learning algorithm fails for a randomly drawn training sample.
However the computation time of LEARN is exponential in the number
of weights of the considered network architecture, and therefore only
of interest for neural nets of small size.
Download Compressed
Postscript
|