AVAILABLE IN NEUROPROSE: paper on finite VC dimension for NN

[Eduardo Sontag]

TITLE:   "Finiteness results for sigmoidal `neural' networks"
AUTHORS:  Angus Macintyre and Eduardo D. Sontag

(To appear in Proc. 25th Annual Symp.Theory Computing, San Diego, May 1993)

FILE: sontag.vc.ps.Z

                                ABSTRACT

This paper deals with analog neural nets.  It establishes the finiteness of VC
dimension, teaching dimension, and several other measures of sample complexity
which arise in learning theory.  It also shows that the equivalence of
behaviors, and the loading problem, are effectively decidable, modulo a widely
believed conjecture in number theory.  The results, the first ones that are
independent of weight size, apply when the gate function is the ``standard
sigmoid'' commonly used in neural networks research.  The proofs rely on very
recent developments in the elementary theory of real numbers with
exponentiation.  (Some weaker conclusions are also given for more general
analytic gate functions.)  Applications to learnability of sparse polynomials
are also mentioned.

**** To retrieve:

unix> ftp archive.cis.ohio-state.edu (or 128.146.8.52)
Name : anonymous
Password: <your id>
ftp> cd pub/neuroprose
ftp> binary
ftp> get sontag.vc.ps.Z
ftp> quit
unix> uncompress sontag.vc.ps.Z
unix> lpr -Pps sontag.vc.ps (or however you print PostScript)

(With many thanks to Jordan Pollack for providing this valuable service!)

Eduardo D. Sontag
Department of Mathematics
Rutgers Center for Systems and Control (SYCON)
Rutgers University
New Brunswick, NJ 08903, USA