Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
A Hybrid Algorithm to Compute Marginal and Joint Beliefs in Bayesian Networks and Its Complexity
Mark Bloemeke, Marco Valtorta
Abstract:
There exist two general forms of exact algorithms for updating probabilities in Bayesian Networks. The first approach involves using a structure, usually a clique tree, and performing local message based calculation to extract the belief in each variable. The second general class of algorithm involves the use of non-serial dynamic programming techniques to extract the belief in some desired group of variables. In this paper we present a hybrid algorithm based on the latter approach yet possessing the ability to retrieve the belief in all single variables. The technique is advantageous in that it saves a NP-hard computation step over using one algorithm of each type. Furthermore, this technique re-enforces a conjecture of Jensen and Jensen [JJ94] in that it still requires a single NP-hard step to set up the structure on which inference is performed, as we show by confirming Li and D'Ambrosio's [LD94] conjectured NP-hardness of OFP.
Keywords:
Pages: 16-23
PS Link:
PDF Link: /papers/98/p16-bloemeke.pdf
BibTex:
@INPROCEEDINGS{Bloemeke98,
AUTHOR = "Mark Bloemeke and Marco Valtorta",
TITLE = "A Hybrid Algorithm to Compute Marginal and Joint Beliefs in Bayesian Networks and Its Complexity",
BOOKTITLE = "Proceedings of the Fourteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-98)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1998",
PAGES = "16--23"
}


hosted by DSL   •   site info   •   help