Unter welchen Umständen ist die Monte-Carlo-Integration besser als die Quasi-Monte-Carlo-Integration?

11

Eine recht einfache Frage: Um ein mehrdimensionales Integral zu erstellen, gibt es einen Vorteil, den eine reguläre MC-Integration unter Verwendung von Pseudozufallszahlen gegenüber einer Quasi-Monte-Carlo-Integration unter Verwendung einer Quasirandom-Sequenz hat, wenn man entschieden hat, dass eine Art Monte-Carlo-Methode geeignet ist ? Wenn ja, wie würde ich Situationen erkennen, in denen dieser Vorteil zum Tragen kommen würde? (Und wenn nicht, warum verwendet jemand jemals eine einfache alte Monte-Carlo-Integration?)

David Z.
quelle

Antworten:

4

Monte-Carlo-Simulationen sind die Methode der Wahl zur Berechnung der Elektronenstreuung. Manchmal werden Tricks wie Wichtigkeitsstichproben verwendet, man könnte also sagen, es ist kein einfaches altes Monte Carlo. Aber der Hauptpunkt ist wahrscheinlich, dass hier ein inhärent stochastischer Prozess simuliert wird, während Sie nur nach der Verwendung von Monte Carlo für die Integration fragen.

Da sonst niemand versucht hat, eine Antwort anzubieten, möchte ich versuchen, meine Antwort ein wenig zu erweitern. Angenommen, wir haben eine Elektronenstreusimulation, bei der nur eine einzige Zahl wie ein Rückstreukoeffizient berechnet wird. Wenn wir dies als mehrdimensionales Integral umformulieren würden, wäre es wahrscheinlich ein unendlich dimensionales Integral. Andererseits ist während der Simulation einer einzelnen Trajektorie nur eine endliche Anzahl von Zufallszahlen erforderlich (diese Anzahl kann ziemlich groß werden, wenn die Erzeugung von Sekundärelektronen berücksichtigt wird). Wenn wir eine quasirandomale Sequenz wie die Latin Hypercube Sampling verwenden würden, müssten wir eine Näherung mit einer festen Anzahl von Dimensionen verwenden und für jede Dimension für jeden Stichprobenpunkt eine Zufallszahl generieren.

Ich denke also, der Unterschied besteht darin, ob eine Art hochdimensionaler Einheitshyperwürfel abgetastet wird, im Vergleich zu einer unendlich dimensionalen Wahrscheinlichkeitswolke um den Ursprung.

Thomas Klimpel
quelle
5

Einige meiner Forschungen umfassen die Lösung großräumiger stochastischer partieller Differentialgleichungen. In diesem Fall konvergiert die traditionelle Monte-Carlo-Approximation des interessierenden Integrals zu langsam, als dass es sich im praktischen Sinne lohnt ... dh ich möchte nicht 100-mal mehr Simulationen ausführen müssen, um einen Dezimalpunkt genauer zu erhalten zum Integral. Stattdessen tendiere ich dazu, andere Methoden wie spärliche Smolyak-Gitter zu verwenden, da sie eine bessere Genauigkeit bei weniger Funktionsbewertungen bieten. Dies ist nur möglich, weil ich einen gewissen Grad an Glätte in der Funktion annehmen kann.

Es ist zu vermuten, dass es am besten ist, das Quasi-Monte-Carlo-Schema zu verwenden, das diese Funktion ausnutzt, wenn Sie erwarten, dass die von Ihnen integrierte Funktion eine bestimmte Struktur aufweist (z. B. Glätte). Wenn Sie wirklich nicht viele Annahmen über die Funktion machen können, dann ist Monte Carlo das einzige Werkzeug, das ich mir vorstellen kann, um damit umzugehen.

Paul
quelle
3
Tatsächlich müssten Sie 100-mal mehr Simulationen ausführen, um eine besonders signifikante Ziffer zu erhalten.
Brian Borchers
4

Die Vorteile der traditionellen Monte-Carlo Integration über Quasi-Monte - Carlo - Integration in Kocis und Whiten Papier diskutiert hier . Sie listen die folgenden Gründe auf:

  • Die Fehlergrenze der qmc-Methoden ist "theoretisch" besser als die durch naive gegebene -Bindung Monte Carlo. Für Werte von , die auf der aktuellen Hardware in angemessener Zeit erreichbar sind, ist die bessere Option für . (Kocis und Whiten haben 1997 geschrieben, also hat vermutlich seitdem etwas zugenommen.)O ( N - 1 / 2 ) N O ( N - 1 / 2 ) d 40 dO(log(N)d/N)O(N1/2)NO(N1/2)d40d
  • Der Fehler einer QMC-Integration ist durch die Koksma-Hlawka-Ungleichung gebunden, wobei die Variation von und ist der Stern der Diskrepanz. Aber zitiert aus Kocis 'Papier, V [ f ] f D * N

    errorV[f]DN
    V[f]fDN

    Leider ist die theoretische Diskrepanzgrenze der vorhandenen Sequenzen für moderate und große Werte von s nicht verwendbar. Die andere Option, eine numerische Bewertung der Sterndiskrepanz einer Sequenz für große s, erfordert einen übermäßigen Rechenaufwand, und selbst vernünftige numerische Schätzungen solcher Diskrepanzen sind sehr schwer zu erhalten.

    Bei der herkömmlichen Monte-Carlo-Integration können wir ein Fehlerziel angeben und warten, da die Fehlergrenze leicht berechenbar ist. Bei QMC müssen wir eine Reihe von Funktionsbewertungen angeben und hoffen, dass der Fehler innerhalb unseres Ziels liegt. (Beachten Sie, dass es Techniken gibt, um dies zu überwinden, wie z. B. randomisiertes Quasi-Monte-Carlo, bei dem mehrere Quasi-Monte-Carlo-Schätzungen verwendet werden, um den Fehler abzuschätzen.)

  • Da die "konstanten Terme" der Fehlergrenzen für viele Sequenzen mit geringer Diskrepanz, die wir tatsächlich besitzen, exponentiell mit der Dimension wachsen, verwenden Kocis und Whiten eine andere Metrik, um den Fehler abzuschätzen: den maximalen Abstand zwischen Stichprobenpunkten. Dies ergibt eine Fehlerschätzung von , und sie behaupten, dass sie zum beobachteten Verhalten vieler Integranden passt.O(1/N1/2+2/d)

  • Damit Quasi-Monte-Carlo das traditionelle Monte-Carlo schlagen kann, muss der Integrand eine "niedrige effektive Dimension" haben. Siehe Art Owens Artikel zu diesem Thema hier .

user14717
quelle