The computational intractability of training sigmoidal neural networks

被引:24
作者
Jones, LK
机构
[1] Department of Mathematical Sciences, University of Massachusetts, Lowell
基金
美国国家科学基金会;
关键词
neural networks; NP-completeness; interpolation; training; Lipschitzian sigmoid;
D O I
10.1109/18.567673
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We demonstrate that the problem of approximately interpolating a target function by a neural network is computationally intractable, In particular the interpolation training problem for a neural network with two monotone Lipschitzian sigmoidal internal activation functions and one linear output node is shown to be NP-hard and NP-complete if the internal nodes are in addition piecewise ratios of polynomials, This partially answers a question of Blum and Rivest concerning the NP-completeness of training a logistic sigmoidal 3-node network, An extension of the result is then given for networks with n monotone sigmoidal internal nodes and one convex output node, This indicates that many multivariate nonlinear regression problems may be computationally infeasible.
引用
收藏
页码:167 / 173
页数:7
相关论文
共 14 条