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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (1.13 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 335 - 344

Year of Publication: 1993

ISBN:0-89791-591-7

Author

Wolfgang Maass

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 27, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167193 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	A	Y.S. Abu-Mostafa, "The Vapnik-Chervonenkis dimension: information versus complexity in learning", Neural Computation, vol. 1, 1989, 312- 317
	B	P. L. Bartlett, "Lower bounds on the Vapnik-Chervonenkis dimension of multilayer threshold networks", preprint (July 1992)
	BH	Eric B. Baum , David Haussler, What size net gives valid generalization?, Neural Computation, v.1 n.1, p.151-160, Spring 1990 [doi>10.1162/neco.1989.1.1.151]
	BR	Avrim Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Proceedings of the first annual workshop on Computational learning theory, p.9-18, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	CSV	A.K. Chandra, L. Stockmeyer, U. Vishkin, "Constant depth reducibility", SIAM Y. Computing, vol. 13 (2), 1984, 423- 439
	C	T.M. Cover, "Capacity problems for linear machines", in: Pattern Recognition, L. K#mal ed., Thompson Book Co., 1988, 283- 289
	DS	B. DasGupta, G. Schnitger, "Efficient approximations with neural networks: a comparison of gate functions", preprint (Aug. 1992)
	DR	Richard Durbin , David E. Rumelhart, Product units: a computationally powerful and biologically plausible extension to backpropagation networks, Neural Computation, v.1 n.1, p.133-142, Spring 1990 [doi>10.1162/neco.1989.1.1.133]
	E	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	EOS	H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
	GJ	P. Goldberg, M. Jerrum, "Bounding the Vapnik- Chervonenkis dimension of concept classes parameterized by real numbers", preprint (February 1993).
	GHR	M. Goldmann, J. Hastad, A. Razborov, "Majority gates vs. general weighted threshold gates", Proc. of the 7th Structure in Complexity Theory Conference, 1992, 2 - 13
	HMPST	András Hajnal , Wolfgang Maass , Pavel Pudlák , György Turán , Márió Szegedy, Threshold circuits of bounded depth, Journal of Computer and System Sciences, v.46 n.2, p.129-154, April 1993 [doi>10.1016/0022-0000(93)90001-D]
	Has	J. Hastad, "On the size of weights for threshold gates", preprint (September 1992)
	H	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	Ho	J.J. Hopfield, "Neurons with graded response have collective computational properties hke those of two-state neurons", Proc. Nat. Acad. of Sciences USA, 1984, 3088 - 3092
	J	David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	KV	M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
	L	R.P. Lippmann, "An introduction to computing with neural nets", IEEE ASSP Magazine, 1987, 4- 22
	Lu	O.B. Lupanov, "On circuits of threshold elements", Dokl. Akad. Nauk SSSR, vol. 202, 1288- 1291; engl. translation in: Soy. Phys. Dokl., vol. 17, 1972, 91 - 93
	M	W. Maass, "Bounds for the computational power and learning complexity of analog neural nets", IIG - Report 3#9 of the Technische UniversitSt Graz, (October 1992).
	MSS	Wolfgang Maass , Georg Schnitger , Eduardo D. Sontag, On the computational power of sigmoid versus boolean threshold circuits (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.767-776, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185447]
	MT	Wolfgang Maass , György Turán, How fast can a threshold gate learn?, Proceedings of a workshop on Computational learning theory and natural learning systems (vol. 1) : constraints and prospects: constraints and prospects, p.381-414, August 1994, Princeton, New Jersey, United States
	MS	Angus Macintyre , Eduardo D. Sontag, Finiteness results for sigmoidal “neural” networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.325-334, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167192]
	MR	James L. McClelland , David E. Rumelhart , CORPORATE PDP Research Group, Parallel distributed processing: explorations in the microstructure, vol. 2: psychological and biological models, MIT Press, Cambridge, MA, 1986
	Me	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	MP	M. Minsky, S. Papert, "Perceptrons: An Introduction to Computational Geometry", Expanded Edition, MIT Press (Cambridge, 1988)
	MD	J. Moody, C. J. Darken, "Fast learning in networks of locally-tuned processing units", Neural Computation, vol. 1, 1989, 281- 294
	Mu	S. Muroga, "Threshold Logic and its Applications", Wiley (New York, 1971)
	N	E.I. Neciporuk, "The synthesis of networks from threshold elements", Probl. Kibern. No. 11, 1964, 49 - 62; engl. translation in: Autom. Expr., vol. 7, No. 1, 1964, 35- 39
	Ni	N.J. Nilsson, Learning Machines, McGraw- Hill (New York, 1971)
	PS	Ian Parberry , Georg Schnitger, Parallel Computation with Threshold Functions, Proceedings of the Conference on Structure in Complexity Theory, p.272-290, June 02-05, 1986
	PG	T. Poggio, F. Girosi, "Networks for approximation and learning", Proc. of the IEEE, vol. 78(9), 1990, 1481- 1497
	R	F. Rosenblatt, "Principles of Neurodynamics", Spartan Books (New York, 1962)
	RM	David E. Rumelhart , James L. McClelland , CORPORATE PDP Research Group, Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations, MIT Press, Cambridge, MA, 1986
	Sch	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	SS	H.T. Siegelmann, E. D. Sontag, "Neural networks with real weights: analog computational complexity", Report SYCON-92- 05, Rutgers Center for Systems and Control (Oct. 1992)
	SBKH	K.Y. Sill, J. Bruck, T. Kailath, T. Hofmeister, "Depth efficient neural networks for division and related problems", to appear in IEEE Transactions on Inf. Theory
	SR	K.Y. Siu, V. Roychowdhury, "On optimal depth threshold circuits for multiplication and related problems", Tech. Report ECE- 92-05, University of California, Irvine (March 1992)
	S1	Eduardo D. Sontag, Remarks on interpolation and recognition using neural nets, Proceedings of the 1990 conference on Advances in neural information processing systems 3, p.939-945, October 1990, Denver, Colorado, United States
	S2	Eduardo D. Sontag, Feedforward nets for interpolation and classification, Journal of Computer and System Sciences, v.45 n.1, p.20-48, Aug. 1992 [doi>10.1016/0022-0000(92)90039-L]
	S3	E.D. Sontag, private communication (July 1992)
	T	G. Wuran, private notes (1989)
	V	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

