Rejection Sampling

Rejection Sampling (Ablehnungsstichprobenverfahren) zieht exakte Stichproben aus einer Zieldichte, indem es Vorschläge aus einer einfacheren Hüllverteilung generiert und jeden Vorschlag mit einer Wahrscheinlichkeit annimmt, die proportional zum Verhältnis von Ziel- zu Hüllverteilung ist, wobei der Rest verworfen wird.

Definition

Rejection Sampling ist eine Monte-Carlo-Technik, die einen Kandidaten aus einer Vorschlagsdichte generiert, die das Ziel bis auf eine Konstante dominiert, und dann den Kandidaten mit einer Wahrscheinlichkeit annimmt, die dem Verhältnis der Ziel- zur Begrenzungsdichte entspricht, wodurch die angenommenen Werte genau wie das Ziel verteilt sind.

Scope

Dieses Thema behandelt den grundlegenden Akzeptanz-Ablehnungs-Algorithmus und seine Korrektheit, die Rolle der Hüllkurve und der Begrenzungskonstante bei der Bestimmung der Effizienz, die Squeeze-Technik zur Vermeidung kostspieliger Dichteberechnungen sowie adaptive Konstruktionen wie das adaptive Rejection Sampling für logarithmisch-konkave Dichten. Es stellt eine Verbindung zu Akzeptanzschritten innerhalb von Markov-Ketten-Methoden her.

Core questions

• Warum sind angenommene Kandidaten genau gemäß der Zieldichte verteilt?
• Wie steuert die Begrenzungskonstante die erwartete Anzahl von Vorschlägen pro angenommener Ziehung?
• Wie reduzieren Squeeze-Funktionen die Anzahl teurer Dichteberechnungen?
• Wie kann die Hüllkurve für logarithmisch-konkave Dichten automatisch erstellt und verfeinert werden?

Key concepts

• Hüllverteilung
• Begrenzungskonstante
• Akzeptanzwahrscheinlichkeit
• Squeeze-Funktion
• Logarithmische Konkavität

Key theories

Akzeptanz-Ablehnungs-Prinzip

Wenn eine Vorschlagsdichte multipliziert mit einer Konstanten das Ziel überall dominiert, erzeugt die Annahme von Vorschlägen mit einer Wahrscheinlichkeit, die dem Verhältnis von Ziel zu Begrenzung entspricht, exakte Zielstichproben; die Akzeptanzwahrscheinlichkeit entspricht dem Kehrwert der Begrenzungskonstante.

Adaptives Rejection Sampling

Für logarithmisch-konkave Dichten kann eine stückweise-exponentielle Hüllkurve, die aus Tangenten und Sehnen konstruiert wird, an jedem abgelehnten Punkt verfeinert werden, wodurch die Akzeptanzrate ohne Kenntnis der Normierungskonstante gegen eins getrieben wird.

Clinical relevance

Rejection Sampling generiert Variaten aus Dichten, die nur bis auf eine Konstante bekannt sind, was in der Bayes'schen Berechnung ständig vorkommt; insbesondere das adaptive Rejection Sampling liefert die vollständigen bedingten Ziehungen innerhalb vieler Gibbs-Sampler und ist somit ein Baustein der praktischen Posterior-Simulation.

History

Von Neumann beschrieb die Akzeptanz-Ablehnungs-Idee in den frühen Tagen der Monte-Carlo-Berechnung; spätere Arbeiten verallgemeinerten die Hüllkurven, fügten Squeeze-Schritte zur Effizienz hinzu und entwickelten adaptive Schemata, die die Hüllkurve für logarithmisch-konkave Ziele, die in der Bayes'schen Stichprobenziehung verwendet werden, automatisch straffen.

Key figures

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

Seminal works

• devroye1986
• gilks1992

Frequently asked questions

Was macht Rejection Sampling effizient oder ineffizient?

Die Effizienz wird davon bestimmt, wie eng die skalierte Hüllkurve das Ziel umschließt. Eine lockere Hüllkurve bedeutet eine große Begrenzungskonstante und viele abgelehnte Vorschläge; in hohen Dimensionen kann die Akzeptanzrate unpraktisch klein werden.

Warum ist Rejection Sampling nützlich, wenn die Normierungskonstante unbekannt ist?

Die Methode benötigt die Zieldichte nur bis auf eine multiplikative Konstante, da diese Konstante in die Begrenzungskonstante absorbiert wird. Deshalb passt sie natürlich zu Bayes'schen Posterioren, die typischerweise nur bis zu ihrem Normierungsfaktor bekannt sind.