Comparación eficiente de estructuras de independencia de modelos loglineales

Abstract

Las distribuciones de probabilidad discretas capturan diversas relaciones entre variables aleatorias, tales como independencias marginales o independencias condicionales. Estos patrones conforman en conjunto lo que se denomina una estructura de independencias. Estas estructuras cumplen dos roles: por un lado, facilitar múltiples reducciones en complejidad, y por otro, capturar conocimiento acerca del dominio de interés. Lo primero consiste en la capacidad de las estructuras para reducir la complejidad muestral de algoritmos que aprenden las distribuciones a partir de observaciones, la complejidad espacial para almacenar las distribuciones en memoria, y la complejidad temporal para realizar inferencia con ellas. Lo segundo ocurre debido a que las estructuras permiten extraer afirmaciones probabilísticas acerca de los eventos posibles de las variables. A pesar de la utilidad de este conocimiento estructural, no fue posible comenzar a obtenerlo, manipularlo e interpretarlo eficientemente hasta la introducción de los modelos probabilísticos gráficos en la década de 1980. Debido a su versatilidad, los modelos probabilísticos gráficos han tenido un gran auge hasta la actualidad. Sin embargo, su eficiencia tiene como contraparte una limitación de expresividad: su representación mediante grafos —dirigidos o no dirigidos— les impide capturar relaciones de grano más fino conocidas como independencias específicas del contexto. Estas definen una estructura local o contextual dentro del modelo. El interés en este tipo de estructuras contextuales ha resultado en muchos avances en una familia de distribuciones de probabilidad más general, que incluye a los modelos gráficos, conocida como modelos loglineales. En ellos, la estructura de independecias puede representar no solo independencias marginales y condicionales, sino también independencias específicas del contexto. En los últimos años, ha habido un resurgimiento de interés en el desarrollo de enfoques para el aprendizaje automático de estructuras de independencias de modelos loglineales a partir de datos. Como resultado, existen actualmente diversos algoritmos que permiten el aprendizaje, la manipulación y la inferencia eficientes de estas estructuras. Sin embargo, no existía aún un método eficiente para evaluar estos enfoques de manera directa en términos de las estructuras de los modelos. Los únicos métodos conocidos evalúan estos enfoques de forma indirecta a través del modelo completo producido, el cual incluye no solo la estructura sino también los parámetros del modelo, introduciendo distorsiones potenciales en la comparación. Esta tesis presenta un método que permite una medición directa para comparar las estructuras de independencia de modelos loglineales, inspirada en la distancia de Hamming utilizada en modelos gráficos no dirigidos, los cuales constituyen solo un subconjunto de los modelos loglineales. La medida presentada provee las ventajas de poder ser computada eficientemente en términos del número de variables del dominio, y de permitir definir una distancia con las propiedades formales de una métrica.