Algorithme de l'arbre de jonction

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Construction du Junction Tree
Construction d'un Junction Tree

L'algorithme de l'arbre de jonction, aussi appelé algorithme somme-produit est un algorithme d'apprentissage automatique. Il est utilisé dans la théorie des modèles graphiques.

Définitions[modifier | modifier le code]

Un arbre de jonction est une factorisation partiellement préconstruite. C'est un graphe de cliques construit de manière que le produit des fonctions de potentiels soit égal à la probabilité conjointe de l'ensemble des variables.

Un arbre de jonction sert à réaliser de l'inférence, par propagation de convictions. Il existe deux méthodes d'inférence sur les réseaux bayésiens : l'inférence exacte et l'inférence approchée. La première donne un résultat exact, mais est extrêmement coûteuse en temps et en mémoire. La seconde, quant à elle, nécessite moins de ressources mais le résultat n'est qu'une approximation de la solution exacte.

Description de l'algorithme[modifier | modifier le code]

En partant d'un graphe orienté:

  1. Moralisation de graphe
  2. Triangulation de graphe
  3. Recherche de cliques maximales
  4. Arbre couvrant de poids maximum
  5. Attribution des fonctions de potentiel

Lien externe[modifier | modifier le code]