Propagation des convictions
Algorithme pour l'inférence statistique sur des modèles graphiques / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Propagation des convictions?
Résumez cet article pour un enfant de 10 ans
La propagation des convictions (Belief Propagation ou BP en anglais), aussi connu comme la transmission de message somme-produit, est un algorithme à passage de message pour effectuer des inférences sur des modèles graphiques, tels que les réseaux Bayésiens et les champs de Markov. Il calcule la distribution marginale de chaque nœud « non-observé » conditionnée sur les nœuds observés. La propagation des convictions est couramment utilisée dans l'intelligence artificielle et la théorie de l'information et a fait la preuve empirique de son succès dans de nombreuses applications, y compris le décodage des codes LDPC ou des turbo codes, l'approximation de l'énergie libre, et les modèles de satisfaisabilité.
Type | |
---|---|
Inventeur | |
Date d'invention | |
Formule |
Cet algorithme fut proposé pour la première fois par Judea Pearl, en 1982[1]. L'algorithme a été initialement formulé sur les arbres, et a ensuite été étendu aux arbres orientés[2]. Il s'est depuis montré utile comme algorithme approximatif sur les graphes plus généraux[3].
Si X={Xi} est un ensemble de variables aléatoires discrètes avec une loi de probabilité conjointe p, la distribution marginale d'un seul élément Xi est simplement la somme de p sur toutes les autres variables :
Cependant, ce calcul devient vite prohibitif : s'il y a 100 variables binaires, alors, on somme sur les 299 ≈ 6.338 × 1029 valeurs possibles. En exploitant la structure en arbre, la propagation des convictions permet de calculer les marginaux de manière beaucoup plus efficace.