Local conditioning in Bayesian networks
Artificial IntelligencePublished 1 November 1996
Francisco Javier Díez
Citations59
SJR quartileQ1
SJR score1.84
SNIP3.30
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
Local conditioning is an exact algorithm for computing probability in Bayesian networks that computes the probability directly on the original network instead of building a cluster tree, and this can save time when debugging a model and when the sparsity of evidence allows a pruning of the network.
Abstract
Local conditioning (LC) is an exact algorithm for computing probability in Bayesian networks, developed as an extension of Kim and Pearl's algorithm for singly-connected networks. A list of variables associated to each node guarantees that only the nodes inside a loop are conditioned on the variable which breaks it. The main advantage of this algorithm is that it computes the probability directly on the original network instead of building a cluster tree, and this can save time when debugging a model and when the sparsity of evidence allows a pruning of the network. The algorithm is also advantageous when some families in the network interact through AND/OR gates. A parallel implementation of the algorithm with a processor for each node is possible even in the case of multiply-connected networks.
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.
Proceedings of the 20th conference on Uncertainty in artificial intelligence
1,546 Citations2004Christopher Meek, Max Chickering +1 more
This volume comprises the papers accepted for presentation at UAI 2004, held at the Banff Park Inn in Banff, Canada, from July 7 through 11, 2004, and is confident that the proceedings will become an important archival reference for the field.
Elsevier eBooksUncertainty in Artificial Intelligence
1,434 Citations1992
Qualitative Probabilistic Reasoning and Cognitive models, Dempster-Shafer Theory in Knowledge Representation, and Possibility Theory: Semantics and Applications.
Artificial IntelligenceApproximating probabilistic inference in Bayesian belief networks is NP-hard
763 Citations1993Paul Dagum, Michael Luby
It is shown that the existence of a polynomial-time relative approximation algorithm for major classes of problem instances implies that NP ⊆ P is NP -hard.
TechnometricsProbabilistic Reasoning in Expert Systems, Theory and Algorithms
616 Citations1992Peter M. Jones, Richard E. Neapolitan
This text is a reprint of the seminal 1989 book Probabilistic Reasoning in Expert systems: Theory and Algorithms, which helped serve to create the field the authors now call Bayesian networks and provides an insightful comparison of the two most prominent approaches to probability.
Communications of the ACMHypermedia and cognition
349 Citations1995Manfred Thüring, Jörg Hannemann +1 more
This discussion of “designing for comprehension” addresses the second type of task—reading a hyperdocument for learning—that is more adequate for tasks requiring deep understanding and learning.
Uncertainty in Artificial IntelligenceParameter adjustment in Bayes networks. The generalized noisy OR–gate
229 Citations1993Francisco Javier Díez
This work generalizes the noisy OR-gate for multivalued variables, develops the algorithm to compute probability in time proportional to the number of parents (even in networks with loops) and applies the learning model to this gate.
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.
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.
Uncertainty in Artificial IntelligenceCausal Independence for Knowledge Acquisition and Inference
97 Citations1993David Heckerman
A temporal belief-network representation of causal independence that a knowledge engineer can use to elicit probabilistic models, and can simplify inference, and does not require the use of unobservable variables.
Statistics and ComputingOptimal decomposition of probabilistic networks by simulated annealing
97 Citations1992Uffe Kjærulff
This paper investigates the applicability of a Monte Carlo technique known as ‘simulated annealing’ to achieve optimum or sub-optimum decompositions of probabilistic networks under bounded resources and proves that cost-function changes can be computed locally.
Communications of the ACMApplying Bayesian networks to information retrieval
97 Citations1995Robert Fung, Brendan Del Favero
Information retrieval (IR) is the identification of documents or other units of information in a collection that are relevant to a particular information need.
Elsevier eBooksGlobal Conditioning for Probabilistic Inference in Belief Networks
86 Citations1994Ross D. Shachter, Stig Kjær Andersen +1 more
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.
Elsevier eBooksApproximation Algorithms for the Loop Cutset Problem
71 Citations1994Ann Becker, Dan Geiger
This work shows how to find a small loop cutset in a Bayesian network and finds a loop cut-set which is guaranteed in the worst case to contain less than twice the number of variables contained in a minimum loop cut set.
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.
arXiv (Cornell University)Optimal Decomposition of Belief Networks
66 Citations2013Wilson X. Wen
The problem of optimum belief network decomposition under this framework is shown to be NP-hard and a new method - the method of Minimum Total Number of States (MTNS) - is proposed.
arXiv (Cornell University)Pruning Bayesian Networks for Efficient Computation
31 Citations2013Michelle Baker, Terrance E. Boult
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.
Uncertainty in Artificial IntelligenceConditioning algorithms for exact and approximate inference in causal networks
23 Citations1995Adnan Darwiche
The first algorithm, dynamic conditioning, is a refinement of cutset conditioning that has linear complexity on some networks for which cutsetconditioning is exponential and an algorithm for approximate inference that allows one to trade-off the quality of approximations with the computation time.
Genetic EpidemiologyEfficient methods for computing linkage likelihoods of recessive diseases in inbred pedigrees
19 Citations1991Augustine Kong, D. C. Rao +1 more
This work proposes alternative procedures that can efficiently provide good approximates of linkage likelihoods for data that involve considerable inbreeding and missing information, characteristics of large pedigrees affected by rare recessive diseases.
Statistics and ComputingProbabilistic text understanding
18 Citations1992Robert P. Goldman, Eugene Charniak
A probabilistic model of text understanding is developed, using probability theory to handle the uncertainty which arises in this abductive inference process, and all aspects of natural language processing are treated in the same framework, allowing to integrate syntactic, semantic and pragmatic constraints.
International Journal of Approximate ReasoningA combination of exact algorithms for inference on Bayesian belief networks
17 Citations1991Henri J. Suermondt, Gregory F. Cooper
An approach called aggregation after decomposition (AD) is described, which can perform inference relatively efficiently for certain network structures in which neither cutset conditioning nor clique-tree propagation performs well.
Dialnet (Universidad de la Rioja)Sistema experto bayesiano para ecocardiografía
13 Citations1994Francisco Javier Díez Vegas
A series of quinazolines were synthesized from 2-aminobenzophenones and benzylic amines in good to excellent yields by employing a new heterogeneous catalyst based on the copper oxide nanoparticles supported on kaolin.
Cybernetics & SystemsDISTRIBUTED INFERENCE IN BAYESIAN NETWORKS
12 Citations1994Francisco Javier Díez, José Mira
It will be shown how all these algorithms admit distributed implementations and two exact and one approximate methods for dealing with general networks are discussed.