Paralleler Mersenne Twister für Monte Carlo

Kürzlich stieß ich auf einen Kommentar, in dem behauptet wurde, dass fast alle Forscher, die Monte-Carlo-Methoden anwenden, es falsch machen. Es wurde weiter ausgeführt, dass die bloße Auswahl verschiedener Samen für verschiedene Instanzen eines PRNG wie des Mersenne Twister nicht ausreicht, um unvoreingenommene Ergebnisse zu gewährleisten, da schlimme Kollisionen auftreten können. Der Wikipedia-Artikel über den Mersenne Twister scheint zu bestätigen:

Mehrere Mersenne Twister-Instanzen, die sich nur im Startwert (aber nicht in anderen Parametern) unterscheiden, sind im Allgemeinen nicht für Monte-Carlo-Simulationen geeignet, für die unabhängige Zufallszahlengeneratoren erforderlich sind, obwohl es eine Methode zur Auswahl mehrerer Sätze von Parameterwerten gibt.

Ich muss zugeben, ich bin schuldig wie angeklagt. Aber auch alle anderen Implementierungen paralleler Monte-Carlo-Bibliotheken, die ich bisher gesehen habe, insbesondere ALPS .

Der Wikipedia-Artikel verweist auch auf zwei Artikel, die Abhilfe bieten:

Das Dynamic Creation (DC) -Schema (1998) wählt Parametersätze für die MTs basierend auf der Hypothese aus, dass sie unabhängig sind, wenn die entsprechenden charakteristischen Polynome Koprime sind.
Der Sprung nach vorne für lineare RNGs $\mathbb F_2$ (2008). Ich denke, es ähnelt der Sprungfrosch-Methode für LCGs.

Beide Methoden wurden von Matsumoto und Nishimura, den ursprünglichen Autoren des Mersenne Twister-Algorithmus, gemeinsam entwickelt.

Ich fürchte, ich bin nicht sehr gut mit Zahlentheorie oder Algebra vertraut und verstehe die oben genannten Schemata oder die Mathematik hinter dem Mersenne Twister nicht vollständig. Meine Fragen sind in erster Linie praktischer Natur:

Wie sehr muss ich mir wirklich Sorgen machen, dass meine Simulationen verzerrt werden, wenn ich ein solches Schema nicht verwende, wenn sich in der Praxis (zumindest in meiner Gemeinde) so gut wie niemand darum kümmert?
Wenn ich eine dieser Gegenmaßnahmen umsetzen würde, kann ich zu Recht davon ausgehen, dass die Jump-Ahead-Maßnahme besser geeignet ist, da sie auf einer festen Theorie basiert und die modernere Methode ist?

parallel-computing monte-carlo random-number-generation Jonas Greitemann
quelle

Ist diese Frage nicht spezifisch für MT? Andere PRNGs haben einfachere Möglichkeiten, unabhängige Streams zu generieren, wie in Pierre L'Ecuyers anderen Arbeiten beschrieben (siehe insbesondere seine Umfragen wie iro.umontreal.ca/~lecuyer/myftp/papers/parallel-rng-imacs.pdf ).

Kirill

Ja, es ist etwas spezifisch für MT. Ich habe MT bisher nur in MC-Simulationen verwendet und es wird von meinen Kollegen als die etwas teurere, aber sicherste Option angesehen. Ich bin mir nicht sicher, ob dies im Allgemeinen zutrifft, aber ich habe es verstanden.

Jonas Greitemann

Antworten:

Wie Sie sagen, wird die Verwendung des Mersenne Twister für parallele Berechnungen fast immer falsch durchgeführt, da die Implementierung der richtigen Methode schwierig ist.

Die mit Abstand einfachste und beste Antwort wäre, sich vollständig vom Mersenne Twister zu entfernen und so etwas wie die PCG-Familie zu verwenden , die mehrere Streams sofort bereitstellt.

Es ist bekannt, dass der Mersenne Twister mehrere statistische Tests nicht besteht und gleichzeitig langsamer ist als neuere RNGs wie die PCG- und XorShift + -Familien.

