Pourquoi le Twister Mersenne est-il considéré comme bon?

39

Le Twister Mersenne est largement considéré comme bon. Heck, la source CPython dit qu’il est "l’un des générateurs les plus testés du monde". mais qu'est ce que ça veut dire? Quand on me demande de lister les propriétés de ce générateur, la plupart de ce que je peux offrir est mauvais:

  • Il est massif et inflexible (par exemple, aucune recherche ou plusieurs flux),
  • Il échoue aux tests statistiques standard malgré sa taille massive,
  • Il a de sérieux problèmes autour de 0, suggérant qu'il se randomise assez mal,
  • C'est à peine rapide

etc. Comparé à des GNA tels que XorShift *, il est également extrêmement compliqué.

J'ai donc cherché des informations sur les raisons pour lesquelles cela avait été considéré comme bon. Le document original fait de nombreux commentaires sur la période "super astronomique" et sur l’équidistribution à 623 dimensions, disant:

Parmi les nombreuses mesures connues, les tests basés sur l'uniformité dimensionnelle supérieure, tels que le test spectral (cf. Knuth [1981]) et le test de distribution k, décrits ci-dessous, sont considérés comme les plus puissants.

Mais, pour cette propriété, le générateur est battu par un compteur de longueur suffisante! Cela ne fait aucun commentaire sur les distributions locales , c'est ce qui compte vraiment dans un générateur (bien que "local" puisse signifier différentes choses). Et même les CSPRNG ne s’inquiètent pas de ces longues périodes, car ce n’est tout simplement pas très important.

Il y a beaucoup de maths dans le journal, mais pour autant que je sache, il s'agit en réalité de qualité aléatoire. Presque toutes les mentions à ce sujet reviennent rapidement à ces revendications originales, en grande partie inutiles.

Il semble que les gens se sont engagés dans ce mouvement au détriment de technologies plus anciennes et plus fiables. Par exemple, si vous augmentez à 3 le nombre de mots d'un LCG (beaucoup moins que le "seulement 624" d'un Twister Mersenne) et que vous transmettez le mot du haut à chaque passage, il passe BigCrush ( la partie la plus difficile de la suite de tests TestU01 ), malgré l’échec du Twister ( papier PCG, fig. 2 ). Compte tenu de cela et de la faiblesse des preuves que j’ai pu trouver à l’appui de Mersenne Twister, qu’est - ce qui a attiré l’attention sur son choix par rapport aux autres choix?

Ce n'est pas purement historique non plus. On m'a dit en passant que le Twister Mersenne était au moins plus éprouvé dans la pratique que, par exemple, PCG aléatoire . Mais les cas d'utilisation sont-ils si intelligents qu'ils peuvent faire mieux que nos batteries de tests? Certains Google suggèrent qu'ils ne le sont probablement pas.

En bref, je me demande comment le Twister Mersenne a obtenu sa réputation positive généralisée, à la fois dans son contexte historique et ailleurs. D'un côté, je suis évidemment sceptique quant à ses qualités, mais de l'autre, il est difficile d'imaginer qu'il s'agisse d'un événement entièrement aléatoire.

