.png){kind=icon}
.png){kind=icon}
返回
An optimal approximation algorithm for Bayesian inference
.png){kind=icon}
PRE
AI
DOI：10.1016/S0004-3702(97)00013-1.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Approximating the inference probability Pr[X = x \ E = e] in any sense, even for a single evidence node E, is NP-hard. This result holds for belief networks that are allowed to contain extreme conditional probabilities-that is, conditional probabilities arbitrarily close to 0. Nevertheless, all previous approximation algorithms have failed to approximate efficiently many inferences, even for belief networks without extreme conditional probabilities. We prove that we can approximate efficiently probabilistic inference in belief networks without extreme conditional probabilities. We construct a randomized approximation algorithm-the bounded-variance algorithm-that is a variant of the known likelihood-weighting algorithm. The bounded-variance algorithm is the first algorithm with provably fast inference approximation on all belief networks without extreme conditional probabilities. From the bounded-variance algorithm, we construct a deterministic approximation algorithm using current advances in the theory of pseudorandom generators. In contrast to the exponential worst-case behavior of all previous deterministic approximations, the deterministic bounded-variance algorithm approximates inference probabilities in worst-c:ase time that is subexponential 2((log n)d), for some integer d that is a linear function of the depth of the belief network. (C) 1997 Elsevier Science B.V.
Keyword:
Bayesian inference
approximation
belief networks
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。