Red de dependencia (modelo gráfico)

Las redes de dependencia (DN) son modelos gráficos , similares a las redes de Markov , en los que cada vértice (nodo) corresponde a una variable aleatoria y cada arista captura dependencias entre variables. A diferencia de las redes bayesianas , las DN pueden contener ciclos. Cada nodo está asociado a una tabla de probabilidad condicional, que determina la realización de la variable aleatoria dadas sus variables parentales. ^[1]

Manta de Markov

En una red bayesiana , la manta de Markov de un nodo es el conjunto de padres e hijos de ese nodo, junto con los padres de los hijos. Los valores de los padres e hijos de un nodo evidentemente dan información sobre ese nodo. Sin embargo, los padres de sus hijos también deben incluirse en la manta de Markov, porque pueden usarse para explicar el nodo en cuestión. En un campo aleatorio de Markov , la manta de Markov para un nodo es simplemente sus nodos adyacentes (o vecinos). En una red de dependencia, la manta de Markov para un nodo es simplemente el conjunto de sus padres.

Redes de dependencia versus redes bayesianas

Las redes de dependencia tienen ventajas y desventajas con respecto a las redes bayesianas. En particular, son más fáciles de parametrizar a partir de los datos, ya que existen algoritmos eficientes para aprender tanto la estructura como las probabilidades de una red de dependencia a partir de los datos. Dichos algoritmos no están disponibles para las redes bayesianas, para las cuales el problema de determinar la estructura óptima es NP-hard. ^[2] No obstante, una red de dependencia puede ser más difícil de construir utilizando un enfoque basado en el conocimiento impulsado por el conocimiento de expertos.

Redes de dependencia versus redes de Markov

Las redes de dependencia consistentes y las redes de Markov tienen el mismo poder de representación. No obstante, es posible construir redes de dependencia no consistentes, es decir, redes de dependencia para las que no existe una distribución de probabilidad conjunta válida y compatible . Las redes de Markov, por el contrario, son siempre consistentes.

Definición

Una red de dependencia consistente para un conjunto de variables aleatorias con distribución conjunta es un par donde es un grafo cíclico dirigido, donde cada uno de sus nodos corresponde a una variable en , y es un conjunto de distribuciones de probabilidad condicional. Los padres del nodo , denotados , corresponden a aquellas variables que satisfacen las siguientes relaciones de independencia ${\textstyle \mathbf {X} =(X_{1},\ldots ,X_{n})}$ ${\displaystyle p(\mathbf {x} )}$ ${\displaystyle (G,P)}$ ${\displaystyle G}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle P}$ ${\displaystyle X_{i}}$ ${\displaystyle \mathbf {Pa_{i}} }$ ${\displaystyle \mathbf {Pa_{i}} \subseteq (X_{1},\ldots ,X_{i-1},X_{i+1},\ldots ,X_{n})}$

${\displaystyle p(x_{i}\mid \mathbf {pa_{i}} )=p(x_{i}\mid x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{n})=p(x_{i}\mid \mathbf {x} -{x_{i}}).}$

La red de dependencia es consistente en el sentido de que cada distribución local puede obtenerse a partir de la distribución conjunta . Las redes de dependencia aprendidas utilizando grandes conjuntos de datos con tamaños de muestra grandes casi siempre serán consistentes. Una red no consistente es una red para la que no existe una distribución de probabilidad conjunta compatible con el par . En ese caso, no existe una distribución de probabilidad conjunta que satisfaga las relaciones de independencia incluidas en ese par. ${\displaystyle p(\mathbf {x} )}$ ${\displaystyle (G,P)}$

Aprendizaje de estructura y parámetros

Dos tareas importantes en una red de dependencia son aprender su estructura y probabilidades a partir de los datos. Esencialmente, el algoritmo de aprendizaje consiste en realizar de forma independiente una regresión o clasificación probabilística para cada variable en el dominio. Proviene de la observación de que la distribución local para la variable en una red de dependencia es la distribución condicional , que puede estimarse mediante cualquier número de técnicas de clasificación o regresión, como métodos que utilizan un árbol de decisión probabilístico, una red neuronal o una máquina de vectores de soporte probabilística. Por lo tanto, para cada variable en el dominio , estimamos de forma independiente su distribución local a partir de los datos utilizando un algoritmo de clasificación, aunque es un método distinto para cada variable. Aquí, mostraremos brevemente cómo se utilizan los árboles de decisión probabilísticos para estimar las distribuciones locales. Para cada variable en , se aprende un árbol de decisión probabilístico donde es la variable objetivo y son las variables de entrada. Para aprender una estructura de árbol de decisión para , el algoritmo de búsqueda comienza con un nodo raíz singleton sin hijos. Luego, cada nodo hoja en el árbol se reemplaza con una división binaria en alguna variable en , hasta que no haya más reemplazos que aumenten la puntuación del árbol. ${\displaystyle X_{i}}$ ${\displaystyle p(x_{i}|\mathbf {x} -{x_{i}})}$ ${\displaystyle X_{i}}$ ${\displaystyle X}$ ${\displaystyle X_{i}}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle X_{i}}$ ${\displaystyle \mathbf {X} -X_{i}}$ ${\displaystyle X_{i}}$ ${\displaystyle X_{j}}$ ${\displaystyle \mathbf {X} -X_{i}}$

