Learning k-term DNF formulas with an incomplete membership oracle

ABSTRACT

We consider the problem of learning k-term DNF formulas using equivalence queries and incomplete membership queries as defined by Angluin and Slonim. We demonstrate that this model can be applied to non-monotone classes. Namely, we describe a polynomial-time algorithm that constructs a k-term DNF formula representationally equivalent to the target using incomplete membership queries and equivalence queries from the class of DNF formulas.

REFERENCES

• AP90: 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]
• AHP92: L. Hellerstein, H. Aizenstein, and L. Pitt. Read-thrice dnf is hard to learn with membership and equivalence queries. Unpublished Manuscript, 1992.
• Ang87a: D. Angluin. Learning k-term DNF formulas using queries and counterexamples. Technical Report YALEU/DCS/RR-559, Yale University, August 1987.
• Ang87b: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• Ang88: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• Ang90: Dana Angluin, Negative Results for Equivalence Queries, Machine Learning, v.5 n.2, p.121-150, Jun. 1990 [doi>10.1023/A:1022692615781]
• AFP90: D. Angluin, M. Frazier, and L. Pitt. Learning conjunctions of horn clauses. In Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science, pages 186-192, October 1990.
• AHK89: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning Read-Once Formulas with Queries, University of California at Berkeley, Berkeley, CA, 1989
• AK91: 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]
• AS91: Dana Angluin , Donna K. Slonim, Learning monotone DNF with an incomplete membership oracle, Proceedings of the fourth annual workshop on Computational learning theory, p.139-146, August 05-07, 1991, Santa Cruz, California, United States
• Blu92: A. Blum. Personal Communication.
• 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
• GKS90: S. Goldman, M. Kearns, and R. Schapire. Exact identification of circuits using fixed points of amplification functions. In Proceedings of the Thirty First Annual Symposium on Foundations of Computer Science, pages 193-202, October 1990.
• Han91: 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
• HH91: Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
• PV88: 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]
• Sak90: Yasubumi Sakakibara, On learning from queries and counterexamples in the presence of noise, Information Processing Letters, v.37 n.5, p.279-284, March 14, 1991 [doi>10.1016/0020-0190(91)90220-C]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Theory, Verification