Abductive Inference Using Probabilistic Networks: Randomized Search Techniques

From Tetherless World Wiki

Jump to: navigation, search

Citation: Richard Lin and Adam Galper and Ross Schachter. (1990) Abductive Inference Using Probabilistic Networks: Randomized Search Techniques. In KSL-90-73, November,1990.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Richard Lin and Adam Galper and Ross Schachter
title Abductive Inference Using Probabilistic Networks: Randomized Search Techniques
number KSL-90-73
institution Knowledge Systems, AI Laboratory
year 1990
month November
Bibtex more
Access Paper
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.

KSL Technical Report ID: KSL-90-73
Facts about Abductive Inference Using Probabilistic Networks: Randomized Search TechniquesRDF feed
Abstract Performance of abductive diagnosis in medi … 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. verge to the most likely set of diagnoses.
Author Richard Lin and Adam Galper and Ross Schachter  +
Bibtype techreport  +
Has author Richard Lin and Adam Galper and Ross Schachter  +
Has identifier KSL-90-73  +
Has publishing details November,1990  +
Has title Abductive Inference Using Probabilistic Networks: Randomized Search Techniques  +
Has where published KSL-90-73  +
Has year 1990  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-90-73  +
Month November  +
Number KSL-90-73  +
Process note NO  +
Title Abductive Inference Using Probabilistic Networks: Randomized Search Techniques  +
Year 1990  +
Retrieved from "http://tw.rpi.edu/wiki/Abductive_Inference_Using_Probabilistic_Networks:_Randomized_Search_Techniques"
Personal tools