Veedrac
la source
2
Je pense que tu as raison. Mersenne Twister n'a rien de particulièrement spécial. C'est juste bien connu (et beaucoup d'autres PRNG bien connus se trouvent être pires). Il y a d'autres PRNG qui sont également très bons. Pour un PRNG encore meilleur, on peut utiliser un PRNG cryptographique. Je ne sais pas quel genre de réponse on peut donner, cependant, au-delà de "rien n’est pas faux avec votre raisonnement".
DW
1
Je pense que la question que vous devriez vous poser n’est pas de savoir si le MT est bon ou non, mais pourquoi il est plus utilisé que les alternatives telles que PCG ou XorShift. La réponse est probablement que cela dure depuis plus longtemps et qu’il s’agissait du meilleur manquement raisonnable depuis longtemps (au cours des années Internet).
Pseudonyme
1
@vzn "une autre considération est le temps de génération; la qualité de PRNGs se fait au détriment du temps d'exécution" → Sauf que le Mersenne Twister est plus lent et moins performant qu'un LCG d'une taille considérable. Voir la figure 16 dans le document PCG. (Pour savoir si j'ai lu le papier: j'ai lu la plupart des parties non mathématiques du papier de Mersenne Twister en détail et tout le papier aléatoire de PCG. J'ai surtout écrémé le troisième, cependant.)
Veedrac
1
Parlez-vous de XorShift ou des algorithmes KISS?
gnasher729
1
@ gnasher729 Je mentionne XorShift *, mais je ne suis pas vraiment spécifique à une alternative. Je ne connaissais pas KISS, FWIW.
Veedrac

Réponses:

15

La MT a été considérée comme bonne pendant quelques années, jusqu'à ce que les tests plus avancés TestU01 BigCrush et de meilleurs PRNGs aient révélé qu'elle était plutôt mauvaise.

Le tableau sur pcg-random.org donne, par exemple, un bon aperçu des caractéristiques de certains des PRNG les plus utilisés, où le seul "bon" avantage du Mersenne Twister est la grande période et la possibilité graine (résultats reproductibles), il réussit les tests simples et rapides TestU01 SmallCrush, mais échoue lors des tests de qualité statistique les plus récents, en particulier les suivants: LinearComp Test de TestU01 et les batteries Crush et BigCrush de TestU01.2219937

Cette page répertorie les fonctionnalités de Mersenne-Twister en détail:

Des qualités positives

  • Produit des nombres 32 bits ou 64 bits (donc utilisables comme source de bits aléatoires)
  • Passe la plupart des tests statistiques

Qualités Neutre

  • Période incroyablement énorme de22199371
  • 623 dimensions équidistribuées
  • La période peut être partitionnée pour émuler plusieurs flux

Qualités Négatives

  • Ne réussit pas certains tests statistiques, avec seulement 45 000 nombres.
  • Prévisible - après 624 sorties, nous pouvons prédire complètement sa sortie.
  • L'état du générateur occupe 2504 octets de RAM. En revanche, un générateur extrêmement utilisable avec une période d'utilisation plus importante que tout le monde peut contenir jusqu'à 8 octets de RAM.
  • Pas particulièrement rapide.
  • Pas particulièrement efficace en termes d'espace. Le générateur utilise 20000 bits pour stocker son état interne (20032 bits sur des machines 64 bits), mais a une période de seulement , un facteur 263 (ou 295) inférieur à celui d’un générateur idéal de la même taille.2219937
  • Inégale dans sa sortie; le générateur peut entrer dans des «mauvais états» dont la récupération est lente.
  • Les semis qui ne diffèrent que légèrement prennent beaucoup de temps à s'écarter l'un de l'autre; l'ensemencement doit être fait avec soin pour éviter les mauvais états.
  • Bien que le saut en avant soit possible, les algorithmes pour le faire sont lents à calculer (c’est-à-dire qu’ils nécessitent plusieurs secondes) et sont rarement fournis par les implémentations.

Résumé : Mersenne Twister n’est plus assez bon, mais la plupart des applications et des bibliothèques ne sont pas encore là.

rurban
la source
7
Merci pour le beau résumé! Toutefois, je suis préoccupé par le fait que la seule source apparente de votre message est un site Web qui est en réalité une publicité pour une autre famille de générateurs de nombres aléatoires qui n'a pas encore été évaluée par des pairs. Le site Web lui-même n'offre aucune référence pour les entrées, mais l'article proposé semble en contenir beaucoup. Par conséquent, je pense que vous pouvez améliorer votre réponse pour le contexte ici (critique de MT) en donnant des références pour les points individuels.
Raphaël
10
Est-ce qu'ils critiquent sérieusement le fait que la période n'est que de lieu de , et qu'après avoir déclaré qu'une longue période est une propriété "neutre" d'un processus? 2219937295×22199372219945
David Richerby
1
"Prévisible" - MT n'est pas conçu comme un PRNG cryptographique. Veuillez modifier votre réponse.
Jason S
"Mersenne Twister n'est plus assez bon": que recommande-t-on si la sécurité n'est pas une préoccupation, établir une graine est important et la rapidité l'est aussi? (Mersenne était assez rapide)
Martin Thoma
8

Je suis l'éditeur qui a accepté l'article de MT dans ACM TOMS en 1998 et je suis également le concepteur de TestU01. Je n'utilise pas MT, mais principalement MRG32k3a, MRG31k3p et LRSR113. Pour en savoir plus sur ceux-ci, sur MT et sur ce qu'il y a d'autre, vous pouvez consulter les articles suivants:

F. Panneton, P. L'Ecuyer et M. Matsumoto, `` Générateurs améliorés à longue période basés sur les récurrences linéaires Modulo 2 '', ACM Transactions on Mathematical Software, 32, 1 (2006), 1-16.

P. L'Ecuyer, «Génération de nombres aléatoires», chapitre 3 du Handbook of Computational Statistics, JE Gentle, W. Haerdle et Y. Mori, éd., Deuxième édition, 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 et R. Simard, «Nombres aléatoires pour ordinateurs parallèles: exigences et méthodes», Mathématiques et ordinateurs en simulation, 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

P. L'Ecuyer, "Génération de nombres aléatoires avec plusieurs flux pour ordinateurs séquentiels et parallèles", a invité le didacticiel avancé, Actes de la conférence de simulation de l'hiver 2015, IEEE Press, 2015, 31-44.

Pierre L'Ecuyer
la source
3
Merci pour votre réponse! Souhaitez-vous ajouter quelque chose à la question? 1) Pourquoi avez-vous pensé que MT était bon (ou du moins mérite d'être publié) alors? 2) Pourquoi ne pensez-vous pas que c'est assez bon pour être utilisé?
Raphaël
Merci d'avoir ajouté ce contexte historique précieux. Je suis également curieux de connaître les questions de Raphaël et votre opinion personnelle lorsque vous avez accepté le document.
Veedrac
5

Un peu comme les algorithmes de tri à cet égard, il n’existe pas de PRNG «taille unique». Différents sont utilisés à des fins différentes et il existe une grande variété de critères de conception et d'utilisations. Il est possible d’appliquer de manière incorrecte les PRNG, par exemple en utilisant un pour la cryptographie pour lequel il n’est pas conçu. L'entrée de Wikipédia sur Mersenne Twister mentionne également qu'il n'a pas été conçu pour les "simulations de Monte-Carlo nécessitant des générateurs de nombres aléatoires indépendants".

Comme indiqué sur Wikipedia, ce PRNG est en effet utilisé dans un grand nombre de langages de programmation et d’applications même comme PRNG par défaut. Il faudrait une analyse quasi sociologique pour expliquer pourquoi un seul PRNG est favorisé. Quelques facteurs possibles pouvant contribuer à ce PRNG:

  • L’auteur a de bonnes compétences scientifiques dans le domaine et travaille dans les GNRP depuis des décennies.

  • Il a été spécialement conçu pour être supérieur aux autres méthodes de l'époque.

  • L'auteur est engagé dans des implémentations et leur suivi, y contribuant également. Certains PRNG sont plus théoriques et les auteurs ne se préoccupent pas toujours des implémentations réelles.

  • Le système est bien pris en charge / mis à jour sur une page Web.

  • De nouvelles versions du PRNG ont été développées pour remédier aux faiblesses. Il n’existe pas un seul algorithme Mersenne Twister, c’est plutôt des versions différentes et une famille de variantes qui peuvent répondre à différents besoins.

  • Il a été analysé et testé de manière approfondie par un logiciel d'analyse aléatoire standard et adopté, par des autorités indépendantes.

  • Il existe un effet connu mesuré avec les sites Web et de nombreux autres contextes tels que les citations scientifiques appelées "attachement préférentiel" qui peuvent être mesurés. C’est essentiellement là où les sources historiques établies de longue date sont de plus en plus utilisées. Un tel effet pourrait expliquer les choix du PRNG au fil du temps.

En d'autres termes, vous parlez d'un phénomène de "popularité" associé et lié à des choix humains, qui n'est pas strictement lié à des qualités particulières, mais qui est une sorte de propriété complexe / émergente et d'interaction entre différents algorithmes, utilisateurs et environnement. / contextes d'utilisation.

Voici une telle analyse indépendante de l’algorithme Mersenne Twister - Un générateur de nombres pseudo-aléatoires et ses variantes de Jagannatam (15p). Le dernier paragraphe est essentiellement une réponse à votre question. citant seulement les 1 er quelques phrases:

Mersenne Twister est théoriquement prouvé être un bon PRNG, avec une longue période et une équidistribution élevée. Il est largement utilisé dans les domaines de la simulation et de la modulation. Les défauts constatés par les utilisateurs ont été corrigés par les inventeurs. MT a été mis à niveau pour être compatible avec les technologies émergentes des processeurs, telles que SIMD et les pipelines parallèles, dans sa version de SFMT.

vzn
la source
2
Merci. Certains de ce que vous dites semblent assez vagues, cependant, comme "Cela a été spécialement conçu pour être supérieur aux autres méthodes de l'époque". et "Il a été analysé et testé en détail par un logiciel d'analyse aléatoire standard et adopté, par des autorités indépendantes.", qui sont exactement les affirmations sur lesquelles je me méfie. Je vais plonger un peu dans le journal, cependant, pour voir si cela clarifie les choses.
Veedrac
Une autre chose à prendre en compte est la reproductibilité scientifique. De nombreux scientifiques travaillant dans la zone de simulation de Monte-Carlo ont beaucoup de mal à s’assurer que le programme dans son ensemble produit le même résultat avec la même graine, quel que soit le nombre de threads. Nombre d'entre eux exigent une compatibilité de bogue à bogue avec la mise en œuvre de référence du PRNG.
Pseudonyme
2
Vous dites également: "Les nouvelles versions du PRNG ont été développées pour traiter les faiblesses.", Mais étant donné que la plupart des implémentations sont la première version au standard standard, cela ressemble davantage à une critique. Je suis aussi un peu surpris de voir que "le système est bien pris en charge / mis à jour sur une page Web". - de combien de soutien une GCL a-t-elle vraiment besoin!?
Veedrac
@ Pseudonym, je ne suis pas vraiment. Pourquoi cela empêcherait-il d'utiliser un générateur différent? Évidemment, vous devez utiliser le même générateur lorsque vous relancez des tests, mais pourquoi pour de nouveaux tests?
Veedrac
toutes les analyses scientifiques dans les articles originaux et suivants ne semblent pas très floues et la question initiale est quelque peu "chargée" de cette manière (autant que de nombreux PRNG avec moins d’analyses / supports sont utilisés). Concernant les pseudonymes, autant que je sache, tous les PRNG sont reproductibles en utilisant les mêmes germes de départ, seuls les générateurs basés sur du matériel ne le sont pas (et ils ne sont plus vraiment des PRNG, mais un "bruit physique réel / aléatoire"). Je ne sais pas trop comment cela est censé être difficile à assurer avec plusieurs threads (je ne sais pas pourquoi des threads séparés ne
peuvent