Eliminación variable

Algoritmo de inferencia para modelos gráficos probabilísticos

La eliminación de variables (VE) es un algoritmo de inferencia exacta simple y general en modelos gráficos probabilísticos , como redes bayesianas y campos aleatorios de Markov . ^[1] Se puede utilizar para la inferencia del estado máximo a posteriori (MAP) o la estimación de distribuciones condicionales o marginales sobre un subconjunto de variables. El algoritmo tiene una complejidad temporal exponencial, pero podría ser eficiente en la práctica para gráficos de ancho de árbol bajo , si se utiliza el orden de eliminación adecuado.

Factores

Para permitir una reducción clave en la complejidad algorítmica, un factor , también conocido como potencial, de variables es una relación entre cada instancia de variables con un número no negativo, comúnmente denotado como . ^[2] Un factor no necesariamente tiene una interpretación establecida. Se pueden realizar operaciones en factores de diferentes representaciones, como una distribución de probabilidad o una distribución condicional. ^[2] Las distribuciones conjuntas a menudo se vuelven demasiado grandes para manejarlas ya que la complejidad de esta operación es exponencial. Por lo tanto, la eliminación de variables se vuelve más factible al calcular entidades factorizadas. ${\displaystyle f}$ ${\displaystyle V}$ ${\displaystyle v}$ ${\displaystyle f}$ ${\displaystyle f(x)}$

Operaciones básicas

Suma de variables

El algoritmo 1, llamado suma-extracción (SO) o marginalización, elimina una única variable de un conjunto de factores ^[3] y devuelve el conjunto de factores resultante. El algoritmo collect-relevant simplemente devuelve aquellos factores que involucran la variable . ${\displaystyle v}$ ${\displaystyle \phi }$ ${\displaystyle \phi }$ ${\displaystyle v}$

Algoritmo 1 suma-salida( , ) ${\displaystyle v}$ ${\displaystyle \phi }$

${\displaystyle \Phi }$= recopilar factores relevantes para ${\displaystyle v}$

${\displaystyle \Psi }$= el producto de todos los factores en ${\displaystyle \Phi }$

${\displaystyle \tau =\sum _{v}\Psi }$

devolver ${\displaystyle (\phi -\Phi )\cup \{\tau \}}$

Ejemplo

Aquí tenemos una distribución de probabilidad conjunta . Una variable, puede sumarse entre un conjunto de instancias donde el conjunto, como mínimo, debe coincidir con las variables restantes. El valor de es irrelevante cuando es la variable que se va a sumar. ^[2] ${\displaystyle v}$ ${\displaystyle V-v}$ ${\displaystyle v}$

Después de eliminar , se excluye su referencia y nos quedamos con una distribución solo sobre las variables restantes y la suma de cada instanciación. ${\displaystyle V_{1}}$

La distribución resultante que sigue a la operación de suma solo ayuda a responder consultas que no mencionan . ^[2] También vale la pena señalar que la operación de suma es conmutativa. ${\displaystyle V_{1}}$

Multiplicación de factores

El cálculo de un producto entre múltiples factores da como resultado un factor compatible con una única instancia en cada factor. ^[2]

Algoritmo 2 multifactores( , ) ^[2] ${\displaystyle v}$ ${\displaystyle \phi }$

${\displaystyle Z}$= Unión de todas las variables entre el producto de los factores ${\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})}$

${\displaystyle f}$= un factor sobre dónde para todos ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$

Para cada instanciación ${\displaystyle z}$

Para 1 a ${\displaystyle m}$

${\displaystyle x_{1}=}$instanciación de variables consistentes con ${\displaystyle X_{1}}$ ${\displaystyle z}$

${\displaystyle f(z)=f(z)f_{i}(x_{i})}$

devolver ${\displaystyle f}$

La multiplicación de factores no sólo es conmutativa sino también asociativa.

Inferencia

El tipo de consulta más común tiene la forma donde y son subconjuntos disjuntos de , y se observa que toma el valor . Un algoritmo básico para calcular p(X|E = e) se llama eliminación de variable (VE), propuesto por primera vez en. ^[1] ${\displaystyle p(X|E=e)}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle U}$ ${\displaystyle E}$ ${\displaystyle e}$

Tomado de, ^[1] este algoritmo calcula a partir de una red bayesiana discreta B. VE llama a SO para eliminar variables una por una. Más específicamente, en el Algoritmo 2, es el conjunto C de tablas de probabilidad condicional (en adelante "CPT") para B, es una lista de variables de consulta, es una lista de variables observadas, es la lista correspondiente de valores observados y es un orden de eliminación para las variables , donde denota . ${\displaystyle p(X|E=e)}$ ${\displaystyle \phi }$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle e}$ ${\displaystyle \sigma }$ ${\displaystyle U-XE}$ ${\displaystyle XE}$ ${\displaystyle X\cup E}$

Algoritmo de eliminación de variables VE( ) ${\displaystyle \phi ,X,E,e,\sigma }$

Multiplica los factores con los CPT apropiados mientras σ no esté vacío

Eliminar la primera variable de ${\displaystyle v}$ ${\displaystyle \sigma }$

${\displaystyle \phi }$= suma total ${\displaystyle (v,\phi )}$

${\displaystyle p(X,E=e)}$= el producto de todos los factores ${\displaystyle \Psi \in \phi }$

devolver ${\displaystyle p(X,E=e)/\sum _{X}p(X,E=e)}$

Realizar pedidos

Encontrar el orden óptimo para eliminar variables es un problema NP-hard. Por ello, existen heurísticas que se pueden seguir para optimizar mejor el rendimiento por orden:

1. Grado mínimo : eliminar la variable lo que da como resultado la construcción del factor más pequeño posible. ^[2]
2. Relleno mínimo: Al construir un gráfico no dirigido que muestre las relaciones de variables expresadas por todos los CPT, elimine la variable que daría como resultado la menor cantidad de aristas a agregar después de la eliminación. ^[2]

Referencias

1. Zhang, NL, Poole, D.: Un enfoque simple para los cálculos de redes bayesianas. En: 7.ª Conferencia canadiense sobre inteligencia artificial, págs. 171-178. Springer, Nueva York (1994)
2. Darwiche, Adnan (1 de enero de 2009). Modelado y razonamiento con redes bayesianas . doi :10.1017/cbo9780511811357. ISBN 9780511811357.
3. Koller, D., Friedman, N.: Modelos gráficos probabilísticos: principios y técnicas. MIT Press, Cambridge, MA (2009)