Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2021, Vol. 15 Issue (6) : 156337    https://doi.org/10.1007/s11704-020-0268-6
RESEARCH ARTICLE
BIC-based node order learning for improving Bayesian network structure learning
Yali LV1,2, Junzhong MIAO1, Jiye LIANG2, Ling CHEN3, Yuhua QIAN2,4()
1. Shanxi University of Finance & Economics, Taiyuan 030031, China
2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006, China
3. The Center for Artificial Intelligence, University of Technology Sydney, New SouthWales 2007, Australia
4. Institute of Big Data Science & Industry, Shanxi University, Taiyuan 030006, China
 Download: PDF(631 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

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.

Keywords probabilistic reasoning      Bayesian networks      node order learning      structure learning      BIC scores      V-structure     
Corresponding Author(s): Yuhua QIAN   
About author:

Just Accepted Date: 05 February 2021   Issue Date: 07 September 2021
 Cite this article:   
Yali LV,Junzhong MIAO,Jiye LIANG, et al. BIC-based node order learning for improving Bayesian network structure learning[J]. Front. Comput. Sci., 2021, 15(6): 156337.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-0268-6
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I6/156337
1 P Judea. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Mateo, California, 1988
2 N Friedman. Inferring cellular networks using probabilistic graphical models. Science, 2004, 303(5659): 799–805
https://doi.org/10.1126/science.1094068
3 A Raval, Z Ghahramani, D L Wild. A Bayesian network model for protein fold and remote homologue recognition. Bioinformatics, 2002, 18(6): 788–801
https://doi.org/10.1093/bioinformatics/18.6.788
4 W Chen, B Zhu, H Zhang. BN-mapping: visual analysis of geospatial data with Bayesian network. Chinese Journal of Computers, 2016, 39(7): 1281–1293
5 P Peng, Y Tian, Y Wang, J Li, T Huang. Robust multiple cameras pedestrian detection with multi-view Bayesian network. Pattern Recognition, 2015, 48(5): 1760–1772
https://doi.org/10.1016/j.patcog.2014.12.004
6 L Liu, S Wang, G Su, Z Huang, M Liu. Towards complex activity recognition using a Bayesian network-based probabilistic generative framework. Pattern Recognition, 2017, 68: 295–309
https://doi.org/10.1016/j.patcog.2017.02.028
7 G Oatley, B Ewart. Crimes analysis software: ‘pins in maps’, clustering and Bayes net prediction. Expert Systems with Applications, 2003, 25(4): 569–588
https://doi.org/10.1016/S0957-4174(03)00097-6
8 D M Chickering, D Heckerman, C Meek. Learning Bayesian networks is NP-hard. Technical Report, MSR-TR-94-17, Microsoft Research, Microsoft Corporation, 1994
9 D M Chickering, D Heckerman, C Meek. Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research, 2004, 5: 1287–1330
10 H Bouhamed, A Masmoudi, T Lecroq, A Rebai. Structure space of Bayesian networks is dramatically reduced by subdividing it in subnetworks. Journal of Computational and Applied Mathematics, 2015, 287: 48–62
https://doi.org/10.1016/j.cam.2015.02.055
11 D Heckerman, D Geiger, D M Chickering. Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning, 1995, 20: 197–243
https://doi.org/10.1007/BF00994016
12 W Lam, F Bacchus. Learning Bayesian belief networks: an approach based on the MDL principle. Computational Intelligence, 1994, 10(3): 269–293
https://doi.org/10.1111/j.1467-8640.1994.tb00166.x
13 M Scanagatta, G Corani, C P De Campos, M Zaffalon. Approximate structure learning for large Bayesian networks. Machine Learning, 2018, 107: 1209–1227
https://doi.org/10.1007/s10994-018-5701-9
14 C P De Campos, M Scanagatta, G Corani, M Zaffalon. Entropy-based pruning for learning Bayesian networks using BIC. Artificial Intelligence, 2018, 260: 42–50
https://doi.org/10.1016/j.artint.2018.04.002
15 G F Cooper, E H Herskovits. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 1992, 9: 309–347
https://doi.org/10.1007/BF00994110
16 M Scanagatta, G Corani, M Zaffalon, J Yoo, U Kang. Efficient learning of bounded-treewidth Bayesian networks from complete and incomplete data sets. International Journal of Approximate Reasoning, 2018, 95: 152–166
https://doi.org/10.1016/j.ijar.2018.02.004
17 S Nie, C P De Campos, Q Ji. Learning Bayesian networks with bounded treewidth via guided search. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. 2016, 3294–3300
18 P Parviainen, H S Farahani, J Lagergren. Learning bounded treewidth Bayesian networks using integer linear programming. In: Proceedings of the 17th International Conference on Artificial Intelligence and Statistics. 2014, 751–759
19 G Elidan, S Gould. Learning bounded treewidth Bayesian networks. Journal of Machine Learning Research, 2008, 9: 2699–2731
20 T Niinimaki, P Parviainen, M Koivisto. Structure discovery in Bayesian networks by sampling partial orders. Journal of Machine Learning Research, 2016, 17(1): 2002–2048
21 M Teyssier, D Koller. Ordering-based search: a simple and effective algorithm for learning Bayesian networks. In: Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence. 2005, 584–590
22 M Scanagatta, C P De Campos, G Corani, M Zaffalon. Learning Bayesian networks with thousands of variables. Neural Information Processing Systems, 2015, 28: 1855–1863
23 X Chen, G Anantha, X Lin. Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(5): 1–13
https://doi.org/10.1109/TKDE.2007.190732
24 S Ko, D Kim. An efficient node ordering method using the conditional frequency for the K2 algorithm. Pattern Recognition Letters, 2014, 40: 80–87
https://doi.org/10.1016/j.patrec.2013.12.021
25 W H Hsu, H Guo, B B Perry, J A Stilson. A permutation genetic algorithm for variable ordering in learning Bayesian networks from data. In: Proceedings of the Genetic and Evolutionary Computation Conference. 2002, 383–390
26 Y W Park, D Klabjan. Bayesian network learning via topological order. Journal of Machine Learning Research, 2017, 18: 1–32
27 L Zhang, H Guo. Introduction to Bayesian Networks. Science Press, 2006
28 N L Zhang, L Yan. Independence of causal influence and clique tree propagation. International Journal of Approximate Reasoning, 1998, 19(3–4): 335–349
https://doi.org/10.1016/S0888-613X(98)10014-2
29 R Mateescu, K Kask, V Gogate, R Dechter. Join-graph propagation algorithms. Journal of Artificial Intelligence Research, 2010, 37: 279–328
https://doi.org/10.1613/jair.2842
30 R J Goudie, S Mukherjee. A Gibbs sampler for learning DAGs. Journal of Machine Learning Research, 2016, 17: 1–39
31 M Benjumeda, C Bielza, P Larranaga. Learning tractable Bayesian networks in the space of elimination orders. Artificial Intelligence, 2019, 274: 66–90
https://doi.org/10.1016/j.artint.2018.11.007
32 M Benjumeda, S Luengosanchez, P Larranaga, C Bielza. Tractable learning of Bayesian networks from partially observed data. Pattern Recognition, 2019, 91: 190–199
https://doi.org/10.1016/j.patcog.2019.02.025
33 I Tsamardinos, L E Brown, C F Aliferis. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 2006, 65: 31–78
https://doi.org/10.1007/s10994-006-6889-7
34 Y Lv, J Wu, J Liang, Y Qian. Random search learning algorithm of BN based on super-structure. Journal of Computer Research and Development, 2017, 54(11): 2558–2566
35 X Qi, X Fan, Y Gao, Y Liu. Learning Bayesian network structures using weakest mutual-information-first strategy. International Journal of Approximate Reasoning, 2019, 114: 84–98
https://doi.org/10.1016/j.ijar.2019.08.004
36 T Talvitie, R Eggeling, M Koivisto. Learning Bayesian networks with local structure, mixed variables, and exact algorithms. International Journal of Approximate Reasoning, 2019, 115: 69–95
https://doi.org/10.1016/j.ijar.2019.09.002
37 M Scutari, C E Graafland, J M Gutiérrez. Who learns better Bayesian network structures: accuracy and speed of structure learning algorithms. International Journal of Approximate Reasoning, 2019, 115: 235–253
https://doi.org/10.1016/j.ijar.2019.10.003
38 Q L Ye, A A Amini, Q Zhou. Optimizing regularized cholesky score for order-based learning of Bayesian networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020,
https://doi.org/10.1109/TPAMI.2020.2990820
39 S Lee, S B Kim. Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(6): 1157–1166
https://doi.org/10.1109/TKDE.2019.2899096
40 T Yao, A Choi, A Darwiche. Learning Bayesian network parameters under equivalence constraints. Artificial Intelligence, 2017, 244: 239–257
https://doi.org/10.1016/j.artint.2015.05.007
41 C Riggelsen. Learning parameters of Bayesian networks from incomplete data via importance sampling. International Journal of Approximate Reasoning, 2006, 42: 69–83
https://doi.org/10.1016/j.ijar.2005.10.005
42 R S Niculescu, T M Mitchell, R B Rao. Bayesian network learning with parameter constraints. Journal of Machine Learning Research, 2006, 7: 1357–1383
43 Y Yang, X Gao, Z Guo, D Chen. Learning Bayesian networks using the constrained maximum a posteriori probability method. Pattern Recognition, 2019, 91: 123–134
https://doi.org/10.1016/j.patcog.2019.02.006
44 M Benjumeda, C Bielza, P Larranaga. Tractability of most probable explanations in multidimensional Bayesian network classifiers. International Journal of Approximate Reasoning, 2018, 93: 74–87
https://doi.org/10.1016/j.ijar.2017.10.024
45 A L Madsen, F Jensen, A Salmeron, H Langseth, T D Nielsen. A parallel algorithm for Bayesian network structure learning from large data sets. Knowledge Based Systems, 2017, 117: 46–55
https://doi.org/10.1016/j.knosys.2016.07.031
46 S Arnborg, D G Corneil, A Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 1987, 8(2): 277–284
https://doi.org/10.1137/0608024
47 S Nie, D D Maua, C P De Campos, Q Ji. Advances in learning Bayesian networks of bounded treewidth. Advances in Neural Information Processing Systems, 2014, 27: 2285–2293
48 W Liao, Q Ji. Learning Bayesian network parameters under incomplete data with domain knowledge. Pattern Recognition, 2009, 42: 3046–3056
https://doi.org/10.1016/j.patcog.2009.04.006
49 Y Lv, J Wu, T Jing. Pqisem: BN’s structure learning based on partial qualitative influences and SEM algorithm from missing data. International Journal of Wireless and Mobile Computing, 2018, 14(4): 348–357
https://doi.org/10.1504/IJWMC.2018.093862
50 A R Masegosa, A Feelders, L C Der Gaag. Learning from incomplete data in Bayesian networks with qualitative influences. International Journal of Approximate Reasoning, 2016, 69: 18–34
https://doi.org/10.1016/j.ijar.2015.11.004
[1] Article highlights Download
[1] Ildar NURGALIEV, Qiang QU, Seyed Mojtaba Hosseini BAMAKAN, Muhammad MUZAMMAL. Matching user identities across social networks with limited profile data[J]. Front. Comput. Sci., 2020, 14(6): 146809-.
[2] Jianjun YANG,Yunhai TONG,Zitian WANG,Shaohua TAN. Efficient and effective Bayesian network local structure learning[J]. Front. Comput. Sci., 2014, 8(4): 527-536.
[3] WEI Hui. A hierarchical model for structure learning based on the physiological characteristics of neurons[J]. Front. Comput. Sci., 2007, 1(3): 361-372.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed