Cost-Sharing in Bayesian Knowledge Bases

Abstract

Bayesian knowledge bases (BKBs) are a gen­ eralization of Bayes networks and weighted proof graphs (WAODAGs), that allow cycles in the causal graph. Reasoning in BKBs re­ quires finding the most probable inferences consistent with the evidence. The cost­ sharing heuristic for finding least-cost ex­ planations in WAODAGs was presented and shown to be effective by Charniak and Hu­ sain. However, the cycles in BKBs would make the definition of cost-sharing cyclic as well, if applied directly to BKBs. By treat­ ing the defining equations of cost-sharing as a system of equations, one can properly de­ fine an admissible cost-sharing heuristic for BKBs. Empirical evaluation shows that cost­ sharing improves performance significantly when applied to BKBs.