¿Por qué se considera que el Mersenne Twister es bueno?

El Mersenne Twister es ampliamente considerado como bueno. Diablos, la fuente de CPython dice que "es uno de los generadores más ampliamente probados que existen". Pero ¿qué significa esto? Cuando se me pide que enumere las propiedades de este generador, la mayoría de lo que puedo ofrecer es malo:

Es masivo e inflexible (por ejemplo, sin búsqueda o múltiples flujos),
No pasa las pruebas estadísticas estándar a pesar de su tamaño de estado masivo,
Tiene serios problemas alrededor de 0, lo que sugiere que se aleatoriza bastante mal,
No es rapido

y así. En comparación con los RNG simples como XorShift *, también es irremediablemente complicado.

Así que busqué información sobre por qué se pensó que esto era bueno. El artículo original hace muchos comentarios sobre el período "súper astronómico" y la equidistribución de 623 dimensiones, diciendo

Entre muchas medidas conocidas, las pruebas basadas en la uniformidad dimensional más alta, como la prueba espectral (cf, Knuth [1981]) y la prueba de distribución k, descritas a continuación, se consideran más fuertes.

Pero, para esta propiedad, ¡el generador es golpeado por un contador de longitud suficiente! Esto no hace ningún comentario sobre las distribuciones locales , que es lo que realmente le importa en un generador (aunque "local" puede significar varias cosas). E incluso los CSPRNG no se preocupan por períodos tan largos, ya que simplemente no es remotamente importante.

Hay muchas matemáticas en el documento, pero hasta donde puedo decir poco, en realidad se trata de la calidad de la aleatoriedad. Casi cada mención de eso salta rápidamente a estas afirmaciones originales, en gran medida inútiles.

Parece que la gente se subió a este carro a expensas de tecnologías más antiguas y confiables. Por ejemplo, si simplemente sube el número de palabras en un LCG a 3 (mucho menos que el "solo 624" de un Mersenne Twister) y genera la palabra superior en cada pase, pasa BigCrush ( la parte más difícil del conjunto de pruebas TestU01 ), a pesar de que Twister falla ( papel PCG, fig. 2 ). Teniendo en cuenta esto, y la evidencia débil pude encontrar en apoyo del Mersenne Twister, lo que hizo causa atención a lo favorecen sobre las otras opciones?

Esto tampoco es puramente histórico. Me han dicho de pasada que el Mersenne Twister está al menos más probado en la práctica que, por ejemplo, PCG al azar . ¿Pero los casos de uso son tan exigentes que pueden funcionar mejor que nuestras baterías de pruebas? Algunos Google sugieren que probablemente no lo sean.

En resumen, me pregunto cómo el Mersenne Twister obtuvo su reputación positiva generalizada, tanto en su contexto histórico como de otro tipo. Obviamente, por un lado, soy escéptico sobre sus cualidades, pero por otro lado, es difícil imaginar que se haya producido de forma totalmente aleatoria.

algorithms randomness sampling pseudo-random-generators Veedrac
fuente

Creo que tienes razón. Mersenne Twister no es nada particularmente especial. Es simplemente conocido (y muchos de los otros PRNG conocidos son peores). Hay otros PRNG que también son bastante buenos. Para un PRNG aún mejor, uno puede usar un PRNG criptográfico. Sin embargo, no estoy seguro de qué tipo de respuesta se puede dar, más allá de "no hay nada malo con su razonamiento".

Creo que la pregunta que debe hacerse no es si la MT es buena (ya que, según muchas métricas), sino por qué se usa con más frecuencia que las alternativas como PCG o XorShift. La respuesta es probablemente que ha existido por más tiempo y fue el mejor valor predeterminado razonable durante mucho tiempo (en años de Internet).

Seudónimo el

@vzn "otra consideración es el tiempo de generación; la" calidad "de los PRNG viene a expensas del tiempo de ejecución" → Excepto que el Mersenne Twister es más lento y peor que un LCG razonablemente grande. Vea la Fig. 16 en el documento PCG. (Acerca de si he leído el documento: he leído la mayoría de las partes no matemáticas del documento de Mersenne Twister en detalle y todo el documento aleatorio de PCG. Sin embargo, en su mayoría leí el tercero.)

Veedrac

¿Estás hablando de XorShift o los algoritmos KISS?

gnasher729

@ gnasher729 Menciono XorShift *, pero realmente no estoy siendo específico para una alternativa en particular. No sabía sobre KISS, FWIW.

Veedrac

Respuestas:

El MT se consideró bueno durante algunos años, hasta que se descubrió que era bastante malo con las pruebas TestU01 BigCrush más avanzadas y mejores PRNG.

