Publicado

2014-07-01

Aprendizaje de Clases de Equivalencia de Redes Bayesianas basado en Búsqueda Competitiva de Hormigas Artificiales

Learning of bayesian networks equivalence classes based on competitive search of artificial ants

Palabras clave:

redes bayesianas, aprendizaje estructural, clases de equivalencia, colonia de hormigas, búsqueda heurística (es)

Descargas

Autores/as

  • Erwing Fabian Cardozo Ojeda Universidad Industrial de Santander
  • Henry Arguello Universidad Industrial de Santander

Título en español: Aprendizaje de clases de equivalencia de redes bayesianas basado en búsqueda competitiva de hormigas artificiales

Título en ingles: Learning of bayesian networks equivalence classes based on competitive search of artificial ants

Resumen: Este artículo propone un algoritmo de aprendizaje de clases de equivalencia de redes bayesianas basado en un algoritmo de búsqueda Greedy y modelos de búsqueda inspirados en hormigas competitivas. Específicamente para el algoritmo propuesto, se obtuvo una mejor aproximación entre la red predicha y la red bayesiana teórica de ejemplo ASIA, con respecto a algoritmos anteriores, para conjuntos de datos con 20 y 500 muestras. En promedio el algoritmo desarrollado obtuvo una aproximación con respecto a la distancia estructural de hamming de 10.7% y 5.3% menor comparada con la obtenida por los algoritmos Greedy y de colonia de hormigas (ACO-E) respectivamente para 20 muestras, y de hasta el 6.8% menor con respecto al algoritmo ACO-E para 500 muestras. Además, para 500 muestras el número de llamadas a la función de puntaje realizadas por el algoritmo propuesto fue menor que las realizadas por el algoritmo ACO-E en el 90% de las combinaciones, concluyendo que hubo una reducción de la complejidad computacional. Finalmente se presentan los resultados de la aplicación del algoritmo propuesto a un microarreglo obtenido por muestras de pacientes con Leucemia Mieloide Aguda (LMA) con 6 nuevas interacciones con dependencias estadísticas como potenciales interacciones biológicas con alta probabilidad.

Palabras clave: redes bayesianas, aprendizaje estructural, clases de equivalencia, colonia de hormigas, búsqueda heurística.

Abstract: This article proposes an algorithm for learning equivalence classes of Bayesian networks based on a Greed search algorithm and search patterns inspired by competitive ants. Specifically, for the proposed algorithm, we obtained a better approximation between the predicted network and the theoretical network ASIA with respect to previous algorithms for data sets with 20 and 500 samples. On average, the algorithm developed an approximation with respect to Structural Hamming Distance of 10.7% and 5.3% lower than Greedy algorithms and ACO-E respectively to 20 samples, and up to 6.8% lower tan ACO-E algorithm for 500 samples.  Furthermore, for 500 samples the number of calls to the scoring function performed by the algorithm proposed was smaller than in the ACO-E algorithm in 90% of the combinations, concluding that there was a reduction in the computational complexity. Finally, we present the results of applying the proposed algorithm to a microarray samples obtained from patients with acute myeloid leukemia (AML) with 6 new interactions with statistical dependencies as potential biological interactions with high probability.

Key words: Bayesian networks, learning sructural equivalence classes, ant colony, heuristic search.

Recibido: mayo 15 de 2013  Aprobado: octubre 1 de 2014

This article proposes an algorithm for learning equivalence classes of Bayesian networks based on a Greed search algorithm and search patterns inspired by competitive ants. Specifically, for the proposed algorithm, we obtained a better approximation between the predicted network and the theoretical network ASIA with respect to previous algorithms for data sets with 20 and 500 samples. On average, the algorithm developed an approximation with respect to Structural Hamming Distance of 10.7% and 5.3% lower than Greedy algorithms and ACO-E respectively to 20 samples, and up to 6.8% lower tan ACO-E algorithm for 500 samples. Furthermore, for 500 samples the number of calls to the scoring function performed by the algorithm proposed was smaller than in the ACO-E algorithm in 90% of the combinations, concluding that there was a reduction in the computational complexity. Finally, we present the results of applying the proposed algorithm to a microarray samples obtained from patients with acute myeloid leukemia (AML) with 6 new interactions with statistical dependencies as potential biological interactions with high probability.

Key words: Bayesian networks, learning sructural equivalence classes, ant colony, heuristic search.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Acid, S. and de Campos, L. M. 2003. Searching for bayesian network structures in the space of restricted acyclic partially directed graphs. Journal of Artificial Intelligence Research. 18: 445-490.

Castro, P. A. D. and Von Zuben, F. J. 2005. An immune-inspired approach to bayesian networks. in HIS '05: Proceedings of the Fifth International Conference on Hybrid Intelligent Systems, (Washington, DC, USA), pp. 23-28, IEEE Computer Society, 2005.

