Cost-Sharing in Bayesian Knowledge Bases
Solomon Shimony, Carmel Domshlak, Eugene Santos Jr.
Bayesian knowledge bases (BKBs) are a generalization of Bayes networks and weighted proof graphs (WAODAGs), that allow cycles in the causal graph. Reasoning in BKBs requires finding the most probable inferences consistent with the evidence. The cost-sharing heuristic for finding least-cost explanations in WAODAGs was presented and shown to be effective by Charniak and Husain. However, the cycles in BKBs would make the definition of cost-sharing cyclic as well, if applied directly to BKBs. By treating the defining equations of cost-sharing as a system of equations, one can properly define an admissible cost-sharing heuristic for BKBs. Empirical evaluation shows that cost-sharing improves performance significantly when applied to BKBs.
Keywords: Probabilistic reasoning, Bayesian knowledge bases,
belief revision, cost-sharing heu
PS Link: http://www.cs.bgu.ac.il/~shimony/datamining/bkb.ps
PDF Link: /papers/97/p421-shimony.pdf
AUTHOR = "Solomon Shimony
and Carmel Domshlak and Eugene Santos Jr.",
TITLE = "Cost-Sharing in Bayesian Knowledge Bases",
BOOKTITLE = "Proceedings of the Thirteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1997",
PAGES = "421--428"