一种混合的贝叶斯网结构学习算法

贝叶斯网是人工智能中一个重要的理论模型,也是现实世界中不确定性问题建模的重要工具.针对贝叶斯网的结构学习问题,提出了一种将约束满足、蚁群优化和模拟退火策略相结合的混合算法.新算法首先利用阈值自调整的条件测试来动态地压缩搜索空间,在加速搜索过程的同时保证学习的求解质量;然后在基于MDL的蚁群随机搜索中引入模拟退火的优化调节机制,改进了算法的优化效率.实验结果验证了所提策略的有效性,与最新的同类算法相比,新算法在保持较快收敛速度的前提下具有更好的求解质量.     

A systematic literature review on the applications of Bayesian networks to predict software quality

Bayesian networks (BN) have been used for decision making in software engineering for many years. In other fields such as bioinformatics, BNs are rigorously evaluated in terms of the techniques that are used to build the network structure and to learn the parameters. We extend our prior mapping study to investigate the extent to which contextual and methodological details regarding BN construction are reported in the studies. We conduct a systematic literature review on the applications of BNs to predict software quality. We focus on more detailed questions regarding (1) dataset characteristics, (2) techniques used for parameter learning, (3) techniques used for structure learning, (4) use of tools, and (5) model validation techniques. Results on ten primary studies show that BNs are mostly built based on expert knowledge, i.e. structure and prior distributions are defined by experts, whereas authors benefit from BN tools and quantitative data to validate their models. In most of the papers, authors do not clearly explain their justification for choosing a specific technique, and they do not compare their proposed BNs with other machine learning approaches. There is also a lack of consensus on the performance measures to validate the proposed BNs. Compared to other domains, the use of BNs is still very limited and current publications do not report enough details to replicate the studies. We propose a framework that provides a set of guidelines for reporting the essential contextual and methodological details of BNs. We believe such a framework would be useful to replicate and extend the work on BNs.     

Identification of I‐equivalent subnetworks in Bayesian networks to incorporate experts' knowledge

Bayesian networks (BNs) have been widely used in causal analysis because they can express the statistical relationship between significant variables. To gain superior causal analysis results, numerous studies have emphasized the importance of combining a knowledge‐based approach and a data‐based approach. However, combining these two approaches is a difficult task because it can reduce the effectiveness of the BN structure learning. Further, the learning schemes of BNs for computational efficiency can cause an inadequate causal analysis. To address these problems, we propose a knowledge‐driven BN structure calibration algorithm for rich causal semantics. We first present an algorithm that can efficiently identify the subnetworks that can be altered to satisfy the learning condition of the BNs. We then reflect experts' knowledge to reduce erroneous causalities from the learned network. Experiments on various simulation and benchmark data sets were conducted to examine the properties of the proposed method and to compare its performance with an existing method. Further, an experimental study with real data from semiconductor fabrication plants demonstrated that the proposed method provided superior performance in improving structural accuracy.     

BNC-VLA: bayesian network structure learning using a team of variable-action set learning automata

Bayesian Network (BN) is a probabilistic graphical model which describes the joint probability distribution over a set of random variables. One of the most important challenges in the field of BNs is to find an optimal network structure based on an available training dataset. Since the problem of searching the optimal BN structure belongs to the class of NP-hard problems, typically greedy algorithms are used to solve it. In this paper a learning automata-based algorithm has been proposed to solve the BNs structure learning problem. There is a learning automaton corresponding with each random variable and at each stage of the proposed algorithm, named BNC-VLA, a set of learning automata is randomly activated and determined the graph edges that must be appeared in that stage. Finally, the constructed network is evaluated using a scoring function. As BNC-VLA algorithm proceeds, the learning process focuses on the BN structure with higher scores. The convergence of this algorithm is theoretically proved; and also some experiments are designed to evaluate the performance of it. Experimental results show that BNC-VLA is capable of finding the optimal structure of BN in an acceptable execution time; and comparing against other search-based methods, it outperforms them.     

Predicting football results using Bayesian nets and other machine learning techniques

