Lower bounds on learning decision lists and trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Thomas Hancock , Tao Jiang , Ming Li , John Tromp

ABSTRACT

k-decision lists and decision trees play important roles in learning theory as well as in practical learning systems, k-decision lists generalize classes such as monomials, k-DNF, and k-CNF and like these subclasses is polynomially PAC-learnable [19]. This leaves open the question of whether k-decision lists can be learned as efficiently as k-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [2]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results. The following problems cannot be approximated in polynomial time within a factor of \(2^{\log ^\delta n}\) for any δpolylog n ]: a generalized set cover, k-decision lists, k-decision lists by monotone decision lists, and decision trees. Decision lists cannot be approximated in polynomial time within a factor of n δ, for some constant δ>0, unless NP=P. Also, k-decision lists with l 0–1 alternations cannot be approximated within a factor logl n unless NP⊂DTIME[n O(log log n)] (providing an interesting comparison to the upper bound recently obtained in [1]). More... »

PAGES

527-538

Book

TITLE

STACS 95

ISBN

978-3-540-59042-2
978-3-540-49175-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-59042-0_102

DOI

http://dx.doi.org/10.1007/3-540-59042-0_102

DIMENSIONS

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


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/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Siemens (United States)", 
          "id": "https://www.grid.ac/institutes/grid.419233.e", 
          "name": [
            "Siemens Corporate Research, 755 College Road East, 08540\u00a0Princeton, NJ"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hancock", 
        "givenName": "Thomas", 
        "id": "sg:person.012746727221.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012746727221.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "McMaster University", 
          "id": "https://www.grid.ac/institutes/grid.25073.33", 
          "name": [
            "Dept. of Comp. Sci., McMaster University, L8S 4K1\u00a0Hamilton, Ont., Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "id": "sg:person.011617335564.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Dept. of Comp. Sci., University of Waterloo, N3L 3G1\u00a0Waterloo, Ont., Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Ming", 
        "id": "sg:person.0621576316.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Dept. of Comp. Sci., University of Waterloo, N3L 3G1\u00a0Waterloo, Ont., Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tromp", 
        "givenName": "John", 
        "id": "sg:person.011226061741.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "k-decision lists and decision trees play important roles in learning theory as well as in practical learning systems, k-decision lists generalize classes such as monomials, k-DNF, and k-CNF and like these subclasses is polynomially PAC-learnable [19]. This leaves open the question of whether k-decision lists can be learned as efficiently as k-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [2]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results. The following problems cannot be approximated in polynomial time within a factor of \\(2^{\\log ^\\delta n}\\) for any \u03b4polylog n ]: a generalized set cover, k-decision lists, k-decision lists by monotone decision lists, and decision trees. Decision lists cannot be approximated in polynomial time within a factor of n \u03b4, for some constant \u03b4>0, unless NP=P. Also, k-decision lists with l 0\u20131 alternations cannot be approximated within a factor logl n unless NP\u2282DTIME[n O(log log n)] (providing an interesting comparison to the upper bound recently obtained in [1]).", 
    "editor": [
      {
        "familyName": "Mayr", 
        "givenName": "Ernst W.", 
        "type": "Person"
      }, 
      {
        "familyName": "Puech", 
        "givenName": "Claude", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-59042-0_102", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-59042-2", 
        "978-3-540-49175-0"
      ], 
      "name": "STACS 95", 
      "type": "Book"
    }, 
    "name": "Lower bounds on learning decision lists and trees", 
    "pagination": "527-538", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-59042-0_102"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2386c57c3a1763e6ba4fe2cc20a6a9c4768d132d2109daaf45e4e8295224beaf"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007458546"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-59042-0_102", 
      "https://app.dimensions.ai/details/publication/pub.1007458546"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T16:58", 
    "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/0000000001_0000000264/records_8678_00000012.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-59042-0_102"
  }
]
 

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/3-540-59042-0_102'

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/3-540-59042-0_102'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-59042-0_102'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-59042-0_102'


 

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

