Importance Sampling |
04.10.2005, 12:25 | Michael78 | Auf diesen Beitrag antworten » | ||||
Importance Sampling 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 » | ||||
Du spielst hier vermutlich auf die Inversionsmethode, d.h. mit an. Wenn dein 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...
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 , wobei (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 ![]() |
||||||
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 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. ![]() |
||||||
04.10.2005, 16:29 | AD | Auf diesen Beitrag antworten » | ||||
Angenommen, du willst bestimmen. Nach partieller Integration ist mit . Um letzteres Integral durch Monte-Carlo berechnen zu können, kannst du nun gemäß sampeln. (Die Idee dahinter ist, dass ja beschränkt ist, also maßgeblich die Größenordnung des Integranden für große beschreibt.) Dann ist nämlich wegen die Funktion tatsächlich eine Dichte auf den positiven reellen Zahlen. In der Simulation hast du nun [0,1]-gleichverteilte Zufallsgrößen und erzeugst daraus die -verteilten über die Inversionsmethode , wobei ja ist. Schließlich und endlich approximiert man dann . |
||||||
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 durch, d.h. man substituiert in , wobei für diese Verteilungsfunktion und gelten möge (ansonsten deckt man ja nicht das ganze Intervall ab!). Dann folgt nach ganz normalen Substitutionsregeln und folglich Und dieses Integral ist es, welches du dann "ganz normal" nach Monte-Carlo integrierst, also Wenn wir jetzt noch dran denken, dass laut Inversionsmethode ist, dann haben wir gerade die Formel 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: |
||||||
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 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. ![]() |
||||||
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.. |
|