Cost-Sharing in Bayesian Knowledge Bases
This work addresses reasoning efficiency in BKBs, an incremental extension of existing methods to handle cyclic causal graphs.
The paper tackled the problem of applying the cost-sharing heuristic to Bayesian knowledge bases (BKBs), which have cycles that prevent direct use, by reformulating it as a system of equations, resulting in significant performance improvements in empirical evaluations.
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.