On the complexity of loading shallow neural networks

✍ Scribed by Stephen Judd

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 898 KB
• Volume: 4
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/0885-064x(88)90019-2

✦ Synopsis

We formalize a notion of loading information into connectionist networks that characterizes the training of feed-forward neural networks. This problem is NPcomplete, so we look for tractable subcases of the problem by placing constraints on the network architecture. The focus of these constraints is on various families of "shallow" architectures which are defined to have bounded depth and unbounded width. We introduce a perspective on shallow networks, called the Support Cone Interaction (SCI) graph, which is helpful in distinguishing tractable from intractable subcases: When the SC1 graph is a tree or is of limited bandwidth, loading can be accomplished in polynomial time; when its bandwidth is not limited we find the problem NP-complete even if the SC1 graph is a simple 2-dimensional planar grid. 0 1988 Academic PRSS. ITIC.