Importance Sampling

04.10.2005, 12:25

Michael78

Auf diesen Beitrag antworten »

Importance Sampling

Hallo!

Ich habe immer wieder den Begriff Importance Sampling gelesen, kann aber nicht recht verstehen, was ich darüber gefunden habe.
Auf wikipedia (http://en.wikipedia.org/wiki/Importance_sampling) steht etwa, dass nicht aus einer Gleichverteilung gesampelt wird, sondern aus einer anderen Verteilung g(u), die - anderen Texten zufolge, die ich ergooglet habe - möglichst ähnlich zu sein hat der gesuchten Verteilung f(u).

Mir ist da mehreres nicht verständlich:
1.) Ist es nicht so, dass immer aus einer Gleichverteilung heraus Zufallszahlen generiert werden und die gezogenen Zufallszahlen anschließend umgewandelt werden in Zahlen einer anderen Verteilung?
Falls ja, verstehe ich nicht, wie man "direkt" aus einer Importance-Verteilung ziehen kann.
2.) Wenn die Verteilung g(u) ohnehin möglichst ähnlich sein soll der gesuchten Verteilung f(u), was bringt es dann, nicht gleich aus dieser gesuchten Verteilung zu ziehen?
3.) So weit ich auf dem wikipedia-Link sah, wird dann f(u)/g(u) * g(u) gerechnet.
D.h. ich rechne dann das f(u) auch aus, ist nicht noch aufwendiger?
4.) Manchmal steht auch was da, dass die Importance-Samples gewichtet werden müssen, aber das ist mir nicht klar.

Vielen Dank für eure Hilfe!!

04.10.2005, 13:19

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Michael78
1.) Ist es nicht so, dass immer aus einer Gleichverteilung heraus Zufallszahlen generiert werden und die gezogenen Zufallszahlen anschließend umgewandelt werden in Zahlen einer anderen Verteilung?
Falls ja, verstehe ich nicht, wie man "direkt" aus einer Importance-Verteilung ziehen kann.

Du spielst hier vermutlich auf die Inversionsmethode, d.h. $\begin{eqnarray*} F_X^{-1}(U) \end{eqnarray*}$ mit $\begin{eqnarray*} U\sim\mathrm{Glm}[0,1] \end{eqnarray*}$ an. Wenn dein $\begin{eqnarray*} F_X^{-1} \end{eqnarray*}$ einfach zu berechnen ist, dann ist das durchaus OK, und sicher auch die beste Wahl.

Aber wenn nicht, was dann? Versuch das z.B. mal bei der Standardnormalverteilung...

Zitat:

Original von Michael78
2.) Wenn die Verteilung g(u) ohnehin möglichst ähnlich sein soll der gesuchten Verteilung f(u), was bringt es dann, nicht gleich aus dieser gesuchten Verteilung zu ziehen?

Siehe Antwort zu 1.): g wird so gewählt, dass es sich leicht direkt simulieren lässt, z.B. eben mit der Inversionsmethode, während das bei f vielleicht eben nicht möglich ist.

04.10.2005, 13:35

Michael78

Auf diesen Beitrag antworten »

Ich dachte, gerade bei der StdNormal-Verteilung geht das so leicht, immerhin bauen alle MC-Simulationen im Risikomanagement auf diesem Schritt auf.

Wie sind dann also die Rechenschritte:
1) u ziehen
2) g(u) mittels Inversionsmethode
3) wie kommt man dann aber aufs f(u)?
4) und warum dann wiederum mit g(u) multiplizieren?
Ich meine f(u)/g(u) * g(u) ergibt doch einfach wieder f(u)

Hast Du da vielleicht ein Beispiel?

04.10.2005, 13:56

AD

Auf diesen Beitrag antworten »

Ich dachte, du hast http://en.wikipedia.org/wiki/Importance_sampling gelesen, da steht es doch klar und deutlich: Du berechnest

$\begin{eqnarray*} \frac{1}{N}\sum\limits_{i=1}^N ~ \frac{f(y_i)}{g(y_i)} \end{eqnarray*}$ ,