CITED BY 13

	Martin Anthony , Sean B. Holden, On the power of polynomial discriminators and radial basis function networks, Proceedings of the sixth annual conference on Computational learning theory, p.158-164, July 26-28, 1993, Santa Cruz, California, United States
	Peter Auer , Stephen Kwek , Wolfgang Maass , Manfred K. Warmuth, Learning of depth two neural networks with constant fan-in at the hidden nodes (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.333-343, June 28-July 01, 1996, Desenzano del Garda, Italy
	Pascal Koiran, Efficient learning of continuous neural networks, Proceedings of the seventh annual conference on Computational learning theory, p.348-355, July 12-15, 1994, New Brunswick, New Jersey, United States
	Angus Macintyre , Eduardo D. Sontag, Finiteness results for sigmoidal “neural” networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.325-334, May 16-18, 1993, San Diego, California, United States
	Paul Goldberg , Mark Jerrum, Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers, Proceedings of the sixth annual conference on Computational learning theory, p.361-369, July 26-28, 1993, Santa Cruz, California, United States
	Pekka Orponen, Computational complexity of neural networks: a survey, Nordic Journal of Computing, v.1 n.1, p.94-110, Spring 1994
	Michael Schmitt, Neural networks with local receptive fields and superlinear VC Dimension, Neural Computation, v.14 n.4, p.919-956, April 2002
	Bhaskar DasGupta , Hava T. Siegelmann , Eduardo Sontag, On a learnability question associated to neural networks with continuous activations (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.47-56, July 12-15, 1994, New Brunswick, New Jersey, United States
	Bhaskar DasGupta , Georg Schnitger, Analog versus discrete neural networks, Neural Computation, v.8 n.4, p.805-818, May 15, 1996
	Wolfgang Maass, Lower bounds for the computational power of networks of spiking neurons, Neural Computation, v.8 n.1, p.1-40, January 1996
	Arne Hole, Vapnik-chervonenkis generalization bounds for real valued neural networks, Neural Computation, v.8 n.6, p.1277-1299, August 15, 1996
	Georgios Lappas, Neural networks and multimedia datasets: estimating the size of neural networks for achieving high classification accuracy, Proceedings of the 9th WSEAS international conference on Multimedia systems & signal processing, p.237-242, May 20-22, 2009, Hangzhou, China
	Georgios Lappas, Designing neural networks for tackling hard classification problems, WSEAS TRANSACTIONS on SYSTEMS, v.8 n.6, p.743-752, June 2009