Agnostic PAC-Learning of Functions on Analog Neural Nets

摘要

We consider learning on multi-layer neural nets with piecewise polynomialactivation functions and a fixed number k of numerical inputs. We exhibitarbitrarily large network architectures for which efficient and provablysuccessful learning algorithms exist in the rather realistic refinement ofValiant'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 arbitraryreals. The number of computation steps of the learning algorithm LEARN thatwe construct is bounded by a polynomial in the bit-length n of the fixednumber of input variables, in the bound s for the allowed bit-length ofweights, in 1/epsilon, where epsilon is some arbitrary given bound for thetrue error of the neural net after training, and in 1/delta, where delta issome arbitrary given bound for the probability that the learning algorithm fails for a randomly drawn training sample. However the computation time ofLEARN is exponential in the number of weights of the considered network architecture, and therefore only of interest for neural nets of small size.