wobei $\begin{eqnarray*} y_i \sim g \end{eqnarray*}$ (W-Dichte!).

Beispiel - hmm, denk ich mir noch aus...

04.10.2005, 14:01

Michael78

Auf diesen Beitrag antworten »

Ja, aber auch das war mir unklar...
Okay, in g(y) folgt y einer g-Verteilung, aber in f(y) wohl eine f-Verteilung?

Und der Punkt ist eben, ich habe an anderer Stelle anderes gelesen.
z.B.: f(y)/g(y) * g(y)
Andere Quellen von mir bisher:
http://rkb.home.cern.ch/rkb/AN16pp/node132.html
Oder auch
http://www.tcm.phy.cam.ac.uk/~ajw29/thesis/node17.html

So weit ich verstanden habe, wählt man g(y) auch nicht deswegen aus, weil f(y) nicht berechenbar wäre, sondern um die Varianz zu verringern?

Danke für das Beispiel!
Ich bin derzeit leider gezwungen, enorm viel Mathe auf einmal mir anzuschauen und seh den Wald vor lauter Bäumen nicht unglücklich

unglücklich

04.10.2005, 14:12

AD

Auf diesen Beitrag antworten »

f(x) ist hier der Integrand, der hat mit gar keiner Verteilung was zu tun!!! Es ist so, dass bei der Berechnung von $\begin{eqnarray*} \int\limits_a^b ~ f(x) ~ \mathrm{d}x \end{eqnarray*}$ mittels Monte-Carlo-Methode im Intervall [a,b] gleichverteilte x Verwendung finden.

Also nochmal: f(x) ist hier keine Dichte.

Anzeige

04.10.2005, 14:23

Michael78

Auf diesen Beitrag antworten »

Hmm... ich fürchte, ich brauch ein wirklich detailliertes Beispiel.
unglücklich

unglücklich

04.10.2005, 16:29

AD

Auf diesen Beitrag antworten »

Angenommen, du willst $\begin{eqnarray*} I:=\int\limits_0^{\infty} ~ \frac{\sin(x)}{x} ~ \mathrm{d}x \end{eqnarray*}$ bestimmen.

Nach partieller Integration ist $\begin{eqnarray*} I=\bigg[\frac{1-\cos(x)}{x}\bigg]_{x=0}^{\infty}-\int\limits_0^{\infty} ~ \frac{1-\cos(x)}{x^2} ~ \mathrm{d}x = -I_1 \end{eqnarray*}$ mit $\begin{eqnarray*} I_1:=\int\limits_0^{\infty} ~ \frac{1-\cos(x)}{x^2} ~ \mathrm{d}x \end{eqnarray*}$ .

Um letzteres Integral durch Monte-Carlo berechnen zu können, kannst du nun gemäß

$\begin{eqnarray*} g(x)= \begin{cases} \displaystyle\frac{1}{2} &\;\mbox{für}\;0\leq x\leq 1\\ \displaystyle\frac{1}{2x^2} & \;\mbox{für}\; x>1 \end{cases} \end{eqnarray*}$

sampeln. (Die Idee dahinter ist, dass $\begin{eqnarray*} 1-\cos(x) \end{eqnarray*}$ ja beschränkt ist, also $\begin{eqnarray*} \frac{1}{x^2} \end{eqnarray*}$ maßgeblich die Größenordnung des Integranden
für große $\begin{eqnarray*} x \end{eqnarray*}$ beschreibt.) Dann ist nämlich wegen

$\begin{eqnarray*} G(x) := \int\limits_0^x ~ g(t) ~ \mathrm{d}t = \begin{cases} \displaystyle\frac{x}{2} &\;\mbox{für}\;0\leq x\leq 1\\ 1-\displaystyle\frac{1}{2x} & \;\mbox{für}\; x>1 \end{cases} \end{eqnarray*}$

