Importance Sampling

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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.

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 den 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).

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. International Statistical Institute: Glossary of statistical terms.
  2. Bachmann, M. (2014). Thermodynamics and Statistical Mechanics of Macromolecular Systems. Vereinigtes Königreich: Cambridge University Press. Seiten 104, 105 Google books