On a learnability question associated to neural networks with continuous activations (extended abstract)

ABSTRACT

This paper deals with learnability of concept classes defined by neural networks, showing the hardness of PAC-learning (in the complexity, not merely information-theoretic sense) for networks with a particular class of activation. The obstruction lies not with the VC dimension, which is known to grow slowly; instead, the result follows the fact that the loading problem is NP-complete. (The complexity scales badly with input dimension; the loading problem is polynomial-time if the input dimension is constant.) Similar and well-known theorems had already been proved by Megiddo and by Blum and Rivest, for binary-threshold networks. It turns out the general problem for continuous sigmoidal-type functions, as used in practical applications involving steepest descent, is not NP-hard—there are “sigmoidals” for which the problem is in fact trivial—so it is an open question to determine what properties of the activation function cause difficulties. Ours is the first result on the hardness of loading networks which do not consist of binary neurons; we employ a piecewise-linear activation function that has been used in the neural network literature. Our theoretical results lend further justification to the use of incremental (architecture-changing) techniques for training networks.

REFERENCES

• 1: Albertini, F., E.D. Sontag, and V. Maillot, "Uniqueness of weights for neural networks," in Artificial Neural Networks for Speech and Vision (R. Mammone, ed.), Chapman and Hall, London, 1993, pp. 115-125.
• 2: A. R. Barron, Approximation and estimation bounds for artificial neural networks, Proceedings of the fourth annual workshop on Computational learning theory, p.243-249, August 05-07, 1991, Santa Cruz, California, United States
• 3: Batruni, R., "A multilayer neural network with piecewise-linear structure and back-propagation learning," IEEE Transactions on Neural Networks 2(1991): 395-403.
• 4: Eric B. Baum , David Haussler, What size net gives valid generalization?, Neural Computation, v.1 n.1, p.151-160, Spring 1990 [doi>10.1162/neco.1989.1.1.151]
• 5: Avrim L. Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Neural Networks, v.5 n.1, p.117-127, 1992 [doi>10.1016/S0893-6080(05)80010-3]
• 6: Brown, J., M. Garber, and S. Vanable, "Artificial neural network on a SIMD architecture," in Proc. 2nd Symposium on the Frontier of Massively Parallel Computation, Fairfax, VA, 1988, pp. 43-47.
• 7: Christian Darken , Michael Donahue , Leonid Gurvits , Eduardo Sontag, Rate of approximation results motivated by robust neural network learning, Proceedings of the sixth annual conference on Computational learning theory, p.303-309, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168357]
• 8: Bhaskar Das Gupta , Georg Schnitger, The Power of Approximation: A Comparison of Activation Functions, Advances in Neural Information Processing Systems 5, [NIPS Conference], p.615-622, November 30-December 03, 1992
• 9: DasGupta, B., Siegelmann, H. T., and Sontag, E., "On the Complexity of Training Neural Networks with Continuous Activation Functions", Tech Report 4~ 93-61, Department of Computer Science, University of Minnesota, September, 1993.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Paul Goldberg , Mark Jerrum, Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers, Proceedings of the sixth annual conference on Computational learning theory, p.361-369, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168377]
• 12: Klaus-Uwe Höffgen, Computational limitations on training sigmoid neural networks, Information Processing Letters, v.46 n.6, p.269-274, July 26, 1993 [doi>10.1016/0020-0190(93)90064-G]
• 13: Jones, K.L., "A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training," Annals of Statistics, 20(1992): 608-613.
• 14: Stephen Judd, On the complexity of loading shallow neural networks, Journal of Complexity, v.4 n.3, p.177-192, Sept. 1988 [doi>10.1016/0885-064X(88)90019-2]
• 15: J. Stephen Judd, Neural network design and the complexity of learning, MIT Press, Cambridge, MA, 1990
• 16: 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]
• 17: Jyh-Han Lin , Jeffrey Scott Vitter, Complexity Results on Learning by Neural Nets, Machine Learning, v.6 n.3, p.211-230, May 1991 [doi>10.1023/A:1022657626762]
• 18: Lippmann, R., "An introduction to computing with neural nets," IEEE Acoustics, Speech, and Signal Processing Magazine, 1987, pp. 4-22.
• 19: Angus Macintyre , Eduardo D. Sontag, Finiteness results for sigmoidal “neural” networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.325-334, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167192]
• 20: Wolfgang Maass, Bounds for the computational power and learning complexity of analog neural nets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.335-344, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167193]
• 21: Megiddo, M., "On the complexity of polyhedral separability," Discrete Computational Geometry, 3(1988): 325-337.
• 22: Muroga, S., Threshold Logic and its Applications, John Wiley & Sons Inc., 1971.
• 23: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 24: Eduardo D. Sontag, Feedforward nets for interpolation and classification, Journal of Computer and System Sciences, v.45 n.1, p.20-48, Aug. 1992 [doi>10.1016/0022-0000(92)90039-L]
• 25: Sontag, E.D. and H.J. Sussmann, "Backpropagation can give rise to spurious local minima even for networks without hidden layers," Complex Systems 3(1989): 91-106.
• 26: Héctor J. Sussmann, Uniqueness of the weights for minimal feedforward nets with a given input-output map, Neural Networks, v.5 n.4, p.589-593, July-Aug. 1992 [doi>10.1016/S0893-6080(05)80037-1]
• 27: Bo Zhang , Ling Zhang , Huai Zhang, A quantitative analysis of the behaviors of the PLN network, Neural Networks, v.5 n.4, p.639-644, July-Aug. 1992 [doi>10.1016/S0893-6080(05)80041-3]
• 28: Zhang, X-D., "Complexity of neural network learning in the real number model," preprint, Comp. Sci. Dept., U. Mass., 1992.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Theory, Verification