Learnability beyond AC0

ABSTRACT

We give an algorithm to learn constant-depth polynomial-size circuits augmented with majority gates under the uniform distribution using random examples only. For circuits which contain a polylogarithmic number of majority gates the algorithm runs in quasipolynomial time. This is the first algorithm for learning a more expressive circuit class than the class AC⁰ of constant-depth polynomial-size circuits, a class which was shown to be learnable in quasipolynomial time by Linial, Mansour and Nisan in 1989. Our approach combines an extension of some of the Fourier analysis from Linial et al. with hypothesis boosting. We also show that under a standard cryptographic assumption our algorithm is essentially optimal with respect to both running time and expressiveness (number of majority gates) of the circuits being learned.

REFERENCES

• 1: J. Aspnes, R. Beigel, M. Furst, and S. Rudich. The expressive power of voting polynomials. Combinatorica, 14(2):1--14, 1994.
• 2: Eric B. Baum, A polynomial time algorithm that learns two hidden unit nets, Neural Computation, v.2 n.4, p.510-522, Winter 1990 [doi>10.1162/neco.1990.2.4.510]
• 3: Richard Beigel, When do extra majority gates help?: polylog(N) majority gates are equivalent to one, Computational Complexity, v.4 n.4, p.314-324, Oct. 1994 [doi>10.1007/BF01263420]
• 4: Richard Beigel , Nick Reingold , Daniel Spielman, PP is closed under intersection, Journal of Computer and System Sciences, v.50 n.2, p.191-202, April 1995
• 5: 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]
• 6: A. Blum, A. Frieze, R. Kannan, and S. Vempala. A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica, 22(1/2):35--52, 1997.
• 7: 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]
• 8: J. Bruck. Harmonic analysis of polynomial threshold functions. SIAM Journal on Discrete (MATH)ematics, 3(2):168--177, 1990.
• 9: 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]
• 10: Nader H. Bshouty , Dmitry Gavinsky, On Boosting with Optimal Poly-Bounded Distributions, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.490-506, July 16-19, 2001
• 11: Nader H. Bshouty , Christino Tamon, On the Fourier spectrum of monotone functions, Journal of the ACM (JACM), v.43 n.4, p.747-770, July 1996 [doi>10.1145/234533.234564]
• 12: Carlos Domingo , Osamu Watanabe, MadaBoost: A Modification of AdaBoost, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.180-189, June 28-July 01, 2000
• 13: 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]
• 14: Yoav Freund, Boosting a weak learning algorithm by majority, Proceedings of the third annual workshop on Computational learning theory, p.202-216, August 06-08, 1990, Rochester, New York, United States
• 15: András Hajnal , Wolfgang Maass , Pavel Pudlák , György Turán , Márió Szegedy, Threshold circuits of bounded depth, Journal of Computer and System Sciences, v.46 n.2, p.129-154, April 1993 [doi>10.1016/0022-0000(93)90001-D]
• 16: Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
• 17: 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]
• 18: Michael Kearns , Ming Li , Leslie Valiant, Learning Boolean formulas, Journal of the ACM (JACM), v.41 n.6, p.1298-1328, Nov. 1994 [doi>10.1145/195613.195656]
• 19: Michael Kharitonov, Cryptographic hardness of distribution-specific learning, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.372-381, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167197]
• 20: Adam R. Klivans , Rocco A. Servedio, Boosting and Hard-Core Sets, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.624, October 17-18, 1999
• 21: Adam R. Klivans , Rocco Servedio, Learning DNF in time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.258-265, July 2001, Hersonissos, Greece [doi>10.1145/380752.380809]
• 22: Matthias Krause , Pavel Pudlák, On the computational power of depth 2 circuits with threshold and modulo gates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.48-57, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195103]
• 23: 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]
• 24: F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correcting Codes. North-Holland, New York, 1977.
• 25: M. Naor , O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.458, October 19-22, 1997
• 26: Rocco Anthony Servedio , Leslie Valiant, Efficient algorithms in computational learning theory, 2001
• 27: 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
• 28: 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]
• 29: Santosh Vempala, A Random Sampling based Algorithm for Learning the Intersection of Half-spaces, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.508, October 19-22, 1997
• 30: Z. L. Zhang. Complexity of symmetric functions in perceptron-like models. Master's thesis, University of Massachusetts at Amherst, 1992.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

General Terms:
Algorithms, Experimentation, Performance, Theory