Importance Sampling

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! (Artikel eintragen)

Importance Sampling (im Deutschen manchmal auch Stichprobenentnahme nach Wichtigkeit, oder Stichprobenziehung nach Wichtigkeit genannt) ist ein Begriff aus der Statistik, 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.

Definition

Der Importance-Sampling-Schätzer des Mittelwertes einer Zufallsvariablen $X\sim P$ ist gegeben durch: ${\widehat {\mathbf {E} }}_{n}[X;P]={\frac {1}{n}}\sum _{i=1}^{n}x_{i}\quad \mathrm {wobei} \;x_{i}\sim P(X)$.

Hintergrund

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 Boltzmann-Faktor ist. ${\mathcal {A}}(x)$ ist der Wert der Größe ${\mathcal {A}}$ im Zustand $x$. Die Summation (oder Integration) läuft dabei den Ergebnisraum $\Omega$, (z. B. den Phasenraum der Teilchen im System). Da dieser Ergebnisraum im Allgemeinen sehr hochdimensional ist, kann die Summe bzw. das Integral im Allgemeinen nicht berechnet werden. Statt den wahren Erwartungswert zu berechnen, berechnet man einen Schätzer ${\overline {\mathcal {A}}}$ mithilfe einer Zufallsstichprobe S, die den Umfang $N$ hat.

Simple Sampling

Für den einfachsten Fall (einfache Stichprobenentnahme, englisch simple sampling) gleichverteilt zufällig ausgewählter Zustände ergibt sich für den geschätzten Mittelwert:

${\overline {\mathcal {A}}}={\frac {\sum _{x\in S}P(x)\,{\mathcal {A}}(x)}{\sum _{x\in S}P(x)}},$

wobei die Summation über die zufälligen Realisierungen in der Stichprobe läuft, $P(x)$ die Wahrscheinlichkeit(sdichte) der Realisierung ist (beispielsweise proportional zu $\exp(-\beta E(x))$) sowie ${\mathcal {A}}(x)$. Für eine große Stichprobe nähert sich der Schätzer dem Mittelwert:

$\lim _{N\to \infty }{\overline {\mathcal {A}}}=\left\langle {\mathcal {A}}\right\rangle$

Importance Sampling

Die Methode des Simple Sampling ist meistens nicht sehr effizient, da oft nur wenige relevante Zustände in die Mittelwertbildung eingehen. Um dieses Problem zu umgehen und so die Standardabweichung des gemessenen Mittelwertes bei gleichem Stichprobenumfang 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: Der obigen Schätzer des Simple Sampling kann durch Erweitern mit $1=W(x)/W(x)$ auch wie folgt ausgedrückt werden:

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

Werden Realisierungen $x$ mit der Wahrscheinlichkeit $W(x)$ erzeugt (Stichprobenentnahme nach Wichtigkeit englisch importance sampling), wird also eine andere Stichprobe S' erzeugt, so berechnet sich der geschätzte Mittelwert in der Folge einfach mithilfe von

${\overline {\mathcal {A}}}={\frac {\sum _{x\in S'}P(x)/W(x){\mathcal {A}}(x)}{\sum _{x\in S'}P(x)\,/\,W(x)}}.$

Beispiel

Werden die Systemzustände z. B. willkürlich mit einer Wahrscheinlichkeit $W(x)$ 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 eine Stichprobenentnahme nach Wichtigkeit in der Praxis zu erreichen, geht man von einer Startkonfiguration aus und erzeugt mithilfe des Metropolisalgorithmus 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))$ diejenige Zustandsdichte der Energie ist, die dem Zustand $x$ zugeordnet ist, das multikanonische Ensemble simuliert werden.

Literatur

• W. K. Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications. In: Biometrika. Band 57, 1970, S. 97–109. 
• Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6, Abschnitt 5.4 Importance Sampling, S. 155–166, doi:10.1007/978-3-540-89141-3. 
• Christian P. Robert, George Casella: Monte Carlo Statistical Methods (= Springer Texts in Statistics). 2. Auflage. Springer, 2004, ISBN 0-387-21239-6, Kap. 3.3 Importance Sampling, S. 90–107, doi:10.1007/978-1-4757-4145-2. 
• R. Srinivasan: Importance sampling – Applications in communications and detection. Springer-Verlag, Berlin 2002, ISBN 978-3-540-43420-7. 
• Suojin Wang: Importance Sampling. In: Samuel Kotz et al. (Hrsg.): Encyclopedia of Statistical Sciences. 2. Auflage. Band 5. Wiley, New York 2006, ISBN 978-0-471-15044-2, S. 3347–3353, doi:10.1002/0471667196.