Agnostic PAC-Learning of Functions on Analog Neural Nets

Abstract

There exist a number of negative results ([J), [BR), [KV]) about learning on neural nets in Valiant's model [V) for probably approx(cid:173) imately correct learning ("PAC-learning"). These negative results are based on an asymptotic analysis where one lets the number of nodes in the neural net go to infinit.y. Hence this analysis is less ad(cid:173) equate for the investigation of learning on a small fixed neural net. with relatively few analog inputs (e.g. the principal components of some sensory data). The latter type of learning problem gives rise to a different kind of asymptotic question: Can the true error of the neural net be brought arbitrarily close to that of a neural net with "optimal" weights through sufficiently long training? In this paper we employ some new arguments ill order to give a positive answer to this question in Haussler's rather realistic refinement of Valiant's model for PAC-learning ([H), [KSS)). In this more realistic model no a-priori assumptions are required about the "learning target" , noise is permitted in the training data, and the inputs and outputs are not restricted to boolean values. As a special case our result implies one of the first positive results about learning on multi-layer neural net.s in Valiant's original PAC-learning model. At the end of this paper we will describe an efficient parallel implementation of this new learning algorit.hm.