Inferencia probabilística

Una inferencia probabilística es la tarea en la que deseamos responder consultas probabilísticas de la forma , dado un modelo gráfico para , donde (las variables 'objetivo') (las variables 'de entrada') son subconjuntos disjuntos de . Una de las alternativas para realizar la inferencia probabilística es usar el muestreo de Gibbs . Un enfoque ingenuo para esto utiliza un muestreador de Gibbs ordenado, una dificultad importante del cual es que si o es pequeño, entonces se requieren muchas iteraciones para una estimación de probabilidad precisa. Otro enfoque para estimar cuándo es pequeño es usar el muestreador de Gibbs ordenado modificado, donde se fija durante el muestreo de Gibbs. ${\displaystyle p(\mathbf {y\mid z} )}$ ${\displaystyle \mathbf {X} }$ ${\displaystyle \mathbf {Y} }$ ${\displaystyle \mathbf {Z} }$ ${\displaystyle \mathbf {X} }$ ${\displaystyle p(\mathbf {y\mid z} )}$ ${\displaystyle p(\mathbf {z} )}$ ${\displaystyle p(\mathbf {y\mid z} )}$ ${\displaystyle p(\mathbf {z} )}$ ${\displaystyle \mathbf {Z=z} }$

También puede ocurrir que sea poco frecuente, por ejemplo, cuando hay muchas variables. Por lo tanto, la ley de probabilidad total junto con las independencias codificadas en una red de dependencia se puede utilizar para descomponer la tarea de inferencia en un conjunto de tareas de inferencia sobre variables individuales. Este enfoque tiene la ventaja de que algunos términos se pueden obtener mediante una búsqueda directa, lo que evita el muestreo de Gibbs. ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {Y} }$

A continuación se puede ver un algoritmo que se puede utilizar para obtener una instancia particular de y , donde y son subconjuntos disjuntos. ${\displaystyle p(\mathbf {y|z} )}$ ${\displaystyle \mathbf {y} \in \mathbf {Y} }$ ${\displaystyle \mathbf {z} \in \mathbf {Z} }$ ${\displaystyle \mathbf {Y} }$ ${\displaystyle \mathbf {Z} }$

• Algoritmo 1:

1. ${\displaystyle \mathbf {U:=Y} }$(*las variables no procesadas*)
2. ${\displaystyle \mathbf {P:=Z} }$(*las variables procesadas y condicionadas*)
3. ${\displaystyle \mathbf {p:=z} }$(* los valores para *) ${\displaystyle \mathbf {P} }$
4. Mientras : ${\displaystyle \mathbf {U} \neq \emptyset }$
   1. Elija uno que no tenga más padres que cualquier variable en ${\displaystyle X_{i}\in \mathbf {U} }$ ${\displaystyle X_{i}}$ ${\displaystyle U}$ ${\displaystyle U}$
   2. Si todos los padres están en ${\displaystyle X}$ ${\displaystyle \mathbf {P} }$
      1. ${\displaystyle p(x_{i}|\mathbf {p} ):=p(x_{i}|\mathbf {pa_{i}} )}$
   3. Demás
      1. Utilice un muestreador de Gibbs ordenado modificado para determinar ${\displaystyle p(x_{i}|\mathbf {p} )}$
   4. ${\displaystyle \mathbf {U:=U} -X_{i}}$
   5. ${\displaystyle \mathbf {P:=P} +X_{i}}$
   6. ${\displaystyle \mathbf {p:=p} +x_{i}}$
5. Devuelve el producto de los condicionales. ${\displaystyle p(x_{i}|\mathbf {p} )}$

Aplicaciones

Además de las aplicaciones a la inferencia probabilística, las siguientes aplicaciones pertenecen a la categoría de filtrado colaborativo (CF), que es la tarea de predecir preferencias. Las redes de dependencia son una clase de modelo natural en la que basar las predicciones de CF, ya que un algoritmo para esta tarea solo necesita la estimación de para producir recomendaciones. En particular, estas estimaciones se pueden obtener mediante una búsqueda directa en una red de dependencia. ${\displaystyle p(x_{i}=1|\mathbf {x} -{x_{i}}=0)}$

• Predecir qué películas le gustarán a una persona basándose en sus calificaciones de las películas vistas;
• Predecir a qué páginas web accederá una persona en función de su historial en el sitio;
• Predecir qué noticias le interesan a una persona basándose en otras noticias que ha leído;
• Predecir qué producto comprará una persona basándose en los productos que ya ha comprado y/o añadido a su cesta de compra.

Otra clase de aplicaciones útiles para las redes de dependencia está relacionada con la visualización de datos, es decir, la visualización de relaciones predictivas.

Véase también

• Red de dependencia relacional

Referencias

1. HECKERMAN, David; MAXWELL C., David; MEEK, Christopher; ROUNTHWAITE, Robert; KADIE, Carl (octubre de 2000). "Redes de dependencia para inferencia, filtrado colaborativo y visualización de datos" (PDF) . Revista de investigación en aprendizaje automático .
2. HECKERMAN, David (2012). "El aprendizaje de redes bayesianas en muestras grandes es NP-difícil" (PDF) . arXiv : 1212.2468 . {{cite journal}}: Requiere citar revista |journal=( ayuda )