La tabla en pcg-random.org, por ejemplo, ofrece una buena visión general de las características de algunos de los PRNG más utilizados, donde la única característica "buena" del Mersenne Twister es el gran período, y la posibilidad de usar una semilla (Reproducible Resultados), pasa las pruebas simples y rápidas TestU01 SmallCrush, pero falla algunas de las nuevas pruebas de calidad estadística, especialmente. Test LinearComp de TestU01 y las baterías Crush y BigCrush de TestU01. $2^{219937}$

Esta página enumera las características de Mersenne-Twister en detalle:

Cualidades positivas

Produce números de 32 bits o 64 bits (por lo tanto utilizable como fuente de bits aleatorios)
Pasa la mayoría de las pruebas estadísticas

Cualidades neutrales

Período grande de $2^{219937} - 1$
623 dimensionalmente equidistribuido
El período se puede dividir para emular múltiples transmisiones

Cualidades negativas

No pasa algunas pruebas estadísticas, con tan solo 45,000 números.
Predecible: después de 624 salidas, podemos predecir completamente su salida.
El estado del generador ocupa 2504 bytes de RAM; en contraste, un generador extremadamente utilizable con un período más grande que cualquiera puede usar puede caber en 8 bytes de RAM.
No particularmente rápido.
$2^{219937}$
Desigual en su salida; el generador puede entrar en "malos estados" de los que es lento recuperarse.
Las semillas que solo difieren un poco tardan mucho en divergir unas de otras; la siembra debe hacerse con cuidado para evitar malos estados.
Si bien es posible avanzar, los algoritmos para hacerlo son lentos de computar (es decir, requieren varios segundos) y rara vez los proporcionan las implementaciones.

Resumen : Mersenne Twister ya no es lo suficientemente bueno, pero la mayoría de las aplicaciones y bibliotecas aún no existen.

rurban
fuente

Gracias por el bonito resumen! Sin embargo, me preocupa que la única fuente aparente para su publicación es un sitio web que es efectivamente un anuncio para otra familia de generadores de números aleatorios que aún no ha sido revisado por pares. El sitio web en sí no ofrece ninguna referencia para las entradas, pero el artículo propuesto parece contener muchas. Por lo tanto, creo que puede mejorar su respuesta para el contexto aquí (crítica de MT) dando referencias para los puntos individuales.

Raphael

2^{219937}

$2^{219937}$

295 \times 2^{219937} \approx 2^{219945}

$295\times 2^{219937} \approx 2^{219945}$

"Predecible" - MT no está pensado como un PRNG criptográfico, así que edite su respuesta.

Jason S

"Mersenne Twister ya no es lo suficientemente bueno": ¿qué se recomienda si la seguridad no es una preocupación, establecer una semilla es importante y la velocidad también es importante? (Mersenne fue lo suficientemente rápido)

Martin Thoma hace

Soy el editor que aceptó el artículo de MT en ACM TOMS en 1998 y también soy el diseñador de TestU01. No uso MT, pero principalmente MRG32k3a, MRG31k3p y LRSR113. Para saber más sobre estos, sobre MT y sobre qué más hay, puede consultar los siguientes documentos:

F. Panneton, P. L'Ecuyer y M. Matsumoto, `` Generadores de período largo mejorados basados en recurrencias lineales Módulo 2 '', Transacciones de ACM en software matemático, 32, 1 (2006), 1-16.

P. L'Ecuyer, `` Generación de números aleatorios '', capítulo 3 del Manual de estadísticas computacionales, JE Gentle, W. Haerdle e Y. Mori, eds., Segunda edición, 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 y R. Simard, `` Números aleatorios para computadoras paralelas: requisitos y métodos '', Matemáticas y computadoras en simulación, 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

P. L'Ecuyer, `` Generación de números aleatorios con múltiples flujos para computadoras secuenciales y paralelas '', invitó a un tutorial avanzado, Actas de la Conferencia de simulación de invierno 2015, IEEE Press, 2015, 31-44.

Pierre L'Ecuyer
fuente

¡Gracias por tu respuesta! ¿Te importaría agregar algo a la pregunta? 1) ¿Por qué creías que MT era bueno (o al menos valía la pena publicar) entonces? 2) ¿Por qué no crees que es lo suficientemente bueno para usar?

Raphael

Gracias por agregar ese valioso contexto histórico. También tengo curiosidad por las preguntas de Raphael y sus pensamientos personales cuando aceptó el documento.

Veedrac

