NDLI: Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Maass, Wolfgang
Copyright Year	1997
Abstract	It is shown that high-order feedforward neural nets of constant depth with piecewise-polynomial activation functions and arbitrary real weights can be simulated for Boolean inputs and outputs by neural nets of a somewhat larger size and depth with Heaviside gates and weights from {-1, 0, 1}. This provides the first known upper bound for the computational power of the former type of neural nets. It is also shown that in the case of first-order nets with piecewise-linear activation functions one can replace arbitrary real weights by rational numbers with polynomially many bits without changing the Boolean function that is computed by the neural net. In order to prove these results, we introduce two new methods for reducing nonlinear problems about weights in multilayer neural nets to linear problems for a transformed set of parameters. These transformed parameters can be interpreted as weights in a somewhat larger neural net.As another application of our new proof technique we show that neural nets with piecewise-polynomial activation functions and a constant number of analog inputs are probably approximately correct (PAC) learnable (in Valiant's model for PAC learning [Comm. Assoc. Comput. Mach., 27 (1984), pp. 1134--1142]).
Starting Page	708
Ending Page	732
Page Count	25
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539793256041
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	26
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-28
Access Restriction	Subscribed
Subject Keyword	circuit complexity Models of computation Learning and adaptive systems Analytic circuit theory neural networks analog computing threshold circuits learning complexity Complexity classes Neural networks, artificial life and related topics
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Algebraic Techniques for Constructing Minimal Weight Threshold Functions

Signal Processing by Model Neural Networks

Deep Recurrent Neural Networks for Time Series Prediction

A Comparative Study of Sparse Associative Memories

On the Power of Threshold Circuits with Small Weights

BOUNDS FOR THE COMPUTATIONAL POWER AND LEARNING COMPLEXITY OF ANALOG NEURAL NETS

Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

Bounds for the computational power and learning complexity of analog neural nets

Associative Memories to Accelerate Approximate Nearest Neighbor Search

Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

Similar Documents

Algebraic Techniques for Constructing Minimal Weight Threshold Functions

Signal Processing by Model Neural Networks

Deep Recurrent Neural Networks for Time Series Prediction

A Comparative Study of Sparse Associative Memories

On the Power of Threshold Circuits with Small Weights

BOUNDS FOR THE COMPUTATIONAL POWER AND LEARNING COMPLEXITY OF ANALOG NEURAL NETS

Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

Bounds for the computational power and learning complexity of analog neural nets

Associative Memories to Accelerate Approximate Nearest Neighbor Search

Bounds for the Computational Power and Learning Complexity of Analog Neural Nets