Attribute-efficient learning in query and mistake-bound models

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Attribute-efficient learning in query and mistake-bound models

Full text

Pdf (1.01 MB)

Source

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

Desenzano del Garda, Italy

Pages: 235 - 243

Year of Publication: 1996

ISBN:0-89791-811-8

Authors

Nader H. Bshouty	Department of Computer Science, University of Calgary, Calgary, Alberta, Canada
Lisa Hellerstein	Department of EECS, Northwestern University, Evanston, Illinois

Sponsors

Univ degli Studi de Milano : Universite degli Studi de Milano
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): 15, Downloads (12 Months): 27, Citation Count: 4

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

	1	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	2	Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
	3	Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Journal of Computer and System Sciences, v.50 n.1, p.32-40, Feb. 1995 [doi>10.1006/jcss.1995.1004]
	4	R. Boppana. Amplification of probabilistic boolean formulas. Advances in Computing Research, 5(4):27-45, 1989.
	5	Nader H. Bshouty , Richard Cleve , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.130-139, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181067]
	6	J. Friedman. Constructing O(n log n) size monotone formulae for the k-th elementary symmetric polynomial of n boolean variables. In IEEE Symposium or, Foundations of Computer Science (FOCS), pages 506-515, 1984.
	7	M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math Systems Theory, 17:13-27, 1984.
	8	Sampath K. Kannan, On the query complexity of learning, Proceedings of the sixth annual conference on Computational learning theory, p.58-66, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168312]
	9	M. Kleiman and N. Pippenger. An explicit construction of short monotone formulae for the monotone symmetric functions. Theoretical Computer Sczence, 7:325-332, 1978.
	10	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]

CITED BY 4

	Peter Damaschke, Adaptive Versus Nonadaptive Attribute-Efficient Learning, Machine Learning, v.41 n.2, p.197-215, November 2000
	Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, More efficient PAC-learning of DNF with membership queries under the uniform distribution, Proceedings of the twelfth annual conference on Computational learning theory, p.286-295, July 07-09, 1999, Santa Cruz, California, United States
	Peter Damaschke, Adaptive versus nonadaptive attribute-efficient learning, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.590-596, May 24-26, 1998, Dallas, Texas, United States
	Peter Damaschke, On parallel attribute-efficient learning, Journal of Computer and System Sciences, v.67 n.1, p.46-62, August 2003