Causal constraint pruning for exact learning of Bayesian network structure

doi:10.23919/JSEE.2021.000074

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (4): 854-872.doi: 10.23919/JSEE.2021.000074

• SYSTEMS ENGINEERING • Previous Articles Next Articles

Causal constraint pruning for exact learning of Bayesian network structure

Xiangyuan TAN¹(), Xiaoguang GAO^1,*(), Chuchao HE^1,²(), Zidong WANG¹()

¹ School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China
² School of Electronics and Information Engineering, Xi’an Technological University, Xi’an 710021, China

Received:2020-06-24 Online:2021-08-18 Published:2021-09-30
Contact: Xiaoguang GAO E-mail:tanxy2017@mail.nwpu.edu.cn;cxg2012@nwpu.edu.cn;xomrssh@163.com;nwpu_wzd@mail.nwpu.edu.cn
About author:|TAN Xiangyuan was born in 1995. He received his B.E. degree from Northwestern Polytechnical University, China, 2017. He is now a Ph.D. candidate in the School of Electronics and Information, Northwestern Polytechnical University. His research interest focuses on Bayesian network learning, especially on structure learning. E-mail: tanxy2017@mail.nwpu.edu.cn||GAO Xiaoguang was born in 1957. She received her Ph.D. degree from Northwestern Polytechnical University, Xi’an, China in 1989. She is currently a professor in the School of Electronics and Information, Northwestern Polytechnical University. She is the deputy director of the 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||HE Chuchao was born in 1992. He received his Ph.D. degree from the Department of System Engineering, Northwestern Polytechnical University, China, 2020. He works in the School of Electronics and?Information?Engineering, Xi’an Technological University. His research interest is Bayesian network learning, especially on structure learning. E-mail: xomrssh@163.com||WANG Zidong was born in 1997. He received his B.E. degree from Northwestern Polytechnical University, China, 2019. He is now a Ph.D. candidate in the School of Electronics and Information, Northwestern Polytechnical University. His research interest is Bayesian network learning, especially on structure learning. E-mail: nwpu_wzd@mail.nwpu.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (61573285)

Abstract

Abstract:

How to improve the efficiency of exact learning of the Bayesian network structure is a challenging issue. In this paper, four different causal constraints algorithms are added into score calculations to prune possible parent sets, improving state-of-the-art learning algorithms’ efficiency. Experimental results indicate that exact learning algorithms can significantly improve the efficiency with only a slight loss of accuracy. Under causal constraints, these exact learning algorithms can prune about 70% possible parent sets and reduce about 60% running time while only losing no more than 2% accuracy on average. Additionally, with sufficient samples, exact learning algorithms with causal constraints can also obtain the optimal network. In general, adding max-min parents and children constraints has better results in terms of efficiency and accuracy among these four causal constraints algorithms.

Key words: Bayesian network, structure learning, exact learning algorithm, causal constraint

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.

Figures/Tables 19

Fig 1

Fig 2

Fig 3

Table 1

Running time for IAMB, interIAMBnPC, HITON_PC and MMPC and the number of remaining possible parent sets by score calculations with Theorems 2?4 and different causal constraints algorithms on benchmark BNs"

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	\|PPS\|	Time/s	\|PPS\|	Time/s	\|PPS\|	Time/s	\|PPS\|	Time/s	\|PPS\|
Asia	8	500	?	56	0.056	27	0.275	27	0.136	28	0.084	28
Asia	8	1 000	?	58	0.061	27	0.284	27	0.148	30	0.090	30
Asia	8	5 000	?	115	0.086	28	0.329	28	0.182	37	0.129	37
Asia	8	10 000	?	132	0.121	35	0.441	35	0.224	41	0.167	41
Asia	8	15 000	?	152	0.138	39	0.497	39	0.249	47	0.175	47
Sachs	11	500	?	105	0.084	53	0.461	53	0.203	78	0.147	78
Sachs	11	1 000	?	135	0.094	58	0.508	58	0.245	87	0.187	87
Sachs	11	5 000	?	249	0.233	107	1.997	115	0.641	137	0.609	137
Sachs	11	10 000	?	331	0.372	115	2.343	115	0.995	161	0.967	161
Sachs	11	15 000	?	352	0.533	141	4.707	145	1.470	164	1.441	164
Child	20	500	?	388	0.187	64	0.701	68	0.757	126	0.383	126
Child	20	1 000	?	718	0.231	83	1.005	96	0.663	143	0.535	146
Child	20	5 000	?	2 952	0.739	101	3.561	182	1.435	196	1.258	199
Child	20	10 000	?	5 350	1.372	202	8.543	258	2.751	233	2.577	236
Child	20	15 000	?	7 766	1.918	234	37.320	389	4.427	268	4.234	270
Boerlage92	23	500	?	188	0.329	98	1.393	90	0.263	91	0.211	91
Boerlage92	23	1 000	?	319	0.415	128	1.551	127	0.328	122	0.267	122
Boerlage92	23	5 000	?	603	0.994	174	3.035	169	0.564	146	0.474	146
Boerlage92	23	10 000	?	935	2.241	229	7.397	217	0.926	179	0.852	179
Boerlage92	23	15 000	?	1 130	3.167	275	17.112	210	1.203	180	1.158	180
Insurance	27	500	?	324	0.332	97	1.056	103	0.482	150	0.402	151
Insurance	27	1 000	?	578	0.411	140	1.596	146	0.675	195	0.664	195
Insurance	27	5 000	?	1 297	1.448	205	7.575	221	2.648	235	2.563	235
Insurance	27	10 000	?	1 681	2.729	233	16.170	258	5.938	259	5.678	260
Insurance	27	15 000	?	2 128	4.357	280	24.737	297	9.455	280	8.695	282

