Orlitsky, editors, Kluwer Academic Publishers Perspectives of Current Research about the Complexity of Learning on Neural Nets

This paper discusses within the framework of computational learning theory the current state of knowledge and some open problems in three areas of research about learning on feedforward neural nets: { Neural nets that learn from mistakes { Bounds for the Vapnik-Chervonenkis dimension of neural nets { Agnostic PAC-learning of functions on neural nets. All relevant denitions are given in this paper, and no previous knowledge about computational learning theory or neural nets is required. We refer to [RSO] for further introductory material and survey papers about the complexity of learning on neural nets. Throughout this paper we consider the following rather general notion of a (feed-forward) neural net. De nition 1.1 A network architecture (or \neural net") N is a labeled acyclic directed graph. Its nodes of fan-in 0 ( \ input nodes"), as well as its nodes of fan-out 0 ( \ output nodes") are labeled by natural numbers. A node g in N with fan-in r> 0 is called a computation node (or gate), and it is labeled by some activation function g: R! R, some polynomial