Approximate Bayesian Computation

Approximate Bayesian Computation (engl., zu dt. „Approximative Bayessche Berechnung“, abgekürzt ABC) stellt eine Klasse von Berechnungsmethoden in der Bayesschen Inferenz dar. In der modellbasierten statistischen Inferenz ist die Likelihood-Funktion von zentraler Bedeutung, da sie die Wahrscheinlichkeit der beobachteten Daten unter einem bestimmten statistischen Modell ausdrückt und somit die Unterstützung quantifiziert, die Daten Parametern und Modellen geben. Für einfache Modelle kann oft eine analytische Formel für die Likelihood-Funktion abgeleitet werden. Bei komplexeren Modellen kann eine analytische Form jedoch schwer zu finden oder aufwändig auszuwerten sein.

ABC-Methoden umgehen die Auswertung der Likelihood-Funktion (indem z. B. Stichproben aus der prior predictive distribution betrachtet werden). Auf diese Weise erweitern sie den Bereich von Modellen, für die statistische Schlussfolgerungen möglich sind. ABC-Methoden sind mathematisch fundiert, aber sie machen Annahmen und Näherungen, deren Auswirkungen beachtet werden müssen. Darüber hinaus verschärft das weitere Anwendungsgebiet von ABC die Herausforderungen in der Parameterschätzung und Modellauswahl.

ABC hat in den letzten Jahren immens an Popularität gewonnen, insbesondere für die Analyse komplexer Probleme in der Populationsgenetik, Ökologie, Epidemiologie und Systembiologie.

Approximate Bayesian Computation kann als Bayessche Version der Indirekten Inferenz verstanden werden.

Geschichte

Die ersten Ideen zu ABC reichen zurück in die 1980er Jahre. Donald Rubin beschrieb bei einer Erörterung der Interpretation Bayesscher Aussagen 1984 einen hypothetischen Sampling-Mechanismus, der eine Probe aus der A-posteriori-Verteilung liefert. Dieses Schema war eher ein konzeptuelles Gedankenexperiment, um zu demonstrieren, welche Art von Manipulationen durchgeführt werden, wenn auf die A-posteriori-Verteilungen von Parametern geschlossen wird. Die Beschreibung des Sampling-Mechanismus stimmt genau mit der des ABC-Rejection-Schemas überein, und dieser Artikel kann als der erste angesehen werden, der die Approximative Bayessche Berechnung beschreibt. Jedoch wurde schon in den späten 1800 Jahren von Francis Galton ein zweistufiger Quincunx konstruiert, der als physikalische Implementierung eines ABC-Rejection-Algorithmus für einen einzelnen unbekannten Parameter und eine einzige Beobachtung angesehen werden kann. Ein anderer vorausschauender Punkt wurde von Rubin gemacht, als er argumentierte, dass sich angewandte Statistiker bei der Bayesschen Inferenz nicht nur mit analytisch handhabbaren Modellen begnügen sollten, sondern stattdessen Rechenmethoden in Betracht ziehen, die es ihnen ermöglichen, die A-posteriori-Verteilung von Interesse zu schätzen. Auf diese Weise kann eine größere Auswahl an Modellen in Betracht gezogen werden. Diese Argumente sind im Zusammenhang mit ABC besonders relevant.

Im Jahr 1984 schlugen Peter Diggle und Richard Gratton vor, ein systematisches Simulationsschema zu verwenden, um die Likelihood-Funktion in Situationen anzunähern, in denen ihre analytische Form nicht praktikabel ist. Ihre Methode basierte darauf, ein Gitter im Parameterraum zu definieren und es zu verwenden, um die Likelihood anzunähern, indem mehrere Simulationen für jeden Gitterpunkt ausgeführt wurden. Die Approximation wurde dann durch Anwendung von Glättungstechniken auf die Ergebnisse der Simulationen verbessert. Während die Idee, Simulationen für Hypothesentests zu verwenden, nicht neu war, führten Diggle und Gratton anscheinend das erste Verfahren ein, das Simulation zur statistischen Inferenz unter Umständen verwendet, bei denen die Likelihood nicht zugänglich ist.

