ON CONSTRUCTING SIZE- AND VLSI-OPTIMAL NEURAL NETWORKS
Dr Valeriu Beiu, Los Alamos National Laboratory, U.S.A.

Abstract: After a short introduction about neural networks in general, we shall present the state-of-the-art of learning techniques, with an emphasis on constructive algorithms. The focus will be on complexity aspects pertaining to neural networks:

* size complexity (and depth-size tradeoffs);
* learning complexity (and time-generalization tradeoffs);
* required precision and limited intrerconnectivity (fan-in = D).

All of these show that we are facing difficult problems - exponential growth in either space (precision and size) and/or time (learning time and depth = delay) - when resorting to neural networks for solving general classes of problems.

Further, we will detail very tight upper and lower bounds for the number-of-bits required for solving a given classification problem (n inputs and m classes). Because they are constructive, they can and will be used to explicitly quantize the input space in O(nm2) time steps.

Two constructive algorithms which generate networks of size O(mn/D) and depth O[log(mn)/log D] will be presented. One very interesting aspect to be discussed is the fact that optimal solutions (size and/or VLSI) can be obtained for small constant fan-ins. Finally, techniques for reducing the size (of the resulting nets) by impressive `constants' - while increasing their generalisation capabilities - will be suggested.

The two-spirals will be used as a leitmotif for exemplifying all the different steps involved, but several examples from automatic synthesis of mixed analogue/digital integrated circuits will end the presentation.

Future directions for research will be pointed out in the conclusions.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 11 June 1997.

back