Inférence probabiliste

L'inférence probabiliste est le calcul de la probabilité de variables de requête étant donné des preuves observées dans un modèle probabiliste, constituant la tâche de raisonnement centrale pour les réseaux bayésiens et de Markov.

Definition

L'inférence probabiliste calcule une distribution a posteriori, telle que la probabilité d'une ou plusieurs variables de requête conditionnées par des preuves observées, à partir d'un modèle probabiliste spécifié, soit de manière exacte, soit par approximation.

Scope

Ce sujet couvre les algorithmes qui répondent aux requêtes probabilistes dans les modèles graphiques : les méthodes exactes telles que l'élimination de variables, la propagation de croyances dans les arbres et l'algorithme de l'arbre de jonction (arbre de cliques) ; et les méthodes approximatives telles que la propagation de croyances en boucle (loopy belief propagation) et l'échantillonnage de Monte Carlo (échantillonnage par rejet, pondération de vraisemblance et chaînes de Markov Monte Carlo). Il aborde la complexité computationnelle de l'inférence et les compromis entre l'exactitude et l'évolutivité. La structure des modèles eux-mêmes est traitée dans le cadre des réseaux bayésiens.

Core questions

• Comment une probabilité conditionnelle ou marginale est-elle calculée à partir d'un modèle conjoint sans énumérer la distribution complète ?
• Comment l'élimination de variables exploite-t-elle la factorisation pour calculer des réponses exactes de manière efficace ?
• Quand l'inférence exacte est-elle intraitable, et quelles méthodes approximatives sont utilisées à la place ?
• Comment les méthodes basées sur l'échantillonnage estiment-elles les probabilités a posteriori ?

Key concepts

• requêtes marginales et conditionnelles
• élimination de variables
• propagation de croyances (passage de messages)
• arbre de jonction et largeur arborescente (treewidth)
• propagation de croyances en boucle (loopy belief propagation)
• échantillonnage par rejet et pondération de vraisemblance
• chaînes de Markov Monte Carlo
• inférence exacte vs. approximative

Key theories

Propagation de croyances

Dans les réseaux structurés en arbre, les probabilités a posteriori exactes peuvent être calculées en transmettant des messages locaux entre les nœuds voisins ; la propagation de croyances de Pearl effectue ce calcul distribué et, appliquée aux graphes avec boucles (loopy graphs), fournit une méthode d'inférence approximative largement utilisée.

Inférence par arbre de jonction (arbre de cliques)

L'inférence exacte dans les réseaux généraux peut être organisée en regroupant les variables en un arbre de cliques et en y propageant des messages, ce qui donne des réponses correctes en un temps exponentiel uniquement par rapport à la plus grande clique (la largeur arborescente ou treewidth).

Inférence approximative par échantillonnage

Lorsque l'inférence exacte est irréalisable, les méthodes de Monte Carlo telles que la pondération de vraisemblance et les chaînes de Markov Monte Carlo tirent des échantillons cohérents avec les preuves pour estimer les probabilités a posteriori, échangeant l'exactitude garantie contre l'évolutivité.

Clinical relevance

Les algorithmes d'inférence rendent les modèles probabilistes utilisables : ils alimentent les systèmes de diagnostic et d'aide à la décision, les codes correcteurs d'erreurs (via la propagation de croyances), la vision par ordinateur, la reconnaissance vocale et la bioinformatique, en calculant les probabilités de variables cachées étant donné les données observées.

History

La propagation de croyances de Pearl (années 1980) a permis une inférence exacte pour les réseaux arborescents, et la méthode de l'arbre de jonction de Lauritzen et Spiegelhalter de 1988 a étendu l'inférence exacte aux réseaux généraux via des calculs locaux sur des cliques. La reconnaissance que l'inférence exacte est NP-difficile en général a stimulé d'importants travaux sur l'échantillonnage et les approximations variationnelles.

Key figures

• Judea Pearl
• Steffen L. Lauritzen
• David J. Spiegelhalter
• Daphne Koller

Seminal works

• pearl1986
• lauritzen1988

Frequently asked questions

L'inférence probabiliste est-elle toujours traitable ?

Non. L'inférence exacte dans les réseaux bayésiens généraux est NP-difficile, et son coût augmente avec la largeur arborescente (treewidth) du réseau. Pour les réseaux qui sont des arbres ou qui ont une faible largeur arborescente, l'inférence exacte est efficace ; sinon, des méthodes approximatives telles que l'échantillonnage ou la propagation de croyances en boucle (loopy belief propagation) sont utilisées.

Quelle est la différence entre l'inférence exacte et l'inférence approximative ?

L'inférence exacte, telle que l'élimination de variables ou l'algorithme de l'arbre de jonction, calcule les probabilités a posteriori réelles. L'inférence approximative, telle que l'échantillonnage de Monte Carlo ou la propagation de croyances en boucle (loopy belief propagation), les estime, ce qui est nécessaire lorsque le calcul exact est trop coûteux pour un modèle vaste ou densément connecté.