Algorithme de l'arbre de jonction
# 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
