CaltechAUTHORS
  A Caltech Library Service

Depth Efficient Neural Networks for Division and Related Problems

Siu, Kai-Yeung and Bruck, Jehoshua and Kailath, Thomas and Hofmeister, Thomas (1993) Depth Efficient Neural Networks for Division and Related Problems. IEEE Transactions on Information Theory, 39 (3). pp. 946-956. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20120309-113620511

[img]
Preview
PDF - Published Version
See Usage Policy.

1234Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120309-113620511

Abstract

An artificial neural network (ANN) is commonly modeled by a threshold circuit, a network of interconnected processing units called linear threshold gates. The depth of a circuit represents the number of unit delays or the time for parallel computation. The size of a circuit is the number of gates and measures the amount of hardware. It was known that traditional logic circuits consisting of only unbounded fan-in AND, OR, NOT gates would require at least Ω(log n/log log n) depth to compute common arithmetic functions such as the product or the quotient of two n-bit numbers, if the circuit size is polynomially bounded (in n). It is shown that ANN’S can be much more powerful than traditional logic circuits, assuming that each threshold gate can be built with a cost that is comparable to that of AND/OloRg ic gates. In particular, the main results show that powering and division can be computed by polynomial-size ANN’S of depth 4, and multiple product can be computed by polynomial-size ANN’S of depth 5. Moreover, using the techniques developed here, a previous result can be improved by showing that the sorting of n n-bit numbers can be carried out in a depth-3 polynomial size ANN. Furthermore, it is shown that the sorting network is optimal in depth.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/18.256501DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=256501PublisherUNSPECIFIED
Additional Information:© 1993 IEEE. Manuscript received January 31, 1992; revised July 29, 1992. This work was supported in part by an Irvine Faculty Research Grant 91/92-27 and by the Joint Services Program at Stanford University (US. Army, U.S. Navy, U.S. Air Force) under Contract DAAL03-88-C-0011, and the Department of the Navy (NAVELEX) under Contract N00039-84-C-0211, NASA Headquarters, Center for Aeronautics, and Space Information Sciences under Grant NAGW-419-S6. The work of T. Hofmeister was supported by DFG Grant We 1066/2-2.
Funders:
Funding AgencyGrant Number
Irvine Faculty Research Grant91/92-27
Stanford University Joint Services ProgramDAAL03-88-C-0011
Department of the Navy (NAVALEX)N00039-84-C-0211
NASA Headquarters, Center for Aeronautics, and Space Information SciencesNAGW-419-S6
DFGUNSPECIFIED
Subject Keywords:Neural networks; threshold circuits; circuit complexity; division; arithmetic functions
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number4505261
Record Number:CaltechAUTHORS:20120309-113620511
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20120309-113620511
Official Citation:Siu, K.-Y.; Bruck, J.; Kailath, T.; Hofmeister, T.; , "Depth efficient neural networks for division and related problems ," Information Theory, IEEE Transactions on , vol.39, no.3, pp.946-956, May 1993 doi: 10.1109/18.256501
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29665
Collection:CaltechAUTHORS
Deposited By: Jason Perez
Deposited On:12 Mar 2012 15:30
Last Modified:26 Dec 2012 14:56

Repository Staff Only: item control page