On Properties of Networks of Neuron-Like Elements

In this article we consider two aspects of computation with neural networks. Firstly we consider the problem of the complexity of the network required to compute classes of specified (structured) functions. We give a brief overview of basic known complexity theoremsfor readers familiar with neural network models but less familiar with circuit complexity theories. We argue that there is considerable computational and physiological justification for the thesis that shallow circuits (Le., networks with relatively few layers) are computationally more efficient. We hence concentrate on structured (as opposed to random) problems that can be computed in shallow (constant depth)circuits with a relatively few number (polynomial) of elements, and demonstrate classes of structured problems that are amenable to such low cost solutions. Wediscuss an allied problem-the complexity of learning-and close with some open problems and a discussion of the observed limitations of the theoretical approach. Wenext turn to a rigourous classification of how much a network of given structure can do; i.e., the computational capacity of a given construct.