Learning boolean functions in an infinite attribute space

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning boolean functions in an infinite attribute space

Full text

Pdf (925 KB)

Source

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

Baltimore, Maryland, United States

Pages: 64 - 72

Year of Publication: 1990

ISBN:0-89791-361-2

Author

A. Blum

MIT Laboratory for Computer Science, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 21, Citation Count: 10

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

	AHK89	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning Read-Once Formulas with Queries, University of California at Berkeley, Berkeley, CA, 1989
	Ang86	Dana Angluin. Learning regular sets from queries and counter-examples. Technical Report YALEU/DCS/TR-464, Yale University Department of Computer Science, March 1986.
	Ang88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	HKLW88	David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
	Kea89	M. J. Kearns, The computational complexity of machine learning, Harvard University, Cambridge, MA, 1990
	KLPV87	Michael Kearns, Ming Li, Leonard Pitt, and Leslie Valiant. Recent results on boolean concept learning. In Proceedings of the Fourth International Workshop on Machine Learning, pages 337-352, University of California, Irvine, June 1987.
	Lit87	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	Lit89	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	Lit90	Nick Littlestone. private communication. 1990.
	Riv87	Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
	Val84	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 10

	William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.307-315, August 18-22, 1996, Zurich, Switzerland
	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
	William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, ACM Transactions on Information Systems (TOIS), v.17 n.2, p.141-173, April 1999
	Jyrki Kivinen , Heikki Mannila , Esko Ukkonen, Learning hierarchical rule sets, Proceedings of the fifth annual workshop on Computational learning theory, p.37-44, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Shai Ben-David , Nadav Eiron , Eyal Kushilevitz, On self-directed learning, Proceedings of the eighth annual conference on Computational learning theory, p.136-143, July 05-08, 1995, Santa Cruz, California, United States
	Shai Ben-David , Eyal Kushilevitz , Yishay Mansour, Online Learning versus Offline Learning, Machine Learning, v.29 n.1, p.45-63, Oct. 1997
	Igal Galperin, Analysis of greedy expert hiring and an application to memory-based learning (extended abstract), Proceedings of the ninth annual conference on Computational learning theory, p.217-223, June 28-July 01, 1996, Desenzano del Garda, Italy
	Adam R. Klivans , Rocco A. Servedio, Toward Attribute Efficient Learning of Decision Lists and Parities, The Journal of Machine Learning Research, 7, p.587-602, 12/1/2006
	Shai Ben-David , Nadav Eiron, Self-Directed Learning and Its Relation to the VC-Dimension and to Teacher-Directed Learning, Machine Learning, v.33 n.1, p.87-104, Oct. 1998
	Jialie Shen , John Shepherd , Bin Cui , Kian-Lee Tan, A novel framework for efficient automated singer identification in large music databases, ACM Transactions on Information Systems (TOIS), v.27 n.3, p.1-31, May 2009