Warum gilt der Mersenne Twister als gut?

38

Der Mersenne Twister gilt weithin als gut. Heck, die CPython-Quelle sagt, dass es "einer der am umfassendsten getesteten Generatoren ist, die es gibt". Aber was heißt das? Wenn ich gefragt werde, ob ich die Eigenschaften dieses Generators auflisten soll, ist das meiste, was ich anbieten kann, schlecht:

  • Es ist massiv und unflexibel (zB keine Suche oder mehrere Streams),
  • Trotz seiner gewaltigen Zustandsgröße scheitert es an statistischen Standardtests.
  • Es hat ernsthafte Probleme um 0, was darauf hindeutet, dass es sich selbst ziemlich schlecht randomisiert,
  • Es ist kaum schnell

und so weiter. Im Vergleich zu einfachen RNGs wie XorShift * ist dies auch hoffnungslos kompliziert.

Also suchte ich nach Informationen, warum dies jemals für gut gehalten wurde. Das Originalpapier enthält viele Kommentare zur "superastronomischen" Periode und zur 623-dimensionalen Gleichverteilung

Unter vielen bekannten Maßnahmen werden die auf der höheren Maßgleichmäßigkeit beruhenden Tests, wie der nachstehend beschriebene Spektraltest (vgl. Knuth [1981]) und der K-Verteilungstest, als am stärksten angesehen.

Aber für diese Eigenschaft wird der Generator von einem Zähler von ausreichender Länge geschlagen! Dies macht keinen Kommentar zu lokalen Distributionen, worum es Ihnen in einem Generator eigentlich geht (obwohl "lokal" verschiedene Dinge bedeuten kann). Und selbst CSPRNGs interessieren sich nicht für so große Zeiträume, da dies nur nicht im entferntesten wichtig ist.

Es gibt eine Menge Mathe in der Zeitung, aber soweit ich das beurteilen kann, geht es hier eigentlich um die Qualität der Zufälligkeit. So gut wie jede Erwähnung davon geht schnell auf diese ursprünglichen, größtenteils nutzlosen Behauptungen zurück.

Es scheint, als wären die Leute auf Kosten älterer, zuverlässigerer Technologien auf diesen Zug gesprungen. Wenn Sie beispielsweise die Anzahl der Wörter in einer LCG auf 3 erhöhen (viel weniger als die "nur 624" eines Mersenne-Twisters) und das oberste Wort bei jedem Durchgang ausgeben, besteht es BigCrush ( den schwierigeren Teil der TestU01-Testsuite) ), obwohl der Twister versagt hat ( PCG-Papier, Abb. 2 ). Angesichts dieser Tatsache und der schwache Beweise ich in der Lage war , zur Unterstützung der Mersenne Twister zu finden, was tat Ursache die Aufmerksamkeit auf sie über die anderen Entscheidungen zu begünstigen?

Dies ist auch nicht rein historisch. Mir wurde im Vorbeigehen gesagt, dass der Mersenne Twister in der Praxis zumindest bewährter ist als beispielsweise PCG Random . Aber sind Use-Cases so anspruchsvoll, dass sie besser funktionieren als unsere Testbatterien? Einige Googler schlagen vor, dass dies wahrscheinlich nicht der Fall ist.

Kurz gesagt, ich frage mich, wie der Mersenne Twister seinen allgemein positiven Ruf erlangt hat, sowohl im historischen als auch im sonstigen Kontext. Einerseits bin ich natürlich skeptisch gegenüber seinen Eigenschaften, andererseits ist es schwer vorstellbar, dass es sich um ein rein zufälliges Ereignis handelt.

