Learning Bayesian networks skeleton: a comparison between TPDA and PMMS algorithm

"Learning the bayesian network structure from a database is an NP-Hard problem for which the existent learning algorithms generally have exponential complexity. During this work in the Master, I did a bibliographic research as well as a comparison between two recent algorithms called TPDA and PMMS (2005) that learns the skeleton of bayesian networks from data. These algorithms have the advantage of having polynomial complexity, and provide good results for learning. After having done a theoretical analysis of the algorithms, I continue with an empiric analysis that consisted in testing these algorithms on data generated from networks knew by the scientific community (I used ASIA and ALARM networks). These tests have been made with the help of the toolboxes developed in Matlab (FullBNT, BNT – SLP and CausalExplorer). The results I have gotten by this analysis have permitted me to make some interesting conclusions about the efficiency and the limits of application of these algorithms." "El aprendizaje del esqueleto de una red bayesiana a partir de una base de datos es un problema NP-Dificil para el cual los algoritmos de aprendizaje existentes son generalmente de complejidad exponencial. En el transcurso de la pasantía del Master, he efectuado una investigación bibliográfica así como una comparación entre dos algoritmos recientes de aprendizaje del esqueleto de las redes bayesianas. Ellos son TPDA y PMMS (2005). Estos algoritmos tienen la ventaja de tener una complejidad polinomial y proveen buenos resultados de aprendizaje. Luego de haber efectuado un análisis teórico de los algoritmos, he continuado con un análisis empírico. Este consistió en testear estos algoritmos sobre datos generados a partir de redes conocidas por la comunidad científica (he utilizado la red ASIA y ALARM). Esto fue realizado con la ayuda de las cajas de herramientas desarrolladas en Matlab (FullBNT , BNT – SLP y CausalExplorer). Los resultados obtenidos por este análisis me permitieron formular conclusiones interesantes en cuanto a la eficacia y a los límites de aplicación de estos algoritmos." Proyecto final Ingeniería Industrial (grado) - Instituto Tecnológico de Buenos Aires, Buenos Aires, 2006