Learning juntas

ABSTRACT

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples which runs in time roughly (n^k)^{ω/(ω + 1)}, where ω < 2.376 is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive n^k time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.

REFERENCES

• 1: Nader H. Bshouty , Vitaly Feldman, On using extended statistical queries to avoid membership queries, The Journal of Machine Learning Research, 2, p.359-395, 3/1/2002 [doi>10.1162/153244302760200669]
• 2: A. Bernasconi. On a hierarchy of boolean functions hard to compute in constant depth. Discrete Mathematics & Theoretical Computer Science, 4:2:79--90, 2001.
• 3: A. Blum. Relevant examples and relevant features: Thoughts from computational learning theory. In AAAI Fall Symposium on `Relevance', 1994.
• 4: Avrim L. Blum , Pat Langley, Selection of relevant features and examples in machine learning, Artificial Intelligence, v.97 n.1-2, p.245-271, Dec. 1997 [doi>10.1016/S0004-3702(97)00063-5]
• 5: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 6: Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, More efficient PAC-learning of DNF with membership queries under the uniform distribution, Proceedings of the twelfth annual conference on Computational learning theory, p.286-295, July 07-09, 1999, Santa Cruz, California, United States [doi>10.1145/307400.307472]
• 7: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 8: Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky, Testing Juntas, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.103-112, November 16-19, 2002
• 9: David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992 [doi>10.1137/0221019]
• 10: 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]
• 11: Jeffrey C. Jackson , Adam R. Klivans , Rocco A. Servedio, Learnability beyond AC⁰, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510018]
• 12: A. Kalai and Y. Mansour. Personal communication., 2001.
• 13: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM (JACM), v.45 n.6, p.983-1006, Nov. 1998 [doi>10.1145/293347.293351]
• 14: 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]
• 15: 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]
• 16: Y. Mansour. Learning Boolean functions via the Fourier transform, pages 391--424. 1994.
• 17: Yishay Mansour, An O(nlog log n) learning algorithm for DNF under the uniform distribution, Journal of Computer and System Sciences, v.50 n.3, p.543-550, June 1995 [doi>10.1006/jcss.1995.1043]
• 18: Y. Mansour. Personal communication., 2001.
• 19: 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]
• 20: 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
• 21: 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
• 22: J. von zur Gathen and J. Roche. Polynomials with two values. Combinatorica, 17(3):345--362, 1997.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
fourier, juntas, learning, relevant variables, uniform distribution