Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers

Full text

Pdf (894 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the sixth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 361 - 369

Year of Publication: 1993

ISBN:0-89791-611-5

Authors

Paul Goldberg
Mark Jerrum

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 19, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/168304.168377 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.

	AB92	Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
	ABB91	Helmut Alt , Bernd Behrends , Johannes Blömer, Approximate matching of polygonal shapes (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.186-193, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109669]
	BEHW87	Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
	BEHW89	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	BH89	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]
	D78	R. M. Dudley, Central Limit Theorems for Empirical Measures, Annals of Probab~hty 6 (1978), pp. 899-929.
	G92	P. Goldberg. PAC-Learning Geometrical Figures. PhD theszs, Department of Computer Science, University of Edinburgh (1992).
	H67	M. Hall Jr, Combinatorial Theory, BlaisdeU, Waltham MA (1967).
	HLW88	D. Haussler, N. Littlestone, M.K. Warmuth (1988). Predicting {0, 1} functions on randomly drawn points. Proceedings of the 1988 IEEE FOCS Symposzum, pp. 100-109.
	L92	M.C. Laskowski. Vapnik-Chervonenkis Classes of Definable Sets. J. London Math. Society, (2) 45 (1992), pp. 377-384.
	M92	Wolfgang Maass, Bounds for the computational power and learning complexity of analog neural nets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.335-344, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167193]
	MS92	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]
	M64	J. Milnor. On the Betti Numbers of Real Varieties. Procs. of the American Mathematical Society, 15, (1964) pp. 275-280.
	N91	Balas Kausik Natarajan, Machine learning: a theoretical approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	R92	James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
	S92	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]
	SY89	G. Stengle and J. E. Yukich, Some New Vapnik-Chervonenkis Classes, Annals of Statistics 17 (1989), pp. 1441-1446.
	VC71	V.N. Vapnik, A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Prob~ ab~hty and zts Apphcatzons 16 (1971), No. 2 pp. 264-280.
	W68	H.E. Warren. Lower Bounds for Approximation by Non-linear Manifolds. Trans. of the AMS 133 (1968), pp. 167-178.
	WD81	R.S. Wenocur, R.M. Dudley. Some special Vapnik-Chervonenkis classes. Dzscrete Mathematics 33 (1981), pp. 313-318.

CITED BY 8

	John Shawe-Taylor, Sample sizes for sigmoidal neural networks, Proceedings of the eighth annual conference on Computational learning theory, p.258-264, July 05-08, 1995, Santa Cruz, California, United States
	Felipe Cucker , Marek Karpinski , Pascal Koiran , Thomas Lickteig , Kai Werther, On real Turing machines that toss coins, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.335-342, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Paul W. Goldberg , Sally A. Goldman, Learning one-dimensional geometric patterns under one-sided random misclassification noise, Proceedings of the seventh annual conference on Computational learning theory, p.246-255, July 12-15, 1994, New Brunswick, New Jersey, United States
	Wee Sun Lee , Peter L. Bartlett , Robert C. Williamson, Lower bounds on the VC-dimension of smoothly parametrized function classes, Proceedings of the seventh annual conference on Computational learning theory, p.362-367, July 12-15, 1994, New Brunswick, New Jersey, United States
	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
	Michael Lindenbaum , Shai Ben-David, VC-Dimension Analysis of Object Recognition Tasks, Journal of Mathematical Imaging and Vision, v.10 n.1, p.27-49, Jan. 1999
	Peter L. Bartlett , Robert C. Williamson, The vc dimension and pseudodimension of two-layer neural networks with discrete inputs, Neural Computation, v.8 n.3, p.625-628, April 1, 1996
	Arne Hole, Vapnik-chervonenkis generalization bounds for real valued neural networks, Neural Computation, v.8 n.6, p.1277-1299, August 15, 1996