Genaue Probenahme aus ungeeigneten Gemischen

Angenommen, ich möchte aus einer kontinuierlichen Verteilung . Wenn ich einen Ausdruck von in der Form habe $p(x)$ $p$

p (x) = \sum_{i = 1}^{\infty} a_{i} f_{i} (x)

$p(x) = \sum_{i=1}^\infty a_i f_i(x)$

wobei und Verteilungen sind, aus denen leicht abgetastet werden kann, dann kann ich leicht Abtastwerte aus erzeugen durch: $a_i \geqslant 0, \sum_i a_i= 1$ $f_i$ $p$

Abtasten eines Labels $i$ mit der Wahrscheinlichkeit $a_i$
Abtastung $X \sim f_i$

Ist es möglich, diese Prozedur zu verallgemeinern, wenn die $a_i$ gelegentlich negativ sind? Ich vermute, ich habe dies irgendwo gesehen - möglicherweise in einem Buch, möglicherweise für die Kolmogorov-Distribution -, daher würde ich gerne eine Referenz als Antwort akzeptieren.

Wenn ein konkretes Spielzeug Beispiel nützlich ist, sagen wir , ich auf Probe möchten

p (x, y) \propto \exp (- x - y - α \sqrt{x y}) x, y > 0

$p(x,y) \propto \exp(-x-y-\alpha\sqrt{xy})\qquad x,y > 0$ dann werde ich Nehmen Sie

α \in (0, 2)

$\alpha \in (0, 2)$ aus technischen Gründen, die im großen Schema der Dinge nicht allzu wichtig sein sollten.

Im Prinzip könnte ich dies dann als folgende Summe erweitern:

p (x, y) \propto \sum_{n = 0}^{\infty} \frac{(- 1)^{n} α^{n} (\frac{n}{2})! (\frac{n}{2})!}{n!} (\frac{x^{n / 2} e^{- x}}{(\frac{n}{2})!}) (\frac{y^{n / 2} e^{- y}}{(\frac{n}{2})!}) .

$p(x,y) \propto \sum_{n=0}^\infty \frac{(-1)^n \alpha^n \left( \frac{n}{2} \right)! \left( \frac{n}{2} \right)!}{n!} \left( \frac{x^{n/2} e^{-x}}{\left( \frac{n}{2} \right)!}\right) \left( \frac{y^{n/2} e^{-y}}{\left( \frac{n}{2} \right)!}\right) .$

Die $(x,y)$ -Terms innerhalb der Summe können dann unabhängig voneinander als Gamma-Zufallsvariablen abgetastet werden. Mein Problem ist offensichtlich, dass die Koeffizienten "gelegentlich" negativ sind.

Bearbeiten 1 : Ich stelle klar, dass ich aus exakte Stichproben generieren möchte , anstatt die Erwartungen unter berechnen . Für Interessenten wird in den Kommentaren auf einige Verfahren hingewiesen. $p$ $p$

Edit 2 : Ich habe die Referenz, die einen bestimmten Ansatz für dieses Problem enthält, in Devroyes 'Non-Uniform Random Variate Generation' gefunden . Der Algorithmus stammt aus 'A Note on Sampling from Combinations of Distributions' von Bignami und de Matteis . Das Verfahren besteht effektiv darin, die Dichte von oben durch die positiven Terme der Summe zu begrenzen und dann eine Ablehnungsabtastung basierend auf dieser Hüllkurve zu verwenden. Dies entspricht der in der Antwort von @ Xi'an beschriebenen Methode.

simulation monte-carlo mixture accept-reject πr8
quelle

Warum können Sie nicht einfach den absoluten Wert von und dann Ihre Stichprobe negieren ? Mit anderen Worten definieren Sie(vorausgesetzt , es ist endlich) und dann renormieren Ihre Summe von .

a_{i}

$a_i$

X \sim f_{i}

$X\sim f_i$

Z := \sum_{i = 1}^{\infty} | a_{i} |

$Z:=\sum_{i=1}^\infty |a_i|$

Z

$Z$

Alex R.

@AlexR. Wenn ich Sie verstehe, wäre eine Version davon praktisch, um die Erwartungen unter zu berechnen , aber immer noch nicht, um genaue Stichproben aus . Dies ist sicherlich eine Antwort auf ein relevantes Problem, obwohl es nicht ganz das ist, wonach ich suche.

p

$p$

p

$p$

πr8

