Entorno para el Desarrollo de Modelos Gráficos Probabilísticos



Plan de Trabajo

El plan de trabajo se estructura en 20 tareas (3 para los objetivos de tipo A, 11 para los objetivos de tipo B y 6 para los de tipo C). Cada tarea tiene asignado un equipo responsable y uno o varios colaboradores. El responsable tendrá la obligación de presentar los resultados de la tarea. Los colaboradores tienen experiencia previa en el tema y aportarán ideas, sugerencias y su trabajo anterior (por ejemplo, algoritmos previamente desarrollados). Participarán también en la experimentación y evaluación de los programas.

El plan de trabajo incluye también la realización de 4 reuniones en las que participarán todos los grupos. Servirán de base para la interacción dentro del proyecto. Estas reuniones estarán abiertas a otros grupos españoles que se quieran integrar en el proceso de normalización y construcción del entorno de desarrollo.

A continuación se detallan las tareas.

A.1
Determinacion de Estructuras de Datos Comunes
Responsable: Universidad de Almería
Colaboradores: Todos los grupos

Un aspecto fundamental en la implementación de algoritmos para el tratamiento de redes bayesianas es la definición de unas estructuras de datos adecuadas. Dentro de esta tarea consideramos la especificación, implementación y revisión de estructuras de datos comunes a los diferentes métodos tratamiento de redes bayesianas.

Deben desarrollarse en esta fase estructuras de datos orientadas a objetos capaces de representar redes bayesianas, tanto estáticas como dinámicas, árboles de cliques, variables discretas y continuas y potenciales de probabilidad. En este último caso, pensamos que es acertado el uso de árboles de decisión. Éstos permiten un tratamiento más eficiente de las distribuciones de probabilidad que las clásicas matrices, además de permitir una representación selectiva de los valores más "importantes" de la distribución, lo que es especialmente interesante para los algoritmos de Monte Carlo.

Las estructuras que en esta tarea se definan deben ser lo suficientemente flexibles como para permitir el uso futuro de otros formalismos para el tratamiento de la incertidumbre distintos de la probabilidad, por ejemplo, probabilidades imprecisas, convexos de probabilidades, funciones de creencia, etc.

Asimismo debe definirse un formato de archivo para el almacenamiento en memoria masiva de las redes. Este formato cumplirá las especificaciones básicas de Microsoft Research.

Temporización

A.2
Librería de Representación Gráfica
Responsable: Universidad de Granada
Colaboradores: Todos los grupos

Se desarrollará una librería de funciones para leer, escribir y editar grafos de dependencias. Incluirá la posibilidad de crear y borrar nodos y enlaces, mover nodos y optimizar la representación gráfica. En el caso de grafos muy complejos, se permitirá la partición del grafo total en subgrafos. Se permitirá una definición paramétrica de la estructura, lo que será muy útil para el caso de problemas dinámicos.

Desde el punto de vista cuantitativo, se desarrollarán métodos de introducir y editar matrices de probabilidades condicionadas. Se integrarán métodos que minimicen el número de valores a introducir, como el uso de puertas OR o de árboles de clasificación.

En todos los procedimientos se pondr especial interés en la facilidad de uso y su adaptación a usuarios no informáticos.

Temporización

A.3
Entorno Gráfico para Desarrollo de Aplicaciones
Responsable: UNED - Madrid
Colaboradores: Todos los grupos

Uno de los factores que más contribuyen a la aceptación de un sistema experto por parte de los usuarios finales es la calidad del interfaz. Entre las características deseables se encuentran las siguientes: facilidad, familiaridad, consistencia, comodidad, flexibilidad, ayuda, claridad, realimentación, comprobación, robustez, seguridad, compatibilidad y reaprovechamiento; la explicación de estos términos, con referencias bibliográficas puede encontrarse en (Díez, 1994, cap. 13).

Por tanto, en la construcción de un entorno para el desarrollo de modelos gráficos probabilistas es imprescindible contar con una serie de funciones y librerías que permitan la construcción de interfaces basados en ventanas para cada aplicación concreta. Basándonos en nuestra experiencia en la implementación de un sistema experto bayesiano para medicina (Díez, 1994, 1996) en el entorno MS-Windows, desarrollaremos iconos tanto para la introducción de datos cualitativos (con la especificación de las desviaciones frente al valor esperado, intervalos para la discretización de las variables, etc.) y para datos cualitativos, con la comprobación de consistencia de datos, menús de barra y de persiana, herramientas de navegación, etc., todo ello con los correspondientes mecanismos ayuda sensible al contexto.

Temporización

B.1
Algoritmos Exactos de Propagación con Variables Discretas
Responsable: UNED - Madrid
Colaborador: Universidad de Almería

