Hispanopedia Wiki
Articulo de referencia

eliminación de variables

La eliminación de variables (EV) es un algoritmo de inferencia exacto, simple y general, en modelos gráficos probabilísticos , como redes bayesianas y campos aleatorios de Marko...

Hispanopedia WikiContenido en espanolLectura gratuita

La eliminación de variables (EV) es un algoritmo de inferencia exacto, simple y general, en modelos gráficos probabilísticos , como redes bayesianas y campos aleatorios de Markov . [ 1 ] Puede utilizarse para la inferencia del estado de máxima probabilidad 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 grafos 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 factorF{\displaystyle f}, también conocido como potencial, de variablesV{\displaystyle V}es una relación entre cada instanciación dev{\displaystyle v}de variablesF{\displaystyle f}a un número no negativo, comúnmente denotado comoF(incógnita){\displaystyle f(x)}[ 2 ] Un factor no tiene necesariamente una interpretación fija. Se pueden realizar operaciones con factores de diferentes representaciones, como una distribución de probabilidad o una distribución condicional. [ 2 ] Las distribuciones conjuntas suelen ser demasiado grandes para manejarlas, ya que la complejidad de esta operación es exponencial. Por lo tanto, la eliminación de variables resulta más factible al calcular entidades factorizadas.

Operaciones básicas

Suma de variables

El algoritmo 1, denominado suma de salida (SO) o marginalización, elimina una sola variable.v{\displaystyle v}de un conjuntoϕ{\displaystyle \phi }de factores, [ 3 ] y devuelve el conjunto resultante de factores. El algoritmo collect-relevant simplemente devuelve esos factores enϕ{\displaystyle \phi }que implica variablesv{\displaystyle v}.

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

Φ{\displaystyle \Phi }= recopilar factores relevantes parav{\displaystyle v}
Ψ{\displaystyle \Psi }= el producto de todos los factores enΦ{\displaystyle \Phi }
τ=∑vΨ{\displaystyle \tau =\sum _{v}\Psi }

devolver(ϕ−Φ)∪{τ}{\displaystyle (\phi -\Phi )\cup \{\tau \}}

Ejemplo

Aquí tenemos una distribución de probabilidad conjunta . Una variable,v{\displaystyle v} se puede resumir entre un conjunto de instanciaciones donde el conjuntoV−v{\displaystyle Vv}como mínimo deben ponerse de acuerdo sobre las variables restantes. El valor dev{\displaystyle v}es irrelevante cuando es la variable que se va a sumar. [ 2 ]

Después de eliminarV1{\displaystyle V_{1}}, su referencia queda excluida y nos queda una distribución solo sobre las variables restantes y la suma de cada instanciación.

La distribución resultante que sigue a la operación de suma solo ayuda a responder consultas que no mencionanV1{\displaystyle V_{1}}. [ 2 ] También es digno de mención que la operación de suma es conmutativa.

Multiplicación de factores

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

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

Z{\displaystyle Z}= Unión de todas las variables entre el producto de factoresF1(incógnita1),...,Fmetro(incógnitametro){\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})}
F{\displaystyle f}= un factor sobre F{\displaystyle f}dónde F{\displaystyle f}a pesar de F{\displaystyle f}
Para cada instanciaz{\displaystyle z}
Para 1 ametro{\displaystyle m}
incógnita1={\displaystyle x_{1}=}instanciación de variablesincógnita1{\displaystyle X_{1}}coherente conz{\displaystyle z}
F(z)=F(z)Fi(incógnitai){\displaystyle f(z)=f(z)f_{i}(x_{i})}
devolverF{\displaystyle f}

La multiplicación de factores no solo es conmutativa, sino también asociativa.

Inferencia

El tipo de consulta más común es el formatopag(incógnita|mi=mi){\displaystyle p(X|E=e)}dóndeincógnita{\displaystyle X}ymi{\displaystyle E}son subconjuntos disjuntos deU{\displaystyle U}, ymi{\displaystyle E}se observa tomando valormi{\displaystyle e}. Un algoritmo básico para calcular p(X|E = e) se llama eliminación de variables (VE), propuesto por primera vez en. [ 1 ]

Tomado de [ 1 ] este algoritmo calculapag(incógnita|mi=mi){\displaystyle p(X|E=e)}de una red bayesiana discreta B. VE llama a SO para eliminar variables una por una. Más específicamente, en el Algoritmo 2,ϕ{\displaystyle \phi }es el conjunto C de tablas de probabilidad condicional (en adelante "TPC") para B,incógnita{\displaystyle X}es una lista de variables de consulta,mi{\displaystyle E}es una lista de variables observadas,mi{\displaystyle e}es la lista correspondiente de valores observados, yσ{\displaystyle \sigma }es un ordenamiento de eliminación para variablesU−incógnitami{\displaystyle U-XE}, dóndeincógnitami{\displaystyle XE}denotaincógnita∪mi{\displaystyle X\cup E}.

Algoritmo de eliminación de variables VE(ϕ,incógnita,mi,mi,σ{\displaystyle \phi ,X,E,e,\sigma })

Multiplica los factores con las CPT apropiadas mientras σ no esté vacío.
Eliminar la primera variablev{\displaystyle v}deσ{\displaystyle \sigma }
ϕ{\displaystyle \phi }= suma-salida(v,ϕ){\displaystyle (v,\phi )}
pag(incógnita,mi=mi){\displaystyle p(X,E=e)}= el producto de todos los factoresΨ∈ϕ{\displaystyle \Psi \in \phi }

devolverpag(incógnita,mi=mi)/∑incógnitapag(incógnita,mi=mi){\displaystyle p(X,E=e)/\sum _ {X}p(X,E=e)}

Pedidos

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

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

Referencias

  1. 1 2 3 Zhang, Nevin L.; Poole, David (1994). " Un enfoque simple para los cálculos de redes bayesianas" . Actas de la 10.ª Conferencia Canadiense de Inteligencia Artificial : 171–178 . Recuperado el 26 de agosto de 2025 .
  2. 1 2 3 4 5 6 7 8 Darwiche, Adnan (2009-01-01). 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)