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 N0907537c84cc45339f99fc338f40b3e3
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 N93454a7c03ca4bf495d155a773cc6231
22 Na78225b9d3f441d0add070fe11bba76f
23 sg:journal.1125588
24 schema:name Complexity results on learning by neural nets
25 schema:pagination 211-230
26 schema:productId N404298e7560947c9b1e708b779711385
27 N473fda2039724948be6ec6339bd19ac8
28 Nb87afc4f0ffa4949a13bb3504d41d792
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 N6f9e61aeb60a493ab48e3d6fe4d826ab
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 N0907537c84cc45339f99fc338f40b3e3 rdf:first sg:person.014122301406.31
39 rdf:rest Nb47aae952d8e493b80ab614724eafc2b
40 N404298e7560947c9b1e708b779711385 schema:name doi
41 schema:value 10.1007/bf00114777
42 rdf:type schema:PropertyValue
43 N473fda2039724948be6ec6339bd19ac8 schema:name readcube_id
44 schema:value b47cde7a1fbdd49a7739c168740dfec0f8fc65214f211863f97f29d6ca4129b2
45 rdf:type schema:PropertyValue
46 N6f9e61aeb60a493ab48e3d6fe4d826ab schema:name Springer Nature - SN SciGraph project
47 rdf:type schema:Organization
48 N93454a7c03ca4bf495d155a773cc6231 schema:issueNumber 3
49 rdf:type schema:PublicationIssue
50 Na78225b9d3f441d0add070fe11bba76f schema:volumeNumber 6
51 rdf:type schema:PublicationVolume
52 Nb47aae952d8e493b80ab614724eafc2b rdf:first sg:person.0613677314.28
53 rdf:rest rdf:nil
54 Nb87afc4f0ffa4949a13bb3504d41d792 schema:name dimensions_id
55 schema:value pub.1037888244
56 rdf:type schema:PropertyValue
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)


...