Node order is one of the most important factors in learning the structure of a Bayesian network(BN)for probabilistic reasoning.To improve the BN structure learning,we propose a node order learning algorithmbased on th...Node order is one of the most important factors in learning the structure of a Bayesian network(BN)for probabilistic reasoning.To improve the BN structure learning,we propose a node order learning algorithmbased on the frequently used Bayesian information criterion(BIC)score function.The algorithm dramatically reduces the space of node order and makes the results of BN learning more stable and effective.Specifically,we first find the most dependent node for each individual node,prove analytically that the dependencies are undirected,and then construct undirected subgraphs UG.Secondly,the UG-is examined and connected into a single undirected graph UGC.The relation between the subgraph number and the node number is analyzed.Thirdly,we provide the rules of orienting directions for all edges in UGC,which converts it into a directed acyclic graph(DAG).Further,we rank the DAG’s topology order and describe the BIC-based node order learning algorithm.Its complexity analysis shows that the algorithm can be conducted in linear time with respect to the number of samples,and in polynomial time with respect to the number of variables.Finally,experimental results demonstrate significant performance improvement by comparing with other methods.展开更多
基金The work partially supported by the National Natural Science Foundation of China(Grant Nos.61432011,U1435212,61322211 and 61672332)the Postdoctoral Science Foundation of China(2016M591409)+1 种基金the Natural Science Foundation of Shanxi Province,China(201801D121115 and 2013011016-4)Research Project Supported by Shanxi Scholarship Council of China(2020-095).
文摘Node order is one of the most important factors in learning the structure of a Bayesian network(BN)for probabilistic reasoning.To improve the BN structure learning,we propose a node order learning algorithmbased on the frequently used Bayesian information criterion(BIC)score function.The algorithm dramatically reduces the space of node order and makes the results of BN learning more stable and effective.Specifically,we first find the most dependent node for each individual node,prove analytically that the dependencies are undirected,and then construct undirected subgraphs UG.Secondly,the UG-is examined and connected into a single undirected graph UGC.The relation between the subgraph number and the node number is analyzed.Thirdly,we provide the rules of orienting directions for all edges in UGC,which converts it into a directed acyclic graph(DAG).Further,we rank the DAG’s topology order and describe the BIC-based node order learning algorithm.Its complexity analysis shows that the algorithm can be conducted in linear time with respect to the number of samples,and in polynomial time with respect to the number of variables.Finally,experimental results demonstrate significant performance improvement by comparing with other methods.
