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é. Cet algorithme fut proposé pour la première fois par Judea Pearl, en 1982. L'algorithme a été initialement formulé sur les arbres, et a ensuite été étendu aux arbres orientés. Il s'est depuis montré utile comme algorithme approximatif sur les graphes plus généraux. 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. Diverses variantes de l'algorithme de propagation des convictions existent pour différents types de graphes (les réseaux Bayésiens et les champs de Markov en particulier). Nous décrivons ici la variante qui fonctionne sur un graphe de factorisation. Un graphe de factorisation est un graphe biparti contenant les nœuds correspondant à des variables V et les facteurs F, avec des liens entre les variables et les facteurs dans lequel ils apparaissent. Nous pouvons alors écrire la fonction de masse conjointe : où xa est le vecteur des nœuds voisins du nœud facteur a.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (7)
EE-613: Machine Learning for Engineers
The objective of this course is to give an overview of machine learning techniques used for real-world applications, and to teach how to implement and use them in practice. Laboratories will be done i
PHYS-512: Statistical physics of computation
The students understand tools from the statistical physics of disordered systems, and apply them to study computational and statistical problems in graph theory, discrete optimisation, inference and m
PHYS-642: Statistical physics for optimization & learning
This course covers the statistical physics approach to computer science problems, with an emphasis on heuristic & rigorous mathematical technics, ranging from graph theory and constraint satisfaction
Afficher plus
Publications associées (73)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.