Cost-Sharing in Bayesian Knowledge Bases

Author(s):

Solomon Eyal Shimony
Ben-Gurion University - Math. and Comp. Sci. Dept.
P. O. Box 653
84105 Be'er Sheva, Israel
e-mail: shimony@cs.bgu.ac.il
Phone: +972-7-461653
FAX : +972-7-472909

Eugene Santos Jr.
Air Force Institute of Technology, Wright-Patterson Air Force Base
Dept. of Elec. and Comp. Eng. Air Force Inst. of Tech.
Wright-Patterson AFB, OH 45433-7765
e-mail: esantos@afit.af.mil

Carmel Domshlak
Ben-Gurion University - Math. and Comp. Sci. Dept.
P. O. Box 653
84105 Be'er Sheva, Israel
e-mail: carmel@cs.bgu.ac.il
FAX : +972-7-472909

Abstract:

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 Heuristic Search.

Availability:

This paper is also available in (PostScript) format.

BACK dsl@sis.pitt.edu / Last update: 22 May 1997