Computational Complexity and Pyramidal Architectures
This papers considers computational complexity issues of loading pyramidal networks. Such networks are relevant for the research in the weightless neural models. The loading problem is a formal model for supervised connectionist learning of feedforward networks. It is proved that the loading problem for pyramidal architectures is NPcomplete. That is still shown true in the context of the probably-approximately-correct learning (PAC-learning). These results, together with previous ones, are evidences that there is no efficient algorithm for training deep networks. A positive result shown in this work is that loading a certain restricted kind of pyramidal architecture can be accomplished in polynomial time (in the length of the input patterns). It is important to point out that the characterisation of a polynomial architecture class (a class such that the loading problem is polynomial in time) can be a fundamental guide to neural network design.
Marc(i)lio C. P. de Souto Wilson R. de Oliveira Teresa B. Ludermir
Centre de Informdtica, Univ. Fed. de Pernambuco, Recife, Brazil Depto. de Ffaica e Estatfetica, Univ. Fed. Rural de Pernambuco, Recife, Brazil
国际会议
8th International Conference on Neural Information Processing(ICONIP 2001)(第八届国际神经信息处理大会)
上海
英文
1376-1381
2001-11-14（万方平台首次上网日期，不代表论文的发表时间）