A search problem in complex diagnostic Bayesian networks

详细信息	查看全文 | 推荐本文 |

• 作者：Dayou Liu ; Yuxiao Huang ; Qiangyuan Yu ; Juan Chen ; ^{chenjuan@jlu.edu.cn} ; Haiyang Jia
• 关键词：Diagnostic Bayesian networks ; Exact inference ; Computation sharing ; Inference simplifying ; Search
• 刊名：Knowledge-Based Systems
• 出版年：2012
• 期刊代码：114_09507051
• 类别：et
• 出版时间：June, 2012
• 卷：30
• 期：Complete
• 页码：95-103
• 文件大小：414 K

摘要

Inference in Bayesian networks (BNs) is NP-hard. We proposed the concept of a node set namely Maximum Quadruple-Constrained subset MQC(A, a 鈭?#xA0;e) to improve the efficiency of exact inference in diagnostic Bayesian networks (DBNs). Here, A denotes a node set in a DBN and a 鈭?#xA0;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 鈭?#xA0;e) and the subsequent computation. For certain complex DBNs and (A, a 鈭?#xA0;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 鈭?#xA0;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³2ⁿ) (n = |A|). In this article, we propose the following algorithms for searching for MQC(A, a 鈭?#xA0;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 鈭?#xA0;e) into sub-problems of searching for MQC(B₁, a 鈭?#xA0;e), 鈥?#xA0;, MQC(B_m, a 鈭?#xA0;e), where B_i 鈯?#xA0;A(1 猢?#xA0;i 猢?#xA0;m, 1 猢?#xA0;m 猢?#xA0;|A|). (ii) A DC-based heuristic algorithm Heuristic-Search (HS) for searching for MQC(B_i, a 鈭?#xA0;e). The time complexity of HS is O(n⁶) (n = |B_i|). Empirical results show that, HS outperforms BS over a range of networks.