Table 1

Table 2

Running time and the number of expanded states for A* on possible parent sets without/with causal constraints from IAMB, interIAMBnPC, HITON_PC and MMPC algorithm on benchmark BNs"

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp
Asia	8	500	0.001	125	<0.001	103	<0.001	117	<0.001	109	<0.001	109
Asia	8	1 000	0.001	136	<0.001	112	<0.001	112	<0.001	108	<0.001	108
Asia	8	5 000	0.001	139	<0.001	113	<0.001	113	<0.001	93	<0.001	93
Asia	8	10 000	0.002	144	<0.001	124	<0.001	124	<0.001	114	<0.001	114
Asia	8	15 000	0.002	140	<0.001	118	0.001	118	<0.001	96	<0.001	96
Sachs	11	500	0.002	165	<0.001	12	<0.001	12	0.001	165	0.001	165
Sachs	11	1 000	0.002	208	0.001	136	0.001	136	0.001	208	0.001	208
Sachs	11	5 000	0.003	504	0.002	399	0.002	407	0.002	208	0.002	416
Sachs	11	10 000	0.003	635	0.003	507	0.002	507	0.002	507	0.002	507
Sachs	11	15 000	0.004	766	0.002	566	0.002	574	0.002	574	0.002	574
Child	20	500	0.134	34 680	0.131	42 878	0.133	52 933	0.095	26 364	0.094	26 364
Child	20	1 000	0.215	54 272	0.118	34 874	0.434	40 846	0.151	42 002	0.148	42 002
Child	20	5 000	1.121	257 794	0.464	128 509	0.434	116 975	0.362	96 994	0.355	97 076
Child	20	10 000	1.767	422 719	0.689	178 713	0.754	185 423	0.401	105 169	0.387	102 443
Child	20	15 000	2.156	515 067	0.724	186 036	0.934	231 675	0.576	157 753	0.561	152 182
Boerlage92	23	500	9.218	2 002 229	7.549	1 629 662	7.531	1 643 588	7.526	1 644 468	7.516	1 644 468
Boerlage92	23	1 000	10.779	2 270 241	8.149	1 676 800	8.159	1 712 640	8.008	1 693 686	8.104	1 693 686
Boerlage92	23	5 000	15.167	3 170 609	9.749	1 971 856	9.297	1 904 565	8.665	1 769 324	8.621	1 777 607
Boerlage92	23	10 000	17.505	3 600 953	11.089	2 279 706	10.853	2 236 253	9.555	1 987 578	9.487	1 987 578
Boerlage92	23	15 000	18.076	3 667 072	11.608	2 396 507	10.369	2 140 995	9.593	2 003 462	9.487	2003 462
Insurance	27	500	186.683	23 824 490	55.613	8 123 998	115.004	16 341 269	70.659	9 026 318	71.113	9 052 354
Insurance	27	1 000	241.012	26 759 491	106.917	13 251 973	95.272	11 620 471	47.259	5 381 061	46.677	5 381 061
Insurance	27	5 000	252.271	24 618 675	89.624	10 120 638	58.262	6 330 008	30.263	3 045 470	30.186	3 045 470
Insurance	27	10 000	260.760	24 781 890	96.715	10 777 479	95.676	10 400 724	54.059	5 998 815	57.933	6 441 043
Insurance	27	15 000	263.783	24 799 024	91.023	10 313 747	94.508	10 499 471	27.062	2 759 230	26.381	2 752 446

Table 2

Table 3

Table 4

