Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Importance Sampling
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Importance Sampling
 
Autor Nachricht
Michael16
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.10.2005
Beiträge: 4

BeitragVerfasst am: 04 Okt 2005 - 15:28:16    Titel: 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!!
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 04 Okt 2005 - 16:13:56    Titel:

Zitat:
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?


So wird es in der Praxis sein. Man hat ja einen Zahlengenerator, der halbwegs uniform verteilt ist.

Zitat:
Falls ja, verstehe ich nicht, wie man "direkt" aus einer Importance-Verteilung ziehen kann.


Werte uniform erzeugen und Stauchen durch g. Wie genau muss ich mir noch überlegen, wenn es Dich interessiert.

Zitat:
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?


f ist im Allgemeinen schwer zu berechnen. Man möchte möglichst wenig damit zu tun haben. g ist dann was viel einfacheres, z.B. ein Polynom oder eine trigonometrische Funktion.

Zitat:
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?


Ja, aber nur an y_i-Punkten.

Zitat:
4.) Manchmal steht auch was da, dass die Importance-Samples gewichtet werden müssen, aber das ist mir nicht klar.


Mir auch nicht.

P.S. Fehlt da nicht (b-a) auf der Wiki-Seite?
Michael16
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.10.2005
Beiträge: 4

BeitragVerfasst am: 04 Okt 2005 - 16:23:46    Titel:

Hi!
Meinst Du mit "Stauchen" die Inversionsmethode? Wenn ja, funktioniert die nicht bei allen stetigen Verteilungen?

Ich habe auf
http://www.tcm.phy.cam.ac.uk/~ajw29/thesis/node17.html
gesehen, dass "the best possible choice is g(x)=|f(x)| und dass man das Ganze nicht macht, um vor f() auszuweichen, sondern um die Varianz der Schätzung zu verringern - ist das falsch?
Unter diesem Link steht auch das, dass man das f(x)/g(x) noch einmal mit g(x) multipliziert, was mir völlig unklar ist.
Ich meine, f(x)/g(x)*g(x) ergibt doch einfach wieder f(x).

Wieder eine andere Version habe ich gefunden auf
http://rkb.home.cern.ch/rkb/AN16pp/node132.html
*seufz*

Deine Antwort auf meine dritte Frage is mir leider unklar.
Es werden also i Punkte in der Simulation erzeugt und für alle i gezogenen gleichverteilten Zufallszahlen muss die Verteilung f(i) berechnet werden.
Falsch?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 04 Okt 2005 - 16:56:24    Titel:

Zitat:
Meinst Du mit "Stauchen" die Inversionsmethode?


Ja, aber man kann das auch anders machen. Über stetige Deformationen. Ich müsste mir aber was dazu überlegen, was wahrscheinlich zu viel Zeit nimmt Sad

Zitat:
gesehen, dass "the best possible choice is g(x)=|f(x)| und dass man das Ganze nicht macht, um vor f() auszuweichen, sondern um die Varianz der Schätzung zu verringern - ist das falsch?
Unter diesem Link steht auch das, dass man das f(x)/g(x) noch einmal mit g(x) multipliziert, was mir völlig unklar ist.
Ich meine, f(x)/g(x)*g(x) ergibt doch einfach wieder f(x).


Das Ziel der Technik ist es natürlich eine geringe Streuung zu erhalten. Man muss aber auch Implementierungstechnisch denken: Wenn Du f intergrieren kannst, warum tust Du es nicht einfach? Praktisch gesehen ist vermutlich f nicht einmal total definiert.

Die Idee ist aber bei der ganzen Geschichte doch trivial. Das, was da steht ist ja im Wesentlichen konstante Approximation des Integrals durch die Fläche eines Rechtecks (konstant, weil man die Funktion durch einen Polynom vom Grad 0 approximiert). Ich habe schon bessere Monter-Carlo-Erklärungen gesehen. Man bekommt aber ein besseres Rechteck, wenn man dort approximiert, wo die Funktion eben eher nach einem Rechteck aussieht: Da wo die Werte halt groß sind.

Zitat:
Unter diesem Link steht auch das, dass man das f(x)/g(x) noch einmal mit g(x) multipliziert, was mir völlig unklar ist.
Ich meine, f(x)/g(x)*g(x) ergibt doch einfach wieder f(x).


Naja. f(x) = f(x) * g(x)/g(x). Das nennt man wohl "Erweitern" in der Mittelschule. Der Rest ist nur "Uminterpretieren" von g(x) dx als ein Wahrscheinlichkeitsmaß, wie das auch in der Bildverarbeitung üblich ist.

P.S. Ich bin Informatiker, kein Statistiker, daher bin ich mehr auf Implementierungskomplexität aus, als auf Streuungsminimalisierung Smile
Michael16
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.10.2005
Beiträge: 4

BeitragVerfasst am: 04 Okt 2005 - 17:51:56    Titel:

Danke! Smile

Und mach Dir bitte keine Mühe wegen der Deformationen *dings* Was ist denn das bzw. worunter muss ich nachschauen? Smile

Schönen Abend!
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 04 Okt 2005 - 18:30:02    Titel:

Das ist nichts zum Nachschauen. Das war nur eine Idee. Man kann folgendes machen: Man definiere eine "Schränkung" phi(x) : D -> D, stetig und bijektiv, sodass die Schränkung f o phi einer Verteilungsfunktion f wieder eine Verteilungsfunktion ist. Die Frage ist dann nur, wie man aus g die Schränkung bekommt. Dazu müsste man aber was machen, d.h. es stinkt nach Arbeit.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Importance Sampling
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum