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
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.
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
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
