| Resumé |
Les algorithmes à propagation de messages constituent un schéma de calcul parallèle pour estimer les marginales d'une loi de probabilité de haute dimension. Ils ont été employés dans des domaines variés où la statistique d'un grand nombre de variables en interaction doit être étudiée, comme la physique statistique, l'intelligence artificielle, le décodage en théorie de l'information. Cette thèse décrit les structures algébriques et topologiques naturelles où se déroulent la propagation de messages. Dans la plupart des applications, la loi de probabilité p est définie par un champ de Markov ou modèle graphique, i.e. par un produit de facteurs locaux qui ne dépendent que d'un petit sous-ensemble de variables en interaction. De manière équivalente, l'énergie totale H = ln p (ou log-vraisemblance) est une somme de potentiels d'interaction locaux. Nous montrons que cette contrainte est équivalente à l'existence d'une paramétrisation biunivoque de l'énergie totale par les classes d'homologie de potentiels locaux, en immergeant les potentiels comme sous-espace de degré 0 d'un complexe de chaînes d'observables locales. Les 1-chaînes de ce complexe sont un analogue statistique des flux de chaleur. L'évolution de potentiels à un bord de flux de chaleur près, préservant l'énergie totale, produit de nouveaux algorithmes à propagation de croyances comme des équations de diffusion à temps continu. La consistance des pseudo-marginales que l'on cherche à approximer est réciproquement traduite par une contrainte cohomologique, demandant que la collection de probabilités locales ait une différentielle nulle. Les potentiels locaux et les probabilités locales forment une paire de variables duales, reliées par une fonctionnelle lisse et non-linéaire, composant essentiellement l'exponentielle avec une somme sur les sous-parties appelée transformée zeta en combinatoire. Les paires à l'intersection des surfaces de contrainte associées à la conservation de l'énergie et à la consistance marginale respectivement sont mises en correspondance avec les points stationnaires des algorithmes à propagation de croyance d'une part, et avec les points critiques d'une approximation locale de l'énergie libre, obtenue par la méthode combinatoire de Bethe-Kikuchi (en tronquant la transformée de Möbius, inverse de la transformée zeta) d'autre part. |