A Randomized Approximation Algorithm for Logic Sampling

From Tetherless World Wiki

Jump to: navigation, search

Citation: R. Martin Chavez and Gregory F. Cooper. (1990) A Randomized Approximation Algorithm for Logic Sampling. In KSL-90-36, May,1990.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author R. Martin Chavez and Gregory F. Cooper
title A Randomized Approximation Algorithm for Logic Sampling
number KSL-90-36
institution Knowledge Systems, AI Laboratory
address Stanford, CA, USA
year 1990
month May
Bibtex more
Access Paper
abstract In recent years, researchers in decision analysis and artificial intelligence (AI) have used Bayesian belief networks to build models of expert opinion. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of exact probabilistic inference in belief networks almost certainly requires exponential computation in the worst case. We have previously proposed a randomized approximation scheme, called BN-RAS, for computation on belief networks. We gave precise analytic bounds on the convergence of BN-RAS and showed how to trade running time for accuracy in the evaluation of posterior marginal probabilities. We now extend our previous results and demonstrate the generality of our framework by applying similar mathematical techniques to the analysis of convergence for logic sampling, an alternative simulation algorithm for probabilistic inference.

KSL Technical Report ID: KSL-90-36
Facts about A Randomized Approximation Algorithm for Logic SamplingRDF feed
Abstract In recent years, researchers in decision a … In recent years, researchers in decision analysis and artificial intelligence (AI) have used Bayesian belief networks to build models of expert opinion. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of exact probabilistic inference in belief networks almost certainly requires exponential computation in the worst case. We have previously proposed a randomized approximation scheme, called BN-RAS, for computation on belief networks. We gave precise analytic bounds on the convergence of BN-RAS and showed how to trade running time for accuracy in the evaluation of posterior marginal probabilities. We now extend our previous results and demonstrate the generality of our framework by applying similar mathematical techniques to the analysis of convergence for logic sampling, an alternative simulation algorithm for probabilistic inference. ion algorithm for probabilistic inference.
Address Stanford, CA, USA  +
Author R. Martin Chavez and Gregory F. Cooper  +
Bibtype techreport  +
Has author R. Martin Chavez and Gregory F. Cooper  +
Has identifier KSL-90-36  +
Has publishing details May,1990  +
Has title A Randomized Approximation Algorithm for Logic Sampling  +
Has where published KSL-90-36  +
Has year 1990  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-90-36  +
Month May  +
Number KSL-90-36  +
Process note NO  +
Title A Randomized Approximation Algorithm for Logic Sampling  +
Year 1990  +
Retrieved from "http://tw.rpi.edu/wiki/A_Randomized_Approximation_Algorithm_for_Logic_Sampling"
Personal tools