Como se ha mencionado en la introducción de esta memoria, uno de los problemas fundamentales de los modelos graficos probabilistas es el calculo de la probabilidad de cada variable dada una cierta evidencia, pues esto es lo que permite su aplicación al diagnóstico y a la toma de decisiones. Existen dos tipos principales de algoritmos: exactos y aproximados. Dentro de los primeros, los dos métodos que se utilizan en la actualidad son el agrupamiento (``clustering'') y el condicionamiento.

El problema principal de los métodos de agrupamiento es la triangulación de la red, puesto que de ella depende el árbol de cúmulos (``clusters'') resultante y, por tanto, la complejidad de la computación. En consecuencia, es importante que el entorno de desarrollo objeto de este proyecto cuente con diferentes algoritmos de triangulación, desde el más simple (búsqueda en cardinalidad) hasta los más sofisticados (temple simulado, algoritmos genéticos ), incluyendo métodos heurísticos.

En cuanto al condicionamiento, se implementará el método más eficiente que existe en la actualidad: el condicionamiento local, desarrollado por F.J. Dí ez (1996), con dos versiones: generación previa o generación dinámica del árbol asociado, cada una con sus ventajas e inconvenientes.

Temporización

B.2
Algoritmos de Propagación Aproximados con Variables Discretas
Responsable: Universidad de Almería
Colaborador: Universidad de Granada

Se pretende estudiar y desarrollar nuevos métodos de propagación para variables discretas basados en técnicas de Monte Carlo, principalmente muestreo por importancia y simulación estratificada. Pensamos que los nuevos métodos deben ser dinámicos, en el sentido de utilizar la información proporcionada por cada simulación para mejorar la calidad de las siguientes, refinando en la medida de lo posible las funciones que se usan para muestrear. Igualmente, consideramos fundamental el estudio de criterios de precomputación aproximada. La idea fundamental es hacer todo el esfuerzo posible antes de comenzar la simulación, con la intención de que ésta sea más efectiva.

Los nuevos algoritmos que se desarrollen deberán ser trasladados al ordenador para comprobar su funcionamiento real. Para ello se realizará una experimentación consistente en analizar tiempos de ejecución y errores en las estimaciones, tanto para redes correspondientes a problemas reales como para redes especialmente diseñadas para los experimentos. Deberá compararse el comportamiento de los algoritmos propuestos con el de los ya existentes, principalmente ponderación por verosimilitud, y los métodos basados en cadenas de Markov (muestreo de Gibbs por bloques).

Temporización

B.3
Algoritmos de Decisión con Variables Discretas
Responsable: UNED - Madrid
Colaboradores: Universidad de Granada, Universidad de Almería

El problema de la decisión consiste en elegir entre una serie de posibles acciones aquella que se considera mejor dado un conjunto de observaciones en el modelo. Este tipo de situaciones se puede modelar mediante un tipo de modelo gráfico probabilístico conocido como diagrama de influencia. En este caso entra en juego el concepto de utilidad, parámetro a maximizar a la hora de determinar la decisión a tomar.

Se estudiarán nuevos algoritmos para la toma de decisiones en modelos representados mediante diagramas de influencia con variables aleatorias discretas, utilizando técnicas análogas a las de propagación de evidencia en redes bayesianas.

El trabajo debe comenzar con el estudio de métodos exactos de decisión, considerando después algoritmos aproximados basados en técnicas de Monte Carlo para problemas de gran tamaño que hagan inviable la realización de cálculos exactos.

Los algoritmos que se propongan han de ser implementados para evaluar su funcionamiento y compararlo con los métodos ya existentes.

Temporización

B.4
Algoritmos de Propagacion de MonteCarlo con Variables Continuas
Responsable: Universidad de Granada
Colaborador: Universidad de Almería

Se tratará de adaptar los algoritmos existentes para variables discretas, tanto los desarrollados en el punto B.2, como los anteriormente existentes.

Primero habrá que determinar los límites de nuestro modelo: qué distribuciones y bajo qué condiciones se van a considerar. Estos límites vendrán fijados por la posibilidad de aplicación de los algoritmos.

Nos proponemos permitir la coexistencia de variables discretas y continuas de distintos tipos. Un tema que habrá que estudiar en relación con la tarea A.1 es la representación de este tipo de distribuciones, sobre todo el caso de distribuciones condicionadas a variables continuas.

Aunque aún no se ha estudiado el tema, las perspectivas son que el método de ponderación por verosimilitud puede ser aplicado a una amplia variedad de distribuciones continuas; más difícil se presenta adaptación de los métodos basados en cadenas de Markov, y aún peor el caso de los métodos basados en precomputación aproximada.

Los algoritmos propuestos se compararán con los basados en una discretización previa del espacio de valores de las variables continuas.

Temporización

B.5
Algoritmos de Aprendizaje en Modelos Gráficos Estáticos
Responsable: Universidad del Pais Vasco - San Sebastián
Colaborador: Universidad de Granada

