Probabilistic Inference Using Belief Networks Is NP-Hard

From Tetherless World Wiki

Jump to: navigation, search

Citation: Gregory F. Cooper. (1987) Probabilistic Inference Using Belief Networks Is NP-Hard. In KSL-87-27, 1987.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Gregory F. Cooper
title Probabilistic Inference Using Belief Networks Is NP-Hard
number KSL-87-27
institution Knowledge Systems, AI Laboratory
address Stanford, CA, USA
year 1987
Bibtex more
Access Paper
abstract [[abstract::Most natural and manmade systems contain partial dependencies among their composistional elements. In medicine, for example, the existence of a finding is generally dependent on some of the other findings and other diseases, but never dependent on all the other findings and diseases. It is this partial dependency structure that makes our world both interesting and at the same time comprehensible. Even so, our models of real-world problem domains are almost always incomplete because all the relevant variables and relationships are not known. It is for this reason that models that most accurately reflect available knowledge are often probabilistic. Thus real-world domains quite naturally lead to partial dependency graph models that are probabilistic.The graphical representation of probabilistic relationships among events has been the subject of considerable research. Markov models form one such class of probabilistic graphical representations [Kemeny 76, Darroch 80]. In the field of artificial intelligence, numerous systems have used a directed graph to represent probabilistic relationships among events [Duda 76, Weiss 78]. A particular type of probabilistic graphical representation, called belief networks, has been defined and explored by numerous researchers. In addition to being called belief networks [Pearl 86], they have been termed causal nets [Good 61a, Good 61b], probabilistic cause-effect models [Rousseau 68], probabilistic causal networks [Cooper 84], and influence diagrams [Howard 84, Shachter 86].A primary advantage of using a graphical representation of probabilistic relationships is the efficiency that results. It is necessary to consider only the known dependencies among variables (events) in a domain, rather that to assume that all variables are dependent on all other variables [Cooper 84, Pearl 87a]. This generally leads to greatly improved efficiency in the acquisition and representation of domain knowledge and in the computations that are used to solve problems in the domain.|Most natural and manmade systems contain partial dependencies among their composistional elements. In medicine, for example, the existence of a finding is generally dependent on some of the other findings and other diseases, but never dependent on all the other findings and diseases. It is this partial dependency structure that makes our world both interesting and at the same time comprehensible. Even so, our models of real-world problem domains are almost always incomplete because all the relevant variables and relationships are not known. It is for this reason that models that most accurately reflect available knowledge are often probabilistic. Thus real-world domains quite naturally lead to partial dependency graph models that are probabilistic.The graphical representation of probabilistic relationships among events has been the subject of considerable research. Markov models form one such class of probabilistic graphical representations [Kemeny 76, Darroch 80]. In the field of artificial intelligence, numerous systems have used a directed graph to represent probabilistic relationships among events [Duda 76, Weiss 78]. A particular type of probabilistic graphical representation, called belief networks, has been defined and explored by numerous researchers. In addition to being called belief networks [Pearl 86], they have been termed causal nets [Good 61a, Good 61b], probabilistic cause-effect models [Rousseau 68], probabilistic causal networks [Cooper 84], and influence diagrams [Howard 84, Shachter 86].A primary advantage of using a graphical representation of probabilistic relationships is the efficiency that results. It is necessary to consider only the known dependencies among variables (events) in a domain, rather that to assume that all variables are dependent on all other variables [Cooper 84, Pearl 87a]. This generally leads to greatly improved efficiency in the acquisition and representation of domain knowledge and in the computations that are used to solve problems in the domain.]]

KSL Technical Report ID: KSL-87-27
Facts about Probabilistic Inference Using Belief Networks Is NP-HardRDF feed
Address Stanford, CA, USA  +
Author Gregory F. Cooper  +
Bibtype techreport  +
Has author Gregory F. Cooper  +
Has identifier KSL-87-27  +
Has publishing details 1987  +
Has title Probabilistic Inference Using Belief Networks Is NP-Hard  +
Has where published KSL-87-27  +
Has year 1987  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-87-27  +
Number KSL-87-27  +
Process note NO  +
Title Probabilistic Inference Using Belief Networks Is NP-Hard  +
Year 1987  +
Retrieved from "http://tw.rpi.edu/wiki/Probabilistic_Inference_Using_Belief_Networks_Is_NP-Hard"
Personal tools