Algo parecido a los algoritmos de clasificación en este sentido, no existe un PRNG de "talla única". Se utilizan diferentes para diferentes propósitos y existe una amplia variedad de criterios de diseño y usos. Es posible aplicar incorrectamente los PRNG, como usar uno para criptografía para el que no está diseñado. La entrada de Wikipedia sobre Mersenne Twister también menciona que no fue diseñada para "simulaciones de Monte-Carlo que requieren generadores independientes de números aleatorios".

Como se señaló en Wikipedia, este PRNG se usa en una gran cantidad de lenguajes de programación y aplicaciones, incluso como un PRNG predeterminado. Se necesitaría un análisis casi sociológico para explicar por qué se prefiere un PRNG. Algunos posibles factores que pueden estar contribuyendo a este PRNG:

El autor tiene credenciales científicas buenas / fuertes en el área y ha estado trabajando en PRNG durante décadas.
Fue diseñado específicamente para ser superior a otros métodos en el momento.
El autor participa en implementaciones y las rastrea, contribuyendo también a ellas. Algunas PRNG son más teóricas y los autores no siempre se preocupan por las implementaciones reales.
El sistema está bien soportado / actualizado en una página web.
Se han desarrollado nuevas versiones de PRNG para hacer frente a las debilidades. No hay un solo algoritmo Mersenne Twister, es más como versiones diferentes y una familia de variantes que pueden manejar diferentes necesidades.
Ha sido ampliamente analizado / probado por un software estándar de análisis de aleatoriedad y aprobado por autoridades independientes.
Existe un efecto conocido medido para sitios web y muchos otros contextos, como citas científicas llamadas "apego preferencial", que pueden medirse. Básicamente es donde las fuentes históricas establecidas desde hace mucho tiempo acumulan un mayor uso. Tal efecto podría explicar las opciones de PRNG con el tiempo.

En otras palabras, usted está preguntando acerca de un fenómeno de "popularidad" que está asociado e interrelacionado con las elecciones humanas y no está estrictamente vinculado a cualidades particulares, sino que es una especie de propiedad compleja / emergente y la interacción entre diferentes algoritmos, usuarios y entorno. / contextos de uso.

Aquí hay uno de esos análisis independientes del algoritmo Mersenne Twister: un generador de números pseudoaleatorios y sus variantes de Jagannatam (15p). El párrafo final es esencialmente una respuesta a su pregunta. citando solo las ^primeras frases:

Mersenne Twister está teóricamente demostrado que es un buen PRNG, con un largo período y una alta equidistribución. Se usa ampliamente en los campos de simulación y modulación. Los defectos encontrados por los usuarios han sido corregidos por los inventores. MT se ha actualizado para usar y ser compatible con las nuevas tecnologías emergentes de CPU como SIMD y tuberías paralelas en su versión de SFMT.

vzn
fuente

Gracias. Sin embargo, parte de lo que dice parece bastante vago, como "Fue diseñado específicamente para ser superior a otros métodos en ese momento". y "Ha sido ampliamente analizado / probado por un software de análisis de aleatoriedad estándar y aprobado por autoridades independientes", que son exactamente las afirmaciones de las que sospecho. Sin embargo, me sumergiré un poco en el periódico para ver si eso aclara las cosas.

Veedrac

Otra cosa a tener en cuenta es la reproducibilidad científica. Muchos científicos que trabajan en el área de simulación de Monte Carlo se toman muchas molestias para asegurarse de que el programa en su conjunto produzca la misma salida dada la misma semilla, independientemente de la cantidad de hilos. Muchos de ellos requieren compatibilidad de error por error con la implementación de referencia del PRNG.

Seudónimo

También dice: "Se han desarrollado nuevas versiones de PRNG para tratar las debilidades", pero dado que la mayoría de las implementaciones son la primera versión de bog-standard, esto me parece más una crítica. También estoy un poco sorprendido de ver "El sistema está bien soportado / actualizado en una página web". - ¿Cuánto apoyo necesita realmente un LCG?

Veedrac

@ Seudónimo Realmente no sigo. ¿Por qué eso impediría usar un generador diferente? Obviamente, debe usar el mismo generador cuando vuelva a ejecutar las pruebas, pero ¿por qué realizar nuevas pruebas?

Veedrac

no parece haber mucha imprecisión sobre todos los análisis científicos en los trabajos originales y posteriores, y la pregunta original está algo "cargada" de esta manera (afaik se usan muchos PRNG con menos análisis / apoyo). En cuanto a los seudónimos, afaik todos los PRNG son repetibles utilizando las mismas semillas iniciales, solo los generadores basados en hardware no lo son (y ya no son realmente PRNG sino "ruido / aleatoriedad física real"). no estoy seguro de cómo esto es supuestamente difícil de asegurar con múltiples hilos (no sé por qué hilos separados no pueden usar un algoritmo idéntico con diferentes semillas)

vzn