On learning Read-k-Satisfy-j DNF

ABSTRACT

We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k•j=O(logn/loglogn). Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size > 2^Wn . Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

REFERENCES

• AFP92: Dana Angluin , Michael Frazier , Leonard Pitt, Learning Conjunctions of Horn Clauses, Machine Learning, v.9 n.2-3, p.147-164, July 1992 [doi>10.1007/BF00992675]
• Aiz93: Howard Jay Aizenstein, On the learnability of disjunctive normal form formulas and decision trees, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 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]
• Ang88: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 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]
• AP92: Howard Aizenstein , Leonard Pitt, Exact learning of read-k disjoint DNF and not-so-disjoint DNF, Proceedings of the fifth annual workshop on Computational learning theory, p.71-76, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130393]
• AP93: H. Aizenstein and L. Pitt. DNF cannot be learned by greedily collecting prime implicants. Unpublished, 1993.
• 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]
• 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]
• Bsh93: N.H. Bshouty. Exact learning via the monotone theory. In Proceedings of the IEEE Syrup. on Foundation of Computer Science, pages 302-311, Palo Alto, CA., 1993.
• 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
• Kha94: Roni Khardon, On using the Fourier transform to learn Disjoint DNF, Information Processing Letters, v.49 n.5, p.219-222, March 11, 1994 [doi>10.1016/0020-0190(94)90057-4]
• 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]
• KR93: 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 [doi>10.1145/168304.168362]
• Mat93: S. Matar. Learning with minimal number of queries. Master's thesis, University of Albert, Canada, 1993.
• PR93: Krishnan Pillaipakkamnatt , Vijay Raghavan, Read-twice DNF formulas are properly learnable, Proceedings of the first European conference on Computational learning theory, p.121-132, October 1994, Royal Holloway, Univ. of London, United Kingdom
• Sim83: Hans-Ulrich Simon, A Tight Omega(loglog n)-Bound on the Time for Parallel Ram's to Compute Nondegenerated Boolean Functions, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.439-444, August 21-27, 1983
• 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:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification