Propagation des convictions

Propagation des convictions

Type	Algorithme
Inventeur	Judea Pearl
Date d'invention	1982
Formule	$p_{X_{i}}(x_{i})=\sum _{\mathbf {x} 'x'_{i}\neq x_{i}}p(\mathbf {x} ')$

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={X_i} est un ensemble de variables aléatoires discrètes avec une loi de probabilité conjointe p, la distribution marginale d'un seul élément X_i est simplement la somme de p sur toutes les autres variables :

$p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ').$

Cependant, ce calcul devient vite prohibitif : s'il y a 100 variables binaires, alors, on somme sur les 2⁹⁹ ≈ 6.338 × 10²⁹ valeurs possibles. En exploitant la structure en arbre, la propagation des convictions permet de calculer les marginaux de manière beaucoup plus efficace.

Description de l'algorithme somme-produit

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 :

$p(\mathbf {x} )=\prod _{a\in F}f_{a}(\mathbf {x} _{a})$

où x_a est le vecteur des nœuds voisins du nœud facteur a. Tout réseau Bayésien ou champs de Markov peut être représenté comme un graphe de factorisation.

L'algorithme fonctionne en « passant » des fonctions à valeur réelle appelées messages le long des liens entre les nœuds cachés. Plus précisément, si v est un nœud variable et a est un nœud facteur connecté à v dans le graphe, les messages de v pour a, (noté par $\mu _{v\to a}$) et de a à v ($\mu _{a\to v}$), sont des fonctions à valeurs réelles dont le domaine est Dom(v) : l'ensemble des valeurs pouvant être prises par la variable aléatoire associée à v. Ces messages contiennent les "influences" qu'une variable exerce sur l'autre. Les messages sont calculées différemment selon que le nœud qui reçoit le message est un nœud variable ou un nœud facteur. En gardant la même notation:

• Un message d'un nœud variable v à un nœud facteur a est le produit des messages de tous les autres nœuds facteurs voisins (à l'exception du destinataire ; à l'inverse, on peut dire que le destinataire envoie en message la fonction constante égale à "1"):

$\forall x_{v}\in Dom(v),\;\mu _{v\to a}(x_{v})=\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v}).$

où N(v) est l'ensemble des nœuds facteurs voisins de v. Si $N(v)\setminus \{a\}$ est vide, alors $\mu _{v\to a}(x_{v})$ est fixé à la distribution uniforme.

• Un message d'un nœud facteur a à un nœud variable v est le produit du facteur en utilisant les messages de tous les autres nœuds : on marginalise toutes les variables à l'exception de celle associée à v:

$\forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).$

où N(a) est l'ensemble des nœuds variables voisins de a. Si $N(a)\setminus \{v\}$ est vide alors $\mu _{a\to v}(x_{v})=f_{a}(x_{v})$ puisque dans ce cas $x_{v}=x_{a}$.

Comme montré par la formule précédente : la marginalisation complète est ainsi réduite à une somme de produits de termes plus simples que celles figurant dans l'intégralité de la distribution conjointe. C'est la raison pour laquelle on l'appelle l'algorithme somme-produit.

Dans une utilisation typique, chaque message sera mis à jour de manière itérative à partir de la valeur précédente des messages voisins. La mise à jour des messages peut être planifiée de différentes manières. Dans le cas où le graphe est un arbre, une planification optimale permet d'obtenir la convergence après le calcul de chacun des messages une seule fois (voir la prochaine sous-section). Lorsque le graphe possède des cycles, une telle planification optimale n'existe pas, et un choix typique est de mettre à jour tous les messages simultanément à chaque itération.

Lors de la convergence (si cette dernière a lieu), l'estimation de la distribution marginale de chacun des nœuds est proportionnelle au produit de tous les messages des facteurs voisins (il ne manque que la constante de normalisation):

$p_{X_{v}}(x_{v})\propto \prod _{a\in N(v)}\mu _{a\to v}(x_{v}).$

De même, l'estimation de la distribution marginale de l'ensemble des variables appartenant à un seul facteur est proportionnelle au produit du facteur avec messages des variables voisines :

$p_{X_{a}}(\mathbf {x} _{a})\propto f_{a}(\mathbf {x} _{a})\prod _{v\in N(a)}\mu _{v\to a}(x_{v}).$

Dans le cas où le facteur de graphe est acyclique (c'est-à-dire un arbre ou une forêt), ces marginaux estimés convergent vers les vrais marginaux en un nombre fini d'itérations. Ce qui peut être prouvé par induction.

Algorithme exact pour les arbres

Dans le cas ou le graphe est un arbre, l'algorithme de propagation des convictions permet d'obtenir les marginales exactes. De plus en planifiant correctement les mises-à-jour des messages, il termine en 2 étapes. Cette planification optimale peut être décrite de la manière suivante. Pour commencer, le graphe est orienté en désignant un nœud comme la racine ; tout autre nœud connecté à un seul autre nœud est appelé une feuille.

Durant la première étape, les messages sont propagés vers l'intérieur : en commençant par les feuilles, chaque nœud propage un message le long de l'unique lien vers la racine. La structure en arbre assure qu'il est possible d'obtenir les messages de tous les nœuds adjacent avant de passer son propre message. Ceci se poursuit jusqu'à ce que la racine ait obtenu les messages de tous ses nœuds adjacents.

La deuxième étape consiste à faire revenir les messages vers l'extérieur : à partir de la racine, les messages sont transmis dans le sens inverse. L'algorithme est terminé lorsque toutes les feuilles ont reçu leurs messages.

Algorithme approximatif pour les graphes génériques

Curieusement, bien qu'il ait été conçu à l'origine pour les graphes acycliques. Il a été constaté que l'algorithme de propagation des convictions peut être utilisé pour des graphes quelconques. L'algorithme est alors parfois appelé la propagation de conviction "à boucle", parce que les graphiques contiennent généralement des cycles, ou des boucles. L'initialisation et la planification de la mise-à-jour des messages doivent être légèrement ajustées (par rapport au cas donné pour les arbres) parce que ces graphes peuvent ne pas contenir de feuilles. Au lieu de cela, on initialise tous les messages des nœuds variables à 1, puis on utilise la définition des messages ci-dessus. La mise-à-jour de tous les messages est effectuées à chaque itération (bien que les messages provenant de feuilles ou de sous-arbres connus n'ont plus besoin de mises-à-jour après un nombre suffisant d'itérations). Il est facile de montrer que, dans un arbre, les messages produit par cette modification convergent vers les messages décrit ci-dessus après un nombre d'itérations égal au diamètre de l'arbre.

Les conditions précises sous lesquelles la propagation de conviction "à boucle" converge ne sont pas encore bien comprises. Il est connu que sur les graphes contenant une seule boucle, elle converge dans la plupart des cas, mais les probabilités obtenues peuvent être incorrects. Plusieurs conditions sont suffisantes (mais pas nécessaires) pour assurer l'existence d'un unique point fixe de convergence. Il existe des graphes qui ne convergent pas, ou même qui oscillent entre plusieurs états après plusieurs itérations. Des techniques comme EXIT peuvent fournir une visualisation approchée de la progression de l'algorithme et fournissent ainsi une évaluation approximative de la convergence.

Il existe d'autres méthodes approximatives pour calculer les marginaux y compris les méthodes variationnelles et les méthodes de Monte Carlo.

Une méthode exacte de calcul des marginales, pour le cas général, est appelée l'algorithme de l'arbre de jonction, qui est tout simplement la propagation des convictions sur une version modifiée du graphe qui est garantie d'être un arbre. Le principe de base est d'éliminer les cycles en les regroupant dans un seul nœud.

Algorithmes analogues et complexité

Un algorithme similaire est communément appelé l'algorithme de Viterbi, il s'agit d'un cas particulier de l'algorithme du max-produit ou de min-somme, pour résoudre le problème de la maximisation, ou de l'explication la plus probable. Au lieu de tenter de calculer les marginaux, le but est ici de trouver les valeurs $\mathbf {x}$ qui maximisent la fonction globale (c'est-à-dire les valeurs les plus probables dans un cadre probabiliste), et il peut être défini à l'aide de l'arg max:

$\operatorname {*} {arg\,max}_{\mathbf {x} }g(\mathbf {x} ).$

Un algorithme qui permet de résoudre ce problème est presque identique à la propagation des convictions, en remplaçant les sommes par des maxima dans les définitions.

Il est intéressant de noter que les problèmes d'inférence tels que la marginalisation et l'optimisation sont NP-difficiles à résoudre dans les cas exact et même approché (au moins pour l'erreur relative) pour un graphe quelconque. Plus précisément, le problème de la marginalisation définie ci-dessus est #P-complet et celui de la maximisation est NP-complet.

L'utilisation de la mémoire par la propagation des convictions peut être réduit grâce à l'utilisation de l'algorithme en île (pour un faible coût sur la complexité temporelle).

Lien avec l'énergie libre

L'algorithme somme-produit est reliée au calcul de l'énergie libre en thermodynamique. Soit Z la fonction de partition. La distribution de probabilité

$P(\mathbf {X} )={\frac {1}{Z}}\prod _{f_{j}}f_{j}(x_{j})$

(notez la ressemblance avec un graphe de factorisation) peut être considérée comme une mesure de l'énergie interne présente dans le système, calculée comme

$E(\mathbf {X} )=\log \prod _{f_{j}}f_{j}(x_{j}).$

L'énergie libre du système est alors

$F=U-H=\sum _{\mathbf {X} }P(\mathbf {X} )E(\mathbf {X} )+\sum _{\mathbf {X} }P(\mathbf {X} )\log P(\mathbf {X} ).$

On peut montré que les points de convergence de l'algorithme somme-produit représentent les états minimales de l'énergie libre d'un tel système. De même, il peut être démontré qu'un point fixe de l'algorithme itératif de propagation des convictions dans les graphes à cycles est aussi un point fixe de l'approximation de l'énergie libre.

La propagation des convictions généralisée

Les algorithmes de propagation des convictions sont normalement présentés comme des mises à jour des équations sur un graphe de factorisation, impliquant des messages entre les nœuds variables et leurs nœuds facteurs voisins et vice versa. Considérer les messages entre des régions d'un graphe est une façon de généraliser l'algorithme de propagation des convictions. Il existe plusieurs façons de définir l'ensemble des régions d'un graphe qui peuvent échanger des messages. Une méthode utilise les idées introduites par Kikuchi dans la littérature physique, et est connu comme la méthode de variation des clusters de Kikuchi.

Des améliorations dans la performance des algorithmes de propagation des convictions sont également possibles en brisant la symétrie des répliques dans les distributions des champs (les messages). Cette généralisation conduit à un nouveau type d'algorithme appelé enquête de propagation, qui se sont révélés très efficaces pour les problèmes NP-complet comme la satisfiabilité et la coloration de graphe.

Les méthodes de variation des clusters et l'enquête de propagation sont deux différentes améliorations de la propagation des convictions.

Propagation des convictions gaussienne

La propagation des convictions gaussienne (PCG) est une variante de l'algorithme de propagation des convictions lorsque les distributions sous-jacentes sont Gaussiennes. Les premiers à analyser ce modèle spécial ont été Weiss et Freeman.

L'algorithme PCG résout le problème de calcul des marginales suivant :

$P(x_{i})={\frac {1}{Z}}\int _{j\neq i}\exp(-1/2x^{T}Ax+b^{T}x)\,dx_{j}$

où Z est une constante de normalisation, A est une matrice définie positive symétrique (l'inverse de la matrice de covariance c'est-à-dire la précision de la matrice) et b est le vecteur de changement.

De manière équivalente, il peut être montré qu'en utilisant le modèle Gaussien, la solution du problème de la marginalisation est l'équivalent du maximum a posteriori du problème d'affectation :

${\underset {x}{\operatorname {argmax} }}\ P(x)={\frac {1}{Z}}\exp(-1/2x^{T}Ax+b^{T}x).$

Ce problème est équivalent au problème de minimisation de l'équation du second degré suivant :

${\underset {x}{\operatorname {min} }}\ 1/2x^{T}Ax-b^{T}x.$

C'est aussi équivalent au système linéaire d'équations

$Ax=b.$

La convergence de l'algorithme PCG est plus facile à analyser (relativement au cas général de la programmation des convictions) et il y a deux conditions de convergence suffisantes connues. La première a été formulée par Weiss et coll. en l'an 2000 : lorsque l'information de la matrice A est à diagonale dominante. La deuxième condition de convergence a été formulée par Johnson et al. en 2006, lorsque le rayon spectral de la matrice vérifie

$\rho (I-|D^{-1/2}AD^{-1/2}|)<1\,$

où D = diag(A).

L'algorithme PCG a été reliée à l'algèbre linéaire et il a été montré que l'algorithme PCG peut être considéré comme un algorithme itératif pour la résolution du système linéaire d'équations Ax = b où A est la matrice d'information et de b est le vecteur de changement. Empiriquement, l'algorithme PCG se trouve converger plus rapidement que les méthodes itératives classiques comme la méthode de Jacobi, la méthode de Gauss–Seidel, ou la méthode de surrelaxation successive, et d'autres. En outre, l'algorithme PCG est montré être à l'abri de problèmes numériques de la méthode du gradient conjugué pré conditionné

Bibliographie

• Bickson, Danny. (2009). Gaussien belief Propagation Page de Ressources —Page web contenant les dernières publications ainsi que le code source Matlab.
• (en) Christopher M. Bishop, Pattern Recognition and Machine Learning, New York, Springer, 2006, 359–418 p. (ISBN 0-387-31073-8), « Chapter 8: Graphical models »
• Coughlan, James. (2009). Un Tutoriel d'Introduction à la Croyance de Propagation.
• Koch, Volker M. (2007). Un Facteur Graphique de l'Approche Basée sur un Modèle de Séparation des Signaux —Un tutoriel de style de thèse
• Hans-Andrea Löliger, « An Introduction to Factor Graphs », IEEE Signal Proc. Mag., vol. 21,‎ 2004, p. 28–41 (lire en ligne)
• Mackenzie, Dana (2005). "Vitesse De Communication À L'Approche De La Vitesse Terminale", Le New Scientist. Le 9 juillet 2005. Question 2507 (Inscription obligatoire)
• Henk Wymeersch, Iterative Receiver Design, Cambridge University Press, 2007, 272 p. (ISBN 978-0-521-87315-4 et 0-521-87315-0, lire en ligne)
• J.S. Yedidia, W.T. Freeman et Y. Weiss, Exploring Artificial Intelligence in the New Millennium, Morgan Kaufmann, janvier 2003, 239–236 p. (ISBN 1-55860-811-7), « Understanding Belief Propagation and Its Generalizations »
• J.S. Yedidia, W.T. Freeman et Y. Weiss, « Constructing free-energy approximations and generalized belief propagation algorithms », IEEE Transactions on Information Theory, vol. 51, n^o 7,‎ juillet 2005, p. 2282–2312 (DOI 10.1109/TIT.2005.850085, lire en ligne, consulté le 28 mars 2009)

Article lié

• Polyarbre