Exact learning of read-k disjoint DNF and not-so-disjoint DNF

ABSTRACT

A polynomial-time algorithm is presented for exactly learning the class of read-k disjoint DNF formulas—boolean formulas in disjunctive normal form where each variable appears at most k) and every assignment to the variables satisfies at most one term of F. The (standard) protocol used allows the learning algorithm to query whether a given assignment of boolean variables satisfies the DNF formula to be learned (membership queries), as well as to obtain counterexamples to the correctness of its current hypothesis which can be any arbitrary DNF formula (equivalence queries). The formula output by the learning algorithm is logically equivalent to the formula to be learned. We show that this result also applies for a generalization of read-k disjoint DNF which we call read-k sat-j DNF; these are DNF formulas in which every variable appears at most k times and every assignment satisfies at most j terms.

REFERENCES

• 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]
• AHP92: H. Aizenstein, L. Hellerstein, and L. Pitt. Read-thice dnf is hard to learn with membership and equivalence queries. Extended abstract, 1992.
• 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]
• Ang89: Dana Angluin, Equivalence queries and approximate fingerprints, Proceedings of the second annual workshop on Computational learning theory, p.134-145, December 1989, Santa Cruz, California, United States
• AP91: 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]
• EH89: A. Ehrenfeucht , D. Haussler , M. Kearns, Learning decision trees from random examples needed for learning, Information and Computation, v.82 n.3, p.231-246, Sep. 1989 [doi>10.1016/0890-5401(89)90001-1]
• 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
• KLPV87: M. Kearns , M. Li , L. Pitt , L. Valiant, On the learnability of Boolean formulae, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.285-295, January 1987, New York, New York, United States [doi>10.1145/28395.28426]
• KM91: Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103466]
• 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Theory, Verification