Bayesian networks (BNs) provide a means for representing, displaying, and making available in a usable form the knowledge of experts in a given field. In this paper, we look at the performance of an expert constructed BN compared with other machine learning (ML) techniques for predicting the outcome (win, lose, or draw) of matches played by Tottenham Hotspur Football Club. The period under study was 1995–1997 – the expert BN was constructed at the start of that period, based almost exclusively on subjective judgement. Our objective was to determine retrospectively the comparative accuracy of the expert BN compared to some alternative ML models that were built using data from the two-year period. The additional ML techniques considered were: MC4, a decision tree learner; Naive Bayesian learner; Data Driven Bayesian (a BN whose structure and node probability tables are learnt entirely from data); and a K-nearest neighbour learner. The results show that the expert BN is generally superior to the other techniques for this domain in predictive accuracy. The results are even more impressive for BNs given that, in a number of key respects, the study assumptions place them at a disadvantage. For example, we have assumed that the BN prediction is ‘incorrect’ if a BN predicts more than one outcome as equally most likely (whereas, in fact, such a prediction would prove valuable to somebody who could place an ‘each way’ bet on the outcome). Although the expert BN has now long been irrelevant (since it contains variables relating to key players who have retired or left the club) the results here tend to confirm the excellent potential of BNs when they are built by a reliable domain expert. The ability to provide accurate predictions without requiring much learning data are an obvious bonus in any domain where data are scarce. Moreover, the BN was relatively simple for the expert to build and its structure could be used again in this and similar types of problems.     

Modeling temporal processes via belief networks and Petri nets,with application to expert systems

We show how Bayesian belief networks (BNs) can be used to model common temporal knowledge. Two approaches to their structuring are proposed. The first leads to BNs with nodes representing states of a process and times spent in such states, and with a graphical structure reflecting the conditional independence assumptions of a Markovian process. A second approach leads to BNs whose topology represents a conditional independence structure between event-times. Once required distributional specifications are stored within the nodes of a BN, this becomes a powerful inference machine capable, for example, of reasoning backwards in time. We discuss computational difficulties associated with propagation algorithms necessary to perform these inferences, and the reasons why we chose to adopt Monte Carlo-based propagation algorithms. Two improvements to existing Monte Carlo algorithms are proposed; an enhancement based on the principle of importance sampling, and a combined technique that exploits both forward and Markov sampling. Finally, we consider Petri nets, a very interesting and general representation of temporal knowledge. A combined approach is proposed, in which the user structures temporal knowledge in Petri net formalism. The obtained Petri net is then automatically translated into an equivalent BN for probability propagation. Inferred conclusions may finally be explained with the aid of Petri nets again.     

Using a Local Discovery Ant Algorithm for Bayesian Network Structure Learning

Bayesian networks (BNs) are knowledge representation tools capable of representing dependence or independence relationships among random variables. Learning the structure of BNs from datasets has received increasing attention in the last two decades, due to the BNs' capacity of providing good inference models and discovering the structure of complex domains. One approach for BNs' structure learning from data is to define a scoring metric that evaluates the quality of the candidate networks, given a dataset, and then apply an optimization procedure to explore the set of candidate networks. Among the most frequently used optimization methods for BN score-based learning is greedy hill climbing (GHC) search. This paper proposes a new local discovery ant colony optimization (ACO) algorithm and a hybrid algorithm max-min ant colony optimization (MMACO), based on the local discovery algorithm max-min parents and children (MMPC) and ACO to learn the structure of a BN. In MMACO, MMPC is used to construct the skeleton of the BN and ACO is used to orientate the skeleton edges, thus returning the final structure. The algorithms are applied to several sets of benchmark networks and are shown to outperform the GHC and simulated annealing algorithms.      

Information integration via hierarchical and hybrid bayesian networks

A collaboration scheme for information integration among multiple agencies (and/or various divisions within a single agency) is designed using hierarchical and hybrid Bayesian networks (HHBNs). In this scheme, raw information is represented by transactions (e.g., communication, travel, and financing) and information entities to be integrated are modeled as random variables (e.g., an event occurs, an effect exists, or an action is undertaken). Each random variable has certain states with probabilities assigned to them. Hierarchical is in terms of the model structure and hybrid stems from our usage of both general Bayesian networks (BNs) and hidden Markov models (HMMs, a special form of dynamic BNs). The general BNs are adopted in the top (decision) layer to address global assessment for a specific question (e.g., "Is target A under terrorist threat?" in the context of counterterrorism). HMMs function in the bottom (observation) layer to report processed evidence to the upper layer BN based on the local information available to a particular agency or a division. A software tool, termed the adaptive safety analysis and monitoring (ASAM) system, is developed to implement HHBNs for information integration either in a centralized or in a distributed fashion. As an example, a terrorist attack scenario gleaned from open sources is modeled and analyzed to illustrate the functionality of the proposed framework.     

Efficient and accurate structural fusion of Bayesian networks