die Funktion $\begin{eqnarray*} g \end{eqnarray*}$ tatsächlich eine Dichte auf den positiven reellen Zahlen. In der Simulation hast du nun [0,1]-gleichverteilte Zufallsgrößen $\begin{eqnarray*} u_1,\ldots,u_N \end{eqnarray*}$ und erzeugst daraus die $\begin{eqnarray*} g \end{eqnarray*}$ -verteilten $\begin{eqnarray*} x_1,\ldots,x_N \end{eqnarray*}$ über die Inversionsmethode $\begin{eqnarray*} x_i=G^{-1}(u_i) \end{eqnarray*}$ , wobei ja

$\begin{eqnarray*} G^{-1}(u) = \begin{cases} 2u &\;\mbox{für}\;0\leq u\leq \displaystyle\frac{1}{2}\\ \displaystyle\frac{1}{2(1-u)} & \;\mbox{für}\; \displaystyle\frac{1}{2}<u<1 \end{cases} \end{eqnarray*}$

ist. Schließlich und endlich approximiert man dann

$\begin{eqnarray*} I_1 \approx \frac{1}{N} \sum\limits_{i=1}^N ~ \frac{f(x_i)}{g(x_i)} = \frac{1}{N} \sum\limits_{i=1}^N ~ \frac{1-\cos(x_i)}{x_i^2g(x_i)} \end{eqnarray*}$ .

04.10.2005, 17:24

Michael78

Auf diesen Beitrag antworten »

Vielen Dank, dieses Beispiel hat mir wieder sehr weitergeholfen!
Ich hätte nur eine Frage:

Und zwar siehe
http://www.imw.tuwien.ac.at/fc/Teaching/...eiten/exner.pdf
(die Quelle habe ich gerade erst gefunden),
da ist Importance Sampling auf S. 19 und 20 erklärt und es kommt durch Erweitern von f(x) zu f(x)/g(x) * g(x)
Der Bruch ist die Likelihood-Ratio, die das g(x) am Ende ist die gezogene Größe, die Du mir grad so gut erklärt hast.

In dem beispiel von Dir (und auf wikipedia) ist aber nur der Bruch f(x)/g(x) zu sehen, nicht mehr die Multiplikation.

Wie kommt das?

04.10.2005, 18:16

AD

Auf diesen Beitrag antworten »

Vielleicht versteht man die Geschichte besser, wenn sie so interpretiert wird:

Man führt eine Integralsubstitution mit Hilfe der Verteilungsfunktion $\begin{eqnarray*} G \end{eqnarray*}$ durch, d.h. man substituiert $\begin{eqnarray*} u=G(x) \end{eqnarray*}$ in $\begin{eqnarray*} I:=\int\limits_a^b ~ f(x) ~ \mathrm{d}x \end{eqnarray*}$ , wobei für diese Verteilungsfunktion $\begin{eqnarray*} G(a)=0 \end{eqnarray*}$ und $\begin{eqnarray*} G(b)=1 \end{eqnarray*}$ gelten möge (ansonsten deckt man ja nicht das ganze Intervall ab!). Dann folgt nach ganz normalen Substitutionsregeln $\begin{eqnarray*} \mathrm{d}u = G'(x) ~ \mathrm{d}x = g(x) ~ \mathrm{d}x \end{eqnarray*}$ und folglich

$\begin{eqnarray*} I = \int\limits_0^1 ~ \frac{f\left(G^{-1}(u)\right)}{g\left(G^{-1}(u)\right)} ~ \mathrm{d}u \end{eqnarray*}$

Und dieses Integral ist es, welches du dann "ganz normal" nach Monte-Carlo integrierst, also

$\begin{eqnarray*} I \approx \frac{1}{N} ~ \sum\limits_{i=1}^N \frac{f\left(G^{-1}(u_i)\right)}{g\left(G^{-1}(u_i)\right)} \end{eqnarray*}$

Wenn wir jetzt noch dran denken, dass laut Inversionsmethode $\begin{eqnarray*} x_i=G^{-1}(u_i) \end{eqnarray*}$ ist, dann haben wir gerade die Formel

