Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard

From Tetherless World Wiki

Jump to: navigation, search

Citation: Paul Dagum and Michael Luby. (1993) Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard. In KSL-91-53, April,1993.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Paul Dagum and Michael Luby
title Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard
number KSL-91-53
institution Knowledge Systems, AI Laboratory
year 1993
month April
Bibtex more
Access Paper
abstract [[abstract::It is known that exact computation of probabilistic inference is NP-hard, [Cooper90]. For inferences that are not conditioned on any evidence nodes, it is relatively straightforward to get approximations in polynomial time with absolute error e and probability of failure d. However, the effort directed at finding efficient approximation algorithms for general inferences, i.e., inferences conditioned on evidence, has been met with little success. Polynomial time algorithms that approximate inferences with absolute or relative bounds have been constructed for special case belief networks only. We prove that even approximating probabilistic inference conditioned on evidence in general belief networks is NP-hard. We prove that if P is not equal to NP, there does not exist an algorithm that can output an estimate Z such that for some e<1/2, Pr[x|It is known that exact computation of probabilistic inference is NP-hard, [Cooper90]. For inferences that are not conditioned on any evidence nodes, it is relatively straightforward to get approximations in polynomial time with absolute error e and probability of failure d. However, the effort directed at finding efficient approximation algorithms for general inferences, i.e., inferences conditioned on evidence, has been met with little success. Polynomial time algorithms that approximate inferences with absolute or relative bounds have been constructed for special case belief networks only. We prove that even approximating probabilistic inference conditioned on evidence in general belief networks is NP-hard. We prove that if P is not equal to NP, there does not exist an algorithm that can output an estimate Z such that for some e<1/2, Pr[x]]

KSL Technical Report ID: KSL-91-53
Facts about Approximating Probabilistic Inference in Bayesian Belief Networks is NP-HardRDF feed
Author Paul Dagum and Michael Luby  +
Bibtype techreport  +
Has author Paul Dagum and Michael Luby  +
Has identifier KSL-91-53  +
Has publishing details April,1993  +
Has title Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard  +
Has where published KSL-91-53  +
Has year 1993  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-91-53  +
Month April  +
Number KSL-91-53  +
Process note YES  +
Title Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard  +
Year 1993  +
Retrieved from "http://tw.rpi.edu/wiki/Approximating_Probabilistic_Inference_in_Bayesian_Belief_Networks_is_NP-Hard"
Personal tools