Esta tarea, junto con la B.6, incluye tanto la implementación de algoritmos ya desarrollados y/o descritos en la literatura como el desarrollo e implementación de nuevos algoritmos. En ambos casos se estudia el comportamiento de los distintos algoritmos de forma empírica.

En este apartado se manejarán mayoritariamente algoritmos de aprendizaje bien documentados y estudiados en la literatura, con excepción de aquellos que dentro del punto “Aproximaciones Híbridas” pretendemos desarrollar.

Se considerarán algoritmos de los siguientes tipos:

--
Aprendizaje en árboles y poliárboles
--
Aprendizaje en redes multiplemente conectadas
--
Métodos basados en tests de independencia condicional
--
Métodos bayesianos y cuasi-bayesianos
--
Aproximaciones híbridas

Por lo que respecta a los métodos de búsqueda en el espacio de soluciones se pretende utilizar: búsqueda local, temple simulado, algoritmos genéticos y búsqueda tabú.

Temporización

B.6
Algoritmos de Aprendizaje para Problemas de Clasificación
Responsable: Universidad del Pais Vasco - San Sebastián
Colaborador: Universidad de Granada

A pesar de que un gran porcentaje de los problemas que surgen en el mundo real se relacionan con la denominada “ clasificación supervisada”, pocos algoritmos de aprendzaje de redes bayesianas se han desarrollado teniendo en cuenta la posterior utilización de los mismos en problemas clasificatorios.

Temas:

--
Desarrollo de medidas de adaptación de la red bayesiana a problemas clasificatorios.
--
Algoritmos de aprendizaje basados exclusivamente en redes bayesianas:
--
Naive Bayes
--
Arbol Naive Bayes completado
--
Markov Blanket de la variable a clasificar

--
Algoritmos de aprendizaje basados en redes bayesianas y árboles de clasificación.
--
Algoritmos de aprendizaje basados en redes bayesianas e inducción de reglas.
--
Algoritmos de integración de redes bayesianas y otros paradigmas clasificatorios.
--
Generalizaciones a dominios dinámicos

Temporización

B.7
Métodos para la Explicación del Conocimiento
Responsable: Universidad de Granada
Colaboradores: UNED - Madrid

El problema de realizar inferencia abductiva en redes causales, también conocido como la búsqueda de las K explicaciones más probables a unos hechos observados, puede descomponerse en dos clases de problemas: abducción total y abducción parcial. Un problema de abducción total consiste en encontrar las configuraciones de estados para las variables no observadas que tienen máxima probabilidad dadas las variables observadas. Este tipo de problemas ha sido estudiado por varios autores, que han desarrollado algoritmos exactos y aproximados para su resolución. Los problemas de abducción parcial consisten en encontrar las configuraciones de estados para algunas de las variables no observadas, que tienen maxima probabilidad dadas las variables observadas. Al contrario que ocurre con los problemas de abducción total, la abducción parcial (en redes causales) no ha sido muy estudiada, y aunque en principio la solución puede plantearse como una adaptación de los métodos desarrollados para los problemas de abducción total, un estudio más detallado del problema nos lleva a ver que esto no es cierto, y que los métodos de resolución deben ser forzosamente más complejos. Nuestro objetivo en esta tarea es desarrollar algoritmos exactos y aproximados que permitan resolver este tipo de problemas.

Temporización

B.8
Algoritmos para la Fusión de Redes.
Responsable: Universidad de Almería
Colaborador: Universidad de Granada

El objetivo principal es desarrollar métodos que permitan la combinación consensuada de redes causales. Para un mismo tema podemos disponer de varios expertos o fuentes de conocimiento (bases de datos) que pueden proporcionar información relevante. Partimos de la idea de que el conocimiento de cada uno de estos expertos se representa como una red causal. El problema será construir una red que resuma o consensue el conocimiento individual de cada uno de ellos. Esta reunión tiene dos partes bien diferenciadas: (1) cualitativa, en la que se persigue obtener la estructura consensuada común y (2) cuantitativa, en la que se busca un modelo numérico común que resuma la información de las distintas fuentes de conocimiento iniciales.

En su vertiente práctica, habrá que diseñar software que implemente las ideas desarrolladas teóricamente y que permita evaluar la calidad de los modelos obtenidos, empleando para ello modelos reales y de laboratorio, contrastando los resultados obtenidos con las técnicas de combinación conocidas.

Los algoritmos que se desarrollen se encuadrarán en cada una de las categorías anteriores. La red común se obtendrá aplicando un algoritmo de cada una de ellas, cubriendo así tanto los aspectos cualitativos como los cuantitativos. A este respecto será interesante estudiar en la práctica cuál será la mejor combinación de algoritmos de cada una de las vertientes del problema, para obtener la mejor red común.

