Name
Abstract | ||
|---|---|---|
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^32^n) (n=|A|). In this article, we propose the following algorithms for searching for MQC(A,a-e) especially in complex DBNs where |A| 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@?A(1= |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.knosys.2011.12.011 | Knowl.-Based Syst. |
Keywords | Field | DocType |
combinatorial optimization problem,complex dbns,exact inference,computation sharing,search problem,complex diagnostic bayesian network,bayesian network,subsequent computation,backtracking-based exact algorithm,certain complex dbns,whole computation,former computation | Data mining,Computer science,Theoretical computer science,Artificial intelligence,Search problem,Time complexity,Backtracking,Real number,Computation,Exact algorithm,Inference,Bayesian network,Machine learning | Journal |
Volume | ISSN | Citations |
30, | 0950-7051 | 2 |
PageRank | References | Authors |
0.37 | 21 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dayou Liu | 1 | 814 | 68.17 |
| Yuxiao Huang | 2 | 10 | 2.25 |
| Qiangyuan Yu | 3 | 41 | 2.93 |
| Juan Chen | 4 | 48 | 10.69 |
| Haiyang Jia | 5 | 28 | 5.49 |