El algoritmo de árbol de unión (también conocido como 'árbol de camarilla') es un método utilizado en el aprendizaje automático para extraer marginalizació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 nodos individuales. Se pueden compilar múltiples clases extensas de consultas al mismo tiempo en estructuras de datos más grandes. [1] Existen diferentes algoritmos para 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]
Tenga en cuenta que este último paso es ineficiente para gráficos con un ancho de árbol grande . Calcular los mensajes que se deben pasar entre supernodos implica hacer una marginalización exacta sobre las variables en ambos supernodos. La ejecución de este algoritmo para un gráfico con un ancho de árbol k tendrá, por lo tanto, al menos un cálculo que lleva un 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.
El algoritmo Shafer-Shenoy es el producto de la suma de un árbol de uniones. [6] Se utiliza porque ejecuta programas y consultas de manera más eficiente que el algoritmo Hugin. El algoritmo hace posible los cálculos de condicionales para funciones de creencias . [7] Se necesitan distribuciones conjuntas para que se realicen los cálculos locales. [7]
El primer paso concierne únicamente a las redes bayesianas y es un procedimiento para convertir un grafo dirigido en uno no dirigido . Lo hacemos porque permite la aplicabilidad universal del algoritmo, independientemente de la dirección.
El segundo paso es fijar las variables en su valor observado. Esto suele ser necesario cuando queremos calcular probabilidades condicionales, por lo que fijamos el valor de las variables aleatorias que condicionamos. También se dice que esas variables están sujetas a su valor particular.
El tercer paso es asegurarse de que los grafos se conviertan en cordales si no lo son ya. Este es el primer paso esencial del algoritmo. Utiliza el siguiente teorema: [8]
Teorema: Para un grafo no dirigido , G, las siguientes propiedades son equivalentes:
Por lo tanto, al triangular un grafo, nos aseguramos de que existe el árbol de uniones 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 dará como resultado agregar más aristas al grafo inicial, de tal manera que la salida será un grafo cordal . Todos los grafos cordales tienen un árbol de uniones. [4] El siguiente paso es construir el árbol de uniones . Para ello, utilizamos el grafo del paso anterior y formamos su grafo de clique correspondiente . [9] Ahora, el siguiente teorema nos da una forma de encontrar un árbol de uniones: [8]
Teorema: Dado un gráfico triangulado, pondere los bordes del gráfico de camarilla por su cardinalidad, |A∩B|, de la intersección de las camarillas adyacentes A y B. Entonces, cualquier árbol de expansión de peso máximo del gráfico de camarilla es un árbol de unión.
Por lo tanto, para construir un árbol de uniones, 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 uniones 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 estructura real del árbol. [11] Un uso específico se puede encontrar en los codificadores automáticos , que combinan el gráfico y una red de paso a gran escala de forma automática. [12]
Propagación de creencias en bucle: un método diferente para interpretar gráficos complejos. La propagación de creencias en bucle se utiliza cuando se necesita una solución aproximada en lugar de la solución exacta . [13] Es una inferencia aproximada . [3]
Condicionamiento de corte: se utiliza con conjuntos de variables más pequeños. El condicionamiento de corte permite obtener gráficos más simples que son más fáciles de leer, pero no son exactos . [3]
{{cite book}}: Mantenimiento de CS1: otros ( enlace )