An O(nlog log n) learning algorithm for DNF under the uniform distribution

ABSTRACT

We show that a DNF with terms of size at most d can be approximated by a function with at most dO(d log 1/&egr;))non zero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most &egr;. This property is used to derive a learning algorithm for DNF, under the uniform distribution. The learning algorithm uses queries and learns, with respect to the uniform distribution, a DNF with terms of size at most d in time polynomial in n and dO(d log 1/egr;). The interesting implications are for the case when &egr; is constant. In this case our algorithm learns a DNF with a polynomial number of terms in time nO(log log n), and a DNF with terms of size at most O(log n/log log n) in polynomial time.

REFERENCES

• Ajt83: M. Ajtai.~'}l-formulae on finite structure. Annals o/Pure and Applied Logic, 24:1- 48, 1983.
• 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]
• AM91: William Aiello , Milena Mihail, Learning the Fourier spectrum of probabilistic lists and trees, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 28-30, 1991, San Francisco, California, United States
• 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]
• FSS84: M. Furst, J. Saxe, and M. 8ipser. Parity, circuits, and the polynomial time hierarchy. Mathematical Systems Theory, 17:13- 27, 1984.
• GL89: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 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
• Has86: Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
• HM91: 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
• KLPV87: 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]
• KM91: Eyal Kushilevitz , Yishay Mansour, Learning decision trees using the Fourier spectrum, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.455-464, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103466]
• LMN89: Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. In Proceedings o.f the Thirtieth Annual Symposium on Foundations o.f Computer Science, pages 574-579, Research Triangle Park, North Carolin~, October 1989.
• LV91: Michael Luby , Boban Veličkovic, On deterministic approximation of DNF, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.430-438, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103464]
• PV88: 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]
• 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]
• Ver90: 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
• Yao85: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing

General Terms:
Theory, Verification