| On a Learnability Question Associated to Neural Networks with Continuous Activations (Extended Abstract) z (2008) | |||||||||||||||
Abstract | |||||||||||||||
| This paper deals with learnability of concept classes de ned 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 isknown 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. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||