Training a 3-node neural network is NP-complete

摘要: We show for many simple two-layer networks whose nodes compute linear threshold functions of their inputs that training is NP-complete. For any algorithm one these there will be some sets data on which it performs poorly, either by running more than an amount time polynomial in the input length, or producing sub-optimal weights. Thus, differ fundamentally from perceptron a worst-case computational sense.