__
TR94-020 | 12th December 1994 00:00
__

#### Agnostic PAC-Learning of Functions on Analog Neural Nets

TR94-020
Authors:

Publication: 12th December 1994 00:00

Downloads: 3419

Keywords:

**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 1/epsilon, where epsilon is some arbitrary given bound for the

true error of the neural net after training, and in 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.