title: Algorithme de l'arbre de jonction
text: # Algorithme de l'arbre de jonction
  
  * Construction du Junction Tree
  * Construction d'un Junction Tree
  
  L'algorithme de l'arbre de jonction (aussi appelé algorithme somme-produit ; en anglais, Junction Tree Algorithm ou JTA) est un algorithme d'apprentissage automatique. Il est utilisé dans la théorie des modèles graphiques.
  
  ## Définitions
  
  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
  
  En partant d'un graphe orienté:
  
  * Moralisation de graphe
  * Triangulation de graphe
  * Recherche de cliques maximales
  * Arbre couvrant de poids maximum
  * Attribution des fonctions de potentiel
  
  ## Lien externe
  
  * Francis Bach (Scribe: Rémi Bardenet et Victor Gabillon), « Introduction aux modèles graphiques : Apprentissage par EM pour l'analyse factorielle », sur Département informatique de l'École normale supérieure, 2009
  