Depth-size tradeoffs for neural computation

The tradeoffs between the depth (i.e., the time for parallel computation) and the size (i.e., the number of threshold gates) in neural networks are studied. The authors focus the study on the neural computations of symmetric Boolean functions and some arithmetic functions. It is shown that a signifi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1991-12, Vol.40 (12), p.1402-1412
Main Authors: Siu, K.Y., Roychowdhury, V.P., Kailath, T.
Format: Article
Language:English
Subjects:
Applied sciences
Arithmetic
Artificial neural networks
Biological neural networks
Biology computing
Boolean functions
Circuits
Computer networks
Concurrent computing
Cybernetics
Electric, optical and optoelectronic circuits
Electronics
Exact sciences and technology
Multi-layer neural network
Neural networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The tradeoffs between the depth (i.e., the time for parallel computation) and the size (i.e., the number of threshold gates) in neural networks are studied. The authors focus the study on the neural computations of symmetric Boolean functions and some arithmetic functions. It is shown that a significant reduction in the size is possible for symmetric functions and some arithmetic functions, at the expense of a small constant increase in depth. In the process, several neural networks which have the minimum size among all the known constructions have been developed. Results on implementing symmetric functions can be used to improve results about arbitrary Boolean functions. In particular, it is shown that any Boolean function can be computed in a depth-3 neural network with O(2/sup n/ /sup 2/) threshold gates; it is also proven that at least Omega (2/sup n/ /sup 3/) threshold gates are required.< >
ISSN:0018-9340
1557-9956
DOI:10.1109/12.106225