Global Conditioning for Probabilistic Inference in Belief Networks
Elsevier eBooksPublished 1 January 1994
Ross D. Shachter, Stig Kjær Andersen, Peter Szolovits
Citations86
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
A new approach to probabilistic inference on belief networks, global conditioning, which is a simple generalization of Pearl's (1986b) method of loop-cutset conditioning is proposed, which provides new opportunities for parallel processing and a tradeoff of time for memory.
Abstract
In this paper we propose a new approach to probabilistic inference on belief networks, global conditioning, which is a simple generalization of Pearl's (1986b) method of loop-cutset conditioning. We show that global conditioning, as well as loop-cutset conditioning, can be thought of as a special case of the method of Lauritzen and Spiegelhalter (1988) as refined by Jensen et al (1990a; 1990b). Nonetheless, this approach provides new opportunities for parallel processing and, in the case of sequential processing, a tradeoff of time for memory. We also show how a hybrid method (Suermondt and others 1990) combining loop-cutset conditioning with Jensen's method can be viewed within our framework. By exploring the relationships between these methods, we develop a unifying framework in which the advantages of each approach can be combined successfully.
Keywords
Computer Science
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
Journal of the ACMOn the Desirability of Acyclic Database Schemes
797 Citations1983Catriel Beeri, Ronald Fagin +2 more
It is shown that this class of database schemes, called acychc, has a number of desirable properties that have been studied by other researchers and are shown to be eqmvalent to acydicity.
NetworksIdentifying independence in bayesian networks
526 Citations1990Dan Geiger, Thomas Verma +1 more
This article characterizes all independence assertions that logically follow from the topology of a network and develops a linear time algorithm that identifies these assertions and is shown to work for a broad class of nonprobabilistic independencies.
NetworksIndependence properties of directed markov fields
521 Citations1990Steffen L. Lauritzen, A. P. Dawid +2 more
A criterion for conditional independence of two groups of variables given a third is given and named as the directed, global Markov property and it is argued that this criterion is easy to use, it is sharper than that given by Kiiveri, Speed, and Carlin and equivalent to that of Pearl.
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.
Advances in Applied ProbabilityProbability functions on complex pedigrees
406 Citations1978C. Cannings, E. A. Thompson +1 more
The calculation of probabilities on pedigrees of arbitrary complexity is discussed for a basic model of transmission and penetrance (encompassing Mendelian inheritance, and certain environmental influences).
Probabilistic Similarity Networks
315 Citations1991Edward H. Shortliffe, David Heckerman
This research suggests strongly that, by identifying specific forms of conditional independence, and by developing representations that exploit these forms of independence for knowledge acquisition, knowledge engineers can construct normative expert systems for domains of larger scope and greater complexity than the domains previously through to be amenable to the decision-theoretic approach.
IEEE ExpertPropagating Belief Functions with Local Computations
236 Citations1986Prakash P. Shenoy, Glenn Shafer
A way to propagate belief functions in certain kinds of trees using only local computations, which generalizes the computational scheme proposed by Pearl5 for Bayesian causal trees and describes qualitative Markov trees.
International Joint Conference on Artificial IntelligenceA computational model for causal and diagnostic reasoning in inference systems
236 Citations1983Jin Hee Kim, Judea Pearl
A representation of evidential relationships which permits updating of belief in two simultaneous modes: causal and diagnostic is introduced, which extends the hierarchical tree representation by allowing multiple causes to a given manifestation.
NetworksAn algebra of bayesian belief universes for knowledge‐based systems
222 Citations1990Finn V. Jensen, Kristian G. Olesen +1 more
A scheme-the algebra of Bayesian belief universes-for absorbing and propagating evidence in multiply connected CPNs is outlined, which provides a secondary structure, a junction tree, and a simple set of algebraic operations between objects in this structure, Collect Evidence and Distribute Evidence.
Annals of Mathematics and Artificial IntelligenceProbability propagation
179 Citations1990Glenn Shafer, Prakash P. Shenoy
The account given here avoids the divisions required by conditional probabilities and generalizes readily to alternative measures of subjective probability, such as Dempster-Shafer or Spohnian belief functions.
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.
Artificial IntelligenceFusion and propagation with multiple observations in belief networks
109 Citations1991Mark A. Peot, Ross D. Shachter
A Revised Polytree Algorithm is developed with the same complexity as the undirected methods, but within the directed framework of the Poly Tree Algorithm, which obtains the corresponding significant improvement in speed, but also a much simpler form for combination.
NetworksAn ordered examination of influence diagrams
85 Citations1990Ross D. Shachter
The graphical orderings underlying the influence diagram and the primitive interchange operations that can reorder the network are examined, finding these operations are sufficient to determine the maximal independent set and minimal relevant sets for any given inference problem.
Machine intelligence and pattern recognitionEvidence Absorption and Propagation Through Evidence Reversals
81 Citations1990Ross D. Shachter
The arc reversal/node reduction approach to probabilistic inference is extended to include the case of instantiated evidence by an operation called “evidence reversal,” which provides a technique for computing posterior joint distributions on general belief networks.
arXiv (Cornell University)Approximations in Bayesian Belief Universe for Knowledge Based Systems
78 Citations2013Frank Jensen, Scot Anderson
International Journal of Approximate ReasoningProbabilistic inference in multiply connected belief networks using loop cutsets
67 Citations1990Henri J. Suermondt, Gregory F. Cooper
It is shown that the problem of finding a loop cutset that optimizes probabilistic inference using the method of conditioning is NP-hard.
Advances in Applied ProbabilityThe recursive derivation of likelihoods on complex pedigrees
43 Citations1976C. Cannings, E. A. Thompson +1 more
By generalizing the recursion so that information on individuals can be collapsed onto an offspring the authors allow pedigrees in which there are no loops (zero-loop), and by introducing the notion of collapsing information onto a set of individuals jointly, the method is extended to pedigree of arbitrary complexity.
Uncertainty in Artificial IntelligenceA combination of cutset conditioning with clique-tree propagation in the Pathfinder system
23 Citations1990Henri J. Suermondt, Gregory F. Cooper +1 more
International Journal of Approximate ReasoningLocal expression languages for probabilistic dependence
19 Citations1995Bruce D’Ambrosio
A representation capable of making this intradistribution structure explicit, and an extension to the SPI algorithm capable of utilizing this structural information to improve the efficiency of inference are presented.
arXiv (Cornell University)Updating Probabilities in Multiply-Connected Belief Networks
13 Citations2013Jaap Suermondt, Gregory F. Cooper
This paper presents a heuristic algorithm for finding a loop-cutset that satisfies conditions that need to be satisfied by the selected nodes of a multiply-connected belief networks.
Elsevier eBooksLocal Expression Languages for Probabilistic Dependence: a preliminary report
13 Citations1991Bruce D’Ambrosio
This work presents a generalization of the local expression language used in the Symbolic Probabilistic Inference (SPI) approach to inference in belief nets and shows how this extended language can be used to capture the semantics, representational advantages, and inferential complexity advantages of the "noisy or" relationship.