Learning Bayesian Networks is NP-Complete View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1996

AUTHORS

David Maxwell Chickering

ABSTRACT

Algorithms for learning Bayesian networks from data have two components: a scoring metric and a search procedure. The scoring metric computes a score reflecting the goodness-of-fit of the structure to the data. The search procedure tries to identify network structures with high scores. Heckerman et al. (1995) introduce a Bayesian metric, called the BDe metric, that computes the relative posterior probability of a network structure given data. In this paper, we show that the search problem of identifying a Bayesian network—among those where each node has at most K parents—that has a relative posterior probability greater than a given constant is NP-complete, when the BDe metric is used. More... »

PAGES

121-130

References to SciGraph publications

Book

TITLE

Learning from Data

ISBN

978-0-387-94736-5
978-1-4612-2404-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4612-2404-4_12

DOI

http://dx.doi.org/10.1007/978-1-4612-2404-4_12

DIMENSIONS

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


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/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of California Los Angeles", 
          "id": "https://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Computer Science Department, University of California, Los Angeles, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chickering", 
        "givenName": "David Maxwell", 
        "id": "sg:person.011240332636.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011240332636.47"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf00994110", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046316965", 
          "https://doi.org/10.1007/bf00994110"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "Algorithms for learning Bayesian networks from data have two components: a scoring metric and a search procedure. The scoring metric computes a score reflecting the goodness-of-fit of the structure to the data. The search procedure tries to identify network structures with high scores. Heckerman et al. (1995) introduce a Bayesian metric, called the BDe metric, that computes the relative posterior probability of a network structure given data. In this paper, we show that the search problem of identifying a Bayesian network\u2014among those where each node has at most K parents\u2014that has a relative posterior probability greater than a given constant is NP-complete, when the BDe metric is used.", 
    "editor": [
      {
        "familyName": "Fisher", 
        "givenName": "Doug", 
        "type": "Person"
      }, 
      {
        "familyName": "Lenz", 
        "givenName": "Hans-J.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4612-2404-4_12", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-0-387-94736-5", 
        "978-1-4612-2404-4"
      ], 
      "name": "Learning from Data", 
      "type": "Book"
    }, 
    "name": "Learning Bayesian Networks is NP-Complete", 
    "pagination": "121-130", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013962799"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4612-2404-4_12"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4283ee04403c6bb28a1b293598ae4d1f89dbb69e85f419df8483a9bc970e8540"
        ]
      }
    ], 
    "publisher": {
      "location": "New York, NY", 
      "name": "Springer New York", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4612-2404-4_12", 
      "https://app.dimensions.ai/details/publication/pub.1013962799"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:26", 
    "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/0000000372_0000000372/records_117092_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-1-4612-2404-4_12"
  }
]
 

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/978-1-4612-2404-4_12'

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/978-1-4612-2404-4_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4612-2404-4_12'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4612-2404-4_12'


 

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

74 TRIPLES      23 PREDICATES      28 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4612-2404-4_12 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N56e12f84987747ff9d7bf75e8728aa61
4 schema:citation sg:pub.10.1007/bf00994110
5 schema:datePublished 1996
6 schema:datePublishedReg 1996-01-01
7 schema:description Algorithms for learning Bayesian networks from data have two components: a scoring metric and a search procedure. The scoring metric computes a score reflecting the goodness-of-fit of the structure to the data. The search procedure tries to identify network structures with high scores. Heckerman et al. (1995) introduce a Bayesian metric, called the BDe metric, that computes the relative posterior probability of a network structure given data. In this paper, we show that the search problem of identifying a Bayesian network—among those where each node has at most K parents—that has a relative posterior probability greater than a given constant is NP-complete, when the BDe metric is used.
8 schema:editor Nf4d9521c50bf4065b2e42374580b29b6
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf Nd6913855d5e542378661f46046e15947
13 schema:name Learning Bayesian Networks is NP-Complete
14 schema:pagination 121-130
15 schema:productId N3894048f96064db6b31f3025af1f0e3f
16 Na16c283db9da45f9ae66b6fc55d901c3
17 Ne7a2d25154fb48b1874e78a63ff0cf2b
18 schema:publisher Ndbb75955c3b6492ab93d36065af27429
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013962799
20 https://doi.org/10.1007/978-1-4612-2404-4_12
21 schema:sdDatePublished 2019-04-16T09:26
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher Na674a082f98a4feb93a042166ed49bce
24 schema:url https://link.springer.com/10.1007%2F978-1-4612-2404-4_12
25 sgo:license sg:explorer/license/
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N3894048f96064db6b31f3025af1f0e3f schema:name readcube_id
29 schema:value 4283ee04403c6bb28a1b293598ae4d1f89dbb69e85f419df8483a9bc970e8540
30 rdf:type schema:PropertyValue
31 N45fc4684b4bb44979ffb54f871b3181b schema:familyName Fisher
32 schema:givenName Doug
33 rdf:type schema:Person
34 N56e12f84987747ff9d7bf75e8728aa61 rdf:first sg:person.011240332636.47
35 rdf:rest rdf:nil
36 Na16c283db9da45f9ae66b6fc55d901c3 schema:name dimensions_id
37 schema:value pub.1013962799
38 rdf:type schema:PropertyValue
39 Na1c9ec7bc3e644709ea3a0d154e0bb4b schema:familyName Lenz
40 schema:givenName Hans-J.
41 rdf:type schema:Person
42 Na674a082f98a4feb93a042166ed49bce schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 Nd6913855d5e542378661f46046e15947 schema:isbn 978-0-387-94736-5
45 978-1-4612-2404-4
46 schema:name Learning from Data
47 rdf:type schema:Book
48 Ndbb75955c3b6492ab93d36065af27429 schema:location New York, NY
49 schema:name Springer New York
50 rdf:type schema:Organisation
51 Ne7a2d25154fb48b1874e78a63ff0cf2b schema:name doi
52 schema:value 10.1007/978-1-4612-2404-4_12
53 rdf:type schema:PropertyValue
54 Neb62b1c844454f5fb69ce8a18e358a86 rdf:first Na1c9ec7bc3e644709ea3a0d154e0bb4b
55 rdf:rest rdf:nil
56 Nf4d9521c50bf4065b2e42374580b29b6 rdf:first N45fc4684b4bb44979ffb54f871b3181b
57 rdf:rest Neb62b1c844454f5fb69ce8a18e358a86
58 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
59 schema:name Mathematical Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
62 schema:name Statistics
63 rdf:type schema:DefinedTerm
64 sg:person.011240332636.47 schema:affiliation https://www.grid.ac/institutes/grid.19006.3e
65 schema:familyName Chickering
66 schema:givenName David Maxwell
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011240332636.47
68 rdf:type schema:Person
69 sg:pub.10.1007/bf00994110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046316965
70 https://doi.org/10.1007/bf00994110
71 rdf:type schema:CreativeWork
72 https://www.grid.ac/institutes/grid.19006.3e schema:alternateName University of California Los Angeles
73 schema:name Computer Science Department, University of California, Los Angeles, USA
74 rdf:type schema:Organization
 




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


...