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 ciclos agrupándolos en nodos individuales. Se pueden compilar varias 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 recogen 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 de gran ancho de árbol . Calcular los mensajes que se transmitirán entre supernodos implica realizar una marginación exacta de las variables en ambos supernodos. Al realizar este algoritmo para un gráfico con un ancho de árbol k, se tendrá al menos un cálculo que requiere 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 suma de un árbol de unión. [6] Se utiliza porque ejecuta programas y consultas de manera más eficiente que el algoritmo de Hugin. El algoritmo hace posibles los cálculos de condicionales para funciones de creencia . [7] Se necesitan distribuciones conjuntas para que se realicen cálculos locales. [7]
El primer paso se refiere únicamente a las redes bayesianas y es un procedimiento para convertir un gráfico 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 que condicionamos. También se dice que esas variables están sujetas a su valor particular.
El tercer paso es garantizar que los gráficos se conviertan en cordales si aún no lo son. 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:
Así, al triangular un gráfico, 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 grafos cordales tienen un árbol de unión. [4] El siguiente paso es construir el árbol de unión . Para hacerlo, utilizamos el gráfico del paso anterior y formamos su correspondiente gráfico de camarilla . [9] Ahora el siguiente teorema nos da una manera de encontrar un árbol de unión: [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 .
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 camarilla. 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]
Propagación de creencias locas: un método diferente para interpretar gráficos complejos. La propagación de creencias descabelladas se utiliza cuando se necesita una solución aproximada en lugar de la solución exacta . [13] Es una inferencia aproximada . [3]
Condicionamiento Cutset: Se utiliza con conjuntos más pequeños de variables. El condicionamiento Cutset permite gráficos más simples que son más fáciles de leer pero no exactos . [3]
{{cite book}}: Mantenimiento CS1: otros ( enlace )