Learning DNF in time

ABSTRACT

Using techniques from learning theory, we show that any s-term DNF over n variables can be computed by a polynomial threshold function of degree O(n^{1/3} \log s). This upper bound matches, up to a logarithmic factor, the longstanding lower bound given by Minsky and Papert in their 1968 book {\em Perceptrons}. As a consequence of this upper bound we obtain the fastest known algorithm for learning polynomial size DNF, one of the central problems in computational learning theory.

REFERENCES

• 1: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 2: James Aspnes , Richard Beigel , Merrick Furst , Steven Rudich, The expressive power of voting polynomials, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.402-409, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103461]
• 3: R. Beigel. The polynomial method in circuit complexity, in "Proc. 8th Conf. on Structure in Complexity Theory" (1993), 82-95.
• 4: R. Beigel, personal communication, 2000.
• 5: R. Beigel, N. Reingold and D. Spielman. The perceptron strikes back, in "Proc. 6th Conf. on Structure in Complexity Theory" (1991), 286-291.
• 6: Avrim Blum, Rank-r decision trees are a subclass of r-decision lists, Information Processing Letters, v.42 n.4, p.183-185, June 19, 1992 [doi>10.1016/0020-0190(92)90237-P]
• 7: A. Blum , A. Frieze, A polynomial-time algorithm for learning noisy linear threshold functions, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.330, October 14-16, 1996
• 8: 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]
• 9: 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]
• 10: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 11: 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]
• 12: Tom Bylander, Worst-case analysis of the perceptron and exponentiated update algorithms, Artificial Intelligence, v.106 n.2, p.335-352, Dec. 1998 [doi>10.1016/S0004-3702(98)00098-8]
• 13: E. W. Cheney. Introduction to approximation theory. McGraw-Hill, 1966.
• 14: E. Cohen, Learning noisy perceptrons by a perceptron in polynomial time, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.514, October 19-22, 1997
• 15: 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]
• 16: 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]
• 17: Yoav Freund, Boosting a weak learning algorithm by majority, Information and Computation, v.121 n.2, p.256-285, Sept. 1995 [doi>10.1006/inco.1995.1136]
• 18: Yoav Freund , Robert E. Schapire, Large margin classification using the perceptron algorithm, Proceedings of the eleventh annual conference on Computational learning theory, p.209-217, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279985]
• 19: B. Fu. Separating PH from PP by relativization. Acta Math. Sinica 8 :3 (1992), 329-336.
• 20: M. Goldmann, J. Hastad and A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity 2 (1992), 277-300.
• 21: 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
• 22: David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning Nested Differences of Intersection-Closed Concept Classes, Machine Learning, v.5 n.2, p.165-196, Jun. 1990 [doi>10.1023/A:1022696716689]
• 23: 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]
• 24: 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]
• 25: Jyrki Kivinen , Manfred K. Warmuth, The perceptron algorithm vs. Winnow: linear vs. logarithmic mistake bounds when few input variables are relevant, Proceedings of the eighth annual conference on Computational learning theory, p.289-296, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225333]
• 26: 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]
• 27: 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]
• 28: N. Linial and N. Nisan. Approximate inclusion-exclusion. Combinatorica 10 :4 (1990), 349-365.
• 29: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 30: S. Lokam, personal communication (2001).
• 31: Wolfgang Maass , György Turán, How fast can a threshold gate learn?, Proceedings of a workshop on Computational learning theory and natural learning systems (vol. 1) : constraints and prospects: constraints and prospects, p.381-414, August 1994, Princeton, New Jersey, United States
• 32: Marvin Minsky , Seymour Papert, Perceptrons, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 33: Y. Sakai and A. Maruoka. Learning monotone log-term DNF formulas under the uniform distribution. Theory Comput. Systems 33 (2000), 17-33.
• 34: Michael Schmitt, Identification criteria and lower bounds for perceptron-like learning rules, Neural Computation, v.10 n.1, p.235-250, Jan. 1, 1998 [doi>10.1162/089976698300017962]
• 35: Rocco A. Servedio, On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm, Proceedings of the twelfth annual conference on Computational learning theory, p.296-307, July 07-09, 1999, Santa Cruz, California, United States [doi>10.1145/307400.307474]
• 36: 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
• 37: 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]
• 38: 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
• 39: Karsten A. Verbeurgt, Learning Sub-classes of Monotone DNF on the Uniform Distribution, Proceedings of the 9th International Conference on Algorithmic Learning Theory, p.385-399, October 08-10, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Algorithms, Performance, Theory, Verification