استراتژی های موثر برای هرس شاخه و یادگیری ساختار شبکه های بیزی محدود از داده ها

In this paper, designing a Bayesian network structure to maximize a score function based on learning from data strategy is studied. The scoring function is considered to be a decomposable one such as BDeu, BIC, BD, BDe or AIC. Optimal design of such a network is known to be an NP-hard problem and the solution becomes rapidly infeasible as the number of variables (i.e., nodes in the network) increases. Several methods such as hill-climbing, dynamic programming, and branch and bound techniques are proposed to tackle this problem. However, these techniques either produce sub-optimal solutions or the time required to produce an optimal solution is unacceptable. The challenge of the latter solutions is to reduce the computation time necessary for large-size problems. In this study, a new branch and bound method called PBB (pruned brand and bound) is proposed which is expected to find the globally optimal network structure with respect to a given score function. It is an any-time method, i.e., if it is externally stopped, it gives the best solution found until that time. Several pruning strategies are proposed to reduce the number of nodes created in the branch and bound tree. Practical experiments show the effectiveness of these pruning strategies. The performance of PBB, on several common datasets, is compared with the latest state-of-the-art methods. The results show its superiority in many aspects, especially, in the required running time, and the number of created nodes of the branch and bound tree.

A Bayesian network or Belief Network (BN) is a probabilistic graphical model that represents conditional independencies between a set of random variables. It is first introduced by Pearl in [1]. It was a directed acyclic graph (DAG) where nodes stand for random variables and edges stand for conditional independencies. The random variables can be discrete, continuous, or both. Bayesian networks are used for modelling knowledge in computational biology and bio-informatics [2], medicine [3], information retrieval [4], and decision support systems [5], etc. They are used for predicting desired outputs in uncertain environments. One of the advantages of BNs compared to other methods is their support of uncertainty. Bayesian network structure learning from data has attracted a great deal of research in recent years. Finding the best structure for a Bayesian network is known to be NP-Hard [6] and [7]. The number of possible structures is View the MathML sourceO(n!2(n2)) [8], where nn is the number of variables (nodes in the Bayesian Network). Consequently, much of the research has focused on methods that find suboptimal solutions. Generally, there are several approaches to learn a structure. Some methods are based on scoring functions that depend on the data (called scoring-based methods) and some approaches are based on statistical similarities among variables (called constraint-based methods). However, there is some research that makes use of both of these such as [9]. Heckerman et al. [10] compare these two general approaches for learning BNs, and show that the scoring-based methods often have certain advantages over the constraint-based methods. We focus on those methods that are based on scoring functions and try to find the optimal solution with respect to this function. The rest of the paper is organized as follows: In Section 2, the related work of Bayesian network structure learning is discussed. In Section 3, the Bayesian networks and scoring functions (i.e. problem description) are introduced. The proposed method i.e. PBB, the branching function and the pruning rules, are explained in Section 4. The performance of PBB through experiments is shown in Section 5 and the paper ends with new ideas for future work in Section 6.

In this study, learning the Bayesian network structure from data for discrete variables is studied. The presented method, i.e. PBB, is also applicable to continuous ones, if the score of the continuous variables is computed, first. The new branch and bound method guarantees global optimality with respect to a decomposable scoring function. It is an any-time method, i.e., if stopped, it provides the best solution found so far. Several effective bounding rules such as “unpromising”, “non-parent”, “irremovable-cycle” and “future-worse-score” nodes are stated and proven to effectively prune the branch and bound tree. The branching method and also bounding rules of the PBB method are totally different in comparison to the previously presented branch and bound methods for finding the optimal Bayesian network structure. Several common datasets are used to demonstrate the efficacy of the PBB method. In practice, the bounding rules, invented here, for the PBB method demonstrate a drastic reduction in the number of created nodes of the branch and bound tree. The result of the PBB method is compared with a latest state-of-the-art method that was shown to have better performance than prior methods. The PBB method always led to the best score in less running time while generating a smaller number of nodes for the branch and bound tree. Furthermore, it leads to the best result in fewer numbers of nodes for the first time. Therefore, before the algorithm stops it most likely reaches the global optimal result. Several aspects remain for future work, such as applying other criteria to avoid unnecessary computations of local scores. In addition, new bounding rules and selection functions could be sought to circumvent creating unneeded branch and bound tree nodes in order to reduce search space and required memory.