Speaker:
Title:
Abstract: Learning problems in feed-forward neural network theory are essentially partial information issues. That is, we wish to reconstruct a desired input-output (i-o) function from partial information consisting of examples (i.e., individual function evaluations). A complexity theory for neural networks from the standpoint of information complexity has had some beginnings in the work of Girosi and Poggio and others. The theory of neural complexity contrasts itself from that of information complexity in that the former deals with numbers of neurons in the hidden layer of a feed-forward network which are necessary for the computation of a given i-o function, generally assuming full information about that function within some tolerance. This theory has seen some extensive and successful development in recent years, particularly in the work, e.g., of Mhaskar and Micchelli and Barron. Information complexity is to an extent the "second half" of complexity theory for neural networks, that which deals with information issues, and numbers of examples needed to encode given tasks into neural networks. Neural complexity has been studied in a number of places, while information complexity is, we believe, still open to a good deal of development. This is an attempt to study the interaction of the two. The first question we ask is, how complex a neural net (how many hidden units) do we need to express the desired i-o function within a given tolerance? The second arises when we assume unlimited neural resources (as large a hidden layer as we please), and asks how many examples of a function are required for its approximation within a given tolerance. The question of what to do with limited information has been at the center of learning theory for a number of years, with algorithms for classical feedforward nets such as backpropagation and the Boltzmann machine having received a good deal of attention. We wish to show the results here have practical significance in that they can be used directly to obtain upper and lower bounds on numbers of examples and neurons needed to develop systems with desired i-o functions. We present some examples of how this might be accomplished. Beyond calculating complexities, we wish also to construct algorithms optimizing neuron and example numbers, to show they are optimal or almost optimal, and to apply them to examples of interest. The optimal prescriptions here are presented with algorithms for the construction of RBF networks.