Reference: Lin, R.; Galper, A.; & Schachter, R. Abductive Inference Using Probabilistic Networks: Randomized Search Techniques. KSL, November, 1990.
Abstract: Performance of abductive diagnosis in medicine can be framed as a search problem: Given a set of findings, determine the diagnostic hypothesis (set of diseases) that best explains the evidence. Solutions to this problem are difficult for two reasons. First, since the most probable hypothesis may have multiple coexisting diseases, the search space is exponential in the number of possible diseases. Second, it is difficult to represent and reason with uncertain knowledge. To address these issues, researchers have reasoned in limited domains using ad hoc evaluation functions to score candidate hypotheses. Recent research has demonstrated the utility of using probabilistic networks (belief networks) to manage uncertainty in a normative framework. However, the problem of calculating the most likely explanation given an arbitrary belief network is NP-hard. In this report, we present the novel approach of using randomized search techniques for solving abductive problems in belief networks. Specifically, we use iterative local search, simulated annealing and genetic algorithms to search for the hypothesis with the highest posterior probability. These methods are approximate algorithms that can be applied to arbitrary network topologies in any domain. Results from an empirical study with a large belief network (the decision-theoretic version of QMR) show that our algorithms are computationally tractable and converge to the most likely set of diagnoses.