Finding optimal Bayesian networks by a layered learning method

doi:10.21629/JSEE.2019.05.12

Journal of Systems Engineering and Electronics ›› 2019, Vol. 30 ›› Issue (5): 946-958.doi: 10.21629/JSEE.2019.05.12

• Systems Engineering • Previous Articles Next Articles

Finding optimal Bayesian networks by a layered learning method

Yu YANG(), Xiaoguang GAO*(), Zhigao GUO()

School of Electronics and Information, Northwestern Polytechnical University, Xi'an 710129, China

Received:2018-11-06 Online:2019-10-08 Published:2019-10-09
Contact: Xiaoguang GAO E-mail:youngiv@126.com;cxg2012@nwpu.edu.cn;buckleyguo@mail.nwpu.edu.cn
About author:YANG Yu was born in 1991. He received his B.S. degree from Northwestern Polytechnical University, Xi'an, China. He is now a Ph.D. candidate from the Department of System Engineering, Northwestern Polytechnical University. His areas of research include Bayesian networks, data mining, and image recognition. E-mail: youngiv@126.com|GAO Xiaoguang received her Ph.D. degree from Northwestern Polytechnical University, Xi'an, China in 1989. She is currently a professor in the Department of System Engineering, Northwestern Polytechnical University. She now is the deputy director of Automatic Control Specialized Committee of China Ordnance Industry Association, and a specialized committee member of China Aviation Society of Weapon System and Photoelectric Technology of China Astronautical Society. Her research interests include probabilistic graphical models, deep learning, reinforcement learning, advanced control theory and its application in complex systems, attack defense confrontation and effectiveness evaluation of integrated avionics systems, and aviation fire control and operational effectiveness analysis. E-mail: cxg2012@nwpu.edu.cn|GUO Zhigao is currently a Ph.D. candidate at the Department of System Engineering, Northwestern Polytechnical University. His research interests cover Bayesian networks, model optimization, knowledge and data mining. He has been the author of peer-reviewed publications on International Journal of Approximate Reasoning, Advanced Methodology for Bayesian Networks, and so on. E-mail: buckleyguo@mail.nwpu.edu.cn
Supported by:
the National Natural Science Foundation of China(61573285);This work was supported by the National Natural Science Foundation of China (61573285)

Abstract

Abstract:

