Importance Sampling

Der Standardansatz zur Approximation des Erwartungswertes ${\displaystyle \operatorname {E} [X]}$ einer Zufallsvariablen ${\displaystyle X}$ durch Monte-Carlo-Simulation besteht darin, Zufallszahlen ${\displaystyle x_{1},\dots ,x_{n}}$ als Realisierungen stochastisch unabhängiger und identisch verteilter Zufallsvariablen ${\displaystyle X_{1},\dots ,X_{n}}$ mit der Wahrscheinlichkeitsverteilung von ${\displaystyle X}$ zu erzeugen und dann den gesuchten Erwartungswert ${\displaystyle \operatorname {E} [X]}$ durch den Monte-Carlo-Schätzwert

${\displaystyle \operatorname {\hat {E}} _{\mathrm {MC} }[X]={\frac {1}{n}}\sum _{i=1}^{n}x_{i}}$

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 ${\displaystyle X}$, die Werte ${\displaystyle x\in \Omega }$ mit den Wahrscheinlichkeiten ${\displaystyle p(x)=P(X=x)}$ annimmt, ist die Grundlage des Importance-Sampling eine Umdeutung des Erwartungswertes

${\displaystyle \operatorname {E} [X]=\sum _{x\in \Omega }xp(x)=\sum _{x\in \Omega }{\frac {xp(x)}{w(x)}}w(x)=\operatorname {E} \left[{\frac {Yp(Y)}{w(Y)}}\right]\;.}$

Dabei ist ${\displaystyle Y}$ eine diskrete Zufallsvariable, die Werte ${\displaystyle y\in \Omega }$ mit den positiven Wahrscheinlichkeiten ${\displaystyle w(y)=P(Y=y)}$ annimmt. Die Erzeugung von ${\displaystyle n}$ Zufallen ${\displaystyle y_{1},\dots ,y_{n}}$ aus der Verteilung von ${\displaystyle Y}$ führt dann zum Monte-Carlo-Schätzwert

${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}{\frac {y_{i}p(y_{i})}{w(y_{i})}}\approx \operatorname {E} \left[{\frac {Yp(Y)}{w(Y)}}\right]\;,}$

der als Importance-Sampling-Schätzwert

${\displaystyle \operatorname {\hat {E}} _{\mathrm {IS} }[X]={\frac {1}{n}}\sum _{i=1}^{n}{\frac {y_{i}p(y_{i})}{w(y_{i})}}}$

für ${\displaystyle \operatorname {E} [X]}$ interpretiert wird. Der Umweg über die Erzeugung aus Zufallszahlen mit einer anderen Verteilung kann lohnend sein, da durch eine geeignete Wahl der Verteilung von ${\displaystyle Y}$ 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 ${\displaystyle \Omega =\{-10,0,10\}}$ veranschaulicht. Die Zufallsvariable ${\displaystyle X}$ mit der Wahrscheinlichkeitsfunktion

${\displaystyle p(x)=P(X=x)={\begin{cases}{\frac {1}{10}}&{\text{für }}x\in \{-10,10\}\\{\frac {8}{10}}&{\text{für }}x=0\end{cases}}}$

hat den Erwartungswert ${\displaystyle \operatorname {E} [X]=0}$ und die Varianz ${\displaystyle \mathrm {Var} [X]=20.}$ Die Wahrscheinlichkeitsfunktion ${\displaystyle p}$ sei als bekannt vorausgesetzt. Der Erwartungswert sei als unbekannt angenommen und soll durch Simulation bestimmt werden. Der gewöhnliche Monte-Carlo-Schätzer

