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 de tiempo exponencial, pero podría ser eficaz en la práctica para los gráficos de bajo ancho de árbol , si se utiliza el orden de eliminación adecuado.
Factores
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 instanciación de de variables a un número no negativo, comúnmente denotado como . [2] Un factor no necesariamente tiene una interpretación establecida. Se pueden realizar operaciones sobre 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 cuando se calculan entidades factorizadas.
Operaciones básicas
Suma variable
El algoritmo 1, llamado suma (SO) o marginación, elimina una sola variable de un conjunto de factores, [3] y devuelve el conjunto de factores resultante. El algoritmo de recopilación relevante simplemente devuelve esos factores en involucrando variable .
Suma del algoritmo 1 (,)
- = recopilar factores relevantes para
- = el producto de todos los factores en
regreso
Ejemplo
Aquí tenemos una distribución de probabilidad conjunta . Una variable, se puede resumir entre un conjunto de instanciaciones donde el conjunto como mínimo debe coincidir con las demás variables. El valor dees irrelevante cuando es la variable a resumir. [2]
cierto | cierto | cierto | falso | falso | 0,80 |
falso | cierto | cierto | falso | falso | 0,20 |
Después de eliminar , se excluye su referencia y nos queda una distribución solo sobre las variables restantes y la suma de cada instanciación.
cierto | cierto | falso | falso | 1.0 |
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.
Multiplicación de factores
Calcular un producto entre múltiples factores da como resultado un factor compatible con una única instanciación en cada factor. [2]
Algoritmo 2 multifactores (,) [2]
- = Unión de todas las variables entre producto de factores
- = un factor sobre dónde para todos
- Para cada instanciación
- De 1 a
- instanciación de variables consistente con
- De 1 a
- regreso
La multiplicación de factores no solo es conmutativa sino también asociativa.
Inferencia
El tipo de consulta más común está en el formulario dónde y son subconjuntos disjuntos de , y se observa tomando valor . Un algoritmo básico para calcular p (X | E = e) se llama eliminación de variable (VE), presentado por primera vez. [1]
Tomado de, [1] este algoritmo calculadesde una red bayesiana discreta B. VE llama a SO para eliminar las 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 variables , dónde denota .
Algoritmo de eliminación variable VE ()
- Multiplique los factores con los CPT apropiados mientras σ no esté vacío
- Eliminar la primera variable de
- = suma
- = el producto de todos los factores
regreso
Ordenando
Encontrar el orden óptimo en el que eliminar variables es un problema NP-difícil. Como tal, hay heurísticas que se pueden seguir para optimizar mejor el rendimiento por orden:
- Grado mínimo : Elimine la variable que resulte en la construcción del factor más pequeño posible. [2]
- Relleno mínimo: al construir un gráfico no dirigido que muestre las relaciones variables expresadas por todos los CPT, elimine la variable que resultaría en la menor cantidad de bordes que se agregarán después de la eliminación. [2]
Referencias
- ^ a b c Zhang, NL, Poole, D.:A Simple Approach to Bayesian Network Computations. En: 7th Canadian Conference on Artificial Intelligence, págs. 171-178. Springer, Nueva York (1994)
- ↑ a b c d e f g h Darwiche, Adnan (1 de enero de 2009). Modelado y razonamiento con redes bayesianas . doi : 10.1017 / cbo9780511811357 . ISBN 9780511811357.
- ^ Koller, D., Friedman, N .: Modelos gráficos probabilísticos: principios y técnicas. Prensa del MIT, Cambridge, MA (2009)