Der Grund, warum der Mersenne Twister heute so weit verbreitet ist, ist hauptsächlich auf die RNGs zurückzuführen, bevor er sowohl in Bezug auf Leistung als auch Qualität weitaus schlechter ist. Es hat auch geholfen, dass die ursprünglichen Autoren Open-Source eine hochperformante Implementierung.

LKlevin
quelle

Es ist erwähnenswert, dass MT in dem von Ihnen verlinkten Artikel nur zwei lineare Komplexitätstests seines Bitstroms nicht bestanden hat, sodass ein Fehler ihn nicht unbedingt von der Verwendung ausschließt, und ich stelle mir vor, dass es viele Anwendungen gibt, für die es keine Empfindlichkeit gibt diese besondere Art von Versagen.

Kirill

Bestimmt. Es ist perfekt für viele Anwendungen geeignet. Bei älteren Anwendungen wäre ein Wechsel von MT meistens eine vergebliche Anstrengung. Für neue Anwendungen oder Anwendungen, die mehrere Zufallszahlenströme benötigen, gibt es keinen Grund, diese zu verwenden.

LKlevin

Die PCG-Generatoren klingen fantastisch. Fast zu schön um wahr zu sein. Vielleicht ist es nur eine Überdosis wissenschaftlicher Skepsis, oder vielleicht ist es das starke Verkaufsargument der Website. In jedem Fall ist es ziemlich neu. Gibt es unabhängige Untersuchungen, die seine Behauptungen bestätigen?

Jonas Greitemann

Sie haben ein sehr starkes Verkaufsgespräch für die PCG, aber das ist auch etwas, das vom Mersenne Twister geerbt wurde. Schauen Sie sich die xorshift + -Homepage an, um zu sehen, wie eine andere Gruppe dasselbe tut. Was Dritte betrifft, so schätze ich, da ich keinerlei Zugehörigkeit zur PCG-Gruppe habe und deren Behauptungen ausführlich überprüft habe (um meinen eigenen RNG-Vorgesetzten zu beweisen). Sie können TestU01 auch selbst auf dem PCG ausführen , um die Ansprüche zu testen.

LKlevin

Für meine Anwendung / Hardware war ich xorshift+ungefähr doppelt so schnell wie ein "äquivalenter" PCG-Generator. Versuchen Sie also beide, wenn die Geschwindigkeit wichtig ist. Der Haupt-PCG-Code verfügt im Vergleich zum sehr leichten xorshift+Code über viele integrierte Funktionen .

Horchler

Wenn Sie MT verwenden möchten, können Sie SFMT als PRNG- und SFMT-Sprung verwenden , um mehrere Streams zu generieren.

Sie können MT einfach mit einem Startwert initialisieren und dann z. B. , , … Schritte vorwärts springen , um mehrere Streams zu generieren. Das Springen ist etwas teuer, aber Sie müssen es nur einmal tun, wenn Sie Ihre PRNGs initialisieren. $1 \cdot 10^{60}$ $2 \cdot 10^{60}$ $3 \cdot 10^{60}$

Jukka Suomela
quelle

Wirklich nur Sie können die Frage nach dem Simulationsfehler beantworten und ob er in Ihrer Anwendung akzeptabel ist. Das Standardverfahren, das ich verwende:

Legen Sie eine Pseudozufallssequenz als Benchmark (Standard-Monte-Carlo) mit einer hohen Anzahl von Simulationen fest (im Risikomanagement werden häufig 10.000 verwendet, in anderen Bereichen können 100.000 bis 1 Million verwendet werden).

Führen Sie Ihr RNG über dieselben Eingabedaten für eine Teilmenge von Daten aus (wir verwenden 1 Jahr, aber das ist oft übertrieben).

Vergleichen Sie die Ergebnisse mithilfe von Statistiken, die Merkmale der Daten beschreiben, die Sie tatsächlich für Schlussfolgerungen / Entscheidungen verwenden. Wir verwenden Perzentile (1,5,25,50,75,95,99), absoluten Fehler, Standardabweichung des Fehlers. All dies ist relativ zu Ihrer Benchmark.

Nachdem Sie die Analyse durchgeführt haben, können Sie selbst beurteilen, ob die RNG-Verzerrung akzeptabel ist.

Matt
quelle