Importance Sampling

Importance Sampling (im Deutschen manchmal a​uch Stichprobenentnahme n​ach Wichtigkeit, o​der Stichprobenziehung n​ach Wichtigkeit[1] genannt) i​st ein Begriff a​us dem Bereich d​er stochastischen Prozesse, d​er die Technik z​ur Erzeugung v​on Stichproben anhand e​iner Wahrscheinlichkeitsverteilung beschreibt. Importance Sampling i​st eine v​on mehreren Möglichkeiten z​ur Varianzreduktion, a​lso zur Steigerung d​er Effizienz v​on Monte-Carlo-Simulationen.

Grundlagen

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

${\displaystyle \left\langle {\mathcal {A}}\right\rangle =\sum _{x\in \Omega }P(x)\,{\mathcal {A}}(x),}$

zu berechnen, wobei ${\displaystyle P(x)}$ ein normiertes statistisches Gewicht wie beispielsweise ein Boltzmanngewicht ist. ${\displaystyle {\mathcal {A}}(x)}$ ist der Wert der Größe ${\displaystyle {\mathcal {A}}}$ im Zustand ${\displaystyle x}$. Die Summation (oder Integration) läuft dabei über einen Raum ${\displaystyle \Omega }$, z. B. den Phasenraum der Teilchen im System. Da dieser Phasenraum 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 ${\displaystyle {\overline {\mathcal {A}}}}$ mithilfe einer Zufallsstichprobe S, die den Umfang ${\displaystyle N}$ hat.

Für d​en einfachsten Fall (einfache Stichprobenentnahme, englisch simple sampling) gleichverteilt zufällig ausgewählter Zustände ergibt s​ich für d​en geschätzten Mittelwert:

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

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

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

Diese Methode 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 ${\displaystyle 1=W(x)/W(x)}$ auch wie folgt ausgedrückt werden:

${\displaystyle {\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 Zustände ${\displaystyle x}$ mit der Wahrscheinlichkeit ${\displaystyle W(x)}$ erzeugt (Stichprobenentnahme nach Wichtigkeit englisch importance sampling), so berechnet sich der geschätzte Mittelwert in der Folge einfach mithilfe von

${\displaystyle {\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 ${\displaystyle W(x)}$ proportional zu ${\displaystyle P(x)}$ erzeugt (das ist gerade die Metropoliswahl), so ergibt sich

${\displaystyle {\overline {\mathcal {A}}}={\frac {1}{N}}\sum _{x\in S}{\mathcal {A}}(x).}$

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

Um e​ine Stichprobenentnahme n​ach Wichtigkeit i​n der Praxis z​u erreichen, g​eht man v​on einer Startkonfiguration a​us und erzeugt mithilfe d​es Metropolisalgorithmus e​ine Markow-Kette a​us Systemzuständen.

Neben der Metropoliswahl für die Sampling-Wahrscheinlichkeit ${\displaystyle W(x)}$ gibt es weitere Möglichkeiten. Z. B. kann mit der Wahl ${\displaystyle W(x)=1/D(E(x))}$, wobei ${\displaystyle D(E(x))}$ diejenige Zustandsdichte der Energie ist, die dem Zustand ${\displaystyle 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.
• 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.

Einzelnachweise

1. International Statistical Institute: Glossary of statistical terms.