Chickering, D. M. 1996. Learning bayesian networks is np-complete. Pp. 121-130.

Chickering, D. M. 2002. Learning equivalence classes of bayesiannetwork structures. The Journal of Machine Learning Research. 2: 445 - 498.

Cooper, G. F. and Herskovits, E. 1992. A bayesian method for the induction of probabilistic networks from data. Machine Learning. 9(4): 309-347.

Daly, R. and Shen, Q. 2009. Learning bayesian network equivalence classes with ant colony optimization. Artificial Intelligence Research. 35: 391-447.

Daly, R. Shen; Q. Aitken, S. 2011. Learning Bayesian networks: approaches and issues. The Knowledge Engineering Review. 26(2): 99-157.

De Campos, L. M.; Fernández-Luna, J. M.; Gámez, J. A., and Puerta, J. M.. 2002. Ant colony optimization for learning bayesian networks. International Journal of Approximate Reasoning. 31(3): 291 - 311.

Djebbari, A.; Quackenbush, J. 2008. Seeded bayesian networks: Constructing genetic networks from microarray data. BMC Systems Biology. 2(1): 57.

Dorigo, M.; Blum, C. 2005. Ant colony optimization theory: A survey. Theoretical Computer Science. 344(2-3): 243 - 278.

Du, Z.; Wang, Y.; Ji; Z. June 2009. A new structure learning method for constructing gene networks. Bioinformatics and Biomedical Engineering, ICBBE 2009. 3rd International Conference. Pp. 1-4.

Gillispie, S. B. 2006. Formulas for counting acyclic digraph markov equivalence classes. Journal of Statistical Planning and Inference. 136(4): 1410 - 1432.

Heckerman, D. 1995. A tutorial on learning with bayesian networks. Tech. Rep., Microsoft Research.

Jensen, F. V. and Nielsen, T. D. 2007. Bayesian Networks and Decision Graphs. Springer Science + Business Media, LLC.

Larrañaga, P.; Karshenas, H.; Bielza, C. and Santana R. 2013. A review on evolutionary algorithms in Bayesian network learning and inference tasks. Information Sciences. 233: 109-125.

Meloni, R.; Khalfallah, O., and Faucon Biguet, N. 2004. DNA microarrays and pharmacogenomics. Pharmacological Research. 49(4): 303 - 308.

Needham, C.; Manfield, I.; Bulpitt, A.; Gilmartin, P.; and Westhead, D. 2009. From gene expression to gene regulatory networks in arabidopsis thaliana. BMC Systems Biology. 3(1): 85.

Pe'er, D. 2005. Bayesian Network Analysis of Signaling Networks: A Primer. Sci. STKE, 281: 14.

Pinto, P.; Nagele, A.; Dejori, M.; Runkler, T.; and Sousa, J. 2009.Using a local discovery ant algorithm for bayesian network structure learning. Evolutionary Computation, IEEE Transactions on. 13: 767-779.

Quackenbush, J. 2002. Microarray data normalization and transformation. Nature Genetics. 32: 496-501.

Verhaak, R.G.W.; Wouters, B.J.; Erpelinck, C.A.J.; Abbas, S.; Beverloo, H.B.; Lugthart, S.; Lwenberg, B.; Delwel, R.; and Valk, P.J.M. 2009. Prediction of molecular subtypes in acute myeloid leukemia based on gene expression profiling. Haematologica. 94(1): 131- 134.

Wang, L. and Li, Paul C.H. 2011. Microfluidic DNA microarray analysis: A review. Analytica Chimica Acta. 687(1): 12 - 27.

Wieser, R. 2007. The oncogene and developmental regulator evi1: Expression, biochemical properties, and biological functions. Gene. 396(2): 346 - 357.

Wong, M. L. and Leung, K. S. Aug. 2004. An efficient data mining method for learning bayesian networks using an evolutionary algorithm-based hybrid approach. Evolutionary Computation, IEEE Transactions. 8: 378-404.

Zhang, Y.; Zhang,W.; Xie, Y. 2013. Improved heuristic equivalent search algorithm based on Maximal Information Coefficient for Bayesian Network Structure Learning. Neurocomputing. 117: 186-195.

Licencia

Derechos de autor 2014 Revista Colombiana de Biotecnología

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Esta es una revista de acceso abierto distribuida bajo los términos de la Licencia Creative Commons Atribución 4.0 Internacional (CC BY). Se permite el uso, distribución o reproducción en otros medios, siempre que se citen el autor(es) original y la revista, de conformidad con la práctica académica aceptada. El uso, distribución o reproducción está permitido desde que cumpla con estos términos.

Todo artículo sometido a la Revista debe estar acompañado de la carta de originalidad. DESCARGAR AQUI (español) (inglés).