Exact learning of random DNF over the uniform distribution

ABSTRACT

We show that randomly generated c log(n)-DNF formula can be learned exactly in probabilistic polynomial time using randomly generated examples. Our notion of randomly generated is with respect to a uniform distribution.

To prove this we extend the concept of well behaved c log(n)-Monotone DNF formulae to c log(n)-DNF formulae, and show that almost every DNF formula is well-behaved, and that there exists a probabilistic polynomial time algorithm that exactly learns all well behaved c log(n)-DNF formula. This is the first algorithm that properly learns (non-monotone) DNF with a polynomial number of terms from random examples alone.

REFERENCES

• 1: Howard Aizenstein , Leonard Pitt, On the Learnability of Disjunctive Normal Form Formulas, Machine Learning, v.19 n.3, p.183-208, June 1995 [doi>10.1023/A:1022697326858]
• 2: Misha Alekhnovich , Mark Braverman , Vitaly Feldman , Adam R. Klivans , Toniann Pitassi, The complexity of properly learning simple concept classes, Journal of Computer and System Sciences, v.74 n.1, p.16-34, February, 2008 [doi>10.1016/j.jcss.2007.04.011]
• 3: 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]
• 4: Uriel Feige , Joe Kilian, Zero Knowledge and the Chromatic Number, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.278, May 24-27, 1996
• 5: Vitaly Feldman, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132569]
• 6: Thomas Hancock , Yishay Mansour, Learning monotone ku DNF formulas on product distributions, Proceedings of the fourth annual workshop on Computational learning theory, p.179-183, August 05-07, 1991, Santa Cruz, California, United States
• 7: J. C. Jackson and R. A. Servedio. On learning random dnf formulas under the uniform distribution. In C. Chekuri, K. Jansen, J. D. P. Rolim, and L. Trevisan, editors, APPROX--RANDOM, volume 3624 of Lecture Notes in Computer Science, pages 342--353. Springer, 2005.
• 8: S. Kutin. Extensions to mcdiarmid's inequality when dierences are bounded with high probability. Technical Report TR-2002-04, Department of Computer Science, University of Chicago, 2002.
• 9: C. McDiarmid. On the method of bounded dierences. Surveys in Combinatorics, pages 148--188, 1989.
• 10: 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]
• 11: 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]
• 12: L. Sellie. Learning random monotone dnf under the uniform distribution. In R. A. Servedio and T. Zhang, editors, COLT, pages 181--192. Omnipress, 2008.
• 13: L. G. Valiant, A theory of the learnable, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.436-445, December 1984 [doi>10.1145/800057.808710]
• 14: Karsten Verbeurgt, Learning DNF under the uniform distribution in quasi-polynomial time, Proceedings of the third annual workshop on Computational learning theory, p.314-326, August 06-08, 1990, Rochester, New York, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
DNF, learning theory