Learning DNF formulae under classes of probability distributions

ABSTRACT

We show that 2-term DNF formulae are learnable in quadratic time using only a logarithmic number of positive examples if we assume that examples are drawn from a bounded distribution. We also show that k-term DNF formulae are learnable in polynomial time using positive and negative examples drawn from a bounded distribution.

REFERENCES

• 1: D. Angluin, L.G.Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. of Comp. and Syst. Sci., 18, 1979.
• 2: Peter L. Bartlett , Robert C. Williamson, Investigating the distribution assumptions in the Pac learning model, Proceedings of the fourth annual workshop on Computational learning theory, p.24-32, August 05-07, 1991, Santa Cruz, California, United States
• 3: 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
• 4: Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
• 5: 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
• 6: David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 7: Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
• 8: 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]
• 9: M. Kearns , L. G. Valiant, Crytographic limitations on learning Boolean formulae and finite automata, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.433-444, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73049]
• 10: Ludek Kucera , Alberto Marchetti-Spaccamela , Marco Protasi, On learning monotone DNF formulae under uniform distributions, Information and Computation, v.110 n.1, p.84-95, April 1994 [doi>10.1006/inco.1994.1024]
• 11: N.Linial, Y.Mansour, N.Nisan, Constant depth circuits, Fourier transform, and learnability, Proc. 30th IEEE Syrup. on Foundations of Computer Science, 1989.
• 12: 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]
• 13: 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]
• 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.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory, Verification