Die Methode von Diggle und Gratton war noch nicht genau identisch mit dem, was heute als ABC bekannt ist, da sie eher auf die Likelihood als auf die A-posteriori-Verteilung abzielte. In einem Artikel von Simon Tavaré et al. wurde zum ersten Mal ein ABC-Algorithmus für die Inferenz der A-posteriori-Verteilung vorgeschlagen. In ihrer bahnbrechenden Arbeit wurde Inferenz über die Genealogie von DNA-Sequenzdaten und insbesondere das Problem der Bestimmung der A-posteriori-Verteilung der Zeit bis zum letzten gemeinsamen Vorfahren der Stichprobenpersonen in Betracht gezogen. Eine solche Inferenz ist für viele demographische Modelle analytisch unlösbar, aber die Autoren präsentierten Möglichkeiten, Koaleszenzbäume unter den mutmaßlichen Modellen zu simulieren. Eine Stichprobe von Modellparametern wurde erhalten, indem Vorschläge angenommen oder abgelehnt wurden, die auf einem Vergleich der Anzahl von Trennstellen in den synthetischen und realen Daten beruhten. Dieser Arbeit folgte eine angewandte Studie zur Modellierung der Variation des menschlichen Y-Chromosoms durch Jonathan K. Pritchard et al. mit der ABC-Methode. Schließlich wurde der Begriff der Approximate Bayesian Computation (ABC) von Mark Beaumont et al. eingeführt, der die ABC-Methodik weiter ausbaute und die Eignung des ABC-Ansatzes für Probleme in der Populationsgenetik diskutierte. Seitdem hat sich ABC auf Anwendungen außerhalb der Populationsgenetik wie Systembiologie, Epidemiologie und Phylogeographie ausgebreitet.

Methode

Motivation

Der Satz von Bayes verbindet die bedingte Wahrscheinlichkeit (oder bedingte Wahrscheinlichkeitsdichte) eines bestimmten Parameterwerts $\theta$ gegeben beobachtete Daten $D$ mit der Wahrscheinlichkeit von $D$ gegeben $\theta$ über die Regel

$p(\theta |D)={\frac {p(D|\theta )p(\theta )}{p(D)}}$,

wo $p(\theta |D)$ die A-posteriori-Wahrscheinlichkeit (auch bekannt als Posterior), $p(D|\theta )$ die Likelihood, $p(\theta )$ die A-priori-Verteilung von $\theta$ (auch bekannt als Prior), und $p(D)$ die Evidenz (auch bekannt als Marginal-Likelihood oder Prior-Predictive-Wahrscheinlichkeit) bezeichnen.

Der Prior spiegelt Überzeugungen über $\theta$ wider, bevor $D$ verfügbar ist, und wird oft spezifiziert, indem eine bestimmte Verteilung aus einer Menge bekannter und handlicher Familien von Verteilungen ausgewählt wird, so dass sowohl die Auswertung des Posterior als auch die Erzeugung von zufälligen $\theta$ relativ einfach sind. Für bestimmte Arten von Modellen ist es pragmatischer, den Prior $p(\theta )$ anzugeben, indem eine Faktorisierung der gemeinsamen Verteilung aller Elemente von $\theta$ verwendet wird über eine Folge ihrer bedingten Verteilungen. Wenn man sich nur für die relativen Posterior-Plausibilitäten verschiedener Werte von $\theta$ interessiert, kann die Evidenz $p(D)$ ignoriert werden, da er eine Normalisierungskonstant darstellt, welche sich herauskürzt. Dies verwenden zum Beispiel MCMC-Verfahren. Es bleibt jedoch notwendig, die Likelihood $p(D|\theta )$ und den Prior $p(\theta )$ auszuwerten. Für zahlreiche Anwendungen ist es allerdings rechenintensiv oder sogar unmöglich, die Likelihood auszuwerten, was die Verwendung von ABC zur Umgehung dieses Problems motiviert.

ABC-Rejection-Algorithmus

Alle ABC-basierten Methoden approximieren die Likelihood-Funktion durch Simulationen, deren Ergebnisse mit den beobachteten Daten verglichen werden. Genauer gesagt wird mit dem ABC-Rejection-Algorithmus (dt. ABC-Zurückweisungsalgorithmus) – der grundlegendsten Form von ABC – zuerst eine Menge von Parametern gemäß A-priori-Verteilung gezogen. Gegeben einen zufällig gezogenen Parameter ${\hat {\theta }}$, wird dann ein Datensatz ${\hat {D}}$ simuliert, unter dem statistischen Modell $M$ spezifiziert durch ${\hat {\theta }}$. Wenn das erzeugte ${\hat {D}}$ zu verschieden von den beobachteten Daten $D$ ist, wird der Parameter verworfen. Konkreter wird ${\hat {D}}$ mit Toleranz $\epsilon \geq 0$ akzeptiert, wenn

$\rho ({\hat {D}},D)\leq \epsilon$,

