Importance Sampling
Importance Sampling (im Deutschen manchmal auch Stichprobenentnahme nach Wichtigkeit, oder Stichprobenziehung nach Wichtigkeit[1] 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.
Motivation
[Bearbeiten | Quelltext bearbeiten]Monte-Carlo-Simulationen werden oft benutzt, um den Erwartungswert
einer reellen Zufallsvariablen zu berechnen, wobei die Wahrscheinlichkeitsverteilung der Zufallsvariablen und die Funktion bekannt sind. Die Zufallsvariable nimmt Werte in der Ergebnismenge an. Für eine Realisierung der Zufallsvariablen ist eine Realisierung der Zufallsvariablen .
Im diskreten Fall ist eine abzählbare Menge und die Wahrscheinlichkeitsverteilung von ist durch die Wahrscheinlichkeitsfunktion mit gegeben. Im stetigen Fall ist typischerweise ein -dimensionales Intervall und die Wahrscheinlichkeitsverteilung von ist durch eine Wahrscheinlichkeitsdichte mit der Eigenschaft gegeben. Für eine Realisierung der Zufallsvariablen ist eine Realisierung der Zufallsvariablen . Da die Ergebnismenge im Allgemeinen hochdimensional sein kann, kann die Berechnung des Erwartungswertes sehr schwierig oder zeitaufwendig sein, so dass dann eine Approximation durch Monte-Carlo-Simulation sinnvoll ist.
Bei Anwendungen im Bereich der Physik ist z. B. die Ergebnismenge der Phasenraum der Teilchen im System, die Zufallsvariablen und sind interessierende Größen und ist proportional zum Boltzmann-Faktor.
Statt den Erwartungswert analytisch zu berechnen oder numerisch zu approximieren, berechnet man im einfachsten Fall den Monte-Carlo-Schätzwert
für den Erwartungswert , wobei die Zufallszahlen Realisierungen von stochastisch unabhängigen und identisch verteilten Zufallsvariablen mit der Verteilung von sind. In statistischer Terminologie ist eine einfache Zufallsstichprobe mit Stichprobenumfang . Der Schätzwert ist eine Realisierung des zugehörigen Schätzers
- ,
der eine Zufallsvariable ist, die nach dem starken Gesetz der großen Zahlen mit Wahrscheinlichkeit Eins gegen den zu schätzenden Erwartungswert konvergiert. Da die Berechnung durch Monte-Carlo-Simulation eine statistische Schätzung ist, gibt es einen Schätzfehler der z. B. durch die Varianz des Schätzer beschrieben werden kann. Beim Importance Sampling wird die zuvor beschriebene einfache Monte-Carlo-Schätzmethode mit dem Ziel modifiziert, die Varianz des Schätzer zu reduzieren bzw. die Genauigkeit bei gegebenem Stichprobenumfang zu erhöhen.
Grundidee des Importance-Sampling
[Bearbeiten | Quelltext bearbeiten]Der Standardansatz zur Approximation des Erwartungswertes einer Zufallsvariablen durch Monte-Carlo-Simulation besteht darin, Zufallszahlen als Realisierungen stochastisch unabhängiger und identisch verteilter Zufallsvariablen mit der Wahrscheinlichkeitsverteilung von zu erzeugen und dann den gesuchten Erwartungswert durch den Monte-Carlo-Schätzwert
zu approximieren.
Beim Importance-Sampling werden stattdessen Zufallszahlen aus einer modifizierten Wahrscheinlichkeitsverteilung mit dem Ziel verwendet, durch eine Varianzreduktion zu rechentechnisch effizienteren Berechnung zu kommen.
Für eine diskrete Zufallsvariable , die Werte mit den Wahrscheinlichkeiten annimmt, ist die Grundlage des Importance-Sampling eine Umdeutung des Erwartungswertes
Dabei ist eine diskrete Zufallsvariable, die Werte mit den positiven Wahrscheinlichkeiten annimmt. Die Erzeugung von Zufallen aus der Verteilung von führt dann zum Monte-Carlo-Schätzwert
der als Importance-Sampling-Schätzwert
für interpretiert wird. Der Umweg über die Erzeugung aus Zufallszahlen mit einer anderen Verteilung kann lohnend sein, da durch eine geeignete Wahl der Verteilung von ein Importance-Sampling-Schätzer eine erhebliche kleinere Varianz als der gewöhnliche Monte-Carlo-Schätzer haben kann.
Beispiel
[Bearbeiten | Quelltext bearbeiten]Die Grundidee des Importance-Sampling sei an einem einfachen Beispiel mit veranschaulicht. Die Zufallsvariable mit der Wahrscheinlichkeitsfunktion
hat den Erwartungswert und die Varianz Die Wahrscheinlichkeitsfunktion sei als bekannt vorausgesetzt. Der Erwartungswert sei als unbekannt angenommen und soll durch Simulation bestimmt werden. Der gewöhnliche Monte-Carlo-Schätzer
basierend auf Zufallszahlen aus der Verteilung von hat dann den Erwartungswert Null und die Varianz
Für das Importance-Sampling wird der Erwartungswert als
geschrieben und die positiven werden so gewählt, dass sie sich zu Eins addieren und damit als Wahrscheinlichkeiten für eine Zufallsvariable interpretiert werden können. Der Importance-Sampling-Schätzer
der als Funktion der Zufallsvariablen selbst eine Zufallsvariable ist, hat in diesem Beispiel den Erwartungswert Null und die Varianz
Die Varianz des Schätzers hängt also von den gewählten Wahrscheinlichkeiten ab und kann bei geeigneter Wahl erheblich kleiner als die Varianz des gewöhnlichen Monte-Carlo-Schätzers sein. Z. B. ergibt sich für die Wahl für die Varianz
Durch den Importance-Sampling-Schätzer mit der Verteilung von lässt sich also der Erwartungswert mit kleinerer Varianz als durch den gewöhnlichen Monte-Carlo-Schätzer bestimmen. Damit erhält man bei gleicher Anzahl von erzeugten Zufallszahlen eine größere Genauigkeit.
Simple Sampling
[Bearbeiten | Quelltext bearbeiten]Im einfachsten Fall (einfache Stichprobenentnahme, englisch simple sampling) werden aus dem Ergebnisraum gleichverteilt zufällig Zustände für die Stichprobe ausgewählt. Dann ergibt sich für den geschätzten Mittelwert:
wobei die Summation über die zufälligen Realisierungen in der Stichprobe läuft. ist die ursprüngliche Wahrscheinlichkeit(sdichte) für die – durch Simple Sampling erzeugte – Realisierung . ist eine Funktionsauswertung
Definition Importance Sampling
[Bearbeiten | Quelltext bearbeiten]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 auch wie folgt ausgedrückt werden:
Werden Realisierungen mit der Wahrscheinlichkeit 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
- für
Die Wahrscheinlichkeitsdichte wird auch als "biased distribution", "proposal distribution" oder "sample distribution" bezeichnet. Da die Stichprobe aus der Verteilung gezogen wurde, müssen die Erwartungswerte durch entsprechendes Reweighting mit errechnet werden (siehe Formel) und nicht einfach als arithmetischen Mittel. Dieses Reweighting wird beispielsweise beim "Temperature Reweighting" von Monte-Carlo Simulationen molekularer Systeme genutzt, bei denen Aussagen über angrenzende Temperaturen gemacht werden sollen.[2]
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.
Schlussfolgerungen
[Bearbeiten | Quelltext bearbeiten]Ziehen von Stichproben ohne, dass die Normierungskonstante einer Verteilung berechnet werden kann
[Bearbeiten | Quelltext bearbeiten]Werden die Realisierungen mit einer Wahrscheinlichkeit proportional zu vorgeschlagen (das ist gerade die Metropoliswahl), so ergibt sich (wie beim Gesetz der großen Zahlen)
Gerade, dass hier nur die Proportionalität erforderlich ist, ist ein Vorteil der Methode, da die Zustandssumme nicht ausgewertet werden muss.
Simple Sampling
[Bearbeiten | Quelltext bearbeiten]Simple sampling erhält man für der Fall, dass die Vorschlagsdichte konstant ist: .
Wang-Landau Sampling
[Bearbeiten | Quelltext bearbeiten]Das multikanonische Ensemble kann mit dem Wang-Landau-Algorithmus simuliert werden, indem die Wahl getroffen wird (wobei die Zustandsdichte der Energie ist, welche dem Zustand zugeordnet ist).
Literatur
[Bearbeiten | Quelltext bearbeiten]- 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.
- Surya T. Tokdar, Robert E. Kass: Importance sampling: a review. In: WIREs Computational Statistics. Band 2, Nr. 1, 2010, S. 54–60, doi:10.1002/wics.56.
- 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.
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ International Statistical Institute: Glossary of statistical terms.
- ↑ Bachmann, M. (2014). Thermodynamics and Statistical Mechanics of Macromolecular Systems. Vereinigtes Königreich: Cambridge University Press. Seiten 104, 105 Google books