Échantillonnage par rejet

L'échantillonnage par rejet permet de tirer des échantillons exacts d'une densité cible en proposant des valeurs à partir d'une distribution enveloppe plus facile à gérer et en acceptant chaque proposition avec une probabilité proportionnelle au rapport de la densité cible à la densité enveloppe, en rejetant le reste.

Definition

L'échantillonnage par rejet est une technique de Monte Carlo qui génère un candidat à partir d'une densité de proposition dominant la cible à une constante près, puis accepte le candidat avec une probabilité égale au rapport de la densité cible à la densité majorante, produisant ainsi des valeurs acceptées distribuées exactement comme la cible.

Scope

Ce sujet couvre l'algorithme de base d'acceptation-rejet et sa validité, le rôle de l'enveloppe et de la constante de majoration dans la détermination de l'efficacité, la technique de compression (squeeze technique) pour éviter les évaluations coûteuses de la densité, et les constructions adaptatives telles que l'échantillonnage par rejet adaptatif pour les densités log-concaves. Il est lié aux étapes d'acceptation dans les méthodes de chaînes de Markov.

Core questions

• Pourquoi les candidats acceptés sont-ils distribués exactement selon la densité cible ?
• Comment la constante de majoration contrôle-t-elle le nombre attendu de propositions par tirage accepté ?
• Comment les fonctions de compression (squeeze functions) réduisent-elles le nombre d'évaluations coûteuses de la densité ?
• Comment l'enveloppe peut-elle être construite et affinée automatiquement pour les densités log-concaves ?

Key concepts

• Distribution enveloppe
• Constante de majoration
• Probabilité d'acceptation
• Fonction de compression
• Log-concavité

Key theories

Principe d'acceptation-rejet

Si une densité de proposition multipliée par une constante domine la cible partout, accepter les propositions avec une probabilité égale au rapport cible-sur-majorant produit des échantillons cibles exacts ; la probabilité d'acceptation est égale à l'inverse de la constante de majoration.

Échantillonnage par rejet adaptatif

Pour les densités log-concaves, une enveloppe exponentielle par morceaux construite à partir de tangentes et de cordes peut être affinée à chaque point rejeté, ce qui tend à augmenter le taux d'acceptation vers un sans nécessiter la constante de normalisation.

Clinical relevance

L'échantillonnage par rejet génère des variables aléatoires à partir de densités connues seulement à une constante près, ce qui se produit constamment dans le calcul bayésien ; l'échantillonnage par rejet adaptatif, en particulier, fournit les tirages conditionnels complets (full-conditional draws) au sein de nombreux échantillonneurs de Gibbs, ce qui en fait un élément constitutif de la simulation a posteriori pratique.

History

Von Neumann a décrit l'idée d'acceptation-rejet aux débuts du calcul de Monte Carlo ; des travaux ultérieurs ont généralisé les enveloppes, ajouté des étapes de compression (squeeze steps) pour l'efficacité, et développé des schémas adaptatifs qui resserrent automatiquement l'enveloppe pour les cibles log-concaves utilisées dans l'échantillonnage bayésien.

Key figures

• John von Neumann
• Luc Devroye
• Walter Gilks
• Christian P. Robert

Seminal works

• devroye1986
• gilks1992

Frequently asked questions

Qu'est-ce qui rend l'échantillonnage par rejet efficace ou inefficace ?

L'efficacité est régie par la façon dont l'enveloppe mise à l'échelle épouse étroitement la cible. Une enveloppe lâche signifie une constante de majoration élevée et de nombreuses propositions rejetées ; dans les grandes dimensions, le taux d'acceptation peut devenir trop faible pour être pratique.

Pourquoi l'échantillonnage par rejet est-il utile lorsque la constante de normalisation est inconnue ?

La méthode n'a besoin de la densité cible qu'à une constante multiplicative près, car cette constante est absorbée dans la constante de majoration. C'est pourquoi elle s'associe naturellement aux distributions a posteriori bayésiennes, qui ne sont généralement connues qu'à leur normalisateur près.