Learning Bayesian Networks in the Space of Structures by a Hybrid Optimization Algorithm
Keywords:
Bayesian network, Artificial Bee Colony, Structural learning, Metaheuristics, Scoring functionAbstract
Bayesian networks (BNs) are one of the most widely used class for machine learning and decision making tasks especially in uncertain domains. However, learning BN structure from data is a typical NP-hard problem. In this paper, we present a novel hybrid algorithm for BN structure learning, called MMABC. It’s based on a recently introduced meta-heuristic, which has been successfully applied to solve a variety of optimization problems: Artificial Bee Colony (ABC). MMABC algorithm consists of three phases: (i) obtain an initial undirected graph by the subroutine MMPC. (ii) Generate the initial population of solutions based on the undirected graph and (iii) perform the ABC algorithm to orient the edges. We describe all the elements necessary to tackle our learning problem, and experimentally compare the performance of our algorithm with two state-of-the-art algorithms reported in the literature. Computational results demonstrate that our algorithm achieves better performance than other two related algorithms.
References
Z. Cai, S. Sun, S. Si, B. Yannou, Identifying product failure rate based on a conditional Bayesian network classifier, Expert Systems with Applications, 38(5): 5036-5043. http://dx.doi.org/10.1016/j.eswa.2010.09.146
Y. Sun, Y.Y. Tang, S.X. Ding, S.P. Lv, Y.F. Cui, Diagnose the mild cognitive impairment by constructing Bayesian network with missing data,Expert Systems with Applications, 38(1): 442-449. http://dx.doi.org/10.1016/j.eswa.2010.06.084
V. Aquaroa, M. Bardoscia, R. Bellotti, A. Consiglio, F.D. Carlo, G. Ferri, A Bayesian Networks approach to Operational Risk, Physica A, 389(8): 1721-1728. http://dx.doi.org/10.1016/j.physa.2009.12.043
D.C. Kim, X. Wang, C.R. Yang, J. Gao, Learning biological network using mutual information and conditional independence, BMC Bioinformatics, 11(3): S9. http://dx.doi.org/10.1186/1471-2105-11-s3-s9
S. Nikolajewa, R. Pudimat, M. Hiller, M. Platzer, R. Backofen, BioBayesNet: a web server for feature extraction and Bayesian network modeling of biological sequence data, Nucleic Acids Research, 35: 688-693. http://dx.doi.org/10.1093/nar/gkm292
R. Wei, J. Zhen, L. Bao, Study on mining big users data in the development of HuBei auto-parts enterprise, Mathematical modelling of engineering problems, 2(4): 1-6.
K. Burns, Bayesian inference in disputed authorship: a case study of cognitive errors and a new system for decision support, Information Science, 176(11): 1570-1589. http://dx.doi.org/10.1016/j.ins.2005.04.011
S. Lee, Y. Son, J. Jin, Decision fild theory extentions for behavior modelling in dynamic environment using Bayesian belief network, Information Science, 178(10) 2297-2314. http://dx.doi.org/10.1016/j.ins.2008.01.009
J. Cheng, R. Greiner, J. Kelly, D. Bell, W. Liu, Learning Bayesian networks from data: an information theory based approach, Artificial Intelligence, 137: 43-90. http://dx.doi.org/10.1016/S0004-3702(02)00191-1
J.P. Pellet, A. Elisseef, Using Markov Blankets for Causal Structure learning, Journal of Machine Learning Research, 9: 1295-1342.
C. Borgelt, A conditional independence algorithm for learning undirected graphical models, Journal of Computer and System Sciences, 76: 21-33. http://dx.doi.org/10.1016/j.jcss.2009.05.003
E. Perrier, S. Imoto, S. Miyano, Finding Optimal Bayesian Network Given a Super- Structure, Journal of Machine Learning Research, 9: 2251-2286.
L.M. de Campos, A Scoring Function for Learning Bayesian Networks based on Mutual Information and Conditional Independence Tests, Journal of Machine Learning Research, 7: 2149-2187.
L.M. de Campos, J.M. Fern andez-Luna, J.A. G amez, J.M. Puerta, Ant colony opyimization for learning Bayesian networks, International Journal of Approximate Reasoning, 31: 291- 311. http://dx.doi.org/10.1016/S0888-613X(02)00091-9
R. Daly, Q. Shen, Learning Bayesian Network Equivalence Classes with Ant Conoly Optimization, Journal of Artificial Intelligence Research, 35: 391-447.
L. Bouchaala, A. Masmoudi, F. Gargouri, A. Rebai,Improving algorithms for structure learning in Bayesian Networks using a new implicit score, Expert Systems with Applications, 37: 5470-5475. http://dx.doi.org/10.1016/j.eswa.2010.02.065
J. Ji, H. Wei, C. Liu, An artificial bee colony algorithm for learning Bayesian networks, Soft Computing, 17: 983¨C994.
I. Tsamardinos, L.F. Brown, C.F. Aliferis, The max-min hillclimbing BN structure learning algorithm, Machine Learning, 65: 31-78. http://dx.doi.org/10.1007/s10994-006-6889-7
D. Karaboga, An idea based on honey bee swarm for numerical optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department.
D. Karaboga, B. Basturk, On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing, 8: 687-697. http://dx.doi.org/10.1016/j.asoc.2007.05.007
R.W. Robinson, Counting unlabeled acyclic digraphs, Combinational Mathematics, 622: 28-43.
D. Chickering, D. Heckerman, C. Meek, Large-Sample Learning of Bayesian Networks is NP-hard, Journal of Machine Learning Research, 5: 1287-1330.
G. Cooper, E. Hersovits, A bayesian method for the induction of probabilistic networks from data, Machine Learning, 9: 309-347. http://dx.doi.org/10.1007/BF00994110
P.C. Pinto, A. Nagele, M. Dejori, T.A. Runkler, J.M.C. Sousa, Using a Local Discovery Ant Algorithm for Bayesian Network Structure Learning, IEEE transactions on evolutionary computation, 13(4): 767-779. http://dx.doi.org/10.1109/TEVC.2009.2024142
K. Murphy, The Bayes net toolbox for Matlab, Computing Science and Statistics, 33: 331- 350.
C.F. Aliferis, I. Tsamardinos, A. statnikov, L.E. Brown, Causal Explorer: A causal probabilistic network learning tooltik for biomedical discovery, In Proceedings of the International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences, 371-376.
S.Lauritzen, D.Spiegelhalter, Local Computations with Probabilities on Graphical Structures and Their Application on Expert Systems, J.Royal Statistical Soc., 50: 157-224.
I. Beinlich, G. Suermondt, R. Chavez, G.Cooper, The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks, Proc. Second European Conf. Artificial Intelligence in Medicine. http://dx.doi.org/10.1007/978-3-642-93437-7_28
J. Binder, D. Koller, S.J. Ruddell, K. Kanazawa, Adaptive probabilistic networks with hidden variables, Machine Learning, 29: 213-244. http://dx.doi.org/10.1023/A:1007421730016
T. Hrycej, Gibbs sampling in BNs, Artificial Intelligence, 46(3): 351-363. http://dx.doi.org/10.1016/0004-3702(90)90020-Z
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
