Las redes de Markov son modelos probabilísticos gráficos, una herramienta computacional para el modelado eficiente de distribuciones de probabilidad que utiliza grafos para facilitar la representación de problemas complejos. Estos modelos han sido diseñados para ser manipulados por sistemas expertos, utilizando la teoría de la probabilidad para razonar eficientemente bajo condiciones de incertidumbre. Sin embargo, una limitación importante para el uso de estos modelos es que en la práctica resulta complejo diseñarlos manualmente, ya que el conocimiento de expertos no siempre es suficiente, sumado al hecho de que muchos dominios reales poseen una gran dimensionalidad. Por esto, el aprendizaje de estos modelos a partir de datos es un tópico que ha tomado gran relevancia, ya que la disponibilidad de datos digitales es cada vez mayor, resultando además en un mecanismo interesante para descubrir nuevo conocimiento a partir de datos digitales.

En este trabajo, la investigación se centra en un enfoque específico de aprendizaje de redes de Markov: los algoritmos basados en independencia. Estos algoritmos están diseñados para aprender la estructura de independencias del modelo, que es la componente que codifica de un modo compacto el conocimiento sobre la distribución. Los algoritmos basados en independencia han sido diseñados bajo lineamientos teóricos que permiten aprender la estructura de un modo eficiente y robusto, a partir de la ejecución de un conjunto de tests estadísticos de independencia sobre los datos. Comúnmente, los resultados de dichos tests son utilizados como restricciones que guían una búsqueda en el espacio de las estructuras de independencia posibles, convergiendo a una estructura que satisface los resultados de todos los tests. Estos algoritmos garantizan que la estructura aprendida es correcta bajo la suposición de que los tests estadísticos son confiables. No obstante, un hecho muy común en la práctica suele ser que los datos disponibles no son suficientes para obtener resultados correctos desde los tests estadísticos. Cuando esto sucede, los algoritmos basados en independencia acumulan y propagan suposiciones de independencia incorrectas, resultando en un aprendizaje con gran cantidad de errores estructurales. Este hecho, que resulta en una limitación de real importancia a la hora de aplicar esta tecnología, es la motivación de la presente tesis.

En este trabajo se presenta el enfoque de máximo a posteriori basado en independencias para aprendizaje de estructuras de redes de Markov (IBMAP, del inglés independence-based maximum-a-posteriori). Dado que los algoritmos tradicionales descartan la estructura correcta cada vez que ejecutan un test erróneo, se propone un enfoque que asigna probabilidades a las distintas estructuras, sin descartar ninguna. Para esto, se propone una función de puntaje de estructuras basada en tests estadísticos denominada IB-score (puntaje basado en independencias). Esta función permite computar de un modo aproximado la probabilidad a posteriori de una estructura dados los datos Pr(G|D), combinando los resultados de un conjunto de tests estadísticos. De este modo, las diferentes estructuras poseen un puntaje más alto o más bajo según las probabilidades de las independencias que codifican. En resumen, el enfoque propuesto consiste en la maximización de la función IB-score sobre el espacio de todas las estructuras posibles. A modo de instanciación de este enfoque se presenta una srie de algoritmos que maximizan dicha función con diversos mecanismos de optimización. 

Para validar el enfoque se evaluó el desempeño de las distintas instanciaciones de la búsqueda, evaluando la calidad de las estructuras aprendidas con respecto a algoritmos basados en independencia que pertenecen al estado del arte. Se presentan resultados sistemáticos sobre una gran variedad de dimensiones del problema, demostrando que este enfoque permite mejorar significativamente la calidad de las estructuras aprendidas. Se demuestra también que dichas mejoras pueden obtenerse a un costo computacional competitivo respecto de los algoritmos del estado del arte. Dicha experimentación fue llevada a cabo sobre datos sintéticos y datos del mundo real, y en una aplicación de aprendizaje de estructuras para algoritmos evolutivos.