${\displaystyle \operatorname {\tilde {E}} _{\mathrm {MC} }[X]={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$

basierend auf ${\displaystyle n}$ Zufallszahlen aus der Verteilung von ${\displaystyle X}$ hat dann den Erwartungswert Null und die Varianz

${\displaystyle \mathrm {Var} [{\tilde {E}}_{\mathrm {MC} }[X]]={\frac {\mathrm {Var} [X]}{n}}={\frac {20}{n}}\;.}$

Für das Importance-Sampling wird der Erwartungswert ${\displaystyle \operatorname {E} [X]}$ als

${\displaystyle \operatorname {E} [X]=\sum _{x\in \Omega }xp(x)=\sum _{x\in \Omega }{\frac {xp(x)}{w(x)}}{w(x)}=\operatorname {E} \left[{\frac {Yp(Y)}{w(Y)}}\right]}$

geschrieben und die positiven ${\displaystyle w(x)}$ werden so gewählt, dass sie sich zu Eins addieren und damit als Wahrscheinlichkeiten ${\displaystyle P(Y=y)=w(y)}$ für eine Zufallsvariable ${\displaystyle Y}$ interpretiert werden können. Der Importance-Sampling-Schätzer

${\displaystyle \operatorname {\tilde {E}} _{\mathrm {IS} }[X]={\frac {1}{n}}\sum _{i=1}^{n}{\frac {Y_{i}p(Y_{i})}{w(Y_{i})}},}$

der als Funktion der Zufallsvariablen ${\displaystyle Y_{1},\dots ,Y_{n}}$ selbst eine Zufallsvariable ist, hat in diesem Beispiel den Erwartungswert Null und die Varianz

${\displaystyle \mathrm {Var} [\operatorname {\hat {E}} _{\mathrm {IS} }[X]]={\frac {1}{n}}\left({\frac {1}{w(-10)}}+{\frac {1}{w(10)}}\right)}$

Die Varianz des Schätzers ${\displaystyle \operatorname {\tilde {E}} _{\mathrm {IS} }[X]}$ hängt also von den gewählten Wahrscheinlichkeiten ${\displaystyle w(y)}$ 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 ${\displaystyle w(y)=1/3}$ für ${\displaystyle y\in \Omega }$ die Varianz

${\displaystyle \mathrm {Var} [\operatorname {\tilde {E}} _{\mathrm {IS} }[X]]={\frac {6}{n}}<\mathrm {Var} [\operatorname {\tilde {E}} _{\mathrm {MC} }[X]]={\frac {20}{n}}\;.}$

Durch den Importance-Sampling-Schätzer mit der Verteilung von ${\displaystyle Y}$ lässt sich also der Erwartungswert ${\displaystyle \mathbb {E} [X]}$ mit kleinerer Varianz als durch den gewöhnlichen Monte-Carlo-Schätzer bestimmen. Damit erhält man bei gleicher Anzahl ${\displaystyle n}$ von erzeugten Zufallszahlen eine größerer Genauigkeit.

Im einfachsten Fall (einfache Stichprobenentnahme, englisch simple sampling) werden aus dem Ergebnisraum gleichverteilt zufällig Zustände ${\displaystyle Y_{i}\sim {\text{uniform}}(\Omega )}$ für die Stichprobe ${\displaystyle S}$ ausgewählt. Dann ergibt sich für den geschätzten Mittelwert:

${\displaystyle \operatorname {\hat {E}} _{X}[f(X)]={\frac {\sum _{y\in S}p(y)\,f(y)}{\sum _{y\in S}p(y)}},}$

wobei die Summation über die zufälligen Realisierungen ${\displaystyle y_{i}\sim Y_{i}}$in der Stichprobe läuft. ${\displaystyle p(y)}$ ist die ursprüngliche Wahrscheinlichkeit(sdichte) für die – durch Simple Sampling erzeugte – Realisierung ${\displaystyle y}$. ${\displaystyle f(y)}$ ist eine Funktionsauswertung

Werden die Realisierungen ${\displaystyle y}$ mit einer Wahrscheinlichkeit ${\displaystyle W(y)}$ proportional zu ${\displaystyle p(y)}$ vorgeschlagen (das ist gerade die Metropoliswahl), so ergibt sich (wie beim Gesetz der großen Zahlen)

${\displaystyle \operatorname {\hat {E}} _{X}[f(X)]={\frac {1}{N}}\sum _{y\in S'}f(y).}$

Gerade, dass hier nur die Proportionalität ${\displaystyle W(y)\propto p(y)}$ erforderlich ist, ist ein Vorteil der Methode, da die Zustandssumme nicht ausgewertet werden muss.

Simple sampling erhält man für der Fall, dass die Vorschlagsdichte konstant ist: ${\displaystyle W(y)={\text{const}}}$.

Das multikanonische Ensemble kann mit dem Wang-Landau-Algortithmus simuliert werden, indem die Wahl ${\displaystyle W(x)=1/D(\operatorname {E} (x))}$ getroffen wird (wobei ${\displaystyle D(\operatorname {E} (x))}$ die Zustandsdichte der Energie ist, welche dem Zustand ${\displaystyle x}$ zugeordnet ist).