مشکل جستجو در شبکه های بیزی تشخیصی پیچیده

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(n32n) (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(B1, a − e), … , MQC(Bm, a − e), where Bi ⊆ A(1 ⩽ i ⩽ m, 1 ⩽ m ⩽ |A|). (ii) A DC-based heuristic algorithm Heuristic-Search (HS) for searching for MQC(Bi, a − e). The time complexity of HS is O(n6) (n = |Bi|). Empirical results show that, HS outperforms BS over a range of networks.

Bayesian networks (BNs) [1] play a central role in a wide range of automated inference applications, including in diagnosis [2], [3], [4], [5], [6], [7], [8], [9], [10] and [11]. In diagnostic Bayesian networks (DBNs), nodes are divided into three categories: the diagnostic nodes D, the measurement nodes M, and the intermediate nodes I [4] 1. Inference in DBNs is to compute the posterior probability for a set of diagnostic variables Q(Q ⊆ D), given the observations e to a set of measurement variables E(E ⊆ M) 2. Inference in BNs includes exact and approximate inference, and both exact and approximate inference are NP-hard [12], [13] and [14]. In this article, we only study the exact one, and term “inference” hereafter refers to exact inference. To improve the efficiency of inference in DBNs, Huang et al. [15] proposed the concept of a node set namely Maximum Quadruple-Constrained subset MQC(A, a − e), where A ⊆ I and a − e denote five real numbers. For simplicity, in the rest of this article, we shorten the notation MQC(A, a − e) to MQC. The improvement in efficiency is accomplished by sharing the computation of eliminating MQC. Specifically, for a query P(Q|E = e) in a DBN, we can divide the inference of computing P(Q|E = e) into the inference of eliminating MQC and the subsequent inference, that is, the one of eliminating N − MQC − (Q ∪ E). Here, we let N be the node set of a DBN, that is, N = D ∪ M ∪ I. For certain complex DBNs and (A, a − e), the former inference covers a major part of the total computation (computing P(Q|E = e)), and the latter one is highly efficient after sharing the former computation. We can see this in Example 3. Moreover, if we eliminate MQC offline and eliminate the remaining variables online, then (i) all P(Q|E = e) can be computed online, and (ii) there are circumstances where online inference can be highly efficient. Note that one might also divide inference into offline and online inference in certain conventional inference algorithms, for instance, Clique Tree Propagation (CTP) [1], [16], [17] and [18] 3. Consequently, the efficiency of online inference can also be improved through sharing the offline computation. However, the improvement in these algorithms can not be as enormous as in ours; see this in Example 3. It is because the offline inference in the algorithms can not carry out most of the computation. Our offline–online method might find applications in complex tasks that need to be executed in real-time, for instance, object tracking in video sequences. The problems of choosing (A, a − e) and searching for the corresponding MQC especially in complex DBNs are critical. In this article, we focus on the study of algorithms for searching for MQC when (A, a − e) is given. We will discuss the algorithms for choosing (A, a − e) in another work. Searching for MQC is a combinatorial optimization problem [15]. Huang et al. [15] proposed a backtracking-based exact algorithm Backtracking-Search (BS) for searching for MQC. The time complexity of BS is O(n32n) (n = |A|), therefore it is computationally hard to use BS when |A| is large. In this article, we propose two algorithms for searching for MQC particularly 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 into sub-problems of searching for MQC (B 1, a − e ), … , MQC (Bm , a − e ), where Bi ⊆ A (1 ⩽ i ⩽ m , 1 ⩽ m ⩽|A |). (ii) A DC-based heuristic algorithm Heuristic-Search (HS) for searching for MQC (Bi , a − e ). The time complexity of HS is O(n 6) (n = |Bi |), and that of DC is View the MathML sourceO(n12+n1n232n2) or View the MathML sourceO(n12+n1n26) (n1 = |A|, n2 = max(|B1|, … , |Bm|)) when searching for MQC(Bi) using BS or HS respectively. Based on computational experiments, it is shown that HS is superior to BS over a range of networks. The remainder of this article is organized as follows. We give a compact introduction to the topic of BN in Section 2. The definition of MQC and the idea of BS will also be provided in this section. We propose algorithm DC and HS in Sections 3 and 4. Empirical results are reported in Section 5. Conclusion and future work are discussed in Section 6.

MQC is a parameterized node set which can be an advantage to inference particularly in complex DBNs. If we divide inference in a DBN into the computation of eliminating MQC and the subsequent computation, then the latter computation can be highly efficient after sharing the former one, which may cover a major part of the whole computation. Searching for MQC is a combinatorial optimization problem, and an exact algorithm BS was proposed for the problem. The time complexity of BS is O(n32n) (n = |A|). In this article, we propose divide-and-conquer algorithm DC and heuristic algorithm HS for searching for MQC especially in complex DBNs where |A| is large. Specifically, we use DC to divide the problem of searching for MQC into sub-problems of searching for MQC (B ). The time complexity of DC is View the MathML sourceO(n12+n1n232n2) (n1 = |A|, n2 = max({|B||B ∈ CMC(MSC(A, a))})) when searching for MQC(B) using BS. The complexity is significantly less than that of BS searching for MQC if n2 << n1. HS is based on DC, and is used to search for MQC (B ). The time complexity of HS is O(n 6) (n = |B |), and the time complexity of DC is View the MathML sourceO(n12+n1n26) (n1 = |A|, n2 = max({|B||B ∈ CMC(MSC(A, a))})) when searching for MQC(B) using HS. Empirical results show that, (i) HS possesses the ability to find MQC(B), and (ii) the efficiency of HS is significantly superior to that of BS particularly when |B| is large. Future work is as follows: (i) to better evaluate the performance of BS and HS, we will study more comprehensive partitions of the problem space, and more networks which are statistically representative of the partitions; (ii) the efficiency of HS is greatly lowered by traversing h from |B| − 1 to |MQC(B)| + 1 and searching for QC. We will study heuristic algorithm which does not depend on the traversing and searching strategy. We believe such algorithm will outperform HS.