Part of Neural Information Processing Systems 0 (NIPS 1987)
Pierre Baldi, Santosh Venkatesh
The complexity and computational capacity of multi-layered, feedforward neural networks is examined. Neural networks for special purpose (structured) functions are examined from the perspective of circuit complexity. Known re(cid:173) sults in complexity theory are applied to the special instance of neural network circuits, and in particular, classes of functions that can be implemented in shallow circuits characterised. Some conclusions are also drawn about learning complexity, and some open problems raised. The dual problem of determining the computational capacity of a class of multi-layered networks with dynamics regulated by an algebraic Hamiltonian is considered. Formal results are pre(cid:173) sented on the storage capacities of programmed higher-order structures, and a tradeoff between ease of programming and capacity is shown. A precise de(cid:173) termination is made of the static fixed point structure of random higher-order constructs, and phase-transitions (0-1 laws) are shown.