It is unpractical to learn the optimal structure of a big Bayesian network (BN) by exhausting the feasible structures, since the number of feasible structures is super exponential on the number of nodes. This paper proposes an approach to layer nodes of a BN by using the conditional independence testing. The parents of a node layer only belong to the layer, or layers who have priority over the layer. When a set of nodes has been layered, the number of feasible structures over the nodes can be remarkably reduced, which makes it possible to learn optimal BN structures for bigger sizes of nodes by accurate algorithms. Integrating the dynamic programming (DP) algorithm with the layering approach, we propose a hybrid algorithm—layered optimal learning (LOL) to learn BN structures. Benefitted by the layering approach, the complexity of the DP algorithm reduces to O(ρ2^n-1) from O(n2^n-1), where ρ < n. Meanwhile, the memory requirements for storing intermediate results are limited to $O(C_{k^\# }^{{{k^\# } \over 2}})$ from $O(C_n^{{n \over 2}} )$, where k^# < n. A case study on learning a standard BN with 50 nodes is conducted. The results demonstrate the superiority of the LOL algorithm, with respect to the Bayesian information criterion (BIC) score criterion, over the hill-climbing, max-min hill-climbing, PC, and three-phrase dependency analysis algorithms.

Key words: Bayesian network (BN), structure learning, layered optimal learning (LOL)

Yu YANG, Xiaoguang GAO, Zhigao GUO. Finding optimal Bayesian networks by a layered learning method[J]. Journal of Systems Engineering and Electronics, 2019, 30(5): 946-958.

Figures/Tables 7

Fig 1

Fig 2

Fig 3

Fig 4

Table 1

Table 2

Table 3

References 42

1	PEARL J. Probabilistic reasoning in intelligent systems: networks of plausible inference. San Mateo: Morgan Kaufmann, 1988.
2	ZHANG N, DING S F, ZHANG J, et al. An overview on restricted Boltzmann machine. Neurocomputing, 2017, 275 (1): 1186- 1199.
3	ZHANG J, DING S F, ZHANG N. An overview on probability undirected graphs and their applications in image processing. Neurocomputing, 2018, 321, 156- 168. doi: 10.1016/j.neucom.2018.07.078
4	DE CAMPOS L M. A scoring function for learning Bayesian networks based on mutual information and conditional independence tests. Journal of Machine Learning Research, 2006, 7 (10): 2149- 2187.
5	PERRIER E, IMOTO S, MIYANO S. Finding optimal Bayesian network given a super-structure. Journal of Machine Learning Research, 2008, 9 (10): 2251- 2286.
6	YEHEZKEL R, LERNER B. Bayesian network structure learning by recursive autonomy identification. Journal of Machine Learning Research, 2009, 10 (7): 1527- 1570.
7	HECKENMAN D, GEIGER D, CHICKERRING D M. Learning Bayesian networks:the combination of knowledge and statistical data. Machine Learning, 1995, 20 (3): 1997- 243.
8	STECK H. Learning the Bayesian network structure: Dirichlet prior versus data. Proc. of the 24th Conference on Uncertainty in Artificial Intelligence, 2008: 511-518.
9	SCHWARZ G. Estimating the dimension of a model. The Annals of Statistics, 1978, 6 (2): 461- 464.
10	SILANDER T, ROOS T, MYLLYMAKI P. Learning locally minimal optimal Bayesian networks. International Journal of Approximate Reasoning, 2010, 51 (5): 544- 557. doi: 10.1016/j.ijar.2010.01.012
11	CARVALHO A M, ROOS T, OLIVEIRA A L, et al. Discriminative learning of Bayesian networks via factorized conditional log-likelihood. Journal of Machine Learning Research, 2011, 12, 2181- 2210.
12	OTT S, IMOTO S, MIYANO S. Finding optimal models for small gene networks. Proc. of the Pacific Symposium on Biocomputing, 2004, 9, 557- 567.
13	OTT S, MIYANO S. Finding optimal gene networks using biological constraints. Genome Informatics, 2003, 14, 124- 133.
14	KOIVISTO M, SOOD K. Exact Bayesian structure discovery in Bayesian networks. Journal of Machine Learning Research, 2004, 5, 549- 573.
15	SINGH A P, MOORE A W. Finding optimal Bayesian networks by dynamic programming, CMUCALD-05-106. Pittsburgh, USA: Carnegie Mellon University, 2005.
16	EATON D, MURPHY K. Bayesian structure learning using dynamic programming and MCMC. Proc. of the 23rd Conference on Uncertainty in Artificial Intelligence, 2007: 101-108.
17	MALONE B, YUAN C H, HANSEN E A. Memory-efficient dynamic programming for learning optimal Bayesian networks. Proc. of the 25th Conference on Artificial Intelligence, 2011, 1057- 1062.
18	COOPER G F, HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 1992, 9 (4): 309- 347.
19	GAMEZ J A, MATEO J L, PUERTA J M. Learning Bayesian networks by hill climbing:efficient methods based on progressive restriction of the neighborhood. Data Mining and Knowledge Discovery, 2011, 22 (1/2): 106- 148.
20	LARRANAGA P, KARSHENAS H, BIELZA C, et al. A review on evolutionary algorithms in Bayesian network learning and inference tasks. Information Sciences, 2013, 233, 109- 125. doi: 10.1016/j.ins.2012.12.051
21	WANG M L, GUO Y Y. Learning Bayesian networks from incomplete database using a novel evolutionary algorithm. Decision Support System, 2008, 45 (2): 368- 383. doi: 10.1016/j.dss.2008.01.002
22	WANG M L, LEUNG K S. An efficient data mining method for learning Bayesian networks using an evolutionary algorithm-based hybrid approach. IEEE Trans. on Evolutionary Computation, 2004, 8 (4): 378- 404.
23	DE CAMPOS L M, HUETE J F. Approximating causal orderings for Bayesian networks using genetic algorithms and simulated annealing. Proc. of the 8th Conference on Information Processing and Management of Uncertainty in KnowledgeBased Systems, 2000.
24	HENG X C, QIN Z, TIAN L, et al. Learning Bayesian network structures with discrete particle swarm optimization algorithm. Proc. of the IEEE Symposium on Foundations of Computational Intelligence, 2007: 47-52.
25	LI X L, WANG S C, HE X D. Learning Bayesian networks structures based on memory binary particle swarm optimization. Proc. of the 6th International Conference on Simulated Evolution and Learning, 2006: 568-574.
26	SAHIN F, DEVASIA A. Distributed particle swarm optimization for structural Bayesian network learning. Swarm Intelligence:Focus on Ant and Particle Swarm Optimization, 2007, 27, 505- 532.
27	DE CAMPOS L M, FERNANDEZ-LUNA J M, GAMEZ J A, et al. Ant colony optimization for learning Bayesian net-works. International Journal of Approximate Reasoning, 2002, 31 (3): 291- 311. doi: 10.1016/S0888-613X(02)00091-9
28	DALY R, SHEN Q. Learning Bayesian network equivalence classes with ant colony optimization. Journal of Artificial Intelligence Research, 2009, 13 (4): 767- 779.
29	JI J Z, WEI H K, LIU C N. An artificial bee colony algorithm for learning Bayesian network. Soft Computing, 2013, 17 (6): 983- 994.
30	PEARL J. Causality:models, reasoning, and inference. Cambridge: Cambridge University Press, 2000.
31	SPIRTES P, GLYMOUR C, SCHEINES R. Causation, prediction and search. Massachusetts: MIT Press, 2000.
32	CHENG J, GREINER R, KELLY J, et al. Learning Bayesian networks form data:an information-theory based approach. Artificial Intelligence, 2002, 137 (1/2): 43- 90.
33	DE COMPOS L M, FERNANDEZ-LUNA, PUERTA J M. An iterated local search algorithm for learning Bayesian networks with restarts based on conditional independence tests. International Journal of Intelligent Systems, 2003, 18 (2): 221- 235.
34	FRIEDMAN N, NACHMAN I, PEER D. Learning Bayesian network structure from massive datasets: the"sparse candidate"algorithm. Proc. of the 15th Conference on Uncertainty in Artificial Intelligence, 1999: 206-215.
35	TSAMARDINOS I, BROWN L E, ALIFERIS C F. The maximin hill-climbing Bayesian network structure learning algorithm. Machine Learning, 2006, 65 (1): 31- 78.
36	KOJIMA K, PERRIER E, IMOTO S, et al. Optimal search on clustered structural constraint for learning Bayesian network structure. Journal of Machine Learning Research, 2010, 11, 663- 689.
37	KOLLER D, FRIEDMAN N. Probabilistic graphical models:principles and techniques. London: MIT Press, 2009.
38	LIU H, ZHOU S G, LAM W, et al. A new hybrid method for learning Bayesian networks:separation and reunion. Knowledge-Based Systems, 2017, 121, 185- 197. doi: 10.1016/j.knosys.2017.01.029
39	XIE X C, GENG Z. A recursive method for structural learning of directed acyclic graphs. Journal of Machine Learning Research, 2008, 9, 459- 483.
40	MURPHY K P. The Bayes net toolbox for matlab. Operations Research, 2001.
41	FRANCOIS O. Structure learning package for bayes net toolbox. https://www.mathworks.cn/matlabcentral/fileexchange/13562-structure-learning-package-for-bayes-net-toolbox.
42	HE C C, GAO X G, GUO Z G. Structure learning on Bayesian networks by finding the optimal ordering with and without priors. Journal of Systems Engineering and Electronics, 2018, 29 (6): 1209- 1227. doi: 10.21629/JSEE.2018.06.09

$n$	Data	PC	TPDA	HC	MMHC	LOL	LOL+
	1 000	-1.216 6E4	-1.203 1E4	-1.176 2E4	-1.206 9E4	$\textbf{-1.175 4E4}$	$\textbf{-1.175 4E4}$
25	2 000	-2.402 3E4	-2.383 8E4	-2.339 6E4	-2.361 8E4	$\textbf{-2.338 5E4}$	$\textbf{-2.338 5E4}$
	5 000	-	-	-5.849 9E4	-5.885 1E4	$\textbf{-5.849 8E4}$	$\textbf{-5.849 8E4}$
	1 000	-1.471 0E4	-1.458 2E4	-1.417 9E4	-1.460 7E4	$\textbf{-1.410 7E4}$	$\textbf{-1.410 7E4}$
30	2 000	-2.903 8E4	-2.861 5E4	-2.813 9E4	-2.862 0E4	$\textbf{-2.799 8E4}$	$\textbf{-2.799 8E4}$
	5 000	-7.189 7E4	-7.007 6E4	-7.004 9E4	-7.038 4E4	$\textbf{-7.002 8E4}$	$\textbf{-7.002 8E4}$
	1 000	-1.727 1E4	-1.712 5E4	-1.671 5E4	-1.714 4E4	$\textbf{-1.663 2E4}$	$\textbf{-1.663 2E4}$
35	2 000	-3.406 4E4	-3.368 1E4	-3.311 7E4	-3.360 8E4	-3.303 5E4	$\textbf{-3.300 2E4}$
	5 000	-8.493 9E4	-	-8.252 3E4	-8.309 8E4	$\textbf{-8.243 3E4}$	$\textbf{-8.243 3E4}$
	1 000	-1.923 3E4	-1.908 9E4	-1.855 2E4	-1.913 2E4	-1.850 3E4	$\textbf{-1.848 4E4}$
40	2 000	-3.779 3E4	-	-3.682 7E4	-3.751 4E4	-3.675 6E4	$\textbf{-3.672 3E4}$
	5 000	-9.427 7E4	-	-9.173 4E4	-9.239 8E4	$\textbf{-9.167 9E4}$	$\textbf{-9.167 9E4}$
	1 000	-2.161 6E4	-2.155 5E4	-2.092 0E4	-2.155 4E4	-2.086 0E4	$\textbf{-2.084 1E4}$
45	2 000	-4.282 0E4	-	-4.152 2E4	-4.227 9E4	-4.143 8E4	$\textbf{-4.140 3E4}$
	5 000	-1.060 8E5	-	-1.036 1E5	-1.048 3E5	$\textbf{-1.034 7E5}$	$\textbf{-1.034 7E5}$
	1 000	-2.458 2E4	-2.454 3E4	-2.386 1E4	-2.447 8E4	-2.378 0E4	$\textbf{-2.376 1E4}$
50	2 000	-4.864 9E4	-	-4.735 9E4	-4.830 1E4	-4.729 2E4	$\textbf{-4.720 9E4}$
	5 000	-1.209 3E5	-	-1.181 7E5	-1.187 9E5	-1.181 1E5	$\textbf{-1.181 0E5}$

$n$	Data	PC	TPDA	HC	MMHC	LOL	LOL+
	1 000	$\textbf{0.20}$	7.99	7.22	0.79	14.16	14.39
25	2 000	$\textbf{0.36}$	17.33	8.84	1.05	21.57	21.82
	5 000	-	-	11.05	$\textbf{1.64}$	42.51	42.81
	1 000	$\textbf{0.25}$	10.38	15.29	1.22	48.97	49.33
30	2 000	$\textbf{0.47}$	26.80	14.42	1.61	72.52	72.15
	5 000	$\textbf{0.89}$	102.88	18.98	2.45	132.50	132.95
	1 000	$\textbf{0.36}$	16.41	24.69	1.61	85.14	86.15
35	2 000	$\textbf{0.69}$	43.32	25.58	2.26	108.85	111.08
	5 000	$\textbf{1.36}$	-	34.11	3.54	247.61	248.08
	1 000	$\textbf{0.42}$	19.16	38.45	2.20	128.66	124.25
40	2 000	$\textbf{0.78}$	-	41.82	2.95	207.80	211.71
	5 000	$\textbf{1.58}$	-	51.02	4.79	431.75	432.67
	1 000	$\textbf{0.51}$	27.17	66.14	3.20	254.66	261.20
45	2 000	$\textbf{0.92}$	97.74	67.48	4.41	851.54	857.26
	5 000	$\textbf{1.86}$	-	51.02	6.60	1 352.62	1 355.26
	1 000	$\textbf{0.62}$	38.00	115.81	4.32	492.13	501.44
50	2 000	$\textbf{1.04}$	-	113.95	5.23	845.47	859.79
	5 000	$\textbf{2.04}$	-	142.07	9.34	1 364.17	1 369.71

$n$	Data	Layers
	1 000	(1-11, 18-21); (12-17, 22-25)
25	2 000	(1-11, 18-21); (12-17, 22-25)
	5 000	(1-11, 18-21); (12-17, 22-25)
	1 000	(1-11, 18-21); (12-17, 22-30)
30	2 000	(1-11, 18-21); (12-17, 22-30)
	5 000	(1-11, 18-21); (12-17, 22-30)
	1 000	(1-11, 18-21); (14-16); (22); (12); (13, 17, 23-35)
35	2 000	(1-11, 18-21); (12, 13, 17); (25, 29, 30, 33); (14-16, 22-24, 26-28, 31, 32, 34, 35)
	5 000	(1-11, 18-21); (12); (14-16); (22); (13, 17, 23-35)
	1 000	(1-11, 18-21); (14-16); (22); (12); (25, 29, 31-34, 38); (13, 17, 23, 24, 26-28, 30, 35-37, 39, 40)
40	2 000	(1-11, 18-21); (12, 13, 17, 24, 25, 30, 31, 33); (26); (29, 32); (14-16, 22, 23, 27, 28, 34-40)
	5 000	(1-11, 18-21); (12); (14-16); (22); (13, 17); (24, 25); (23); (26-40)
	1 000	(1-11, 18-21); (14-16); (22); (12); (25, 29, 31-34, 38, 39, 42); (13, 17, 23, 24, 26-28, 30, 35-37, 40, 41, 43-45)
45	2 000	(1-11, 18-21); (12, 13, 17); (24, 25, 29-31, 33); (26); (14-16, 22, 23, 27, 28, 32, 34-45)
	5 000	(1-11, 18-21); (12); (13-16); (17); (22); (24, 25); (26); (23, 27-45)
	1 000	(1-11, 18-21); (14-16); (22); (12); (25, 29, 31-34, 38, 39, 42); (30, 40, 41); (13, 17, 23, 24, 26-28, 35-37, 43-50)
50	2 000	(1-11, 18-21); (12, 13, 17); (24, 25, 29-31, 33); (26); (32); (14); (15, 16, 22, 23); (27, 28, 34-50)
	5 000	(1-11, 18-21); (12); (13-16); (17); (22); (23); (32-38, 40, 44, 46); (24-31, 39, 41-43, 45, 47-50)

[1]	Xiangyuan TAN, Xiaoguang GAO, Chuchao HE, Zidong WANG. Causal constraint pruning for exact learning of Bayesian network structure [J]. Journal of Systems Engineering and Electronics, 2021, 32(4): 854-872.
[2]	Chuchao HE, Xiaoguang GAO, Zhigao GUO. Structure learning on Bayesian networks by finding the optimal ordering with and without priors [J]. Journal of Systems Engineering and Electronics, 2018, 29(6): 1209-1227.
[3]	Zhiqiang Cai, Shubin Si, Shudong Sun, and Hongyan Dui. Learning Bayesian network structure with immune algorithm [J]. Journal of Systems Engineering and Electronics, 2015, 26(2): 282-291.
[4]	Chunfeng Wang, Sanyang Liu, and Mingmin Zhu. Bayesian network learning algorithm based on unconstrained optimization and ant colony optimization [J]. Journal of Systems Engineering and Electronics, 2012, 23(5): 784-790.
[5]	Mingmin Zhu, Sanyang Liu, Youlong Yang, and Kui Liu. Using junction trees for structural learning of Bayesian networks [J]. Journal of Systems Engineering and Electronics, 2012, 23(2): 286-292.
[6]	Chen Fei, Wang Xiufeng & Rao Yimei. Learning Bayesian networks using genetic algorithm [J]. Journal of Systems Engineering and Electronics, 2007, 18(1): 142-147.

Finding optimal Bayesian networks by a layered learning method

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 7

References 42

Related Articles 6

Recommended Articles

Metrics

Comments