Ce module présente l'algorithme le plus simple pour l'inférence exacte dans les modèles graphiques : l'élimination des variables. Nous décrivons l'algorithme et analysons sa complexité en termes de propriétés de la structure du graphe.

Ce module décrit une vision alternative de l'inférence exacte dans les modèles graphiques : celle du passage de messages entre les clusters, chacun d'entre eux codant un facteur sur un sous-ensemble de variables. Ce cadre fournit une base pour une variété d'algorithmes d'inférence exacts et approximatifs. Nous nous concentrons ici sur le cadre de base et sur son instanciation dans le cas exact de la propagation d'arbres de cliques. Une leçon optionnelle décrit l'algorithme de propagation de croyances en boucle (LBP) et ses propriétés.

Ce module décrit les algorithmes permettant de trouver l'affectation la plus probable pour une distribution codée sous forme de MGP (une tâche connue sous le nom d'inférence MAP). Nous décrivons les algorithmes de passage de messages, qui sont très similaires aux algorithmes de calcul des probabilités conditionnelles, à ceci près que nous devons également réfléchir à la manière de décoder les résultats pour construire une affectation unique. Dans un module optionnel, nous décrivons quelques autres algorithmes capables d'utiliser des techniques très différentes en exploitant la nature d'optimisation combinatoire de la tâche MAP.

Dans ce module, nous discutons d'une classe d'algorithmes qui utilise l'échantillonnage aléatoire pour fournir des réponses approximatives à des requêtes de probabilités conditionnelles. La classe la plus couramment utilisée est celle des algorithmes de Monte Carlo par chaîne de Markov (MCMC), qui comprend l'algorithme simple d'échantillonnage de Gibbs, ainsi qu'une famille de méthodes connues sous le nom de Metropolis-Hastings.

Dans cette brève leçon, nous discuterons de la complexité de l'application aux réseaux bayésiens dynamiques de certains algorithmes d'inférence exacts ou approximatifs que nous avons appris plus tôt dans ce cours.

Ce module résume certains des sujets abordés dans ce cours et discute des compromis entre les différents algorithmes. Il comprend également l'examen final du cours.