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()   

  • 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:

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(ρ2n-1) from O(n2n-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)