Running time and the number of expanded states for AWA* on possible parent sets without/with causal constraints from IAMB, interIAMBnPC, HITON_PC and MMPC algorithm on benchmark BNs"

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp
Asia	8	500	0.001	168	<0.001	138	<0.001	149	<0.001	140	<0.001	140
Asia	8	1 000	0.001	171	<0.001	137	<0.001	137	<0.001	126	<0.001	126
Asia	8	5 000	0.001	215	<0.001	132	<0.001	132	<0.001	107	<0.001	107
Asia	8	10 000	0.002	200	<0.001	150	<0.001	150	<0.001	140	<0.001	140
Asia	8	15 000	0.002	193	<0.001	141	0.001	141	<0.001	107	<0.001	107
Sachs	11	500	0.001	211	<0.001	11	0.001	11	0.001	211	0.001	211
Sachs	11	1 000	0.002	271	0.001	210	0.001	210	0.001	271	0.001	271
Sachs	11	5 000	0.003	629	0.002	465	0.002	474	0.002	515	0.002	515
Sachs	11	10 000	0.003	783	0.002	590	0.002	590	0.002	567	0.002	567
Sachs	11	15 000	0.004	914	0.002	648	0.002	657	0.002	672	0.002	672
Child	20	500	0.106	45 312	0.089	56 377	0.083	70 166	0.075	36 423	0.074	36 423
Child	20	1 000	0.206	69 590	0.105	56 365	0.124	66 338	0.137	54 962	0.136	54 968
Child	20	5 000	0.136	323 846	0.532	157 852	0.510	144 046	0.363	115 466	0.354	115 359
Child	20	10 000	2.426	534 444	0.741	206 651	0.799	221 970	0.395	124 774	0.389	122 045
Child	20	15 000	2.679	595 660	0.718	197 563	0.961	258 258	0.584	167 969	0.566	162 513
Boerlage92	23	500	12.437	3 641 617	8.650	2 620 661	8.689	2 525 971	8.868	2 527 587	8.379	2 527 587
Boerlage92	23	1 000	18.308	5 219 135	11.861	2 790 937	12.239	3 016 173	11.597	2 603 555	11.620	2 603 555
Boerlage92	23	5 000	34.003	7 824 034	13.538	3 187 562	12.043	2 924 839	10.425	2 383 324	10.449	2 404 162
Boerlage92	23	10 000	43.521	9 344 601	18.528	4 074 288	15.784	3 613 529	13.082	3 001 835	13.054	3 001 835
Boerlage92	23	15 000	50.139	11 392 055	22.779	5 890 686	15.868	4 255 227	13.775	3 667 091	13.840	3 667 091
Insurance	27	500	326.255	35 221 890	121.797	13 147 458	240.307	24 872 911	117.765	12 159 904	118.266	12 175 999
Insurance	27	1 000	440.560	36 488 412	190.548	16 189 733	148.147	13 831 906	79.761	6 674 497	79.076	6 674 497
Insurance	27	5 000	422.335	32 290 896	153.058	12 203 266	97.446	7 284 575	45.638	3 531 862	46.176	3 531 862
Insurance	27	10 000	418.924	32 537 843	150.942	13 010 259	94.225	10 400 724	86.234	6 773 569	89.966	7 282 880
Insurance	27	15 000	423.794	31 664 273	145.392	11 579 608	144.688	11 510 705	41.545	3 056 943	38.542	3 038 247

Table 4

Table 5

Table 6

Running time and the number of expanded states for BFBnB on possible parent sets without/with causal constraints from IAMB, interIAMBnPC, HITON_PC and MMPC algorithm on benchmark BNs"

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp
Asia	8	500	0.003	135	0.002	115	0.002	129	0.002	121	0.003	121
Asia	8	1 000	0.003	147	0.003	125	0.003	125	0.002	119	0.002	119
Asia	8	5 000	0.003	151	0.002	125	0.002	125	0.002	105	0.002	105
Asia	8	10 000	0.003	151	0.002	131	0.002	131	0.003	121	0.003	121
Asia	8	15 000	0.003	151	0.003	129	0.003	129	0.003	107	0.003	107
Sachs	11	500	0.004	389	0.003	286	0.003	286	0.003	389	0.003	389
Sachs	11	1 000	0.004	567	0.003	487	0.003	487	0.003	567	0.003	567
Sachs	11	5 000	0.005	751	0.004	647	0.004	655	0.004	663	0.004	663
Sachs	11	10 000	0.006	887	0.004	759	0.004	759	0.004	759	0.004	759
Sachs	11	15 000	0.006	848	0.004	648	0.004	656	0.004	656	0.004	656
Child	20	500	0.092	92 481	NF	NF	NF	NF	0.061	57 947	0.060	57 947
Child	20	1 000	0.128	76 775	NF	NF	NF	NF	0.072	45 131	0.070	45 131
Child	20	5 000	0.603	376 865	0.214	184 286	0.202	170 007	0.158	124 484	0.151	124 605
Child	20	10 000	0.891	423 868	0.219	179 870	0.229	186 590	0.165	106 323	0.157	103 591
Child	20	15 000	1.012	516 250	0.234	187 198	0.398	232 894	0.221	158 911	0.195	153 340
Boerlage92	23	500	3.526	2 090 821	2.706	1 673 951	2.681	1 670 347	2.705	1 671 227	2.718	1 671 227
Boerlage92	23	1 000	4.321	2 454 960	2.979	1 793 979	3.044	1 827 721	3.002	1 799 098	3.012	1 799 098
Boerlage92	23	5 000	6.056	3 419 002	3.594	2 082 056	3.478	2 009 629	3.271	1 876 156	3.216	1 876 999
Boerlage92	23	10 000	6.876	3 839 752	4.384	2 458 616	4.236	2 381 948	3.679	2 111 023	3.648	2 111 023
Boerlage92	23	15 000	7.207	3 917 658	4.521	2 556 979	3.872	2 252 900	3.650	2 096 352	3.597	2 096 352
Insurance	27	500	226.386	55 726 235	NF	NF	NF	NF	51.986	14 205 451	52.052	14 247 975
Insurance	27	1 000	212.368	50 838 649	NF	NF	NF	NF	23.654	6 571 771	23.572	6 571 771
Insurance	27	5 000	148.417	35 098 042	55.001	14 126 761	NF	NF	10.813	3 298 588	10.754	3 298 588
Insurance	27	10 000	130.424	30 399 206	45.651	11 668 957	46.962	11 905 130	25.667	7 201 991	24.988	7 003 247
Insurance	27	15 000	132.896	30 768 715	45.121	11 545 319	48.683	12 176 353	NF	NF	11.004	3 309 853

Table 6

Table 7

Table 8

Running time and score error ratio for GOBNILP on possible parent sets without/with causal constraints from IAMB, interIAMBnPC, HITON_PC and MMPC algorithm on benchmark BNs"

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	Error/%	Time/s	Error/%	Time/s	Error/%	Time/s	Error/%	Time/s	Error/%
Asia	8	500	0.047	?	0.011	0.051	0.010	0.051	0.036	0.051	0.027	0.051
Asia	8	1 000	0.055	?	0.011	0	0.010	0	0.036	0	0.030	0
Asia	8	5 000	0.056	?	0.010	0	0.010	0	0.043	0	0.042	0
Asia	8	10 000	0.064	?	0.020	0	0.019	0	0.036	0	0.037	0
Asia	8	15 000	0.519	?	0.028	0	0.029	0	0.041	0	0.040	0
Sachs	11	500	0.148	?	0.031	0	0.030	0	0.125	0	0.126	0
Sachs	11	1 000	0.236	?	0.066	0	0.064	0	0.182	0	0.184	0
Sachs	11	5 000	0.277	?	0.128	0	0.150	0	0.172	0	0.171	0
Sachs	11	10 000	0.286	?	0.110	0	0.095	0	0.173	0	0.175	0
Sachs	11	15 000	0.237	?	0.112	0	0.100	0	0.141	0	0.140	0
Child	20	500	0.255	?	0.056	3.946	0.060	4.302	0.073	0.355	0.075	0.355
Child	20	1 000	0.423	?	0.078	1.136	0.088	1.136	0.089	0.291	0.087	0.291
Child	20	5 000	4.174	?	0.171	0	0.389	0	0.092	0	0.091	0
Child	20	10 000	9.810	?	0.350	0	0.723	0	0.109	0	0.105	0
Child	20	15 000	22.694	?	0.361	0	0.725	0	0.115	0	0.127	0
Boerlage92	23	500	0.261	?	0.076	0.02	0.017	0.04	0.017	0.03	0.016	0.03
Boerlage92	23	1 000	0.323	?	0.097	0	0.086	0	0.065	0	0.061	0
Boerlage92	23	5 000	0.215	?	0.080	0	0.068	0	0.053	0	0.052	0
Boerlage92	23	10 000	0.447	?	0.119	0	0.066	0	0.082	0	0.081	0
Boerlage92	23	15 000	1.131	?	0.159	0	0.117	0	0.115	0	0.118	0
Insurance	27	500	0.983	?	0.037	1.494	0.049	2.69	0.107	0.796	0.105	0.796
Insurance	27	1 000	1.054	?	0.068	1.485	0.057	1.399	0.122	1.006	0.121	1.006
Insurance	27	5 000	7.294	?	0.145	0.074	0.472	0.712	0.125	0.607	0.123	0.607
Insurance	27	10 000	9.690	?	0.746	0.266	0.221	0.154	0.160	0.171	0.138	0.098
Insurance	27	15 000	5.940	?	1.338	0.226	1.199	0.155	0.218	0.756	0.125	0.188

Table 8

Table 9

Table 10

Table 11

Table 12

Table 13

Table 14

Table 15

Table 16

References 41

1	PEARL J. Probabilistic reasoning in intelligent systems: networks of plausible inference. San Mateo: Morgan Kaufmann Publishers, 1988.
2	ZHAO Y P, CHEN Y T, TU K W, et al Learning Bayesian network structures under incremental construction curricula. Neurocomputing, 2017, 258 (10): 30- 40.
3	CHICKERING D M. Learning from data. Berlin: Springer, 1996.
4	CHICKERING D M, HECKENMAN D, MEEK C Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research, 2004, 5 (10): 1287- 1330.
5	SCANAGATTA M, CORANI G, DE CAMPOS C P, et al Approximate structure learning for large Bayesian networks. Machine Learning, 2018, 107 (8−10): 1209- 1227. doi: 10.1007/s10994-018-5701-9
6	SCANAGATTA M, SALMERON A, STELLA F A survey on Bayesian network structure learning from data. Progress in Artificial Intelligence, 2019, 8, 425- 439. doi: 10.1007/s13748-019-00194-y
7	KOIVISTO M, SOOD K Exact Bayesian structure discovery in Bayesian networks. Journal of Machine Learning Research, 2004, 5, 549- 573.
8	SINGH A P, MOORE A W. Finding optimal Bayesian networks by dynamic programming. Pittsburgh, USA: Carnegie Mellon University, 2005.
9	SILANDER T, MYLLYMAKI P A simple approach for finding the globally optimal Bayesian network structure. Proc. of the 22nd Conference on Uncertainty in Artificial Intelligence, 2006, 445- 452.
10	MALONE B, YUAN C H Memory-efficient dynamic programming for learning optimal Bayesian networks. Proc. of the 25th AAAI Conference on Artificial Intelligence, 2011, 1057- 1062.
11	YUAN C H, MALONE B Learning optimal Bayesian networks: a shortest path perspective. Journal of Artificial Intelligence Research, 2013, 48 (1): 23- 65.
12	YUAN C H, MALONE B, WU X J Learning optimal Bayesian networks using A* search. Proc. of the 22nd International Joint Conference on Artificial Intelligence, 2011, 2186- 2191.
13	MALONE B, YUAN C H Evaluating anytime algorithms for learning optimal Bayesian networks. Proc. of the 29th Conference on Uncertainty in Artificial Intelligence, 2013, 381- 390.
14	MALONE B, YUAN C H, HANSEN E, et al Improving the scalability of optimal Bayesian network learning with external-memory frontier breadth-first branch and bound search. Proc. of the 27th Conference on Uncertainty in Artificial Intelligence, 2011, 479- 488.
15	YUAN C H, MALONE B An improved admissible heuristic for learning optimal Bayesian networks. Proc. of the 28th Conference on Uncertainty in Artificial Intelligence, 2012, 924- 933.
16	VAN BEEK P, HOFFMANN H F Machine learning of Bayesian networks using constraint programming. Proc. of the 21st International Conference on Principles and Practice of Constraint Programming, 2015, 429- 445.
17	CUSSENS J Bayesian network learning with cutting planes. Proc. of the 27th Conference on Uncertainty in Artificial Intelligence, 2011, 153- 160.
18	BARLETT M, CUSSENS J Advances in Bayesian network learning using integer programming. Proc. of the 29th Conference on Uncertainty in Artificial Intelligence, 2013, 182- 191.
19	BARTLETT M, CUSSENS J Integer linear programming for the Bayesian network structure learning problem. Artificial Intelligence, 2017, 244, 258- 271. doi: 10.1016/j.artint.2015.03.003
20	CUSSENS J, JARVISALO M, KORHONEN J H, et al Bayesian network structure learning with integer programming: polytopes, facets and complexity. Journal of Artificial Intelligence Research, 2017, 58 (1): 185- 229.
21	MALONE B, KANGAS K, JARVISALO M, et al Empirical hardness of finding optimal Bayesian network structures: algorithm selection and runtime prediction. Machine Learning, 2018, 107 (1): 247- 283. doi: 10.1007/s10994-017-5680-2
22	YANG Y, GAO X G, GUO Z G Finding optimal Bayesian networks by a layered learning method. Journal of Systems Engineering and Electronics, 2019, 30 (5): 946- 958. doi: 10.21629/JSEE.2019.05.12
23	WANG Z D, GAO X G, YANG Y, et al Learning Bayesian networks based on order graph with ancestral constraints. Knowledge-Based Systems, 2021, 211, 106515. doi: 10.1016/j.knosys.2020.106515
24	TAN X Y, GAO X G, WANG Z D, et al Bidirectional heuristic search to find the optimal Bayesian network structure. Neurocomputing, 2021, 426 (2): 35- 46.
25	DE CAMPOS C P, SCANAGATTA M, CORANI G, et al Entropy-based pruning for learning Bayesian networks using BIC. Artificial Intelligence, 2018, 260, 42- 50. doi: 10.1016/j.artint.2018.04.002
26	CORREIA A H C, CUSSENS J, DE CAMPOS C P On pruning for score-based Bayesian network structure learning. Proc. of the 32nd International Conference on Artificial Intelligence and Statistics, 2020, 2709- 2718.
27	MARGARITIS D. Learning Bayesian network model structure from data. Pittsburgh, USA: Carnegie Mellon University, 2003.
28	TSAMARDINOS I, BROWN L E, ALIFERIS C F The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 2006, 65 (1): 31- 78. doi: 10.1007/s10994-006-6889-7
29	TSAMARDINOS I, ALIFERIS C F, STATNIKOV A, et al Algorithms for large scale Markov blanket discovery. Proc. of FLAIRS Conference, 2003, 376- 381.
30	ALIFERIS C F, TSAMARDINOS I, STATNIKOV A HITON: a novel Markov blanket algorithm for optimal variable selection. Proc. of American Medical Informatics Association Annual Symposium, 2003, 21- 25.
31	TSAMARDINOS I, ALIFERIS C F, STATNIKOV A Time and sample efficient discovery of Markov blankets and direct causal relations. Proc. of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, 673- 678.
32	KOLLER D, FRIEDMAN N. Probabilistic graphical models: principles and techniques. Massachusetts: MIT Press, 2009.
33	RISSANEN J Modeling by shortest data description. Automatica, 1978, 14, 465- 471. doi: 10.1016/0005-1098(78)90005-5
34	SCHWARZ G Estimating the dimension of a model. The Annals of Statistics, 1978, 6 (2): 461- 464.
35	BUNTINE W Theory refinement on Bayesian networks. Proc. of the 7th Conference on Uncertainty in Artificial Intelligence, 1991, 52- 60.
36	TIAN J A branch-and-bound algorithm for MDL learning Bayesian networks. Proc. of the 16th Conference on Uncertainty in Artificial Intelligence, 2000, 580- 588.
37	PERRIER E, IMOTO S, MIYANO S Finding optimal Bayesian network given a super-structure. Journal of Machine Learning Research, 2008, 9 (10): 2251- 2286.
38	HE C C, GAO X G, WAN K F MMOS+ ordering search method for Bayesian network structure learning and its application. Chinese Journal of Electronics, 2020, 29 (1): 147- 153. doi: 10.1049/cje.2019.11.004
39	ALIFERIS C F, TSAMARDINOS I, STATNIKOV A R, et al Causal explorer: a causal probabilistic network learning toolkit for biomedical discovery. Proc. of the International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences, 2003, 371- 376.
40	BOERLAGE B. Link strength in Bayesian networks. Vancouver, Canada: University of British Columbia, 1992.
41	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

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	\|PPS\|	Time/s	\|PPS\|	Time/s	\|PPS\|	Time/s	\|PPS\|	Time/s	\|PPS\|
Wine	14	178	?	471	0.148	62	0.645	64	0.274	95	0.190	98
Adult	14	30 162	?	3 536	5.939	2 507	3 376.793	2 576	88.530	1 962	161.775	1 915
Zoo	17	101	?	823	0.133	80	0.663	82	0.263	111	0.217	118
Letter	17	20 000	?	115 671	6.056	13 636	2 950.391	13 585	662.529	36 264	2 505.648	36 264
Voting	17	435	?	392	0.161	72	0.758	75	0.573	124	0.520	128
Statlog	19	752	?	3 953	0.368	393	6.438	371	0.604	226	0.555	231
Hepatitis	20	126	?	302	0.166	86	0.651	88	0.257	90	0.206	94
Segment	20	2 310	?	3 423	0.586	557	13.710	514	2.043	412	2.025	426
Imports	22	205	?	1 388	0.265	167	2.019	158	0.452	212	0.385	223
Meta	22	528	?	42 527	0.291	321	2.388	329	8.123	1 939	7.947	1 516
Parkinsons	23	195	?	2 441	0.258	142	1.412	149	0.401	152	0.310	149
Heart	23	212	?	435	0.285	131	1.710	123	0.321	122	0.248	122
Horse	23	300	?	663	0.295	156	1.928	155	0.401	152	0.332	153
Mushroom	23	8 124	?	13 025	0.984	181	3.142	179	344.839	5 499	396.121	5 717
Autos	26	159	?	2 391	0.267	135	1.231	141	0.416	188	0.353	198

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp
Wine	14	178	0.008	2 807	0.003	1 415	0.003	1 138	0.004	1 975	0.004	1 371
Adult	14	30 162	0.046	12 416	0.040	12 415	0.040	12 414	0.040	12 332	0.039	12 310
Zoo	17	101	0.054	20 469	0.020	9 214	0.019	7 566	0.016	6 756	0.015	5 825
Letter	17	20 000	3.212	99 581	0.622	89 327	0.620	89 313	1.278	94 709	1.271	94 709
Voting	17	435	0.010	2 522	0.006	2 176	0.005	1 563	0.006	1 652	0.008	1 822
Statlog	19	752	0.906	220 236	0.294	74 676	0.335	80 678	0.275	68 507	0.238	73 410
Hepatitis	20	126	0.033	8 515	0.023	4 141	0.023	4 239	0.025	6 921	0.019	2 824
Segment	20	2 310	1.928	428 083	0.655	136 947	0.701	152 096	0.900	201 572	0.918	218 456
Imports	22	205	11.560	2 052 430	6.797	1 282 205	5.233	984 647	5.823	1 095 346	5.692	1 067 093
Meta	22	528	5.917	441 824	1.344	236 035	1.348	231 464	2.194	316 992	1.290	189 239
Parkinsons	23	195	7.169	1 152 578	6.988	1 229 496	1.522	261 314	1.237	204 660	1.204	196 702
Heart	23	212	23.488	4 456 334	16.236	3 274 159	15.476	3 139 622	15.652	3 405 704	17.202	3 517 762
Horse	23	300	15.754	3 126 901	13.218	2 722 928	12.205	2 526 467	12.725	2 457 079	12.173	2 618 225
Mushroom	23	8 124	0.601	49 593	0.030	5 917	0.027	5 328	0.263	29 159	0.358	38 835
Autos	26	159	45.141	4 762 546	7.072	896 549	12.71	1 596 750	12.848	1 448 494	14.911	1 646 928