wo das Distanzmaß $\rho ({\hat {D}},D)$ die Diskrepanz zwischen ${\hat {D}}$ und $D$ basierend auf einer gegebenen Metrik (z. B. Euklidischer Abstand) quantifiziert. Eine streng positive Toleranz ist (außer in diskreten Räumen) normalerweise notwendig, da die Wahrscheinlichkeit, dass das Simulationsergebnis genau mit den Daten übereinstimmt (Ereignis ${\hat {D}}=D$) vernachlässigbar ist für alle außer trivialen Anwendungen von ABC, was in der Praxis zur Zurückweisung fast aller abgetasteten Parameterpunkte führen würde. Das Ergebnis des ABC-Rejection-Algorithmus ist eine Stichprobe von Parameterwerten, die approximativ entsprechend der gewünschten A-posteriori-Verteilung verteilt sind, und, im Wesentlichen, erhalten ohne die explizite Auswertung der Likelihood-Funktion.

Darstellung der prinzipiellen Funktionsweise von Approximate Bayesian Computation

Zusammenfassende Statistiken

Die Wahrscheinlichkeit, einen Datensatz ${\hat {D}}$ mit einem kleinen Abstand zu $D$ zu erzeugen, nimmt typischerweise exponentiell ab, wenn die Dimensionalität der Daten zunimmt. Dies führt zu einer wesentlichen Verringerung der Recheneffizienz des obigen grundlegenden ABC-Rejection-Algorithmus. Ein üblicher Ansatz, um dieses Problem zu verringern, besteht darin, $D$ durch einen Satz von geringer-dimensionalen zusammenfassenden Statistiken (engl. Summary Statistics) $S(D)$ zu ersetzen, welche ausgewählt werden, die relevanten Informationen in $D$ zu erfassen. Das Akzeptanzkriterium im ABC-Zurückweisungsalgorithmus wird ersetzt durch

$\rho (S({\hat {D}}),S(D))\leq \epsilon$.

Wenn die zusammenfassenden Statistiken in Bezug auf die Modellparameter $\theta$ suffizient sind, führt die so erzielte Effizienzsteigerung zu keinem Fehler. Definitionsgemäß bedeutet Suffizienz, dass alle Informationen in $D$ über $\theta$ von $S(D)$ erfasst werden.

Typischerweise ist es außerhalb der Exponentialfamilie von Verteilungen unmöglich, einen endlichen dimensionalen Satz von ausreichenden Statistiken zu identifizieren. Dennoch werden informative, aber möglicherweise unzureichende Zusammenfassungsstatistiken häufig in Anwendungen verwendet, in denen Inferenz mit ABC-Methoden durchgeführt wird. Somit gibt es zwei Quellen für Approximationefehler bei der Verwendung von ABC zum Sampling von der A-posteriori-Verteilung: Durch den Akzeptanz-Toleranz-Parameter $\epsilon$ und durch die zusammenfassenden Statistiken $S(D)$.

ABC-MCMC- und ABC-SMC-Algorithmus

Ein Nachteil des ABC-Rejection-Algorithmus ist, dass Parameterwerte direkt aus der A-priori-Verteilung gezogen werden. Sind zum Beispiel die Daten informativ, wird die A-posteriori-Verteilung deutlich konzentrierter sein, so dass viele simulierte Daten nicht gut mit den beobachteten Daten übereinstimmen, mithin wird die Akzeptanzrate gering sein. Daher ist es sinnvoll, die Parameter von einer Verteilung zu ziehen, welche (adaptiv) näher an der A-posteriori-Verteilung ist. Hierzu gibt es im Wesentlichen zwei Wege: Über einen Markov-Chain-Monte-Carlo-Algorithmus (MCMC) oder einen Sequential-Monte-Carlo-Algorithmus (SMC). Beide haben ihre jeweiligen Stärken, im ABC-Kontext hat sich SMC stärker etabliert, da dieses Schema gut zu parallelisieren ist und eine adaptive Verringerung des Akzeptanz-Toleranz-Parameters $\epsilon$ ermöglicht. Eine Übersicht der Algorithmen findet sich in Beaumont (2010).

Software

Es existieren verschiedene Software-Implementierungen für ABC. Es folgt eine nicht-erschöpfende Auflistung von Implementierungen:

• pyABC
• DIY-ABC
• abc R package
• EasyABC R package
• ABC-SysBio
• ABCtoolbox (Memento vom 19. Februar 2013 im Webarchiv archive.today)
• msBayes
• PopABC
• ONeSAMP
• ABC4F
• 2BAD
• ELFI