$\begin{eqnarray*} I \approx \frac{1}{N} ~ \sum\limits_{i=1}^N \frac{f\left(x_i\right)}{g\left(x_i\right)} \end{eqnarray*}$

des Importance Sampling bewiesen.

05.10.2005, 11:02

Michael78

Auf diesen Beitrag antworten »

Das wirkt so schlüssig, aber noch mal meine Frage zu
http://www.imw.tuwien.ac.at/fc/Teaching/...eiten/exner.pdf
S. 19 und 20.

Die ziehen aus der Importance-Verteilung f'(x) und korrigieren dann (den Betrag) g(x) durch Multiplikation mit f(x)/f'(x).

In Deiner - nachvollziehbaren - Lösung wird f'(x) gezogen (um die Notation beizubehalten) und dann f(x) durch f'(x) dividiert.

Wie kann ich mir diesen Unterschied in der Vorgehensweise und effektiv der Formel erklären?

05.10.2005, 11:23

AD

Auf diesen Beitrag antworten »

Ich sehe keinen Unterschied - vielleicht verwirren dich nur die unterschiedlich verwendeten Bezeichnungen:

$\begin{eqnarray*} \end{eqnarray*}\begin{tabular}{|l|l|l|}\cline{2-3} \multicolumn{1}{l|}{} & Bezeichnung hier & Bezeichnung Exner\\[2ex] \cline{2-3}\hline Integrationsvariable & $x$ & $y$\\ \hline Integrand & $f(x)$ & $f(y)g(y)$\\[2ex] \hline Dichte der Sampleverteilung & $g(x)$ & $f^*(y)$\\[2ex] \hline Zu summierendes Glied bei MC & $\displaystyle\frac{f(x)}{g(x)}$ & $\displaystyle\frac{f(y)g(y)}{f^*(y)}=g(y)L(y)$\\[4ex] \hline \end{tabular}\begin{eqnarray*} \end{eqnarray*}$

05.10.2005, 11:56

Michael78

Auf diesen Beitrag antworten »

Das Wort "verwirren" passt leider völlig.

Danke für die Darstellung - nur: ich finde im Exner-Text das zu summierende Glied bei MC nicht so, wie Du es dargestellt hast.

Hast Du dieses wieder so hergeleitet, wie Du es mir gestern erklärt hast?
(letzter gestriger Eintrag von Dir)

05.10.2005, 12:03

AD

Auf diesen Beitrag antworten »

Meinen letzten Beitrag verstehe ich nicht als Herleitung, sondern als einfache Symbolzuordnung zwischen beiden Darstellungen. Das $\begin{eqnarray*} g \end{eqnarray*}$ etwa hat im Vergleich eine völlig unterschiedliche Bedeutung! Aber diese Symbolzuordnung berücksichtigend ist die Exner-Darstellung mit der hiesigen konform. Bei Exner wird vom Samplingplan

{ g(y)L(y), f*(y) }

gesprochen - ich nehme einfach mal an, dass das heißt, dass gemäß Dichte f* das y ausgewürfelt wird, und damit dann g(y)L(y) summiert wird. Und das habe ich in der letzten Tabellenzeile dann entsprechend so vermerkt.

05.10.2005, 12:12

Michael78

Auf diesen Beitrag antworten »

Ja, ich meinte Deinen letzten Eintrag von gestern (mit der Integralsubstitution).

Wenn ich es recht verstehe, müsste ich statt f(x) als Integrand die gleiche Integralsubstitution nur mit f(y) g(y) durchführen und würde dann zum Samplingplan von Exner gelangen, richtig?

05.10.2005, 12:14

AD

Auf diesen Beitrag antworten »

Genau so ist es. Freude

Freude

05.10.2005, 12:20

Michael78

Auf diesen Beitrag antworten »

Danke!!!!

:-)))

Sehe nun zwischen zwei mächtigen Bäumen ein kleines Stück Wald... ;-)

Jetzt muss ich nur noch multivariates M-H verstehen..

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »