Fast learning of k-term DNF formulas with queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast learning of k-term DNF formulas with queries

Full text

Pdf (832 KB)

Source

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

Victoria, British Columbia, Canada

Pages: 382 - 389

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Avrim Blum	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Steven Rudich	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/129712.129748 What is a DOI?

ABSTRACT

This paper presents an algorithm that uses equivalence and membership queries to learn the class of k-term DNF formulas in time O(n•2o(k)), where n is the number of input variables. This improves upon previous O(nk) bounds and allows one to learn DNF of O(log n) terms in polynomial time. We present the algorithm in its most natural form as a randomized algorithm, and then show how recent derandomization techniques can be used to make it deterministic. The algorithm is an exact learning algorithm, but one where the equivalance query hypotheses and the final output are general (not necessarily k-term) DNF formulas. For the special case of 2-term DNF formulas, we give a simpler version of our algorithm that uses at most 4n + 2 total membership and equivalence queries.

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	Howard Aizenstein , Leonard Pitt, Exact learning of read-twice DNF formulas (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.170-179, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185366]
	2	D. Angluin. Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Yale University Department of Computer Science, 1987.
	3	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	4	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
	5	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
	6	Thomas R. Hancock, Learning 2u DNF formulas and ku decision trees, Proceedings of the fourth annual workshop on Computational learning theory, p.199-212, August 05-07, 1991, Santa Cruz, California, United States
	7	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]
	8	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	9	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 [doi>10.1145/48014.63140]
	10	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 19

	Nader H. Bshouty, Simple learning algorithms using divide and conquer, Proceedings of the eighth annual conference on Computational learning theory, p.447-453, July 05-08, 1995, Santa Cruz, California, United States
	Nader H. Bshouty , Zhixiang Chen , Scott E. Decatur , Steven Homer, On the learnability of Zn-DNF formulas (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.198-205, July 05-08, 1995, Santa Cruz, California, United States
	Nader H. Bshouty , Jeffrey C. Jackson, Learning DNF over the uniform distribution using a quantum example oracle, Proceedings of the eighth annual conference on Computational learning theory, p.118-127, July 05-08, 1995, Santa Cruz, California, United States
	Sally A. Goldman , H. David Mathias, Learning k-term DNF formulas with an incomplete membership oracle, Proceedings of the fifth annual workshop on Computational learning theory, p.77-84, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Mihir Bellare, A technique for upper bounding the spectral norm with applications to learning, Proceedings of the fifth annual workshop on Computational learning theory, p.62-70, 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
	Krishnan Pillaipakkamnatt , Vijay Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Proceedings of the seventh annual conference on Computational learning theory, p.118-129, July 12-15, 1994, New Brunswick, New Jersey, United States
	Peter L. Bartlett , Paul Fischer , Klaus-Uwe Höffgen, Exploiting random walks for learning, Proceedings of the seventh annual conference on Computational learning theory, p.318-327, July 12-15, 1994, New Brunswick, New Jersey, United States
	Ulf Berggren, Linear time deterministic learning of k-term DNF, Proceedings of the sixth annual conference on Computational learning theory, p.37-40, July 26-28, 1993, Santa Cruz, California, United States
	Eyal Kushilevitz , Dan Roth, On learning visual concepts and DNF formulae, Proceedings of the sixth annual conference on Computational learning theory, p.317-326, July 26-28, 1993, Santa Cruz, California, United States
	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
	Avrim Blum , Roni Khardon , Eyal Kushilevitz , Leonard Pitt , Dan Roth, On learning Read-k-Satisfy-j DNF, Proceedings of the seventh annual conference on Computational learning theory, p.110-117, July 12-15, 1994, New Brunswick, New Jersey, United States
	Paul W. Goldberg , Sally A. Goldman , H. David Mathias, Learning unions of boxes with membership and equivalence queries, Proceedings of the seventh annual conference on Computational learning theory, p.198-207, July 12-15, 1994, New Brunswick, New Jersey, United States
	Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Proceedings of the sixth annual conference on Computational learning theory, p.41-50, July 26-28, 1993, Santa Cruz, California, United States
	Zhixiang Chen , Steven Homer, On learning counting functions with queries, Proceedings of the seventh annual conference on Computational learning theory, p.218-227, July 12-15, 1994, New Brunswick, New Jersey, United States
	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
	Kazuhisa Makino, Efficient dualization of O(log n)-term monotone disjunctive normal forms, Discrete Applied Mathematics, v.126 n.2-3, p.305-312, 15 March 2003
	Michael Frazier , Sally Goldman , Nina Mishra , Leonard Pitt, Learning from a consistently ignorant teacher, Proceedings of the seventh annual conference on Computational learning theory, p.328-339, July 12-15, 1994, New Brunswick, New Jersey, United States
	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