Veedrac
quelle
2
Ich denke, du hast recht. Mersenne Twister ist nichts Besonderes. Es ist nur bekannt (und viele der anderen bekannten PRNGs sind zufällig schlimmer). Es gibt andere PRNGs, die auch ganz gut sind. Für ein noch besseres PRNG kann man ein kryptografisches PRNG verwenden. Ich bin mir nicht sicher, welche Art von Antwort man geben kann, abgesehen von "Es ist nichts Falsches an Ihrer Argumentation".
DW
1
Ich denke, die Frage, die Sie sich stellen sollten, ist nicht, ob MT gut ist oder nicht (da es nach vielen Metriken gut ist), sondern warum es häufiger verwendet wird als die Alternativen wie PCG oder XorShift. Die Antwort ist wahrscheinlich, dass es sie nur für längere Zeit gibt und dass sie für lange Zeit (in Internetjahren) die beste vernünftige Standardeinstellung war.
Pseudonym
1
@vzn "Eine weitere Überlegung betrifft die Generierungszeit. PRNGs" Qualität "geht zu Lasten der Laufzeit" → Nur dass der Mersenne Twister langsamer und schlechter ist als ein vernünftig großes LCG. Siehe Abb. 16 im PCG-Papier. (Über die Frage, ob ich die Zeitung gelesen habe: Ich habe die meisten nicht-mathematischen Teile der Mersenne Twister-Zeitung im Detail und die gesamte PCG-Zufallszeitung gelesen. Die dritte habe ich jedoch größtenteils
überflogen
1
Sprechen Sie über XorShift oder die KISS-Algorithmen?
gnasher729
1
@ gnasher729 Ich erwähne XorShift *, aber ich bin nicht wirklich spezifisch für eine bestimmte Alternative. Ich wusste nichts über KISS, FWIW.
Veedrac

Antworten:

15

MT galt einige Jahre als gut, bis sich herausstellte, dass es mit den fortgeschritteneren TestU01 BigCrush-Tests und besseren PRNGs ziemlich schlecht war.

2219937

Diese Seite listet die Mersenne-Twister-Funktionen im Detail auf:

Positiven Eigenschaften

  • Erzeugt 32-Bit- oder 64-Bit-Zahlen (daher als Quelle für Zufallsbits verwendbar)
  • Besteht die meisten statistischen Tests

Neutrale Eigenschaften

  • 22199371
  • 623-dimensional gleichverteilt
  • Punkt kann partitioniert werden, um mehrere Streams zu emulieren

Negative Eigenschaften

  • Schlägt einige statistische Tests mit nur 45.000 Zahlen fehl.
  • Vorhersehbar - Nach 624 Ausgaben können wir ihre Ausgabe vollständig vorhersagen.
  • Der Status des Generators belegt 2504 Byte RAM - im Gegensatz dazu passt ein äußerst benutzerfreundlicher Generator mit einer unübertroffenen Nutzungsdauer auf 8 Byte RAM.
  • Nicht besonders schnell.
  • 2219937
  • Ungleichmäßige Leistung; Der Generator kann in "schlechte Zustände" geraten, von denen er sich nur langsam erholt.
  • Samen, die sich nur geringfügig unterscheiden, brauchen lange, um voneinander abzuweichen. Das Säen muss sorgfältig durchgeführt werden, um schlechte Zustände zu vermeiden.
  • Während ein Jump-Ahead möglich ist, sind Algorithmen dazu langsam zu berechnen (dh benötigen mehrere Sekunden) und werden selten von Implementierungen bereitgestellt.

Zusammenfassung : Mersenne Twister ist nicht mehr gut genug, aber die meisten Anwendungen und Bibliotheken sind noch nicht da.

Rurban
quelle
6
Danke für die nette Zusammenfassung! Ich bin jedoch besorgt, dass die einzige offensichtliche Quelle für Ihren Beitrag eine Website ist, die effektiv eine Werbung für eine andere Familie von Zufallszahlengeneratoren ist, die noch nicht einer Peer-Review unterzogen wurde. Die Website selbst bietet keine Referenzen für die Einträge, aber der vorgeschlagene Artikel scheint viele zu enthalten. Daher denke ich, dass Sie Ihre Antwort auf den Kontext hier verbessern können (Kritik an MT), indem Sie Referenzen für die einzelnen Punkte angeben.
Raphael
9
2219937295×22199372219945
1
"Vorhersehbar" - MT ist nicht als kryptografisches PRNG gedacht. Bearbeiten Sie daher Ihre Antwort.
Jason S
8

Ich bin der Herausgeber, der das MT-Papier bereits 1998 in ACM TOMS akzeptiert hat, und ich bin auch der Designer von TestU01. Ich verwende kein MT, sondern hauptsächlich MRG32k3a, MRG31k3p und LRSR113. Um mehr über diese, über MT und über das, was es sonst noch gibt, zu erfahren, können Sie sich die folgenden Papiere ansehen:

F. Panneton, P. L'Ecuyer und M. Matsumoto, "Verbesserte Langperiodengeneratoren basierend auf linearen Rekursionen Modulo 2", ACM Transactions on Mathematical Software, 32, 1 (2006), 1-16.

P. L'Ecuyer, "Random Number Generation", Kapitel 3 des Handbook of Computational Statistics, JE Gentle, W. Haerdle und Y. Mori, Herausgeber, 2. Auflage, Springer-Verlag, 2012, 35-71 . https://link.springer.com/chapter/10.1007/978-3-642-21551-3_3

P. L'Ecuyer, D. Munger, B. Oreshkin und R. Simard, "Random Numbers for Parallel Computers: Requirements and Methods", Mathematics and Computers in Simulation, 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

P. L'Ecuyer, "Zufallszahlengenerierung mit mehreren Streams für sequentielle und parallele Computer", lud ein erweitertes Tutorial, Proceedings of the 2015 Winter Simulation Conference, IEEE Press, 2015, 31-44.

Pierre L'Ecuyer
quelle
3
Danke für deine Antwort! Würde es Ihnen etwas ausmachen, der Frage etwas hinzuzufügen? 1) Warum fandest du MT damals gut (oder zumindest eine Veröffentlichung wert)? 2) Warum denkst du nicht, dass es gut genug für den Gebrauch ist?
Raphael
Vielen Dank, dass Sie diesen wertvollen historischen Kontext hinzugefügt haben. Ich bin auch neugierig auf Raffaels Fragen und Ihre persönlichen Gedanken, als Sie das Papier akzeptierten.
Veedrac
5

Ähnlich wie bei Sortieralgorithmen gibt es in dieser Hinsicht kein "one size fits all" PRNG. Unterschiedliche werden für unterschiedliche Zwecke verwendet und es gibt eine Vielzahl von Designkriterien und Verwendungen. Es ist möglich, PRNGs falsch anzuwenden, z. B. für die Kryptografie, für die sie nicht entwickelt wurde. Der Wikipedia-Eintrag zu Mersenne Twister erwähnt auch, dass er nicht für "Monte-Carlo-Simulationen entwickelt wurde, die unabhängige Zufallszahlengeneratoren erfordern".

Wie bei Wikipedia vermerkt, wird dieses PRNG in der Tat in einer Vielzahl von Programmiersprachen und Anwendungen verwendet, sogar als Standard-PRNG. Es würde eine fast soziologische Analyse erfordern, um zu erklären, warum ein PRNG bevorzugt wird. Einige mögliche Faktoren, die zu diesem PRNG beitragen können:

  • Der Autor hat gute / starke wissenschaftliche Referenzen auf dem Gebiet und arbeitet seit Jahrzehnten in PRNGs.

  • Es wurde speziell entwickelt, um anderen Methoden zu dieser Zeit überlegen zu sein.

  • Der Autor befasst sich mit der Implementierung und deren Verfolgung und trägt auch dazu bei. Einige PRNGs sind eher theoretisch und die Autoren beschäftigen sich nicht immer mit tatsächlichen Implementierungen.

  • Das System wird auf einer Webseite gut unterstützt / aktualisiert.

  • Neue Versionen des PRNG wurden entwickelt, um mit Schwachstellen umzugehen. Es gibt keinen einzigen Mersenne-Twister-Algorithmus, sondern verschiedene Versionen und eine Reihe von Varianten, die unterschiedliche Anforderungen erfüllen.

  • Es wurde von einer Standard-Zufallsanalysesoftware ausgiebig analysiert / getestet und von unabhängigen Behörden genehmigt.

  • Es gibt einen bekannten Effekt, der mit für Websites und viele andere Kontexte gemessen werden kann, wie beispielsweise wissenschaftliche Zitate, die als "bevorzugte Bindung" bezeichnet werden und gemessen werden können. Es ist im Grunde genommen der Ort, an dem seit langem etablierte historische Quellen weitere Verwendung finden. Ein solcher Effekt könnte die PRNG-Entscheidungen im Laufe der Zeit erklären.

