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 Nc8a9b3e92ca9446289a14f74604c322f
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 N37079f5b22e642b1afe5ad43ee6c3f1d
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf N88715a5ffd604275881c2c88cc5c2add
13 schema:name Learning Bayesian Networks is NP-Complete
14 schema:pagination 121-130
15 schema:productId N6cc511e054974b82b3c887066cb2fc67
16 N86a929ac7f0a4e4aa5b4e15c5fedd6cb
17 Nb7b0d90b3b0540c6a0d3848593cb8e91
18 schema:publisher N3fa74c68029a4da8bdf9fa93fb205a86
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 Na0fd74f28e8d433abc527a08f277f15b
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 N37079f5b22e642b1afe5ad43ee6c3f1d rdf:first N6b2d5d3036d74cf6bcc2bb5d1ab91485
29 rdf:rest Nf552e40177334c988a8d61c623121ffd
30 N3bba3edb42e546e8afb5e45ec6eab7ab schema:familyName Lenz
31 schema:givenName Hans-J.
32 rdf:type schema:Person
33 N3fa74c68029a4da8bdf9fa93fb205a86 schema:location New York, NY
34 schema:name Springer New York
35 rdf:type schema:Organisation
36 N6b2d5d3036d74cf6bcc2bb5d1ab91485 schema:familyName Fisher
37 schema:givenName Doug
38 rdf:type schema:Person
39 N6cc511e054974b82b3c887066cb2fc67 schema:name dimensions_id
40 schema:value pub.1013962799
41 rdf:type schema:PropertyValue
42 N86a929ac7f0a4e4aa5b4e15c5fedd6cb schema:name readcube_id
43 schema:value 4283ee04403c6bb28a1b293598ae4d1f89dbb69e85f419df8483a9bc970e8540
44 rdf:type schema:PropertyValue
45 N88715a5ffd604275881c2c88cc5c2add schema:isbn 978-0-387-94736-5
46 978-1-4612-2404-4
47 schema:name Learning from Data
48 rdf:type schema:Book
49 Na0fd74f28e8d433abc527a08f277f15b schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 Nb7b0d90b3b0540c6a0d3848593cb8e91 schema:name doi
52 schema:value 10.1007/978-1-4612-2404-4_12
53 rdf:type schema:PropertyValue
54 Nc8a9b3e92ca9446289a14f74604c322f rdf:first sg:person.011240332636.47
55 rdf:rest rdf:nil
56 Nf552e40177334c988a8d61c623121ffd rdf:first N3bba3edb42e546e8afb5e45ec6eab7ab
57 rdf:rest rdf:nil
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)


...