PICT-2008-0241: Diseño de algoritmos basados en independencia para el aprendizaje de modelos probabilísticos gráficos de mejor calidad

Nuestra investigación se enmarca en el problema del aprendizaje de representaciones gráficas de modelos probabilísticos (e.g., redes Bayesianas, redes Markovianas). Estos modelos presentan una importante aumento en la eficiencia del proceso de inferencia estadística y el de aprendizaje automatizado de dichos modelos a partir de conjuntos
de datos (Geman and Geman (1984); Besag et. al. 1991 and Anguelov et. al. 2005; Friedman et. al. 2000, otros). Los modelos gráficos (y el aprendizaje de estos modelos) consisten de dos partes: un grafo (que representa una estructura de independencias) y un conjunto de parámetros numéricos. El aprendizaje de la estructura de los modelos Markovianos ha presentado importantes dificultades computacionales debido a que requiere estimar los parámetros, un problema NP-completo para modelos Markovianos (Barahona 1982). Esta dificultad ha forzado la necesidad de recurrir a expertos para la estimación de las estructuras (e.g., Kindermann and Snell 1980, Geman and Geman 1984, Besag et. al. 1991).
En (Bromberg et al. 2006, 2007, 2007a, y Gandhi et al. 2008) se presentan una serie de algoritmos eficientes para el aprendizaje de estructuras Markovianas, que no requieren el aprendizaje de parametros. Estos utilizan un enfoque conocido como aprendizaje de estructuras basado en independencias (Spirtes et. al. 2000). Este enfoque consiste en la realización de una serie de tests estadísticos de independencias liminando, en cada iteración, aquellas estructuras inconsistentes con los resultados de estos tests.  Desafortunadamente, la enorme ventaja computacional obtenida por estos algoritmos se vé opacada por la sensibilidad en la calidad de los tests estadísticos de independencia - y por lo tanto de las estructuras producidas por estos algoritmos cuando los datos disponibles son insuficientes (Agresti 2002).

El presente proyecto propone mejorar la calidad de estos algoritmos por medio de dos métodos alternativos: La mejora de la calidad de los test estadísticos de independencia, y el diseño de algoritmos basados en independencias más robustos a errores en los test. El primer método consiste en generalizar el Argumentative Independence Test (AIT) de (Bromberg and Margaritis 2009). La principal hipótesis del AIT es que es posible mejorar la calidad de tests estadísticos de independencia por medio de la ejecución de tests relacionados y explotar ciertas restricciones que existen entre estos tests para corregir los resultados del test de interés. Generalizaremos el AIT por medio del estudio de metodologias alternativas a la de argumentación para explotar las restricciones. El segundo método consiste en atacar directamente el ?efecto cascada? (Spirtes et al 2001), que ocurre en los algoritmos basados en independencias. Estos algoritmos restringen los tests a ser realizados según el valor de los tests realizados hasta el momento. De esta manera, errores en los tests producen un efecto cascada desviando al algoritmo de la realización de tests mas relevantes e informativos.

Monto solicitado: 
$ 70.326 ARS
Fecha de inicio: 
Viernes, 11 Marzo, 2011
Fecha de finalización: 
Jueves, 11 Septiembre, 2014

Director

Facundo Bromberg

Tesistas Doctorales

Alejandro Edera

Federico Schlüter

Estudiantes de Grado

Diego Sebastián Pérez