Algorithme de l'arbre de jonction

Pour les articles homonymes, voir JTA.

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

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.

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

• 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

• Portail de l'informatique théorique