BACK TO INDEX
Publications of Eduardo D. Sontag jointly with A. Macintyre
A. Macintyre and E.D. Sontag.
Finiteness results for sigmoidal neural networks.
In STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing,
New York, NY, USA,
Keyword(s): machine learning,
theory of computing and complexity.
This paper deals with analog circuits. 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.
BACK TO INDEX
This material is presented to ensure timely dissemination of
scholarly and technical work. Copyright and all rights therein
are retained by authors or by other copyright holders.
Last modified: Wed Aug 17 10:22:06 2022
This document was translated from BibTEX by