Simple learning algorithms using divide and conquer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple learning algorithms using divide and conquer

Full text

Pdf (762 KB)

Source

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

Santa Cruz, California, United States

Pages: 447 - 453

Year of Publication: 1995

ISBN:0-89791-723-5

Author

Nader H. Bshouty

Department of Computer Science, The University of Calgary, Calgary, Alberta, Canada T2N 1N4

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	A88	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	AHK89	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]
	Bs93	N. H. Bshouty. Exact learning via the monotone theory. In Proceeding of the 34th Symposium on Foundations of Computer Science. pages 302-311, November 1993~
	BR92	Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129748]
	BS90	Avrim Blum , Mona Singh, Learning functions of k terms, Proceedings of the third annual workshop on Computational learning theory, p.144-153, August 06-08, 1990, Rochester, New York, United States
	BFJ+94	Avrim Blum , Merrick Furst , Jeffrey Jackson , Michael Kearns , Yishay Mansour , Steven Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.253-262, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195147]
	K93	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
	KM93	Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, SIAM Journal on Computing, v.22 n.6, p.1331-1348, Dec. 1993 [doi>10.1137/0222080]
	KV94	Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
	SM94	Yoshifumi Sakai , Akira Maruoka, Learning monotone log-term DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.165-172, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181095]
	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 6

	Eyal Kushilevitz, A simple algorithm for learning O(log n)-term DNF, Proceedings of the ninth annual conference on Computational learning theory, p.266-269, June 28-July 01, 1996, Desenzano del Garda, Italy
	Amos Beimel , Felix Geller , Eyal Kushilevitz, The query complexity of finding local minima in the lattice, Information and Computation, v.171 n.1, p.69-83, November 25, 2001
	Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Journal of the ACM (JACM), v.43 n.4, p.747-770, July 1996
	Sally A. Goldman , Stephen S. Kwek , Stephen D. Scott, Learning from examples with unspecified attribute values (extended abstract), Proceedings of the tenth annual conference on Computational learning theory, p.231-242, July 06-09, 1997, Nashville, Tennessee, United States
	Marta Arias , Aaron Feigelson , Roni Khardon , Rocco A. Servedio, Polynomial certificates for propositional classes, Information and Computation, v.204 n.5, p.816-834, May 2006
	Rotem Bennet , Nader H. Bshouty, Learning attribute-efficiently with corrupt oracles, Theoretical Computer Science, v.387 n.1, p.32-50, November, 2007