Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension

Full text

Pdf (1.00 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 273 - 282

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

A Blumer	University of California at Santa Cruz and Department of Mathematics and Computer Science, University of Denver, Denver, Colorado
A Ehrenfeucht	Department of Computer Science, University of Colorado, Boulder, Colorado
D Haussler	Department of Mathematics and Computer Science, University of Denver, Denver, Colorado
M Warmuth	Department of Computer and Information Sciences, University of California, Santa Cruz, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 61, Citation Count: 23

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/12130.12158 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.

	A83	Assouad, P., "Densite et Dimension," Ann. Inst. Fourier, Grenoble 33 (3) (1983) 233-282.
	BEHW85	Bhmer, A., A. Ehrenfeucht, D. Haussler and M. Warmuth, "Occam's Razor," Technical Report UCSC-CRL-86-2, Computer Research Laboratory, University of California at Santa Cruz, February 1986.
	DW76	Devroye, L.P. and T.J.Wagner, "A distribution-free performance bound in error estimation," IEEE Trans. Info. Th., 22, 1976, pp. 586-7.
	D78	Dudley, R.M., "Central limit theorems for empirical measures," Ann. Prob., 6(6), 1978, pp. 899- 929.
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	GGM84	Goldreich, O., S. Goldwasser, and S. Micali, "How to construct random functions," 25th FOCS, 1984, pp. 464-79.
	H85	Haussler, D., "Space Efficient Learning Algorithms," unpublished manuscript.
	HW85	Haussler, D. and E. Welzl, "Epsilon-nets and range queries," in preparation.
	J74	Johnson, D.S., "Approximation Algorithms for combinatorial problems," Journal of Computer and Systems Sciences, Vol. 9, 1974.
	K84	N. Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.302-311, December 1984 [doi>10.1145/800057.808695]
	LP85	Lee, D.T. and F.P.Preparata, "Computational geometry - a survey," IEEE Trans. Comp., 33(12), 1984, pp. 1072-101.
	L85	Littlestone, N., unpublished manuscript.
	M78	Masek, WJ., "Some NP-Complete Set Cover Problems," MIT Laboratory for Computer Science, unpublished manuscript.
	M84	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]
	N69	Nigmatullin, R.G., "The Fastest Descent Method for Covering Problems (in Russian)," Proceedings of a Symposium on Questions of Precision and Efficiency of Computer Algorithms," Book 5, Kiev, 1969, pp. 116-126.
	P78	Pearl, J., "On the connection between the complexity and credibility of inferred models," Int. J. Gen. Sys., 4, 1978, pp. 255-64.
	P79	Pearl, J., "Capacity and error estimates for Boolean classifiers with limited capacity," IEEE Trans. Patt. An. Mach. Intell., 1(4), 1979, pp. 350-5.
	V84	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]
	VP86	Valiant, L.G., L. Pitt, Technical Report, Aiken Computing Lab., Harvard University, to appear.
	V85	Valiant, L.G., "Learning disjunctions of conjunctions," Proc. 9th IJCAI, Los Angeles, CA, August 1985, vol. 1, pp. 560-6.
	VC71	Vapnik, V.N. and A.Ya.Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities," Th. Prob. and its Appl., 16(2), 1971, pp. 264-80.
	VC74	Vapnik, V.N. and A.Ya.Chervonenkis, Theory of Pattern Recognition (in Russian), Nauka, Moscow, 1974.
	W86	Welzl, E., "Some properties of the Vapnik- Chervonenkis dimension," in preparation.
	WD81	Wenocur, R.S. and R.M.Dudley, "Some special Vapnik-Chervonenkis classes," Discrete Math., 33, 1981, pp. 313-8.
	YC74	Young, T. and T. Calvert, Classification, Estimarion, and Pattern Recognition, Elsevier, New York, 1974.

CITED BY 23

	Arlindo L. Oliveira , João P. M. Silva, Efficient Algorithms for the Inference of Minimum Size DFAs, Machine Learning, v.44 n.1-2, p.93-119, July-August 2001
	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
	K L Clarkson, Further applications of random sampling to computational geometry, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.414-423, May 28-30, 1986, Berkeley, California, United States
	M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States
	Kathleen Romanik, Approximate testing and learnability, Proceedings of the fifth annual workshop on Computational learning theory, p.327-332, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Gyora M. Benedek , Alon Itai, Dominating distributions and learnability, Proceedings of the fifth annual workshop on Computational learning theory, p.253-264, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Yoav Freund, An improved boosting algorithm and its implications on learning complexity, Proceedings of the fifth annual workshop on Computational learning theory, p.391-398, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada
	D Haussler , E Welzl, Epsilon-nets and simplex range queries, Proceedings of the second annual symposium on Computational geometry, p.61-71, June 02-04, 1986, Yorktown Heights, New York, United States
	Michael Kearns , Ming Li , Leslie Valiant, Learning Boolean formulas, Journal of the ACM (JACM), v.41 n.6, p.1298-1328, Nov. 1994
	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988
	B. K. Natarajan, On learning Boolean functions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.296-304, January 1987, New York, New York, United States
	Philip Laird , Ronald Saul , Peter Dunning, A model of sequence extrapolation, Proceedings of the sixth annual conference on Computational learning theory, p.84-93, July 26-28, 1993, Santa Cruz, California, United States
	Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States
	William W. Cohen , Haym Hirsh, Learnability of description logics, Proceedings of the fifth annual workshop on Computational learning theory, p.116-127, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	S. R. Kulkarni , J. N. Tsitsiklis , S. K. Mitter , O. Zeitouni, PAC learning with generalized samples and an application to stochastic geometry, Proceedings of the fifth annual workshop on Computational learning theory, p.172-179, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Naoki Abe, Feasible learnability of formal grammars and the theory of natural language acquisition, Proceedings of the 12th conference on Computational linguistics, p.1-6, August 22-27, 1988, Budapest, Hungry
	Haim Shvaytser, Representing knowledge in learning systems by pseudo boolean functions, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
	S. R. Kulkarni , S. K. Mitter , J. N. Tsitsiklis , O. Zeitouni, PAC Learning with Generalized Samples and an Applicaiton to Stochastic Geometry, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.933-942, September 1993
	Benjamin W. Wah, Generalization and Generalizability Measures, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.175-186, January 1999
	Yaser S. Abu-Mostafa, Review:, Neural Computation, v.1 n.3, p.312-317, Fall 1989
	Qiong Gao , Ming Li, The minimum description length principle and its application to online learning of handprinted characters, Proceedings of the 11th international joint conference on Artificial intelligence, p.843-848, August 20-25, 1989, Detroit, Michigan
	Achim G. Hoffmann , Sunil Thakar, Acquiring knowledge by efficient query learning, Proceedings of the 12th international joint conference on Artificial intelligence, p.783-788, August 24-30, 1991, Sydney, New South Wales, Australia