c++ - number - mersenne twister python

Mersenne twister calentamiento vs. reproducibilidad

Question

En mi proyecto actual de C ++ 11, necesito realizar simulaciones M. Para cada simulación m = 1, ..., M , genero aleatoriamente un conjunto de datos utilizando un objeto std::mt19937 , construido de la siguiente manera:

std::mt19937 generator(m);
DatasetFactory dsf(generator);

De acuerdo con https://stackoverflow.com/a/15509942/1849221 y https://stackoverflow.com/a/14924350/1849221 , el PRNG de Mersenne Twister se beneficia de una fase de calentamiento, que actualmente está ausente en mi código. Informo por conveniencia el fragmento de código propuesto:

#include <random>
std::mt19937 get_prng() {
std::uint_least32_t seed_data[std::mt19937::state_size];
std::random_device r;
std::generate_n(seed_data, std::mt19937::state_size, std::ref(r));
std::seed_seq q(std::begin(seed_data), std::end(seed_data));
return std::mt19937{q};
}

El problema en mi caso es que necesito reproducibilidad de los resultados, es decir, entre las diferentes ejecuciones, para cada simulación, el conjunto de datos debe ser el mismo. Esa es la razón por la cual en mi solución actual uso la simulación actual para sembrar Mersenne Twister PRNG. Me parece que el uso de std::random_device impide que los datos sean los mismos (AFAIK, este es el propósito exacto de std::random_device ).

EDITAR: por diferentes ejecuciones me refiero a relanzar el ejecutable.

¿Cómo puedo introducir la fase de calentamiento antes mencionada en mi código sin afectar la reproducibilidad? Gracias.

Posible solución # 1

Aquí hay una implementación tentativa basada en la segunda propuesta de @SteveJessop

#include <random>
std::mt19937 get_generator(unsigned int seed) {
std::minstd_rand0 lc_generator(seed);
std::uint_least32_t seed_data[std::mt19937::state_size];
std::generate_n(seed_data, std::mt19937::state_size, std::ref(lc_generator));
std::seed_seq q(std::begin(seed_data), std::end(seed_data));
return std::mt19937{q};
}

Posible solución # 2

Aquí hay una implementación tentativa basada en la contribución conjunta de @SteveJassop y @ AndréNeve. La función sha256 está adaptada de https://stackoverflow.com/a/10632725/1849221

#include <openssl/sha.h>
#include <sstream>
#include <iomanip>
#include <random>
std::string sha256(const std::string str) {
unsigned char hash[SHA256_DIGEST_LENGTH];
SHA256_CTX sha256;
SHA256_Init(&sha256);
SHA256_Update(&sha256, str.c_str(), str.size());
SHA256_Final(hash, &sha256);
std::stringstream ss;
for(int i = 0; i < SHA256_DIGEST_LENGTH; i++)
ss << std::hex << std::setw(2) << std::setfill(''0'') << (int)hash[i];
return ss.str();
}
std::mt19937 get_generator(unsigned int seed) {
std::string seed_str = sha256(std::to_string(seed));
std::seed_seq q(seed_str.begin(), seed_str.end());
return std::mt19937{q};
}

Compilar con: -I/opt/ssl/include/ -L/opt/ssl/lib/ -lcrypto

Answer 1

Creo que solo necesita almacenar el inicial inicial (en su caso, la std::uint_least32_t seed_data[std::mt19937::state_size] ) y el número n de pasos de preparación que realizó (por ejemplo, utilizando discard(n) como mencionado) para cada ejecución / simulación que desea reproducir.

Con esta información, siempre puedes crear una nueva instancia de MT, seed_data con seed_data anterior y ejecutarla para los mismos n pasos de calentamiento. Esto generará la misma secuencia de valores en adelante ya que la instancia de MT tendrá el mismo estado interno cuando termine el calentamiento.

Cuando mencionas el std::random_device afecta la reproducibilidad, creo que en tu código simplemente se está utilizando para generar los datos de std::random_device . Si lo estuvieras usando como fuente de números aleatorios, entonces no podrías tener resultados reproducibles. Como lo está utilizando solo para generar la semilla, no debería haber ningún problema. ¡Simplemente no puede generar una nueva semilla cada vez que quiera reproducir valores!

De la definición de std::random_device :

"std :: random_device es un generador de números aleatorios enteros uniformemente distribuidos que produce números aleatorios no deterministas".

Entonces, si no es determinista, no puedes reproducir la secuencia de valores que produce. Una vez dicho esto, utilícelo simplemente para generar buenas semillas aleatorias solo para almacenarlas luego para las repeticiones.

Espero que esto ayude

EDITAR:

Después de discutir con @SteveJessop, llegamos a la conclusión de que un hash simple del conjunto de datos (o parte de él) sería suficiente para usarlo como una semilla decente para el propósito que necesita. Esto permite una forma determinística de generar las mismas semillas cada vez que ejecuta sus simulaciones. Como mencionó @Steve, deberá garantizar que el tamaño del hash no sea demasiado pequeño en comparación con std::mt19937::state_size . Si es demasiado pequeño, puede concatenar los hashes de m, m + M, m + 2M, ... hasta que tenga suficientes datos, como sugirió.

Estoy publicando la respuesta actualizada aquí, ya que la idea de utilizar un hash fue mía, pero votaré la respuesta de @ SteveJessop porque él contribuyó.

Answer 2

Dos opciones:

1. Siga la propuesta que tiene, pero en lugar de usar std::random_device r; para generar su secuencia de semillas para MT, use un PRNG diferente sembrado con m . Elija uno que no sufra como MT por necesitar un calentamiento cuando se usa con datos de semilla pequeños: sospecho que un LCG probablemente lo haga. Para una sobrecarga masiva, incluso podría usar un PRNG basado en un hash seguro. Esto es muy parecido a "estiramiento de teclas" en la criptografía, si es que has oído hablar de eso. De hecho, podría utilizar un algoritmo de extensión de clave estándar, pero lo está usando para generar una secuencia de inicialización larga en lugar de un material de clave grande.

2. Continúe usando m para inicializar su MT, pero discard una gran cantidad constante de datos antes de comenzar la simulación. Es decir, ignore el consejo de usar una semilla fuerte y en su lugar ejecute el MT el tiempo suficiente para que alcance un estado interno decente. No sé de antemano cuántos datos necesita descartar, pero espero que Internet sí.

Answer 3

Un comentario en una de las respuestas que enlazas indica:

Casualmente, el C ++ 11 seed_seq predeterminado es la secuencia de calentamiento de Mersenne Twister (aunque las implementaciones existentes, por ejemplo, mt19937 de libc ++, usan un calentamiento más simple cuando se proporciona una semilla de un solo valor)

Por lo tanto, es posible que pueda usar sus semillas fijas actuales con std::seed_seq para hacer el calentamiento para usted.

std::mt19937 get_prng(int seed) {
std::seed_seq q{seed, maybe, some, extra, fixed, values};
return std::mt19937{q};
}