Result available.

[Bhaskar DasGupta]

************** PLEASE DO NOT FORWARD TO OTHER NEWSGROUPS ****************

The following technical report has been placed in the neuroprose 
archives at Ohio State University. Questions and comments about
the result will be very highly appreciated.


    EFFICIENT APPROXIMATION WITH NEURAL NETWORKS: A COMPARISON OF
                       GATE FUNCTIONS*

		Bhaskar DasGupta    Georg Schnitger

                    Tech. Rep. CS-92-14

          	 Department of Computer Science
         	The Pennsylvania State University
	         	University Park
		   	   PA 16802
                email: {bhaskar,georg}@cs.psu.edu


			ABSTRACT
		    	--------

We compare different gate functions in terms of the approximation
power of their circuits.  Evaluation criteria are circuit size s, circuit
depth d and the approximation error e(s,d).  We consider two 
different error models, namely ``extremely tight'' approximations (i.e. 
e(s,d) = 2^{-s}) and the ``more relaxed'' approximations (i.e. e(s,d) = s^{-d}).
Our goal is to determine those gate functions that are equivalent to
the standard sigmoid sigma (x) = 1/(1+exp(-x)) under these two
error models.

For error e(s,d) = 2^{-s}, the class of equivalent gate functions contains, 
among others, (non-polynomial) rational functions, (non-polynomial) 
roots and most radial basis functions.  Newman's approximation of |x| 
by rational functions is obtained as a corollary of this equivalence result. 
Provably not equivalent are polynomials, the sine-function and linear splines.  
For error e(s,d) = s^{-d}, the class of equivalent activation functions grows 
considerably, containing for instance linear splines, polynomials and the 
sine-function. This result only holds if the number of input units is counted 
when determining circuit size.  The standard sigmoid is distinguished in that 
relatively small weights and thresholds suffice.  

Finally, we consider the computation of boolean functions.  Now the binary
threshold gains considerable power. Nevertheless, we show that the standard 
sigmoid is capable of computing a certain family of n-bit functions
in constant size, whereas circuits composed of binary thresholds require size
at least proportional to log n (and, O(log n loglog n logloglog n) gates are
sufficient). This last result improves the previous best
known separation result of Maass, Schnitger and Sontag(FOCS, 1991).


(We wish to thank J. Lambert, W. Maass, R. Paturi, V. P. Roychodhury, K. Y. Siu 
and E. Sontag).

-------------------------------------------------------------------
(* This research was partially supported by NSF Grant CCR-9114545)
-------------------------------------------------------------------

************************ How to obtain a copy ************************

a) Via FTP:

unix> ftp archive.cis.ohio-state.edu (or 128.146.8.52)
Name: anonymous
Password: (type your email address)
ftp> cd pub/neuroprose
ftp> binary
ftp> get dasgupta.approx.ps.Z
ftp> quit
unix> uncompress dasgupta.approx.ps.Z
unix> lpr dasgupta.approx.ps (or however you print PostScript)

b) Via postal mail:

Request a hardcopy from one of the authors.

***********************************************************************

Bhaskar DasGupta                    | email: bhaskar at omega.cs.psu.edu
Department of Computer Science      | phone: (814)-863-7326
333 Whitmore Laboratory             | fax:   (814)-865-3176
The Pennsylvania State University
University Park
PA 16802.

***********************************************************************