Temporización

C.1
Aplicación a Problemas Ganaderos
Responsable: Universidad de Granada
Colaborador: Universidad de Almería

Los modelos gráficos probabilísticos has sido usados para la determinación de probabilidades en árboles genealógicos. En concreto, calcular cuál es la probabilidad de ser portador de una enfermedad recesiva para un progenitor o pariente de un individuo que presenta dicha enfermedad. Este problema no es complejo desde el punto de vista de la modelización pero sí desde el punto de vista computacional.

Las posibilidades de aplicación se extienden a otros problemas en los que han mostrado su interés CEFUSA, la empresa que participa como Ente Promotor Observador en esta tarea. Entre ellos cabe destacar la determinación de dietas alimenticias óptimas (problema de decisión dinámico) y el diagnóstico de enfermedades (razonamiento con variables continuas y discretas).

Temporización

C.2
Aplicación a Problemas Agrícolas
Responsable: Universidad de Almería
Colaborador: Universidad de Granada

En las últimas décadas, y debido a las favorables condiciones medioambientales, el cultivo intensivo bajo plástico ha experimentado un gran auge an Almería, convirtiéndose en la principal actividad económica de la provincia.

A ello se debe la importancia del estudio de las posibles aplicaciones de los modelos gráficos probabilísticos a la agricultura. Estas técnicas han sido aplicadas con anterioridad al control del uso de pesticidas en plantaciones.

El ente promotor observador se muestra especialmente interesado en problemas de lucha integrada contra plagas, control y diagnósico de enfermedades en las plantas y control genético para la selección de cualidades para las nuevas generaciones.

Se estudiará la posible aplicación de los modelos probabilísticos al tratamiento de los temas anteriormente citados.

Temporización

C.3
Aplicación a Problemas Médicos.
Responsable: UNED - Madrid
Colaboradores: Universidad del País Vasco - San Sebastián

La mayor parte de los sistemas expertos que existen en la actualidad se han desarrollado en el campo de la medicina, y esto es especialmente cierto dentro de los sistemas expertos bayesianos. La aplicación comercial más conocida es PATHFINDER, desarrollado por varios investigadores vinculados a la Universidad de Stanford. También Microsoft está construyendo un sistema de este tipo para cardiología, aunque todavía no han publicado los resultados de este proyecto. Entre los grupos de investigación universitarios destacan el de la Universidad de Aalborg (Dinamarca), que ha trabajado en el diagnóstico de enfermedades musculares y en el tratamiento de pacientes diabéticos, y el de la Universidad de Pavía (Italia), que ha creado aplicaciones para hematología, cardiología, SIDA, etc. También son reseñables la conversión de sistemas expertos famosos, como INTERNIST e ILYAD, al formalismo bayesiano, demostrando las ventajas de éste frente al encadenamiento de reglas.

En nuestro país, los resultados más destacados son

El entorno de desarrollo objeto de este proyecto serviría para lograr una implementación mucho más eficiente de las aplicaciones mencionadas y para construir otras nuevas.

Temporización

C.4
Problemas Industriales
Responsable: Universidad del Pais Vasco - San Sebastián
Colaboradores: Universidad de Granada

Los proyectos en los que los centros tutelados del Gobierno Vasco ---Labein, Tekniker, Ikerlan--- han mostrado su interés por la aplicación de los modelos gráficos probabilísticos al control de calidad, al diagnóstico de fallos en máquinas herramienta, así como a la visión industrial.

Por lo que se refiere a Inguru, esta empresa ha mostrado su interés en la utilización de los modelos gráficos probabilísticos en el análisis de la información mensual obtenida durante los 6 últimos años sobre las condiciones higiénico-sanitarias de los ríos del País Vasco. Dichos trabajos se han realizado bajo contrato de la Viceconsejería de Medio Ambiente del Gobierno Vasco.

Temporización

C.5
Aplicaciones Sociológicas
Responsable: Universidad del Pais Vasco - San Sebastián
Colaborador: Universidad de Almería

Proyecto Hombre Gipuzkoa está interesado en estudiar como influyen las distintas variables relativas a los individuos que efectúan el Programa del Proyecto Hombre en el éxito o fracaso de las distintas fases de las que consta dicho programa. Además de la información proveniente de otros programas de Proyecto Hombre nacionales ---Bilbao, Sevilla, Madrid--- así como internacionales: se mantienen contactos con grupos de Bélgica e Italia.

Por su parte, Siadeco ha mostrado su interés en este proyecto por su posible aplicabilidad al estudio de las variables que influyen en la transmisión y/o recuperación del vascuence. Para ello, se cuenta con un fichero que recoge datos relacionados con 15.000 familias, fruto del trabajo realizado por la Viceconsejería de Política Lingüística del Gobierno Vasco.

Temporización



Indice: Página Inicial