Algoritmo de eliminación de variables

El algoritmo de eliminación de variables es un algoritmo de adquisición de conocimiento probabilístico a partir de una red bayesiana. Dada una red bayesiana y una serie de valores observados para ciertas variables, denominadas de evidencia, se obtiene las probabilidades esperadas de una variable de consulta.

El algoritmo trata de hacer uso de diversas técnicas para reducir los calculos en la medida de lo posible. El nombre de eliminación de variables proviene de desechar del calculo de la probabilidad de la variable de consulta a aquellas variables que no tienen ninguna relación de dependencia.

Algoritmo

función inferencia_eliminacion_variables(X,e,RED)

   1. Sea RED_E el resultado de eliminar de RED las variables irrelevantes
   2. Sea FACTORES igual a vacío
   3. Sea VARIABLES el conjunto de variables de RED_E
   4. Sea VAR_ORD el conjunto de VARIABLES ordenado según un orden de eliminación
   5. PARA cada VAR en VAR_ORD HACER
       5.1 Sea FACTOR el factor correspondiente a VAR
       5.2 Añadir FACTOR a FACTORES
       5.3 Si VAR es una variable oculta hacer FACTORES igual a AGRUPA(VAR,FACTORES)
   6. Devolver NORMALIZA(MULTIPLICA(FACTORES))

Variables irrelevantes

Las variables irrelevantes en general son aquellas que no sea antecesor en la red de alguna de las variables de consulta o evidencia. Con ello dichas variables se eliminan.

Orden de variables

La ordenación de las variables tiene un factor esencial para la eficiencia del algoritmo. El orden de este está dominado por el tamaño del mayor factor contenido durante el proceso. Este viene fuertemente influenciado por el orden en que se consideran las variables.

Una heurística (informática) habitual es moverse desde las hojas hacia arriba dentro de la topología de la red bayesiana.

Si la red está simplemente conectada (poliárbol) se puede demostrar que la complejidad del algoritmo (en tiempo y espacio) es lineal en el tamaño de la red (el número de entradas de sus tablas). Además hay a lo sumo un camino no dirigido entre cada dos nodos.

Agrupación de tablas

Dado un conjunto de factores, la operación de agrupar (respecto de los valores de una variable aleatoria X) consiste en obtener otro conjunto de factores. Se dejan igual aquellos factores que no tienen a la variable X entre sus argumentos. El resto de factores se multiplican y se sustituyen por el resultado de multiplicarlos y sumar en la tabla por cada posible valor de X. En cierta forma esta operación es similar a la agregación de una columna en bases de datos.

Multiplicación de tablas

Si f1(X,Y) y f2(Y,Z) son dos tablas cuyas variables en común son las de Y, se define su producto f(X,Y,Z) como la tabla cuyas entradas son f(x,y,z)=f1(x,y)f2(y,z).

Es similar al concepto de un join en base de datos, multiplicando los valores correspondientes.

La operación multiplicar tablas es previa a cada agrupamiento y en el paso final.

Normalizar

El proceso de normalización convierte los valores finales del proceso del algoritmo de forma que la suma de dichos valores pase a ser 1. Para ello basta multiplicar a todos los valores por una constante de normalizacion.

Bibliografía

• Rusell, S. y Norvig, P. Inteligencia artificial (Un enfoque moderno).

Enlaces externos

• Applets explicativos de redes bayesianas y eliminación de variables