Exact learning of DNF formulas using DNF hypotheses

ABSTRACT

(MATH) We show the following: <ol>

For any &egr; ρ 0, (log n)^{(3 + &egr;)}-term DNF cannot be polynomial-query learned with membership and strongly proper equivalence queries.

For any function f(n) &egr; o [box] (&frac;^√n \over _{log n}) [end-box] , m-term DNF formulas cannot be polynomial-query learned by a membership and equivalence query algorithm that uses m &dotfill; f(n)-term DNF formulas as hypotheses.

Read-thrice DNF formulas are not learnable with membership and proper equivalence queries.

log n-term DNF formulas can be polynomial-query learned with membership and proper equivalence queries. (This complements a result of Bshouty, Goldman, Hancock, and Matar stating that [box] √log n [end-box] -term DNF can be so learned in polynomial time.

</ol>.Using purely information theoretic techniques, these results extend and improve what is currently known. (For example, a weaker version of (a) was known only under a barely plausible complexity theoretic assumption, (b) was previously unknown, and (c) was known under the assumption P ‡ NP.)

REFERENCES

• 1: Howard Aizenstein , Tibor Hegedűs , Lisa Hellerstein , Leonard Pitt, Complexity theoretic hardness results for query learning, Computational Complexity, v.7 n.1, p.19-53, Jul. 1998 [doi>10.1007/PL00001593]
• 2: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 3: Dana Angluin , Michael Kharitonov, When won't membership queries help?, Journal of Computer and System Sciences, v.50 n.2, p.336-355, April 1995
• 4: José L. Balcázar , Jorge Castro , David Guijarro, Abstract Combinatorial Characterizations of Exact Learning via Queries, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.248-254, June 28-July 01, 2000
• 5: A. Beimel, On the applications of multiplicity automata in learning, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.349, October 14-16, 1996
• 6: José L. Balcázar , Jorge Castro , David Guijarro, A General Dimension for Exact Learning, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.354-367, July 16-19, 2001
• 7: 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 [doi>10.1145/168304.168309]
• 8: Avrim L. Blum, Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain, SIAM Journal on Computing, v.23 n.5, p.990-1000, Oct. 1994 [doi>10.1137/S009753979223455X]
• 9: 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]
• 10: Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Journal of Computer and System Sciences, v.51 n.3, p.367-373, Dec. 1995 [doi>10.1006/jcss.1995.1075]
• 11: N. H. Bshouty. Simple learning algorithms using divide and conquer. Information Processing Letters.
• 12: Nader H. Bshouty, Exact learning Boolean functions via the monotone theory, Information and Computation, v.123 n.1, p.146-153, Nov. 15, 1995 [doi>10.1006/inco.1995.1164]
• 13: Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Journal of Computer and System Sciences, v.52 n.2, p.268-286, April 1996 [doi>10.1006/jcss.1996.0021]
• 14: Nader H. Bshouty, A subexponential exact learning algorithm for DNF using equivalence queries, Information Processing Letters, v.59 n.1, p.37-39, July 8, 1996 [doi>10.1016/0020-0190(96)00077-4]
• 15: A. Chandra and G. Markowsky. On the number of prime implicants. Discrete (MATH)ematics, 24:7--11, 1978.
• 16: Tibor Hegedűs, Generalized teaching dimensions and the query complexity of learning, Proceedings of the eighth annual conference on Computational learning theory, p.108-117, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225311]
• 17: Lisa Hellerstein , Krishnan Pillaipakkamnatt , Vijay Raghavan , Dawn Wilkins, How many queries are needed to learn?, Journal of the ACM (JACM), v.43 n.5, p.840-862, Sept. 1996 [doi>10.1145/234752.234755]
• 18: Jeffrey C. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, Journal of Computer and System Sciences, v.55 n.3, p.414-440, Dec. 1997 [doi>10.1006/jcss.1997.1533]
• 19: Adam R. Klivans , Rocco Servedio, Learning DNF in time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.258-265, July 2001, Hersonissos, Greece [doi>10.1145/380752.380809]
• 20: Johannes Köbler , Wolfgang Lindner, Oracles in Sigmap2 are Sufficient for Exact Learning, Proceedings of the 8th International Conference on Algorithmic Learning Theory, p.277-290, October 06-08, 1997
• 21: Eyal Kushilevitz, A simple algorithm for learning O (log n)-term DNF, Information Processing Letters, v.61 n.6, p.289-292, March 28, 1997 [doi>10.1016/S0020-0190(97)00026-4]
• 22: Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993 [doi>10.1145/174130.174138]
• 23: W. J. Masek. Some NP-complete set covering problems. Unpublished manuscript, 1979.
• 24: David E. Muller , Franco P. Preparata, Bounds to Complexities of Networks for Sorting and for Switching, Journal of the ACM (JACM), v.22 n.2, p.195-201, April 1975 [doi>10.1145/321879.321882]
• 25: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 26: Krishnan Pillaipakkamnatt , Vijay Raghavan, On the limits of proper learnability of subclasses of DNF formulas, Machine Learning, v.25 n.2-3, p.237-263, Nov./Dec. 1996 [doi>10.1007/BF00114011]
• 27: Jun Tarui , Tatsuie Tsukiji, Learning DNF by Approximating Inclusion-Exclusion Formulae, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.215, May 04-06, 1999
• 28: Christopher Umans, The Minimum Equivalent DNF Problem and Shortest Implicants, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.556, November 08-11, 1998
• 29: Christopher Umans, Hardness of Approximating Minimization Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.465, October 17-18, 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Theory

Keywords:
DNF, algorithms, certificates, complexity theory, computational learning theory, disjunctive normal form, representations of boolean functions