.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
We introduce an any-space algorithm for exact inference in Bayesian networks, called recursive conditioning. On one extreme, recursive conditioning takes O(n) space and O(n exp(w log n)) time-where n is the size of a Bayesian network and u, is the width of a given elimination order-therefore, establishing a new complexity result for linear-space inference in Bayesian networks. On the other extreme, recursive conditioning takes O(n exp(w)) space and O(n exp(w)) time, therefore, matching the complexity of state-of-the-art algorithms based on clustering and elimination. In between linear and exponential space, recursive conditioning can utilize memory at increments of X-bytes, where X is the number of bytes needed to store a floating point number in a cache. Moreover, the algorithm is equipped with a formula for computing its average running time under any amount of space, hence, providing a valuable tool for time-space tradeoffs in demanding applications. Recursive conditioning is therefore the first algorithm for exact inference in Bayesian networks to offer a smooth tradeoff between time and space, and to explicate a smooth, quantitative relationship between these two important resources. (C) 2001 Elsevier Science B.V. All rights reserved.
Keyword:
Bayesian networks
probabilistic inference
time-space tradeoff
conditioning methods
decompositional reasoning
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
暂无机构信息
引用论文
.png){kind=icon}
查看更多内容