Skip to main content
Presentation
On a Learnability Question Associated to Neural Networks with Continuous Activations
Proceedings of the Sixth ACM Workshop on Computational Learning (COLT) (1994)
  • Bhaskar DasGupta
  • Hava Siegelmann, University of Massachusetts - Amherst
  • Eduardo Sontag
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.
Disciplines
Publication Date
July, 1994
Citation Information
Bhaskar DasGupta, Hava Siegelmann and Eduardo Sontag. "On a Learnability Question Associated to Neural Networks with Continuous Activations" Proceedings of the Sixth ACM Workshop on Computational Learning (COLT) (1994)
Available at: http://works.bepress.com/hava_siegelmann/19/