We first present a brief survey of hardness results for training feedforward neural networks. These results are then completed by the proof that the simplest architecture containing only a single neuron that applies a sigmoidal activation function sigma: kappa --> [alpha, beta], satisfying certain natural axioms (e.g., the standard (logistic) sigmoid or saturated-linear function), to the weighted sum of n inputs is hard to train. In particular, the problem of finding the weights of such a unit that minimize the quadratic training error within (beta - alpha)(2) or its average (over a training set) within 5(beta - alpha)(2)/ (12n) of its infimum proves to be NP-hard. Hence, the well-known backpropagation learning algorithm appears not to be efficient even for one neuron, which has negative consequences in constructive learning.

Institute of Computer Science Academy of Sciences of the Czech Republic PO Box 5 18207 Prague 8 Czech Republic

Citace poskytuje Crossref.org