Name	$n$	$N$	IAMB	interIAMBnPC	HITON_PC	MMPC
Name	$n$	$N$	Error/%	Error/%	Error/%	Error/%
Wine	14	178	0.478	0	0.047	0
Adult	14	30 162	0	0	0	0
Zoo	17	101	2.973	2.67	1.373	1.373
Letter	17	20 000	0.105	0.107	0	0
Voting	17	435	0.331	0.228	0.193	0.045
Statlog	19	752	0.608	0.608	0.534	0.459
Hepatitis	20	126	0.265	0.265	0.538	0.265
Segment	20	2 310	0.012	0.545	0.764	0.764
Imports	22	205	2.084	3.694	4.093	3.996
Meta	22	528	25.416	25.484	28.171	28.089
Parkinsons	23	195	8.015	2.915	2.180	1.357
Heart	23	212	0.552	0.300	0.695	0.565
Horse	23	300	0.298	0.136	0.253	0.169
Mushroom	23	8 124	14.367	14.506	2.369	2.074
Autos	26	159	2.088	3.185	2.828	2.607

Name	$n$	$N$	O		IAMB		interIAMBnPC		HITON_PC		MMPC
Name	$n$	$N$	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp	Time/s	Exp
Wine	14	178	0.008	4 172	0.003	1 934	0.003	1 537	0.004	2 757	0.004	1 948
Adult	14	30 162	0.067	30 948	0.054	29 172	0.057	31 018	0.047	28 321	0.050	3 1562
Zoo	17	101	0.055	25 131	0.021	10 992	0.019	9 096	0.018	8 916	0.015	7 772
Letter	17	20 000	3.839	129 184	0.883	147 182	0.855	139 858	1.546	134 134	1.535	134 134
Voting	17	435	0.011	3 771	0.006	3 929	0.006	2 800	0.006	2 474	0.007	2 865
Statlog	19	752	1.099	338 997	0.266	107 030	0.292	116 200	0.221	98 668	0.227	98 586
Hepatitis	20	126	0.032	10 641	0.018	5 842	0.017	5 424	0.029	104 90	0.012	3 826
Segment	20	2 310	3.311	908 547	0.800	289 212	0.891	329 840	1.080	413 734	1.171	442 602
Imports	22	205	18.539	3 075 638	9.601	1 688 208	7.011	1 388 255	8.296	1 606 617	7.824	1449 783
Meta	22	528	7.358	517 954	1.730	257 423	1.724	251 933	2.273	354 016	1.416	211 890
Parkinsons	23	195	8.659	1744 071	8.528	2 095 918	1.611	396 070	1.390	358 517	1.211	317 486
Heart	23	212	40.887	7 787 034	28.810	5 503 125	27.917	4 852 437	26.574	5 037 576	30.895	6 236 589
Horse	23	300	30.282	5 386 046	21.360	4 115 989	19.718	3 724 605	18.805	3 505 212	18.829	4 111 884
Mushroom	23	8 124	0.654	64 057	0.045	9 441	0.044	9 412	0.239	35 906	0.302	51 448
Autos	26	159	70.516	7 528 551	8.968	1 401 600	15.667	2 463 736	16.46	2 268 550	18.919	2 513 044