Bayesian Network (BN) fusion provides a precise theoretical framework for aggregating the graphical structure of a set of BNs into a consensus network. The fusion process depends on a total ordering of the variables, but both the problem of searching for an optimal consensus structure (according to the standard problem definition) as well as the one of looking for the optimal ordering are NP-hard.In this paper we start with this theoretical framework and extend it from a practical point of view. The two main methodological contributions we make are: (1) an adaptation of the well-known BN learning algorithm GES (Greedy Equivalence Search) to the case of having a set of BNs as input instead of data (we prove the correctness of the adapted algorithm, i.e., under certain standard assumptions the optimal solution for the BN fusion process is obtained); and (2) a heuristic method for identifying a suitable order of the variables, which allows us to obtain consensus BNs having (far) fewer edges than those obtained by using random orderings.Finally, we design several computational experiments to test our proposals. From the results, we can conclude that the consensus network can be efficiently obtained by using the proposed heuristic to compute the total order of the variables, with this DAG being very close to the optimal one.     

Structural learning of Bayesian networks using local algorithms based on the space of orderings

Structural learning of Bayesian networks (BNs) is an NP-hard problem which is generally addressed by means of heuristic search algorithms. Despite the fact that earlier proposals for dealing with this task were based on searching the space of Directed Acyclic Graphs (DAGs), there are some alternative approaches. One of these approaches for structural learning consists of searching the space of orderings, as given a certain topological order among the problem variables, it is relatively easy to build (and evaluate) a BN compatible with it. In practice, the latter methods make it possible to obtain good results, but they are still costly in terms of computation. In this article, we prove the correctness of the method used to evaluate each ordering, and we propose some efficient learning algorithms based on it. Our first proposal is based on the Hill-Climbing algorithm, and uses an improved neighbourhood definition. The second algorithm is an extension of the first one, and is based on the well-known Variable Neighbourhood Search metaheuristic. Finally, iterative versions of both algorithms are also proposed. The algorithms have been tested over a set of different domains, and have been compared with other methods such as Hill-Climbing in the space of DAGs or Greedy Equivalent Search, in order to study their behaviour in practice.     

Understanding the scalability of Bayesian network inference using clique tree growth curves

One of the main approaches to performing computation in Bayesian networks (BNs) is clique tree clustering and propagation. The clique tree approach consists of propagation in a clique tree compiled from a BN, and while it was introduced in the 1980s, there is still a lack of understanding of how clique tree computation time depends on variations in BN size and structure. In this article, we improve this understanding by developing an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of a BN's non-root nodes to the number of root nodes, and (ii) the expected number of moral edges in their moral graphs. Analytically, we partition the set of cliques in a clique tree into different sets, and introduce a growth curve for the total size of each set. For the special case of bipartite BNs, there are two sets and two growth curves, a mixed clique growth curve and a root clique growth curve. In experiments, where random bipartite BNs generated using the BPART algorithm are studied, we systematically increase the out-degree of the root nodes in bipartite Bayesian networks, by increasing the number of leaf nodes. Surprisingly, root clique growth is well-approximated by Gompertz growth curves, an S-shaped family of curves that has previously been used to describe growth processes in biology, medicine, and neuroscience. We believe that this research improves the understanding of the scaling behavior of clique tree clustering for a certain class of Bayesian networks; presents an aid for trade-off studies of clique tree clustering using growth curves; and ultimately provides a foundation for benchmarking and developing improved BN inference and machine learning algorithms.     

Bayesian Network Models for Web Effort Prediction: A Comparative Study

OBJECTIVE – The objective of this paper is to compare, using a cross-company dataset, several Bayesian Network (BN) models for Web effort estimation. METHOD – Eight BNs were built; four automatically using Hugin and PowerSoft tools with two training sets, each with 130 Web projects from the Tukutuku database; four using a causal graph elicited by a domain expert, with parameters automatically fit using the same training sets used in the automated elicitation (hybrid models). Their accuracy was measured using two validation sets, each containing data on 65 projects, and point estimates. As a benchmark, the BN-based estimates were also compared to estimates obtained using Manual StepWise Regression (MSWR), Case-Based Reasoning (CBR), mean- and median-based effort models. RESULTS – MSWR presented significantly better predictions than any of the BN models built herein, and in addition was the only technique to provide significantly superior predictions to a Median-based effort model. CONCLUSIONS – This paper investigated data-driven and hybrid BN models using project data from the Tukutuku database. Our results suggest that the use of simpler models, such as the median effort, can outperform more complex models, such as BNs. In addition, MSWR seemed to be the only effective technique for Web effort estimation.     

Toward intrusion detection using belief decision trees for big data

Big data refers to datasets that we cannot manage with standard tools and within which lie valuable information previously hidden. New data mining techniques are needed to deal with the increasing size of such data, their complex structure as well as their veracity which is on covering questions of data imperfection and uncertainty. Even though big data veracity is often overlooked, it is very challenging and important for an accurate and reliable mining and knowledge discovery. This paper proposes MapReduce-based belief decision trees for big data as classifiers of uncertain large-scale datasets. The proposed averaging and conjunctive classification approaches are experimented for intrusion detection on KDD’99 massive intrusion dataset. Several granularity attacks’ levels have been considered depending on whether dealing with whole kind of attacks, or grouping them in categories or focusing on distinguishing normal and abnormal connections.     

Learning Bayesian network parameters under incomplete data with domain knowledge

Bayesian networks (BNs) have gained increasing attention in recent years. One key issue in Bayesian networks is parameter learning. When training data is incomplete or sparse or when multiple hidden nodes exist, learning parameters in Bayesian networks becomes extremely difficult. Under these circumstances, the learning algorithms are required to operate in a high-dimensional search space and they could easily get trapped among copious local maxima. This paper presents a learning algorithm to incorporate domain knowledge into the learning to regularize the otherwise ill-posed problem, to limit the search space, and to avoid local optima. Unlike the conventional approaches that typically exploit the quantitative domain knowledge such as prior probability distribution, our method systematically incorporates qualitative constraints on some of the parameters into the learning process. Specifically, the problem is formulated as a constrained optimization problem, where an objective function is defined as a combination of the likelihood function and penalty functions constructed from the qualitative domain knowledge. Then, a gradient-descent procedure is systematically integrated with the E-step and M-step of the EM algorithm, to estimate the parameters iteratively until it converges. The experiments with both synthetic data and real data for facial action recognition show our algorithm improves the accuracy of the learned BN parameters significantly over the conventional EM algorithm.     

复杂系统的图模型多智能体协同故障诊断

为解决复杂、不确定系统的故障诊断实时推理问题,提出了基于图模型-多连片贝叶斯网络架构下多智能体协同推理的故障诊断方法。该方法将一个复杂贝叶斯网分割成若干有重叠的贝叶斯子网,使监控网络的单个智能体被抽象为一个拥有局部知识的贝叶斯网,利用成熟的贝叶斯网推理算法可完成智能体的自主推理。随后,通过重叠的子网接口进行多智能体间消息的传播,实现了多智能体协同故障诊断推理。实验结果表明了基于图模型多智能体的协同故障诊断方法的正确性和有效性。     

A Novel Method for Aggregation of Bayesian Networks without Considering an Ancestral Ordering

A good method of combining Bayesian networks (BNs) should be a generic one that ensures a combined BN meets three important criteria of avoiding cycles, preserving conditional independencies, and preserving the characteristics of individual BN parameters. All combination methods assumed that there is an ancestral ordering shared by individual BNs. If this assumption is violated, then avoiding cycles may be inefficient.

In this paper, without considering an ancestral ordering, we introduce a novel method for aggregation of BNs. For this purpose, we first combine the BNs using the modification of the method introduced by Feng et al. We then use the simulated annealing algorithm for getting an acyclic graph in which the minimum arcs have been removed. Using this method, most of the conditional independencies are preserved. We compare the results of the proposed method with the two classical BNs combination methods; union and intersection, and hence to demonstrate the distinctive advantages of the proposed BNs combination method.     

New skeleton-based approaches for Bayesian structure learning of Bayesian networks

Automatically learning the graph structure of a single Bayesian network (BN) which accurately represents the underlying multivariate probability distribution of a collection of random variables is a challenging task. But obtaining a Bayesian solution to this problem based on computing the posterior probability of the presence of any edge or any directed path between two variables or any other structural feature is a much more involved problem, since it requires averaging over all the possible graph structures. For the former problem, recent advances have shown that search + score approaches find much more accurate structures if the search is constrained by a previously inferred skeleton (i.e. a relaxed structure with undirected edges which can be inferred using local search based methods). Based on similar ideas, we propose two novel skeleton-based approaches to approximate a Bayesian solution to the BN learning problem: a new stochastic search which tries to find directed acyclic graph (DAG) structures with a non-negligible score; and a new Markov chain Monte Carlo method over the DAG space. These two approaches are based on the same idea. In a first step, both employ a previously given skeleton and build a Bayesian solution constrained by this skeleton. In a second step, using the preliminary solution, they try to obtain a new Bayesian approximation but this time in an unconstrained graph space, which is the final outcome of the methods. As shown in the experimental evaluation, this new approach strongly boosts the performance of these two standard techniques proving that the idea of employing a skeleton to constrain the model space is also a successful strategy for performing Bayesian structure learning of BNs.     

Further results for synchronization of two coupled Boolean networks

This paper investigates the complete synchronization of drive-response Boolean networks (BNs ) using the semi-tensor product of matrices. First, a necessary and sufficient condition for complete synchronization is obtained. Next, a pinning control method for achieving complete synchronization of drive-response BNs is proposed, based on certain transformations of the state transition matrix of drive BN . Then, an algorithm is proposed to obtain the minimum number of pinning nodes, based on the perturbation method. Finally, two numerical examples are given to verify the validity of the study results.