Resumen de Bayesian networks: structural learning on alternative search spaces and applications
Juan Ignacio Alonso Barba 
Las redes Bayesianas son un modelo gráfico probabilístico que utilizan un grafo dirigido acíclico (GDA) para representar relaciones de independencia entre un conjunto de variables aleatorias. Las redes Bayesianas representan la distribución de probabilidad conjunta sobre las variables del grafo de una forma compacta, lo que hace posible algoritmos de inferencia eficientes. Las redes Bayesianas se usan con frecuencia para modelar diferentes tipos de dominios, y estos modelos pueden usarse tanto para representar las relaciones causales y/o estadísticas como para estimar probabilidades.
Aunque las redes Bayesianas pueden ser construidas manualmente por expertos, es más común aprenderlas directamente a partir de datos. La estrategia de búsqueda+score usa una función que evalúa cada red candidata y un algoritmo de búsqueda para encontrar la red con la mejor métrica. Respecto al espacio de búsqueda, la estrategia más directa es usar un GDA para representar cada potencial solución. Sin embargo, existen espacios de búsqueda alternativos que presentan ciertas ventajas respecto al espacio de los GDA. Dos de estos espacios alternativos son el espacio de órdenes y el de clases de equivalencia.
Greedy Equivalence Search (GES) es el algoritmo de búsqueda más representativo para el aprendizaje de redes Bayesianas sobre el espacio de clases de equivalencia y está considerado como el algoritmo de referencia para el aprendizaje. GES no sólo presenta resultados competitivos en la práctica, si no que además, bajo condiciones de fidelidad, asindóticamente obtiene un mapa de independencias perfecto de la distribución de probabilidad original.
En estas tesis, presentamos un conjunto de variaciones de GES basadas en 2 ideas principales: 1) restringir el espacio de búsqueda para obtener algoritmos más eficientes y 2) mejorar la búsqueda local con el uso de metaheurísticas de búsqueda local para escapar de los óptimos locales. Desde el punto de vista teórico, la mayoría de nuestras propuestas mantienen las mismas propiedades teóricas que el algoritmo base. Desde el punto de vista práctico, las diferentes propuestas han sido probadas en profundidad obteniendo que el primer conjunto de algoritmos son más eficientes que GES y obtienen un nivel de exactitud similar a GES y el segundo grupo obtiene redes más exactas a costa de ser menos eficientes.
Para la búsqueda de redes Bayesianas en el espacio de órdenes, se debe definir un método para convertir un orden en un GDA. Entonces, el valor de la métrica para la red aprendida a partir del orden se usa como valor de la métrica del propio orden. Para lograr este objetivo (es decir, convertir un orden en un GDA), presentamos el algoritmo K2M, una variante del algoritmo K2 original equipado con un operador de borrado. Basados en el algoritmo K2M, se presentan una serie de algoritmos de búsqueda locales en el espacio de órdenes que son competitivos con GES en términos de eficiencia y exactitud.
Respecto al comportamiento teórico de los algoritmos de búsqueda en el espacio de órdenes, nosotros hemos probado que el algoritmo K2M y los algoritmos locales basados en él, obtienen de forma asindótica un mapa de independencias mínimo de la distribución de probabilidad original bajo condiciones de fidelidad.
Finalmente, respecto al objetivo de aplicar las redes Bayesianas para la resolución de un problema real, se presenta un método basado en un clasificador Naïve Bayes de dos niveles para la detención y el conteo de un cierto tipo de células en imágenes médicas.