Dies hängt davon ab, was Sie mit diesem Beispiel tun möchten. Zum Beispiel zum Berechnen von Momenten erscheint es einfach, die Abtastung aus Dichtemischungen zu verallgemeinern, indem zusätzlich jeder Punkt, der aus einer Komponente mit negativem Koeffizienten ausgewählt wurde, als "negativer" Punkt markiert und sein Beitrag in der Momentschätzung negativ gewichtet wird. Ebenso könnten Sie eine KDE mit solchen negativen Gewichten konstruieren, vorausgesetzt, Sie können die Möglichkeit akzeptieren, dass einige ihrer Werte negativ sind! (cc @ Xi'an)

whuber

Was wäre eine "genaue" Stichprobe einer Verteilung? Ob und wie Sie eine Mischung mit negativen Gewichten nutzen können, hängt wiederum davon ab, wie Sie die Probe verwenden möchten.

whuber

Dies beantwortet Ihre Frage nicht, aber Sie könnten daran interessiert sein, Informationen

Tim

Antworten:

Ich habe über diese Frage gerätselt, aber nie eine zufriedenstellende Lösung gefunden.

Eine mögliche Eigenschaft ist, dass wenn eine Dichte schreibt, wobei ist Dichte, so dass , Simulation von und Zurückweisen dieser Simulationen mit der Wahrscheinlichkeit Simulationen von liefert . Im aktuellen Fall ist die normalisierte Version der positiven Gewichtskomponenten und ist der Rest

f (x) = \frac{g (x) - ω h (x)}{1 - ω} ω > 0

$f(x)=\frac{g(x)-\omega h(x)}{1-\omega}\qquad \omega>0$

g

$g$

g (x) \geq ω h (x)

$g(x)\ge \omega h(x)$

g

$g$

ω h (x) / g (x)

$\omega h(x)/g(x)$

f

$f$

g

$g$

g (x) = \sum_{α_{i} > 0} α_{i} f_{i} (x) / \sum_{α_{i} > 0} α_{i}

$g(x)=\sum_{\alpha_i>0} \alpha_i f_i(x) \big/ \sum_{\alpha_i>0} \alpha_i$

ω h

$\omega h$

h (x) = \sum_{α_{i} < 0} α_{i} f_{i} (x) / \sum_{α_{i} < 0} α_{i}

$h(x)=\sum_{\alpha_i<0} \alpha_i f_i(x) \big/ \sum_{\alpha_i<0}\alpha_i$ Dies findet sich zwar in der Simulationsbibel von Devroye, Ungleichmäßige Erzeugung zufälliger Variablen , Abschnitt II.7.4, folgt jedoch aus einer einfachen Annahme-Ablehnungs-Argumentation.

Ein erster rechnerischer Nachteil dieses Ansatzes besteht darin, dass trotz der ersten Simulation aus einer ausgewählten Komponente die Summen in und für den Zurückweisungsschritt berechnet werden müssen. Wenn die Summen ohne geschlossene Form unendlich sind, kann die Methode "Akzeptieren / Ablehnen" nicht implementiert werden . $f_i$ $g$ $h$

Eine zweite Schwierigkeit besteht darin, dass die Ablehnungsrate ist, da beide Gewichtssummen in derselben Reihenfolge sindhat keine Obergrenze. Wenn die mit verknüpfte Reihe nicht absolut konvergiert, ist die Akzeptanzwahrscheinlichkeit tatsächlich Null! Und die Methode kann in dieser Situation nicht implementiert werden.

\sum_{α_{i} > 0} α_{i} = 1 - \sum_{α_{i} < 0} α_{i}

$\sum_{\alpha_i>0}\alpha_i = 1 - \sum_{\alpha_i<0}\alpha_i$

1 - ϱ^{accept} = \sum_{α_{i} < 0} | α_{i} | / \sum_{i} | α_{i} |

$1-\varrho^\text{accept}=\sum_{\alpha_i<0}|\alpha_i| \Big/ \sum_i |\alpha_i|$ $\alpha_i$

Wenn im Fall einer Mischungsdarstellung geschrieben werden kann als Die Komponente kann zuerst ausgewählt und dann die auf die Komponente angewendete Methode. Dies kann jedoch schwierig zu implementieren sein, da die Identifizierung von Paaren , die zu passen, aus der möglicherweise unendlichen Summe nicht unbedingt machbar ist. $f$

f (x) = \sum_{i = 1}^{\infty} α_{i} \frac{g_{i} (x) - ω_{i} h (x_{i})}{1 - ω_{i}} ω_{i} > 0

$f(x)=\sum_{i=1}^\infty \alpha_i \frac{g_i(x)-\omega_i h(x_i)}{1-\omega_i}\qquad \omega_i>0$

(g_{i}, h_{i})

$(g_i,h_i)$

g_{i} (x) - ω_{i} h (x_{i}) > 0

$g_i(x)-\omega_i h(x_i)>0$

Ich denke, eine effizientere Auflösung könnte von der Seriendarstellung selbst kommen. Devroye, Uneinheitliche Erzeugung zufälliger Variablen , Abschnitt IV.5, enthält eine Vielzahl von Serienmethoden. Wie zum Beispiel der folgende Algorithmus für eine alternative Seriendarstellung des Ziels wenn ' s konvergieren mit gegen Null und ist eine Dichte:

f (x) = κ h (x) {1 - a_{1} (x) + a_{2} (x) - \dots}

$f(x)=\kappa h(x)\{1-a_1(x)+a_2(x)-\cdots\}$

a_{i} (x)

$a_i(x)$

n

$n$

h

$h$

Das Problem wurde kürzlich im Zusammenhang mit dem Debiasing von voreingenommenen Schätzern für MCMC betrachtet, wie beispielsweise beim Glynn-Rhee-Ansatz . Und der russische Roulette- Schätzer (mit einem Zusammenhang mit dem Bernoulli-Fabrikproblem). Und die unvoreingenommene MCMC-Methodik . Aber es gibt kein Entkommen vor dem Vorzeichenproblem ... Dies macht seine Verwendung bei der Schätzung von Dichten wie bei pseudo-marginalen Methoden schwierig.

Bei weiterem Denken, ist meine Schlussfolgerung , dass es keine generische Methode ist eine tatsächliche Simulation von dieser zu erzeugen Serie [anstatten Mischung , die eine falsche Bezeichnung erweist], ohne die Einführung weitere> Struktur mit den Elementen der Serie, wie die in der obige Algorithmus aus Devroyes Bibel . Da die meisten (?) Dichten eine Serienerweiterung der oben genannten Art ermöglichen, würde dies ansonsten die Existenz einer Art universeller Simulationsmaschine implizieren ...

Xi'an
quelle

Vielen Dank! Ich schätze auch die zusätzlichen Referenzen.

πr8

Zusätzlicher Dank für die sehr gründliche Antwort und Referenzen. Ich bin froh, diese Antwort zu akzeptieren, da es gelingt, exakte Stichproben aus in endlicher Zeit zu generieren . Ich werde wahrscheinlich bis zu einem gewissen Grad weiter über das Problem nachdenken. Die einzige zusätzliche Idee, die ich hatte und die vielversprechend erscheint, besteht darin, die Abtastung von als Abtastung , abhängig von , und dass es möglicherweise geometrische gibt Einsicht, die für diese Charakterisierung nützlich ist (ich denke wie ein Slice-Sampler auf ). Prost!

p

$p$

p = λ g - μ h

$p = \lambda g - \mu h$

X \sim g

$X \sim g$

λ g ⩾ μ h

$\lambda g \geqslant \mu h$

{(x, y) : μ h (x) < y < λ g (x)}

$\{(x,y): \mu h (x) < y < \lambda g(x) \}$

Ich habe den bedingten Sampler ziemlich schlecht erklärt; Die satzbasierte Charakterisierung ist (meiner Meinung nach) etwas klarer. Mein entscheidender Punkt ist, dass, wenn Sie gleichmäßig aus der zweidimensionalen Menge in der letzten Zeile abtasten können , die Koordinate die richtige Verteilung hat. Ob diese Charakterisierung für längere summenbasierte unsachgemäße Gemische nützlich sein kann, bleibt abzuwarten.

(x, y)

$(x,y)$

x

$x$

πr8

Ich habe auch an einen Slice-Sampler gedacht, aber dies ist im Sinne einer Simulation nicht "genau".

Xi'an

Ich habe den Entwurf einer Idee, die funktionieren könnte. Es ist nicht genau , aber hoffentlich asymptotisch genau. Um daraus eine wirklich strenge Methode zu machen, bei der die Annäherung kontrolliert wird oder etwas daran bewiesen werden kann, ist wahrscheinlich viel Arbeit erforderlich.

Erstens können Sie, wie von Xi'an erwähnt, die positiven Gewichte einerseits und die negativen Gewichte andererseits gruppieren, so dass das Problem schließlich nur zwei Verteilungen und : $g$ $h$

p = λ g - μ h

$p=\lambda g - \mu h$

mit . Beachten Sie, dass Sie . $\lambda-\mu=1$ $\lambda\geq 1$

Meine Idee ist die folgende. Sie möchten Beispiel Beobachtungen von . Machen: $N$ $p$

Probieren Sie Werte aus und speichern Sie sie in einer Liste $\lambda N$ $g$
Entfernen Sie für jeden von abgetasteten -Wert den nächsten (verbleibenden) Nachbarn aus der Liste. $\mu N$ $h$

Am Ende erhalten Sie Punkte. Es muss nicht genau der nächste Nachbar sein, sondern nur ein Punkt, der "nah genug" ist. Der erste Schritt ist wie das Erzeugen von Materie. Der zweite Schritt ist wie die Erzeugung von Antimaterie und deren Kollision und Aufhebung mit Materie. Diese Methode ist nicht genau, aber ich glaube, unter bestimmten Bedingungen ist sie für großes asymptotisch genau (um sie für kleines fast genau zu machen, müssen Sie zuerst ein großes und dann einen kleinen zufälligen Teil der endgültigen Liste nehmen). . Ich gebe ein sehr informelles Argument, das eher eine Erklärung als ein Beweis ist. $(\lambda-\mu)N=N$ $N$ $n$ $N$

Betrachten Sie im Beobachtungsraum und ein kleines Volumen um mit Lebesgue-Volumen . Nach dem Abtasten von beträgt die Anzahl der Elemente in der Liste, die sich ebenfalls in befinden, ungefähr . Nach dem zweiten Schritt wird ungefähr daraus entfernt, und Sie haben ungefähr die gewünschte Anzahl . Dazu müssen Sie davon ausgehen, dass die Anzahl der Punkte im Volumen ausreichend groß ist. $x$ $v$ $x$ $\epsilon$ $g$ $v$ $\lambda Ng(x)\epsilon$ $\mu Nh(x)\epsilon$ $Np(x)\epsilon$

Es ist sehr unwahrscheinlich, dass dieses Verfahren einer großen Dimension oder einigen Pathologien von und widersteht, es kann jedoch in einer kleinen Dimension und ausreichend glatten, "ausreichend gleichmäßigen" Verteilungen arbeiten. $g$ $h$

Hinweis zu einer genauen Methode:

Ich habe dies zuerst für diskrete Verteilungen gedacht, und in diesem Fall ist die Methode eindeutig nicht genau, da sie Stichproben mit der Wahrscheinlichkeit 0 erzeugen kann. Ich habe die starke Intuition, dass eine genaue Methode mit endlicher Verarbeitungszeit nicht möglich ist und dass dies der Fall ist Unmöglichkeit konnte zumindest für diskrete Verteilungen nachgewiesen werden. Die Regel des Spiels ist, dass Sie nur exakte "Orakel" -Sampler für und aber und als Funktionen von . Der Einfachheit halber beschränken Sie sich auf Bernoulli-Verteilungen. Die Nichtexistenz einer exakten Methode hängt mit der Bernoulli-Factory- Theorie zusammen: Wenn Sie aus einem eine -Münze erstellen könnten $g$ $h$ $g$ $h$ $x$ $(\lambda p - \mu q)$ $p$ -coin und eine -coin, dann könnten Sie eine -coin aus einer -coin erstellen, von der bekannt ist, dass sie für unmöglich ist . $q$ $\lambda p$ $p$ $\lambda>1$

Benoit Sanchez
quelle

Ich dachte darüber nach, lehnte es jedoch ab, weil meine anfänglichen Bemühungen, zu demonstrieren, dass es funktionieren könnte, zu der Erkenntnis führten, dass es bestenfalls eine Annäherung und möglicherweise eine schlechte sein wird. Ja, asymptotisch könnte es funktionieren, aber es wird die Anforderung des OP nach "exakten" Stichproben aus der Verteilung nicht erfüllen.

whuber

Die Effizienz dieser Methode liegt genau in der gleichen Größenordnung wie die exakte Annahme-Zurückweisungs-Methode.

Xi'an

Einverstanden. Sie sind jedoch ganz anders. Die Accept-Reject-Methode muss und als Funktionen von berechnen . Ich konzentrierte mich darauf, nur Sampling von und als "Orakel" -Sampler zu verwenden, wie in einer echten Mischung. Je mehr ich darüber nachdenke, desto mehr bin ich davon überzeugt, dass eine exakte Methode, die auf der Probenahme von Orakeln basiert, nicht existieren kann.

g

$g$

h

$h$

x

$x$

g

$g$

h

$h$

Benoit Sanchez

Ich denke , das ist grundsätzlich richtig, aber es können nützliche Klassen von Sonderfällen, in denen eine solche genaue Methode tut exist. Dies liegt daran, dass (1) in einigen Fällen die Berechnung von einfach ist und (2) Sie nicht sowohl als auch berechnen müssen - Sie müssen nur dieses Verhältnis berechnen.

g / (g + h)

$g/(g+h)$

g

$g$

h

$h$

whuber

@ BenoitSanchez Vielen Dank für Ihre ausführliche Antwort; Ich schätze besonders die Kommentare am Ende über die (mögliche) Unmöglichkeit der Genauigkeit. Ich bin in der Vergangenheit auf Bernoulli-Fabriken gestoßen und fand sie ziemlich herausfordernd. Ich werde versuchen, das Thema erneut zu betrachten und zu prüfen, ob es Erkenntnisse liefert.