An algorithm for rinding MAPs for belief networks through cost-based abduction

摘要

In cost-based abduction, the objective is to find the least-cost set of hypotheses that are sufficient to explain the observed evidence. In the maximuma-posteriori (MAP) assignment problem on Bayesian belief networks, the objective is to find the network assignment A with highest conditional probability P(A¦ε), where L represents the observed evidence. In this paper, we present a provablycorrect linear-time transformation that allows algorithms and heuristic methods for cost-based abduction, such as Charniak and Shimony's best-first search method or Santos' integer linear programming approach, to be used for the MAP problem.