Name	$n$	$N$	IAMB	interIAMBnPC	HITON_PC	MMPC
Name	$n$	$N$	Error/%	Error/%	Error/%	Error/%
Wine	14	178	0.478	0	0.047	0
Adult	14	30 162	0	0	0	0
Zoo	17	101	2.973	2.67	1.373	1.373
Letter	17	20 000	0.105	0.107	0	0
Voting	17	435	0.331	0.228	0.193	0.045
Statlog	19	752	0.608	0.608	0.534	0.459
Hepatitis	20	126	0.265	0.265	0.538	0.265
Segment	20	2 310	0.012	0.545	0.764	0.764
Imports	22	205	2.084	3.694	4.093	3.996
Meta	22	528	25.416	25.484	28.171	28.089
Parkinsons	23	195	8.015	2.915	2.180	1.357
Heart	23	212	0.552	0.300	0.695	0.565
Horse	23	300	0.298	0.136	0.253	0.169
Mushroom	23	8 124	14.367	14.506	2.369	2.074
Autos	26	159	2.088	3.185	2.828	2.607

Causal constraint pruning for exact learning of Bayesian network structure

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 19

References 41

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Fang YE, Ying MAO, Yibing LI, Xinrui LIU. Target threat estimation based on discrete dynamic Bayesian networks with small samples [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1135-1142.
[2]	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.
[3]	Xiaoguang GAO, Yu YANG, Zhigao GUO. Learning Bayesian networks by constrained Bayesian estimation [J]. Journal of Systems Engineering and Electronics, 2019, 30(3): 511-524.
[4]	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.
[5]	Ruohai Di, Xiaoguang Gao, and Zhigao Guo. Learning Bayesian network parameters under new monotonic constraints#br# [J]. Journal of Systems Engineering and Electronics, 2017, 28(6): 1248-1255.
[6]	Binghua Song, Zhongbao Zhou, Chaoqun Ma, Jinglun Zhou, and Shaofeng Geng. Reliability analysis of monotone coherent multi-state systems based on Bayesian networks [J]. Journal of Systems Engineering and Electronics, 2016, 27(6): 1326-1335.
[7]	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.
[8]	Zhengdao Zhang, Jinlin Zhu, and Feng Pan. Fault detection and diagnosis for data incomplete industrial systems with new Bayesian network approach [J]. Journal of Systems Engineering and Electronics, 2013, 24(3): 500-.
[9]	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.
[10]	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.
[11]	Li Wang, and Mingzhe Wang. Modeling of combined Bayesian networks and cognitive framework for decision-making in C2 [J]. Journal of Systems Engineering and Electronics, 2010, 21(5): 812-820.
[12]	Lian Guangyao, Huang Kaoli, Chen Jianhui & Wei Zhonglin. Study of testability measurement method for equipment based on Bayesian network model [J]. Journal of Systems Engineering and Electronics, 2009, 20(5): 1017-1023.
[13]	Tang Zheng & Gao Xiaoguang. Research on the self-defence electronic jamming decision-making based on the discrete dynamic Bayesian network [J]. Journal of Systems Engineering and Electronics, 2008, 19(4): 702-708.
[14]	Chen Fei, Wang Xiufeng & Rao Yimei. Learning Bayesian networks using genetic algorithm [J]. Journal of Systems Engineering and Electronics, 2007, 18(1): 142-147.
[15]	Shi Zhifu , Zhang An & Wang Anli. Target distribution in cooperative combat based on Bayesian optimization algorithm* [J]. Journal of Systems Engineering and Electronics, 2006, 17(2): 339-342.