El algoritmo del árbol de unión (también conocido como 'Clique Tree') es un método utilizado en el aprendizaje automático para extraer la marginación en gráficos generales . En esencia, implica realizar la propagación de creencias en un gráfico modificado llamado árbol de unión . El gráfico se llama árbol porque se ramifica en diferentes secciones de datos; los nodos de variables son las ramas. [1] La premisa básica es eliminar los ciclos agrupándolos en un solo nodo. Se pueden compilar varias clases extensas de consultas al mismo tiempo en estructuras de datos más grandes. [1] Hay diferentes algoritmospara satisfacer necesidades específicas y para lo que se necesita calcular. Los algoritmos de inferencia recopilan nuevos desarrollos en los datos y los calculan en función de la nueva información proporcionada. [2]
Algoritmo de árbol de unión
Algoritmo de Hugin
- Si el gráfico está dirigido, moralícelo para que no esté dirigido.
- Presente la evidencia.
- Triangula la gráfica para hacerla cordal.
- Construya un árbol de unión a partir del gráfico triangulado (llamaremos " supernodos " a los vértices del árbol de unión ).
- Propagar las probabilidades a lo largo del árbol de unión (a través de la propagación de creencias )
Tenga en cuenta que este último paso es ineficaz para gráficos de gran ancho de árbol . Calcular los mensajes para pasar entre supernodos implica hacer una marginación exacta sobre las variables en ambos supernodos. La realización de este algoritmo para un gráfico con un ancho de árbol k tendrá, por lo tanto, al menos un cálculo que requiere tiempo exponencial en k. Es un algoritmo de paso de mensajes . [3] El algoritmo de Hugin requiere menos cálculos para encontrar una solución en comparación con Shafer-Shenoy.
Algoritmo de Shafer-Shenoy
- Calculado de forma recursiva [3]
- Múltiples recursiones del algoritmo de Shafer-Shenoy dan como resultado el algoritmo de Hugin [4]
- Encontrado por la ecuación de paso de mensajes [4]
- Los potenciales del separador no se almacenan [5]
El algoritmo de Shafer-Shenoy es el producto de la suma de un árbol de unión. [6] Se usa porque ejecuta programas y consultas de manera más eficiente que el algoritmo de Hugin. El algoritmo hace posible los cálculos de condicionales para funciones de creencias . [7] Se necesitan distribuciones conjuntas para que sucedan los cálculos locales. [7]
Teoría subyacente
El primer paso concierne solo a las redes bayesianas y es un procedimiento para convertir un grafo dirigido en uno no dirigido . Hacemos esto porque permite la aplicabilidad universal del algoritmo, independientemente de la dirección.
El segundo paso es establecer las variables a su valor observado. Esto suele ser necesario cuando queremos calcular probabilidades condicionales, por lo que fijamos el valor de las variables aleatorias sobre las que condicionamos. También se dice que esas variables están sujetas a su valor particular.
El tercer paso es asegurarse de que los gráficos se hagan acordes si aún no lo están. Este es el primer paso esencial del algoritmo. Hace uso del siguiente teorema: [8]
Teorema: para un gráfico no dirigido, G, las siguientes propiedades son equivalentes:
- El gráfico G está triangulado.
- El gráfico de camarilla de G tiene un árbol de unión.
- Hay un orden de eliminación para G que no da lugar a bordes añadidos.
Por lo tanto, al triangular una gráfica, nos aseguramos de que exista el árbol de unión correspondiente. Una forma habitual de hacer esto es decidir un orden de eliminación para sus nodos y luego ejecutar el algoritmo de eliminación de Variables . El algoritmo de eliminación de variables establece que el algoritmo debe ejecutarse cada vez que haya una consulta diferente. [1] Esto resultará en agregar más aristas al gráfico inicial, de tal manera que la salida será un gráfico cordal . Todos los gráficos de cuerdas tienen un árbol de unión. [4] El siguiente paso es construir el árbol de unión . Para hacerlo, usamos el gráfico del paso anterior y formamos su gráfico de camarilla correspondiente . [9] Ahora, el siguiente teorema nos da una forma de encontrar un árbol de unión: [8]
Teorema: Dado un gráfico triangulado, ponderar los bordes del gráfico de clique por su cardinalidad, | A∩B |, de la intersección de los cliques adyacentes A y B. Luego, cualquier árbol de expansión de peso máximo del gráfico de clique es un árbol de unión .
Entonces, para construir un árbol de unión, solo tenemos que extraer un árbol de expansión de peso máximo del gráfico de clique. Esto se puede hacer de manera eficiente, por ejemplo, modificando el algoritmo de Kruskal . El último paso es aplicar la propagación de creencias al árbol de unión obtenido. [10]
Uso: Se utiliza un gráfico de árbol de unión para visualizar las probabilidades del problema. El árbol puede convertirse en un árbol binario para formar la construcción real del árbol. [11] Se podría encontrar un uso específico en los codificadores automáticos , que combinan el gráfico y una red de paso a gran escala de forma automática. [12]
Algoritmos de inferencia
Propagación de creencias disparatadas: un método diferente para interpretar gráficos complejos. La propagación de creencias descabelladas se usa cuando se necesita una solución aproximada en lugar de la solución exacta . [13] Es una inferencia aproximada . [3]
Acondicionamiento del conjunto de cortes: se utiliza con conjuntos de variables más pequeños. El acondicionamiento de conjuntos de cortes permite gráficos más simples que son más fáciles de leer pero que no son exactos . [3]
Referencias
- ^ a b c Paskin, Mark. "Un curso corto sobre modelos gráficos" (PDF) . Stanford .
- ^ "El algoritmo de inferencia" . www.dfki.de . Consultado el 25 de octubre de 2018 .
- ^ a b c d "Resumen de modelos gráficos" (PDF) .
- ^ a b c "Algoritmos" (PDF) . Instituto de Tecnología de Massachusetts . 2014.
- ^ Roweis, Sam (2004). "Algoritmo de inferencia de Hugin" (PDF) . NYU .
- ^ "Algoritmos de inferencia" (PDF) . Instituto de Tecnología de Massachusetts . 2014.
- ^ a b Kłopotek, Mieczysław A. (6 de junio de 2018). "Red de creencias Dempsterian-Shaferian a partir de datos". arXiv : 1806.02373 [ cs.AI ].
- ^ a b Wainwright, Martin (31 de marzo de 2008). "Modelos gráficos, algoritmos de paso de mensajes y métodos variacionales: Parte I" (PDF) . Berkeley EECS . Consultado el 16 de noviembre de 2016 .
- ^ "Clique Graph" . Consultado el 16 de noviembre de 2016 .
- ^ Barber, David (28 de enero de 2014). "Razonamiento y modelado probabilístico, el algoritmo del árbol de unión" (PDF) . Universidad de Helsinki . Consultado el 16 de noviembre de 2016 .
- ^ "Diagnóstico de fallas en un proceso industrial usando redes bayesianas: aplicación del algoritmo del árbol de unión - Publicación de la conferencia IEEE". doi : 10.1109 / CERMA.2009.28 . S2CID 6068245 . Cite journal requiere
|journal=
( ayuda ) - ^ Jin, Wengong (febrero de 2018). "Autoencoder variacional de árbol de unión para la generación de gráficos moleculares". Universidad de Cornell . arXiv : 1802.04364 . Código bibliográfico : 2018arXiv180204364J .
- ^ CERMA 2009: actas: 2009 Conferencia de Electrónica, Robótica y Mecánica Automotriz: 22-25 de septiembre de 2009: Cuernavaca, Morelos, México . Instituto de Ingenieros Eléctricos y Electrónicos. Los Alamitos, Calif .: IEEE Computer Society. 2009. ISBN 9780769537993. OCLC 613519385 .CS1 maint: otros ( enlace )
- Lauritzen, Steffen L .; Spiegelhalter, David J. (1988). "Cálculos locales con probabilidades sobre estructuras gráficas y su aplicación a sistemas expertos". Revista de la Royal Statistical Society. Serie B (Metodológica) . 50 (2): 157–224. doi : 10.1111 / j.2517-6161.1988.tb01721.x . JSTOR 2345762 . Señor 0964177 .
- Dawid, AP (1992). "Aplicaciones de un algoritmo de propagación general para sistemas expertos probabilísticos". Estadística y Computación . 2 (1): 25-26. doi : 10.1007 / BF01890546 . S2CID 61247712 .
- Huang, Cecil; Darwiche, Adnan (1996). "Inferencia en redes de creencias: una guía de procedimiento" . Revista Internacional de Razonamiento Aproximado . 15 (3): 225–263. CiteSeerX 10.1.1.47.3279 . doi : 10.1016 / S0888-613X (96) 00069-2 .
- Paskin, Mark A. "Un curso corto sobre modelos gráficos: 3. Los algoritmos del árbol de unión" (PDF) . Archivado desde el original el 19 de marzo de 2015. Cite journal requiere
|journal=
( ayuda )CS1 maint: URL no apta ( enlace ) - Lepar, V., Shenoy, P. (1998). "Una comparación de las arquitecturas Lauritzen-Spiegelhalter, Hugin y Shenoy-Shafer para calcular los márgenes de distribuciones de probabilidad". https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf