dc.contributor.author | Lin, Jyh-Han | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-21T19:04:59Z | |
dc.date.available | 2011-03-21T19:04:59Z | |
dc.date.issued | 1991 | |
dc.identifier.citation | J.-H. Lin and J. S. Vitter. “Complexity Results on Learning by Neural Nets,” Machine Learning, 6, 1991, 211–230. An extended abstract appears in Proceedings of the 2nd Annual ACM Workshop on Computational Learning Theory (COLT ’89), Santa Cruz, CA, July–August 1989, published by Morgan Kaufmann, San Mateo, CA, 118–133. http://dx.doi.org/10.1023/A:1022657626762 | |
dc.identifier.uri | http://hdl.handle.net/1808/7214 | |
dc.description.abstract | We consider the computational complexity of learning by neural nets. We are inter-
ested in how hard it is to design appropriate neural net architectures and to train
neural nets for general and specialized learning tasks. Our main result shows that
the training problem for 2-cascade neural nets (which have only two non-input nodes,
one of which is hidden) is NP-complete, which implies that nding an optimal net
(in terms of the number of non-input units) that is consistent with a set of exam-
ples is also NP-complete. This result also demonstrates a surprising gap between the
computational complexities of one-node (perceptron) and two-node neural net training
problems, since the perceptron training problem can be solved in polynomial time by
linear programming techniques. We conjecture that training a k-cascade neural net,
which is a classical threshold network training problem, is also NP-complete, for each
xed k 2. We also show that the problem of nding an optimal perceptron (in
terms of the number of non-zero weights) consistent with a set of training examples is
NP-hard.
Our neural net learning model encapsulates the idea of modular neural nets, which
is a popular approach to overcoming the scaling problem in training neural nets. We
investigate how much easier the training problem becomes if the class of concepts to
be learned is known a priori and the net architecture is allowed to be su ciently
non-optimal. Finally, we classify several neural net optimization problems within the
polynomial-time hierarchy. | |
dc.language.iso | en_US | |
dc.publisher | Springer Verlag | |
dc.title | Complexity Results on Learning by Neural Nets | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1023/A:1022657626762 | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |