Enfoque perturbativo para mejorar la calidad de modelos probabilísticos gŕaficos

SCHLUTER, FEDERICO; BROMBERG, FACUNDO

Los Reyunos, San Rafael, Mendoza, ARGETINA

Congreso; Encuentro de Investigadores y Docentes de Ingeniería (EnIDI); 2009

UTN-FRM y UNCuyo

Existen infinidad de campos de la ciencia que se benefician de la posibilidad de calcular automáticamente la probabilidad de ciertas cantidades de interés, una tarea difícil y costosa de observar directamente. Una herramienta que ha recibido un creciente interés en los últimos años son los modelos probabilísticos gráficos, modelos que por medio de un grafo con nodos como variables del dominio, representan  explícitamente por medio de sus aristas las independencias probabilísticas entre estas variables. El conocimiento y codificación explícita de estas independencias permite mejoras exponenciales en la eficiencia del proceso de su aprendizaje a partir del análisis de los datos, de su re\-pre\-sen\-ta\-ción en memoria, y su uso para estimación de probabilidades de subconjuntos de variables del dominio. Redes Bayesianas y redes Markovianas son sub-familias de modelos gráficos, muy utilizadas en incontables áreas de investigación. En este trabajo nos concentramos en el aprendizaje de las estructuras de independencia de redes Markovianas, un campo muy poco explorado en contraste con el aprendizaje de redes de Bayes. Presentamos un enfoque práctico, al cual llamamos enfoque perturbativo, que mejora la calidad de las estructuras de redes Markovianas aprendidas (i.e., acercándolas a las estructuras correctas). En trabajos previos de los autores se presentó este enfoque demostrando importantes mejoras en la calidad, pero con tiempos de corrida exponencial. En este trabajo presentamos una implementación práctica del enfoque, que con tiempos de corrida polinomiales aún produce importantes mejoras en la calidad de las estructuras aprendidas.