Complexity results on learning by neural nets View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1991-05

AUTHORS

Jyh-Han Lin, Jeffrey Scott Vitter

ABSTRACT

We consider the computational complexity of learning by neural nets. We are interested 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 N℘-complete, which implies that finding an optimal net (in terms of the number of non-input units) that is consistent with a set of examples is also N℘-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 N℘-complete, for each fixed k≥2. We also show that the problem of finding an optimal perceptron (in terms of the number of non-zero weights) consistent with a set of training examples is N℘-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 sufficiently non-optimal. Finally, we classify several neural net optimization problems within the polynomial-time hierarchy. More... »

PAGES

211-230

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf00114777

DOI

http://dx.doi.org/10.1007/bf00114777

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1037888244


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912-1910, Providence, RI"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Jyh-Han", 
        "id": "sg:person.014122301406.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014122301406.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912-1910, Providence, RI"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/76359.76371", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004063675"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(88)90002-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006302975"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(88)90002-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006302975"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1162/neco.1989.1.1.39", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011040689"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0885-064x(88)90019-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025324848"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1968.1972", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038881641"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(76)90062-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039975132"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(89)90049-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040179661"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0004-3702(89)90049-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040179661"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/800125.804029", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047409927"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(76)90061-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048647089"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1162/neco.1989.1.1.151", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053187839"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.21236/ada164453", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091744995"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1991-05", 
    "datePublishedReg": "1991-05-01", 
    "description": "We consider the computational complexity of learning by neural nets. We are interested 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 N\u2118-complete, which implies that finding an optimal net (in terms of the number of non-input units) that is consistent with a set of examples is also N\u2118-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 N\u2118-complete, for each fixed k\u22652. We also show that the problem of finding an optimal perceptron (in terms of the number of non-zero weights) consistent with a set of training examples is N\u2118-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 sufficiently non-optimal. Finally, we classify several neural net optimization problems within the polynomial-time hierarchy.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf00114777", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1125588", 
        "issn": [
          "0885-6125", 
          "1573-0565"
        ], 
        "name": "Machine Learning", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "6"
      }
    ], 
    "name": "Complexity results on learning by neural nets", 
    "pagination": "211-230", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00114777"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b47cde7a1fbdd49a7739c168740dfec0f8fc65214f211863f97f29d6ca4129b2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037888244"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00114777", 
      "https://app.dimensions.ai/details/publication/pub.1037888244"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-15T08:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000374_0000000374/records_119727_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF00114777"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf00114777'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf00114777'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00114777'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00114777'


 

This table displays all metadata directly associated to this object as RDF triples.

101 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00114777 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nced74869c34e415b9332585757105bbe
4 schema:citation https://doi.org/10.1016/0004-3702(88)90002-1
5 https://doi.org/10.1016/0004-3702(89)90049-0
6 https://doi.org/10.1016/0304-3975(76)90061-x
7 https://doi.org/10.1016/0304-3975(76)90062-1
8 https://doi.org/10.1016/0885-064x(88)90019-2
9 https://doi.org/10.1145/1968.1972
10 https://doi.org/10.1145/76359.76371
11 https://doi.org/10.1145/800125.804029
12 https://doi.org/10.1162/neco.1989.1.1.151
13 https://doi.org/10.1162/neco.1989.1.1.39
14 https://doi.org/10.21236/ada164453
15 schema:datePublished 1991-05
16 schema:datePublishedReg 1991-05-01
17 schema:description We consider the computational complexity of learning by neural nets. We are interested 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 N℘-complete, which implies that finding an optimal net (in terms of the number of non-input units) that is consistent with a set of examples is also N℘-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 N℘-complete, for each fixed k≥2. We also show that the problem of finding an optimal perceptron (in terms of the number of non-zero weights) consistent with a set of training examples is N℘-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 sufficiently non-optimal. Finally, we classify several neural net optimization problems within the polynomial-time hierarchy.
18 schema:genre research_article
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf N736e2ff93a8c41a28f667112a93da220
22 Nfab22a5126d54e96a5a8342f30ae8826
23 sg:journal.1125588
24 schema:name Complexity results on learning by neural nets
25 schema:pagination 211-230
26 schema:productId N6755c4b79c0f46ad840c616e36d6b843
27 N67905a96674f4204acd25e388f70374e
28 Naa964813b71d4cdba8cd7c7c98075e26
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037888244
30 https://doi.org/10.1007/bf00114777
31 schema:sdDatePublished 2019-04-15T08:50
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N377e8f7e9c644aee9cb73870370cc6a8
34 schema:url http://link.springer.com/10.1007/BF00114777
35 sgo:license sg:explorer/license/
36 sgo:sdDataset articles
37 rdf:type schema:ScholarlyArticle
38 N377e8f7e9c644aee9cb73870370cc6a8 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N6755c4b79c0f46ad840c616e36d6b843 schema:name readcube_id
41 schema:value b47cde7a1fbdd49a7739c168740dfec0f8fc65214f211863f97f29d6ca4129b2
42 rdf:type schema:PropertyValue
43 N67905a96674f4204acd25e388f70374e schema:name dimensions_id
44 schema:value pub.1037888244
45 rdf:type schema:PropertyValue
46 N736e2ff93a8c41a28f667112a93da220 schema:volumeNumber 6
47 rdf:type schema:PublicationVolume
48 N7747dc7692a14f878283f6bfe60b4aa8 rdf:first sg:person.0613677314.28
49 rdf:rest rdf:nil
50 Naa964813b71d4cdba8cd7c7c98075e26 schema:name doi
51 schema:value 10.1007/bf00114777
52 rdf:type schema:PropertyValue
53 Nced74869c34e415b9332585757105bbe rdf:first sg:person.014122301406.31
54 rdf:rest N7747dc7692a14f878283f6bfe60b4aa8
55 Nfab22a5126d54e96a5a8342f30ae8826 schema:issueNumber 3
56 rdf:type schema:PublicationIssue
57 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
58 schema:name Information and Computing Sciences
59 rdf:type schema:DefinedTerm
60 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
61 schema:name Computation Theory and Mathematics
62 rdf:type schema:DefinedTerm
63 sg:journal.1125588 schema:issn 0885-6125
64 1573-0565
65 schema:name Machine Learning
66 rdf:type schema:Periodical
67 sg:person.014122301406.31 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
68 schema:familyName Lin
69 schema:givenName Jyh-Han
70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014122301406.31
71 rdf:type schema:Person
72 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
73 schema:familyName Vitter
74 schema:givenName Jeffrey Scott
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
76 rdf:type schema:Person
77 https://doi.org/10.1016/0004-3702(88)90002-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006302975
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1016/0004-3702(89)90049-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040179661
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1016/0304-3975(76)90061-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048647089
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1016/0304-3975(76)90062-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039975132
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1016/0885-064x(88)90019-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025324848
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/1968.1972 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038881641
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1145/76359.76371 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004063675
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1145/800125.804029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047409927
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1162/neco.1989.1.1.151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053187839
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1162/neco.1989.1.1.39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011040689
96 rdf:type schema:CreativeWork
97 https://doi.org/10.21236/ada164453 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091744995
98 rdf:type schema:CreativeWork
99 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
100 schema:name Department of Computer Science, Brown University, 02912-1910, Providence, RI
101 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...