An Optimization Approach for Structural Learning Bayesian Networks Based on Prior Node Ordering
-
摘要: 针对小样本数据集下学习贝叶斯网络 (Bayesian networks, BN)结构的不足, 以及随着条件集的增大, 利用统计方法进行条件独立 (Conditional independence, CI) 测试不稳定等问题, 提出了一种基于先验节点序学习网络结构的优化方法. 新方法通过定义优化目标函数和可行域空间, 首次将贝叶斯网络结构学习问题转化为求解目标函数极值的数学规划问题, 并给出最优解的存在性及唯一性证明, 为贝叶斯网络的不断扩展研究提出了新的方案. 理论证明以及实验结果显示了新方法的正确性和有效性.Abstract: To solve the drawbacks of learning Bayesian networks (BN) from small data set and the unreliability of the conditional independence (CI) tests when the conditioning sets become too large, this paper proposes an optimization approach for structural learning Bayesian networks based on prior node ordering. It is the first time that a problem of structural learning for a Bayesian network is transformed into its related mathematical programming problem by defining objective function and feasible region. And, we have proved the existence and uniqueness of the numerical solution. The approach offers a new opinion for the research of extended Bayesian networks. Theoretical and experimental results show that the new approach is correct and effective.
-
[1] Cai Z Q, Sun S D, Si S B, Yannou B. Identifying product failure rate based on a conditional Bayesian network classifier. Expert Systems with Applications, 2011, 38(5): 5036-5043[2] Hsieh N C, Hung L P. A data driven ensemble classifier for credit scoring analysis. Expert Systems with Applications, 2011, 37(1): 534-545[3] Sun Y, Tang Y Y, Ding S X, Lv S P, Cui Y F. Diagnose the mild cognitive impairment by constructing Bayesian network with missing data. Expert Systems with Applications, 2011, 38(1): 442-449[4] Ben-Gal I, Shani A, Gohr A, Grau J, Arviv S, Shmilovici A, Posch S, Grosse I. Identification of transcription factor binding sites with variable-order Bayesian networks. Bioinformatics, 2005, 21(11): 2657-2666[5] Aquaroa V, Bardoscia M, Bellotti R, Consiglio A, Carlo F D, Ferri G. A Bayesian networks approach to operational risk. Physica A: Statistical Mechanics and Its Applications, 2010, 389(8): 1721-1728[6] Bouchaala L, Masmoudi A, Gargouri F, Rebai A. Improving algorithms for structure learning in Bayesian networks using a new implicit score. Expert Systems with Applications, 2010, 37(7): 5470-5475[7] Perrier E, Imoto S, Miyano S. Finding optimal Bayesian network given a super-structure. Journal of Machine Learning Research, 2008, 9: 2251-2286[8] Borgelt C. A conditional independence algorithm for learning undirected graphical models. Journal of Computer and System Sciences, 2010, 76(1): 21-33[9] Ji Jun-Zhong, Zhang Hong-Xun, Hu Ren-Bing, Liu Chun-Nian. A Bayesian network learning algorithm based on independence test and ant colony optimization. Acta Automatica Sinica, 2009, 35(3): 281-288[10] Robinson R W. Counting unlabeled acyclic digraphs. Lecture Notes in Mathematics. Berlin: Springer, 1977. 28-43[11] Heckerman D, Geiger D, Chickering D M. Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning, 1995, 20(3): 197-243[12] Pellet J P, Elisseef A. Using Markov blankets for causal structure learning. Journal of Machine Learning Research, 2008, 9: 1295-1342[13] Cheng J, Greiner R, Kelly J, Bell D, Liu W. Learning Bayesian networks from data: an information-theory based approach. Artificial Intelligence, 2002, 137(1-2): 43-90[14] Tsamardinos I, Brown L F, Aliferis C F. The max-min hill-climbing Bayesian networks structure learning algorithm. Machine Learning, 2006, 65(1): 31-78[15] 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: 2149-2187[16] Ziegler V. Approximation algorithms for restricted Bayesian network structures. Information Processing Letters, 2008, 108(2): 60-63[17] Chen X W, Anantha G, Lin X. 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): 628-640[18] Kullback S. Information Theory and Statistics. New York: Dover Publication, 1968[19] Lauritzen S, Spiegelhalter D. Local computations with probabilities on graphical structures and their application on expert systems. Journal of the Royal Statistical Society: Series B, 1988, 50(2): 157-224[20] Cooper G, Hersovits E. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 1992, 9(4): 309-347
点击查看大图
计量
- 文章访问数: 2528
- HTML全文浏览量: 72
- PDF下载量: 984
- 被引次数: 0