.png){kind=icon}
返回
A search problem in complex diagnostic Bayesian networks
.png){kind=icon}
PRE
AI
DOI：10.1016/j.knosys.2011.12.011.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Inference in Bayesian networks (BNs) is NP-hard. We proposed the concept of a node set namely Maximum Quadruple-Constrained subset MQC(A,a - e) to improve the efficiency of exact inference in diagnostic Bayesian networks (DBNs). Here, A denotes a node set in a DBN and a - e represent five real numbers. The improvement in efficiency is achieved by computation sharing. That is, we divide inference in a DBN into the computation of eliminating MQC(A, a - e) and the subsequent computation. For certain complex DBNs and (A, a - e), the former computation covers a major part of the whole computation, and the latter one is highly efficient after sharing the former computation. Searching for MQC(A, a - e) is a combinatorial optimization problem. A backtracking-based exact algorithm Backtracking-Search (BS) was proposed, however the time complexity of BS is O(n(3)2(n)) (n = vertical bar A vertical bar). In this article, we propose the following algorithms for searching for MQC(A, a - e) especially in complex DBNs where vertical bar A vertical bar is large. (i) A divide-and-conquer algorithm Divide-and-Conquer (DC) for dividing the problem of searching for MQC(A, a - e) into sub-problems of searching for MQC(B-1, a - e), ...,MQC(B-m, a - e), where B-i subset of A(1 <= i m, 1 <= m <= vertical bar A vertical bar). (ii) A DC-based heuristic algorithm Heuristic-Search (HS) for searching for MQC(B-i, a - e). The time complexity of HS is O(n(6)) (n = vertical bar B-i vertical bar). Empirical results show that, HS outperforms BS over a range of networks.(C) 2011 Elsevier B.V. All rights reserved.
Keyword:
Diagnostic Bayesian networks
Exact inference
Computation sharing
Inference simplifying
Search
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
K
IF:
7.6
论文数:
1.3W
被引数:
4.5W
机构
引用论文
.png){kind=icon}
查看更多内容