On the complexity of loading shallow neural networks (Q1105389)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexity of loading shallow neural networks |
scientific article |
Statements
On the complexity of loading shallow neural networks (English)
0 references
1988
0 references
We formalize a notion of loading information into connectionist networks that characterizes the training of feed-forward neural networks. This problem is NP-complete, 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 SCI graph is a tree or if 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 SCI graph is a simple 2-dimensional planar grid.
0 references
support cone interaction graph
0 references
loading
0 references
connectionist networks
0 references
neural networks
0 references
NP-complete
0 references
shallow networks
0 references