Learning Bayesian Networks with the Combination of Evolutionary Algorithm and EMI Method  

作　　者：TIAN Fengzhan YU Jian HUANG Houkuan 

机构地区：[1]School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China

出　　处：《Chinese Journal of Electronics》2008年第3期437-442,共6页电子学报（英文版）

基　　金：Manuscript Received Apr. 2007; Accepted Nov. 2007. This work is supported by the National Natural Science Foundation of China （No.60503017）, Beijing Nova Program （No.2006A17） and the Science Foundation of Beijing Jiaotong University （No.2005SM012）.

摘　　要：Most Bayesian network （BN） learning algorithms use EMI algorithm to deal with incomplete data. But EMI algorithm is of low efficiency due to its iterative parameter refinement, and the problem will become even worse when multiple runs of EMI algorithm are needed. Besides, EMI algorithm usually converges to local maxima, which also degrades the accuracy of EMI based BN learning algorithms. In this paper, we replace EMI algorithm used in BN learning tasks with EMI method to deal with incomplete data. EMI is a very efficient method, which estimates probability distributions directly from incomplete data rather than performs iterative refinement of parameters. Base on EMI method, we propose an effec- tive algorithm, namely EMI-EA. EMI-EA algorithm uses EMI method to estimate probability distribution over local structures in BNs, and evaluates BN structures with a variant of MDL scoring function. To avoid getting into local maxima of the search process, EMI-EA evolves BN struc- tures with an Evolutionary algorithm （EA）. The experi- mental results on Alarm, Asia and an examplar network show that EMI-EA algorithm outperforms EMI-EA for all samples and E-TPDA algorithms for small and middle size of samples in terms of accuracy. In terms of efficiency, EMI-EA is comparable with E-TPDA algorithm and much more efficient than EMI-EA algorithm. EMI-EA also out- performs EMI-EA and M-V algorithm when learning BNs with hidden variables.

关 键 词：Bayesian networks LEARNING Evolutionary algorithm EMI method 

分 类 号：TN911.7[电子电信—通信与信息系统]