| Abstract
|
Performance of abductive diagnosis in medi … Performance of abductive diagnosis in medicine can be framed as a searchproblem: Given a set of findings, determine the diagnostic hypothesis (set ofdiseases) that best explains the evidence. Solutions to this problem aredifficult for two reasons. First, since the most probable hypothesis may havemultiple coexisting diseases, the search space is exponential in the number ofpossible diseases. Second, it is difficult to represent and reason withuncertain knowledge. To address these issues, researchers have reasoned inlimited domains using ad hoc evaluation functions to score candidatehypotheses. Recent research has demonstrated the utility of usingprobabilistic networks (belief networks) to manage uncertainty in a normativeframework. However, the problem of calculating the most likely explanationgiven an arbitrary belief network is NP-hard. In this report, we present thenovel approach of using randomized search techniques for solving abductiveproblems in belief networks. Specifically, we use iterative local search,simulated annealing and genetic algorithms to search for the hypothesis withthe highest posterior probability. These methods are approximate algorithmsthat can be applied to arbitrary network topologies in any domain. Resultsfrom an empirical study with a large belief network (the decision-theoreticversion of QMR) show that our algorithms are computationally tractable andconverge to the most likely set of diagnoses. verge to the most likely set of diagnoses.
|