Mit anderen Worten, Sie fragen nach einem Phänomen der "Popularität", das mit menschlichen Entscheidungen verbunden und verbunden ist und nicht streng an bestimmte Eigenschaften gebunden ist, sondern eine Art komplexe / aufkommende Eigenschaft und Wechselwirkung zwischen verschiedenen Algorithmen, Benutzern und der Umgebung darstellt / Nutzungskontexte.

Hier ist eine solche unabhängige Analyse des Algorithmus Mersenne Twister - Ein Pseudozufallszahlengenerator und seiner Varianten von Jagannatam (15p). Der abschließende Absatz ist im Wesentlichen eine Antwort auf Ihre Frage. nur die 1 zitiert st paar Sätze:

Mersenne Twister ist theoretisch ein gutes PRNG mit einer langen Periode und einer hohen Gleichverteilung. Es wird häufig in den Bereichen Simulation und Modulation eingesetzt. Die von den Anwendern festgestellten Mängel wurden von den Erfindern behoben. MT wurde aktualisiert, um die neuen Technologien von CPUs wie SIMD und parallele Pipelines in seiner Version von SFMT zu nutzen und mit diesen kompatibel zu sein.

vzn
quelle
2
Vielen Dank. Einiges von dem, was Sie sagen, klingt jedoch ziemlich vage: "Es wurde speziell entwickelt, um anderen Methoden zu dieser Zeit überlegen zu sein." und "Es wurde von Standard-Zufallsanalysesoftware ausgiebig analysiert / getestet und von unabhängigen Behörden bestanden.", was genau die Behauptungen sind, denen ich misstrauisch gegenüberstehe. Ich gehe ein bisschen in die Zeitung, um zu sehen, ob das alles klärt.
Veedrac
Eine weitere zu berücksichtigende Sache ist die wissenschaftliche Reproduzierbarkeit. Viele Wissenschaftler, die im Monte-Carlo-Simulationsgebiet arbeiten, tun sich große Mühe, um sicherzustellen, dass das gesamte Programm unabhängig von der Anzahl der Threads bei gleichem Startwert die gleiche Ausgabe liefert. Viele von ihnen erfordern Bug-for-Bug-Kompatibilität mit der Referenzimplementierung des PRNG.
Pseudonym
2
Sie sagen auch: "Neue Versionen des PRNG wurden entwickelt, um mit Schwachstellen umzugehen." Bei den meisten Implementierungen handelt es sich jedoch um die Standard-Erstversion, die für mich eher nach Kritik klingt. Ich bin auch ein wenig überrascht zu sehen, dass das System auf einer Webseite gut unterstützt / aktualisiert wird. - Wie viel Unterstützung braucht eine LCG wirklich?
Veedrac
@Pseudonym, dem ich nicht wirklich folge. Warum sollte dies die Verwendung eines anderen Generators ausschließen? Natürlich müssen Sie beim erneuten Ausführen von Tests denselben Generator verwenden, aber warum für neue Tests?
Veedrac
Es scheint nicht viel Unbestimmtheit über alle wissenschaftlichen Analysen im Original und in den nachfolgenden Artikeln zu geben, und die ursprüngliche Frage wird auf diese Weise etwas "geladen" (afaik viele PRNGs mit weniger Analyse / Unterstützung werden verwendet). Was Pseudonyme angeht, so sind alle PRNGs unter Verwendung der gleichen Ausgangsdaten wiederholbar , nur Hardware-basierte Generatoren nicht (und sie sind eigentlich keine PRNGs mehr, sondern "echtes physikalisches Rauschen / Zufälligkeit").
Ich bin