Learning Bayesian network structure is one of the most exciting challenges in machine learning. Discovering a correct skeleton of a directed acyclic graph（DAG） is the foundation for dependency analysis algorithms fo...Learning Bayesian network structure is one of the most exciting challenges in machine learning. Discovering a correct skeleton of a directed acyclic graph（DAG） is the foundation for dependency analysis algorithms for this problem. Considering the unreliability of high order condition independence（CI） tests, and to improve the efficiency of a dependency analysis algorithm, the key steps are to use few numbers of CI tests and reduce the sizes of conditioning sets as much as possible. Based on these reasons and inspired by the algorithm PC, we present an algorithm, named fast and efficient PC（FEPC）, for learning the adjacent neighbourhood of every variable. FEPC implements the CI tests by three kinds of orders, which reduces the high order CI tests significantly. Compared with current algorithm proposals, the experiment results show that FEPC has better accuracy with fewer numbers of condition independence tests and smaller size of conditioning sets. The highest reduction percentage of CI test is 83.3% by EFPC compared with PC algorithm.展开更多
The learning Bayesian network （BN） structure from data is an NP-hard problem and still one of the most exciting chal- lenges in the machine learning. In this work, a novel algorithm is presented which combines ideas...The learning Bayesian network （BN） structure from data is an NP-hard problem and still one of the most exciting chal- lenges in the machine learning. In this work, a novel algorithm is presented which combines ideas from local learning, constraint- based, and search-and-score techniques in a principled and ef- fective way. It first reconstructs the junction tree of a BN and then performs a K2-scoring greedy search to orientate the local edges in the cliques of junction tree. Theoretical and experimental results show the proposed algorithm is capable of handling networks with a large number of variables. Its comparison with the well-known K2 algorithm is also presented.展开更多
To solve the drawbacks of the ant colony optimization for learning Bayesian networks(ACO-B),this paper proposes an improved algorithm based on the conditional independence test and ant colony optimization(I-ACO-B).Fir...To solve the drawbacks of the ant colony optimization for learning Bayesian networks(ACO-B),this paper proposes an improved algorithm based on the conditional independence test and ant colony optimization(I-ACO-B).First,the I-ACO-B uses order-0 independence tests to effectively restrict the space of candidate solutions,so that many unnecessary searches of ants can be avoided.And then,by combining the global score increase of a solution and local mutual information between nodes,a new heuristic function with better heuristic ability is given to induct the process of stochastic searches.The experimental results on the benchmark data sets show that the new algorithm is effective and efficient in large scale databases,and greatly enhances convergence speed compared to the original algorithm.展开更多
Discernment of seismic soil liquefaction is a complex and non-linear procedure that is affected by diversified factors of uncertainties and complexity.The Bayesian belief network(BBN)is an effective tool to present a ...Discernment of seismic soil liquefaction is a complex and non-linear procedure that is affected by diversified factors of uncertainties and complexity.The Bayesian belief network(BBN)is an effective tool to present a suitable framework to handle insights into such uncertainties and cause–effect relationships.The intention of this study is to use a hybrid approach methodology for the development of BBN model based on cone penetration test(CPT)case history records to evaluate seismic soil liquefaction potential.In this hybrid approach,naive model is developed initially only by an interpretive structural modeling(ISM)technique using domain knowledge(DK).Subsequently,some useful information about the naive model are embedded as DK in the K2 algorithm to develop a BBN-K2 and DK model.The results of the BBN models are compared and validated with the available artificial neural network(ANN)and C4.5 decision tree(DT)models and found that the BBN model developed by hybrid approach showed compatible and promising results for liquefaction potential assessment.The BBN model developed by hybrid approach provides a viable tool for geotechnical engineers to assess sites conditions susceptible to seismic soil liquefaction.This study also presents sensitivity analysis of the BBN model based on hybrid approach and the most probable explanation of liquefied sites,owing to know the most likely scenario of the liquefaction phenomenon.展开更多
It's a well-known fact that constraint-based algorithms for learning Bayesian network(BN) structure reckon on a large number of conditional independence(C1) tests.Therefore,it is difficult to learn a BN for indica...It's a well-known fact that constraint-based algorithms for learning Bayesian network(BN) structure reckon on a large number of conditional independence(C1) tests.Therefore,it is difficult to learn a BN for indicating the original causal relations in the true graph.In this paper,a two-phase method for learning equivalence class of BN is introduced.The first phase of the method learns a skeleton of the BN by CI tests.In this way,it reduces the number of tests compared with other existing algorithms and decreases the running time drastically.The second phase of the method orients edges that exist in all BN equivalence classes.Our method is tested on the ALARM network and experimental results show that our approach outperforms the other algorithms.展开更多
Bayesian network is a popular approach to uncertainty knowledge representation and reasoning. Structure learning is the first step to learn a Bayesian network. Score-based methods are one of the most popular ways of l...Bayesian network is a popular approach to uncertainty knowledge representation and reasoning. Structure learning is the first step to learn a Bayesian network. Score-based methods are one of the most popular ways of learning the structure. In most cases, the score of Bayesian network is defined as adding the log-likelihood score and complexity score by using the penalty function. If the penalty function is set unreasonably, it may hurt the performance of structure search. Thus, Bayesian network structure learning is essentially a bi-objective optimization problem. However, the existing bi-objective structure learning algorithms can only be applied to small-scale networks. To this end, this paper proposes a bi-objective evolutionary Bayesian network structure learning algorithm via skeleton constraint (BBS) for the medium-scale networks. To boost the performance of searching, BBS introduces the random order prior (ROP) initial operator. ROP generates a skeleton to constrain the searching space, which is the key to expanding the scale of structure learning problems. Then, the acyclic structures are guaranteed by adding the orders of variables in the initial skeleton. After that, BBS designs the Pareto rank based crossover and skeleton guided mutation operators. The operators operate on the skeleton obtained in ROP to make the search more targeted. Finally, BBS provides a strategy to choose the final solution. The experimental results show that BBS can always find the structure which is closer to the ground truth compared with the single-objective structure learning methods. Furthermore, compared with the existing bi-objective structure learning methods, BBS is scalable and can be applied to medium-scale Bayesian network datasets. On the educational problem of discovering the influencing factors of students’ academic performance, BBS provides higher quality solutions and is featured with the flexibility of solution selection compared with the widely-used Bayesian network structure learning methods.展开更多
When learning the structure of a Bayesian network,the search space expands significantly as the network size and the number of nodes increase,leading to a noticeable decrease in algorithm efficiency.Traditional constr...When learning the structure of a Bayesian network,the search space expands significantly as the network size and the number of nodes increase,leading to a noticeable decrease in algorithm efficiency.Traditional constraint-based methods typically rely on the results of conditional independence tests.However,excessive reliance on these test results can lead to a series of problems,including increased computational complexity and inaccurate results,especially when dealing with large-scale networks where performance bottlenecks are particularly evident.To overcome these challenges,we propose a Markov blanket discovery algorithm based on constrained local neighborhoods for constructing undirected independence graphs.This method uses the Markov blanket discovery algorithm to refine the constraints in the initial search space,sets an appropriate constraint radius,thereby reducing the initial computational cost of the algorithm and effectively narrowing the initial solution range.Specifically,the method first determines the local neighborhood space to limit the search range,thereby reducing the number of possible graph structures that need to be considered.This process not only improves the accuracy of the search space constraints but also significantly reduces the number of conditional independence tests.By performing conditional independence tests within the local neighborhood of each node,the method avoids comprehensive tests across the entire network,greatly reducing computational complexity.At the same time,the setting of the constraint radius further improves computational efficiency while ensuring accuracy.Compared to other algorithms,this method can quickly and efficiently construct undirected independence graphs while maintaining high accuracy.Experimental simulation results show that,this method has significant advantages in obtaining the structure of undirected independence graphs,not only maintaining an accuracy of over 96%but also reducing the number of conditional independence tests by at least 50%.This significant performance improvement is due to the effective constraint on the search space and the fine control of computational costs.展开更多
基金Supported by the National Natural Science Foundation of China(61403290,11301408,11401454)the Foundation for Youths of Shaanxi Province(2014JQ1020)+1 种基金the Foundation of Baoji City(2013R7-3)the Foundation of Baoji University of Arts and Sciences(ZK15081)
文摘Learning Bayesian network structure is one of the most exciting challenges in machine learning. Discovering a correct skeleton of a directed acyclic graph（DAG） is the foundation for dependency analysis algorithms for this problem. Considering the unreliability of high order condition independence（CI） tests, and to improve the efficiency of a dependency analysis algorithm, the key steps are to use few numbers of CI tests and reduce the sizes of conditioning sets as much as possible. Based on these reasons and inspired by the algorithm PC, we present an algorithm, named fast and efficient PC（FEPC）, for learning the adjacent neighbourhood of every variable. FEPC implements the CI tests by three kinds of orders, which reduces the high order CI tests significantly. Compared with current algorithm proposals, the experiment results show that FEPC has better accuracy with fewer numbers of condition independence tests and smaller size of conditioning sets. The highest reduction percentage of CI test is 83.3% by EFPC compared with PC algorithm.
基金supported by the National Natural Science Fundation of China (6097408261075055)the Fundamental Research Funds for the Central Universities (K50510700004)
文摘The learning Bayesian network （BN） structure from data is an NP-hard problem and still one of the most exciting chal- lenges in the machine learning. In this work, a novel algorithm is presented which combines ideas from local learning, constraint- based, and search-and-score techniques in a principled and ef- fective way. It first reconstructs the junction tree of a BN and then performs a K2-scoring greedy search to orientate the local edges in the cliques of junction tree. Theoretical and experimental results show the proposed algorithm is capable of handling networks with a large number of variables. Its comparison with the well-known K2 algorithm is also presented.
基金Supported by National Natural Science Foundation of China(60496322)Natural Science Foundation of Beijing(4083034)Scientific Research Common Program of Beijing Municipal Commission.of Education(KM200610005020)
文摘To solve the drawbacks of the ant colony optimization for learning Bayesian networks(ACO-B),this paper proposes an improved algorithm based on the conditional independence test and ant colony optimization(I-ACO-B).First,the I-ACO-B uses order-0 independence tests to effectively restrict the space of candidate solutions,so that many unnecessary searches of ants can be avoided.And then,by combining the global score increase of a solution and local mutual information between nodes,a new heuristic function with better heuristic ability is given to induct the process of stochastic searches.The experimental results on the benchmark data sets show that the new algorithm is effective and efficient in large scale databases,and greatly enhances convergence speed compared to the original algorithm.
基金Projects(2016YFE0200100,2018YFC1505300-5.3)supported by the National Key Research&Development Plan of ChinaProject(51639002)supported by the Key Program of National Natural Science Foundation of China
文摘Discernment of seismic soil liquefaction is a complex and non-linear procedure that is affected by diversified factors of uncertainties and complexity.The Bayesian belief network(BBN)is an effective tool to present a suitable framework to handle insights into such uncertainties and cause–effect relationships.The intention of this study is to use a hybrid approach methodology for the development of BBN model based on cone penetration test(CPT)case history records to evaluate seismic soil liquefaction potential.In this hybrid approach,naive model is developed initially only by an interpretive structural modeling(ISM)technique using domain knowledge(DK).Subsequently,some useful information about the naive model are embedded as DK in the K2 algorithm to develop a BBN-K2 and DK model.The results of the BBN models are compared and validated with the available artificial neural network(ANN)and C4.5 decision tree(DT)models and found that the BBN model developed by hybrid approach showed compatible and promising results for liquefaction potential assessment.The BBN model developed by hybrid approach provides a viable tool for geotechnical engineers to assess sites conditions susceptible to seismic soil liquefaction.This study also presents sensitivity analysis of the BBN model based on hybrid approach and the most probable explanation of liquefied sites,owing to know the most likely scenario of the liquefaction phenomenon.
文摘It's a well-known fact that constraint-based algorithms for learning Bayesian network(BN) structure reckon on a large number of conditional independence(C1) tests.Therefore,it is difficult to learn a BN for indicating the original causal relations in the true graph.In this paper,a two-phase method for learning equivalence class of BN is introduced.The first phase of the method learns a skeleton of the BN by CI tests.In this way,it reduces the number of tests compared with other existing algorithms and decreases the running time drastically.The second phase of the method orients edges that exist in all BN equivalence classes.Our method is tested on the ALARM network and experimental results show that our approach outperforms the other algorithms.
基金supported by the Fundamental Research Funds for the Central Universities,the Science and Technology Commission of Shanghai Municipality(No.19511120601)the Scientific and Technological Innovation 2030 Major Projects(No.2018AAA0100902)+1 种基金the CCF-AFSG Research Fund(No.CCF-AFSG RF20220205)the“Chenguang Program”sponsored by Shanghai Education Development Foundation and Shanghai Municipal Education Commission(No.21CGA32).
文摘Bayesian network is a popular approach to uncertainty knowledge representation and reasoning. Structure learning is the first step to learn a Bayesian network. Score-based methods are one of the most popular ways of learning the structure. In most cases, the score of Bayesian network is defined as adding the log-likelihood score and complexity score by using the penalty function. If the penalty function is set unreasonably, it may hurt the performance of structure search. Thus, Bayesian network structure learning is essentially a bi-objective optimization problem. However, the existing bi-objective structure learning algorithms can only be applied to small-scale networks. To this end, this paper proposes a bi-objective evolutionary Bayesian network structure learning algorithm via skeleton constraint (BBS) for the medium-scale networks. To boost the performance of searching, BBS introduces the random order prior (ROP) initial operator. ROP generates a skeleton to constrain the searching space, which is the key to expanding the scale of structure learning problems. Then, the acyclic structures are guaranteed by adding the orders of variables in the initial skeleton. After that, BBS designs the Pareto rank based crossover and skeleton guided mutation operators. The operators operate on the skeleton obtained in ROP to make the search more targeted. Finally, BBS provides a strategy to choose the final solution. The experimental results show that BBS can always find the structure which is closer to the ground truth compared with the single-objective structure learning methods. Furthermore, compared with the existing bi-objective structure learning methods, BBS is scalable and can be applied to medium-scale Bayesian network datasets. On the educational problem of discovering the influencing factors of students’ academic performance, BBS provides higher quality solutions and is featured with the flexibility of solution selection compared with the widely-used Bayesian network structure learning methods.
基金This work is supported by the National Natural Science Foundation of China(62262016,61961160706,62231010)14th Five-Year Plan Civil Aerospace Technology Preliminary Research Project(D040405)the National Key Laboratory Foundation 2022-JCJQ-LB-006(Grant No.6142411212201).
文摘When learning the structure of a Bayesian network,the search space expands significantly as the network size and the number of nodes increase,leading to a noticeable decrease in algorithm efficiency.Traditional constraint-based methods typically rely on the results of conditional independence tests.However,excessive reliance on these test results can lead to a series of problems,including increased computational complexity and inaccurate results,especially when dealing with large-scale networks where performance bottlenecks are particularly evident.To overcome these challenges,we propose a Markov blanket discovery algorithm based on constrained local neighborhoods for constructing undirected independence graphs.This method uses the Markov blanket discovery algorithm to refine the constraints in the initial search space,sets an appropriate constraint radius,thereby reducing the initial computational cost of the algorithm and effectively narrowing the initial solution range.Specifically,the method first determines the local neighborhood space to limit the search range,thereby reducing the number of possible graph structures that need to be considered.This process not only improves the accuracy of the search space constraints but also significantly reduces the number of conditional independence tests.By performing conditional independence tests within the local neighborhood of each node,the method avoids comprehensive tests across the entire network,greatly reducing computational complexity.At the same time,the setting of the constraint radius further improves computational efficiency while ensuring accuracy.Compared to other algorithms,this method can quickly and efficiently construct undirected independence graphs while maintaining high accuracy.Experimental simulation results show that,this method has significant advantages in obtaining the structure of undirected independence graphs,not only maintaining an accuracy of over 96%but also reducing the number of conditional independence tests by at least 50%.This significant performance improvement is due to the effective constraint on the search space and the fine control of computational costs.
