Importance Sampling

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Importance Sampling ist ein Begriff aus dem Bereich der stochastischen Prozesse, der die Technik zur Erzeugung von Stichproben anhand einer Wahrscheinlichkeitsverteilung beschreibt. Importance Sampling ist eine von mehreren Möglichkeiten zur Varianzreduktion, also zur Steigerung der Effizienz von Monte-Carlo-Simulationen.

Beispiel[Bearbeiten]

Monte-Carlo-Simulationen werden oft benutzt, um Erwartungswerte einer Größe \mathcal{A} (hier mit \left\langle \mathcal{A} \right\rangle bezeichnet, sonst – insbesondere in der Mathematik – oft als \operatorname{E}(\mathcal{A}) dargestellt),

\left\langle \mathcal{A} \right\rangle  = \sum_{x \in \Omega} P(x) \, \mathcal{A}(x),

zu berechnen, wobei P(x) ein normiertes statistisches Gewicht wie beispielsweise ein Boltzmanngewicht ist. \mathcal{A}(x) ist der Wert der Größe \mathcal{A} im Zustand x. Die Summation (Integration) verläuft dabei über einen Raum \Omega, z. B. den Phasenraum der Teilchen im System. Da dieser Phasenraum im Allgemeinen sehr hochdimensional ist, kann die Summation, bzw. das Integral darüber im Allgemeinen nicht berechnet werden. Statt den Erwartungswert tatsächlich zu berechnen, berechnet man einen Schätzer \overline{\mathcal{A}} mithilfe einer Zufallsstichprobe S, die den Umfang N hat.

Für den einfachsten Fall (Simple Sampling) gleichverteilt zufällig ausgewählter Zustände ergibt sich für den Mittelwert:

\overline{\mathcal{A}} = \frac{\sum_{x \in S} P(x) \, \mathcal{A}(x)}{\sum_{x \in S} P(x)},

wobei P(x) (beispielsweise proportional zu \exp(-\beta E)), sowie \mathcal{A}(x) nach der zufälligen Wahl von x berechnet werden. Für eine unendlich große Stichprobe entspricht der Schätzer dem Mittelwert:

\lim_{N \to \infty} \overline{\mathcal{A}} = \left\langle \mathcal{A} \right\rangle.

Diese Methode ist meistens nicht sehr effektiv, da häufig nur wenige relevante Zustände in die Mittelwertbildung eingehen. Um dieses Problem zu umgehen und so die Standardabweichung des gemessenen Mittelwertes bei gleicher Anzahl von Stichproben zu reduzieren, versucht man Zustände mit einem größeren Gewicht häufiger in die Mittelwertbildung eingehen zu lassen als Zustände mit einem geringeren Gewicht.

Werden Zustände mit einer Wahrscheinlichkeit W(x) erzeugt (Importance Sampling), so berechnet sich der Mittelwert zu

\overline{\mathcal{A}} = \frac{\sum_{x \in S} P(x) \, \mathcal{A}(x) \,/\,  W(x)}{\sum_{x \in S} P(x) \,/\, W(x)}.

Werden die Systemzustände z.B. willkürlich mit der Wahrscheinlichkeit proportional zu P(x) erzeugt (das ist gerade die Metropoliswahl), so ergibt sich

\overline{\mathcal{A}} = \frac{1}{N}\sum_{x \in S} \mathcal{A}(x).

Gerade dass hier nur die Proportionalität W(x) \propto P(x) erforderlich ist, ist ein Vorteil der Methode.

Um Importance Sampling in der Praxis zu erreichen, geht man von einer Startkonfiguration aus und erzeugt mithilfe des Metropolis-Algorithmus eine Markow-Kette aus Systemzuständen.

Neben der Metropoliswahl für die Sampling-Wahrscheinlichkeit W(x) gibt es weitere Möglichkeiten. Z.B. kann mit der Wahl W(x)=1/D(E(x)), wobei D(E(x)) die Zustandsdichte der Energie ist, welche dem Zustand x zugeordnet ist, das Multikanonische Ensemble simuliert werden.

Literatur[Bearbeiten]

  •  W.K. Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications. In: Biometrika. 57, 1970, S. 97-109.
  •  R. Srinivasan: Importance sampling - Applications in communications and detection. Springer-Verlag, Berlin 2002, ISBN 978-3-540-43420-7.
  • Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6, Abschnitt 5.4, S. 155-165.