Probabilistic inference in multiply connected belief networks using loop cutsets
International Journal of Approximate ReasoningPublished 1 July 1990
Henri J. Suermondt, Gregory F. Cooper
Citations67
SJR quartileQ2
SJR score0.73
SNIP1.18
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the problem of finding a loop cutset that optimizes probabilistic inference using the method of conditioning is NP-hard.
Abstract
The method of conditioning permits probabilistic inference in multiply connected belief networks using an algorithm by Pearl. This method uses a select set of nodes, the loop cutset, to render the multiply connected network singly connected. We discuss the function of the nodes of the loop cutset and a condition that must be met by the nodes of the loop cutset. We show that the problem of finding a loop cutset that optimizes probabilistic inference using the method of conditioning is NP-hard. We present a heuristic algorithm for finding a small loop cutset in polynomial time, and we analyze the performance of this heuristic algorithm empirically.
Keywords
Computer ScienceDecision Sciences
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
16,927 Citations1988Judea Pearl
The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems
3,970 Citations1988Steffen L. Lauritzen, David J. Spiegelhalter
This work exploits a range of local representations for the joint probability distribution, combined with topological changes to the original network termed 'marrying' and 'filling-in', which allows efficient algorithms for transfer between representations, providing rapid absorption and propagation of evidence.
Artificial IntelligenceFusion, propagation, and structuring in belief networks
2,152 Citations1986Judea Pearl
Artificial IntelligenceThe computational complexity of probabilistic inference using bayesian belief networks
1,935 Citations1990Gregory F. Cooper
It is shown that probabilistic inference using belief networks is NP-hard,Therefore, research should be directed away from the search for a general, efficient probabilism inference algorithm, and toward the design of efficient special-case, average- case, and approximation algorithms.
Operations ResearchEvaluating Influence Diagrams
1,276 Citations1986Ross D. Shachter
An algorithm is developed that can evaluate any well-formed influence diagram and determine the optimal policy for its decisions and can be performed using the decision maker's perspective on the problem.
EconometricaThe Theory of Graphs and Its Applications
912 Citations1965Elizna Burger, Claude Berge +1 more
Operations ResearchProbabilistic Inference and Influence Diagrams
498 Citations1988Ross D. Shachter
This work develops algorithms to address questions of inference within a probabilistic model represented as an influence diagram and uses the conditional independence implied by the diagram's structure to determine the information needed to solve a given problem.
International Journal of Approximate ReasoningDecision theory in expert systems and artificial intelligence
371 Citations1988Eric Horvitz, John S. Breese +1 more
The potential for addressing problems in representation, inference, knowledge engineering, and explanation within the decision-theoretic framework is surveyed and the belief network and influence diagram representations are presented.
Artificial IntelligenceEvidential reasoning using stochastic simulation of causal models
346 Citations1987Judea Pearl
The method proposed renders stochastic simulation a powerful technique of coherent inferencing, especially suited for tasks involving complex, nondecomposable models where “ballpark” estimates of probabilities will suffice.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)NESTOR: A Computer-Based Medical Diagnostic Aid That Integrates Causal and Probabilistic Knowledge.
223 Citations1984Gregory F. Cooper
This dissertation presents the problems that are addressed by each of the three tasks of NESTOR, the use of knowledge-based methods within a formal probability theory framework, and the details of the methods used to address them.
Artificial IntelligenceDistributed revision of composite beliefs
190 Citations1987Judea Pearl
The chapter demonstrates how numerical probabilities can be used as a catalyst for coherent transformations from evidence sentences to conclusion sentences and identifies the structures that allow such transformations to be executed by autonomous production rules and those that invite problems of intractability and instability unless treated with care.
Machine intelligence and pattern recognitionA Constraint – Propagation Approach to Probabilistic Reasoning
169 Citations1986Judea Pearl
The paper demonstrates that strict adherence to probability theory does not preclude the use of concurrent, self-activated constraint-propagation mechanisms for managing uncertainty and maintains local records of sources-of-belief.
National Conference on Artificial IntelligenceThe logic of representing dependencies by directed graphs
119 Citations1987Judea Pearl, Thomas Verma
The etiology and prevalence of OH in the general population is outlined, its relationship with morbidity and mortality is summarized, a diagnostic and therapeutic algorithm is proposed, and current challenges and future perspectives are delineated.
NetworksIterative algorithms for generating minimal cutsets in directed graphs
33 Citations1986Douglas R. Shier, David E. Whited
Plusieurs approches pour evaluer la fiabilite d'un reseau necessitent de generer tous les ensembles de coupe minimaux dans un graphe oriente, and on propose pour cela un algorithme general iteratif, base sur une structure algebrique sous-jacente.
Artificial IntelligenceInitialization for the method of conditioning in Bayesian belief networks
27 Citations1991Henri J. Suermondt, Gregory F. Cooper
A method is presented that lets us compute the joint prior probabilities of the nodes of the loop cutset by instantiating the loop-cutset nodes sequentially.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)A method for computing probabilities in complex situations
19 Citations1968William Frederick Rousseau
Machine intelligence and pattern recognitionKNET: Integrating Hypermedia and Normative Bayesian Modeling
13 Citations1990R. Martin Chavez, Gregory F. Cooper
KNET is a general-purpose shell for constructing expert systems based on belief networks and decision networks that features a coherent probabilistic scheme for managing uncertainty, an object-oriented graphics editor for drawing and manipulating decision networks, and HyperCard's potential for quickly constructing flexible and friendly user interfaces.