97 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-59042-0_102 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N255631c0f6d242fba9a7f0ad8d670ebc
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description k-decision lists and decision trees play important roles in learning theory as well as in practical learning systems, k-decision lists generalize classes such as monomials, k-DNF, and k-CNF and like these subclasses is polynomially PAC-learnable [19]. This leaves open the question of whether k-decision lists can be learned as efficiently as k-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [2]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results. The following problems cannot be approximated in polynomial time within a factor of \(2^{\log ^\delta n}\) for any δpolylog n ]: a generalized set cover, k-decision lists, k-decision lists by monotone decision lists, and decision trees. Decision lists cannot be approximated in polynomial time within a factor of n δ, for some constant δ>0, unless NP=P. Also, k-decision lists with l 0–1 alternations cannot be approximated within a factor logl n unless NP⊂DTIME[n O(log log n)] (providing an interesting comparison to the upper bound recently obtained in [1]).
7 schema:editor N1a01743eb3704269a6f38b02aabf0548
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N76bb2822be1d4510bbd063d4ada68b4c
12 schema:name Lower bounds on learning decision lists and trees
13 schema:pagination 527-538
14 schema:productId N64e0a34c17dc419bb72f8cc2401b6d94
15 N7ecc7ff2d78d4f6d8ed13eae6c6887a2
16 Nf0d0a4c2639b4c57aefc9ef82a3ea4a3
17 schema:publisher Nc76f8ea5a173457e8e63540fef0f2a6e
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007458546
19 https://doi.org/10.1007/3-540-59042-0_102
20 schema:sdDatePublished 2019-04-15T16:58
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N63f02977f9744124ba0e05cc666a88ab
23 schema:url http://link.springer.com/10.1007/3-540-59042-0_102
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N05757a46e20345f899d310cc1b5366da schema:familyName Puech
28 schema:givenName Claude
29 rdf:type schema:Person
30 N0a59d6b799c640cfa2d56dcfdd19e5a3 rdf:first sg:person.0621576316.79
31 rdf:rest Nbc649b0c7ac049c891b520d060831346
32 N1a01743eb3704269a6f38b02aabf0548 rdf:first N6c65f07ea4374ff6ac07ecc52520e54a
33 rdf:rest N4d7d7330a18d4c129dd8d46e0974aa8c
34 N255631c0f6d242fba9a7f0ad8d670ebc rdf:first sg:person.012746727221.11
35 rdf:rest Nfd22df7e3e05413688c6e6ec8742546a
36 N4d7d7330a18d4c129dd8d46e0974aa8c rdf:first N05757a46e20345f899d310cc1b5366da
37 rdf:rest rdf:nil
38 N63f02977f9744124ba0e05cc666a88ab schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N64e0a34c17dc419bb72f8cc2401b6d94 schema:name readcube_id
41 schema:value 2386c57c3a1763e6ba4fe2cc20a6a9c4768d132d2109daaf45e4e8295224beaf
42 rdf:type schema:PropertyValue
43 N6c65f07ea4374ff6ac07ecc52520e54a schema:familyName Mayr
44 schema:givenName Ernst W.
45 rdf:type schema:Person
46 N76bb2822be1d4510bbd063d4ada68b4c schema:isbn 978-3-540-49175-0
47 978-3-540-59042-2
48 schema:name STACS 95
49 rdf:type schema:Book
50 N7ecc7ff2d78d4f6d8ed13eae6c6887a2 schema:name dimensions_id
51 schema:value pub.1007458546
52 rdf:type schema:PropertyValue
53 Nbc649b0c7ac049c891b520d060831346 rdf:first sg:person.011226061741.52
54 rdf:rest rdf:nil
55 Nc76f8ea5a173457e8e63540fef0f2a6e schema:location Berlin, Heidelberg
56 schema:name Springer Berlin Heidelberg
57 rdf:type schema:Organisation
58 Nf0d0a4c2639b4c57aefc9ef82a3ea4a3 schema:name doi
59 schema:value 10.1007/3-540-59042-0_102
60 rdf:type schema:PropertyValue
61 Nfd22df7e3e05413688c6e6ec8742546a rdf:first sg:person.011617335564.48
62 rdf:rest N0a59d6b799c640cfa2d56dcfdd19e5a3
63 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
64 schema:name Psychology and Cognitive Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
67 schema:name Psychology
68 rdf:type schema:DefinedTerm
69 sg:person.011226061741.52 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
70 schema:familyName Tromp
71 schema:givenName John
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011226061741.52
73 rdf:type schema:Person
74 sg:person.011617335564.48 schema:affiliation https://www.grid.ac/institutes/grid.25073.33
75 schema:familyName Jiang
76 schema:givenName Tao
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48
78 rdf:type schema:Person
79 sg:person.012746727221.11 schema:affiliation https://www.grid.ac/institutes/grid.419233.e
80 schema:familyName Hancock
81 schema:givenName Thomas
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012746727221.11
83 rdf:type schema:Person
84 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
85 schema:familyName Li
86 schema:givenName Ming
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
88 rdf:type schema:Person
89 https://www.grid.ac/institutes/grid.25073.33 schema:alternateName McMaster University
90 schema:name Dept. of Comp. Sci., McMaster University, L8S 4K1 Hamilton, Ont., Canada
91 rdf:type schema:Organization
92 https://www.grid.ac/institutes/grid.419233.e schema:alternateName Siemens (United States)
93 schema:name Siemens Corporate Research, 755 College Road East, 08540 Princeton, NJ
94 rdf:type schema:Organization
95 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
96 schema:name Dept. of Comp. Sci., University of Waterloo, N3L 3G1 Waterloo, Ont., Canada
97 rdf:type schema:Organization
 




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


...