Las matemáticas del Machine Learning: Números aleatorios y dónde encontrarlos (II)

Fran Ramírez    24 febrero, 2021
Aleatorios

En el artículo anterior mencionamos la importancia que tienen en nuestro día a día los números aleatorios, utilizados para realizar cualquier tipo de simulación y fundamentales a la hora de la seguridad en un mundo cada vez más digital. Sabemos que su origen se remonta al principio de los tiempos, y su evolución ha sido constante desde entonces. No obstante para conseguir una secuencia de números aleatorios necesitaremos un determinado algoritmo determinista el cual asemeje su secuencia a una realmente aleatoria. Dichos algoritmos reciben el nombre de generadores de números pseudo-aleatorios. En este artículo nombraremos algunos de ellos y su importancia a lo largo de nuestra historia.

Fueron Maurice Kendall y Bernard Babington-Smith a finales de los años 30 quienes nos aportaron nada más y nada menos que 100.000 dígitos completamente aleatorios, una cifra que en aquella época era todo un logro, y que hasta que Rand Corporation en 1955 publicó un millón de dígitos fueron ampliamente utilizados en diferentes campos de investigación. Pero podríamos afirmar que los grandes impulsores de los números aleatorios fueron Von Neumann, Metropolis, Ulam y Lehmer, quienes con sus diferentes métodos revolucionaron el mundo de lo aleatorio.

El método MidSquare

Durante los años 40, John Von Neumann y Nicholas Metropolis desarrollaron el método de los cuadrados medios, Mid-square Method. Originalmente dicho método era para poder generar números pseudoaleatorios de 4 dígitos, aunque bien es cierto que el algoritmo también funciona si introducimos un valor inicial x0 que tenga 2n cifras.

El algoritmo en reglas generales consiste en los siguientes pasos:

  1. Coger un valor inicial denominado semilla x0 de 4 dígitos.
  2. Elevar dicho número al cuadrado x20 y obtener sus 4 cifras centrales x1.
  3. Se genera un número pseudoaleatorio:
Fórmula para generar un número pseudoaleatorio
Figura 1. Fórmula para generar un número pseudoaleatorio

4. Volver al paso 2 y repetir proceso.

Continuaremos repitiendo y obteniendo una sucesión hasta obtener un valor repetido, lo que producirá que la secuencia pase a ser cíclica y por tanto predecible completamente.

En el siguiente fichero PDF contiene un par de ejemplos obtenidos utilizando este método:

Métodos Congruenciales

Hoy en día, los métodos más utilizados para obtener una sucesión de números pseudo-aleatorios son mediante los generadores congruenciales lineales, (GLC), los cuales fueron introducidos en 1951 por Lehmer. Un generador GLC es un algoritmo que obtiene números pseudoaleatorios a través de una función lineal definida a trozos discontinua. La sucesión de números pseudoaleatorios se obtiene mediante la siguiente fórmula de recurrencia:

Fórmula de recurrencia.
Figura 2. Fórmula de recurrencia.

Donde m es un número natural, recibe el nombre de módulo, a es el multiplicador y b el incremento. Además tanto a como b son números naturales menores que el valor m.

Diremos que se trata de un generador congruencial lineal multiplicativo (GLMC) cuando b=0. Dicho generador también recibe el nombre de Generador de números pseudoaleatorios de Lehmer. En caso de que b sea no nulo diremos que el generador congruencial es mixto.

La secuencia de números generada será el residuo de la operación aXk+b entre m. Eso es lo que significa el operador mod. Por lo tanto los resultados del residuo de la división pueden ir desde 0 hasta m-1.

Veamos a continuación un ejemplo:

Consideramos x0 = 17, a = 6, b = 5, m = 38

xkabaxk+bmmod mx{k+1}
1775124361616
16  117 99
9  68 3232
32  229 1313
13  96 2424
24  173 2929
29  208 2828
28  201 2121
21  152 88
8  61 2525
25  180 00
0  5 55
5  40 44
4  33 3333
33  236 2020
20  145 11
1  12 1212
12  89 1717
17  124 1616
16  117 99

Los números pseudoaleatorios, los obtenemos:

Fórmula para obtener los números pseudoaleatorios.
Figura 3. Fórmula para obtener los números pseudoaleatorios.

Otros métodos de la actualidad

Uno de las variantes de los métodos congruenciales evolucionados de los métodos congruenciales lineales de Lehmer es el conocido como Generador Lagger-Fibonacci. El nombre es por la familiaridad con la famosa serie de Fibonacci. La serie de recurrencia viene dada por la siguiente expresión:

Fórmula para la serie de recurrencia.
Figura 4. Fórmula para la serie de recurrencia.

Donde:

  • M = 2m , siendo m cualquier entero positivo.
  • ⊗ es cualquier operador binario como + , – , * …
  • 0 < J < k < n

Entre sus características podemos destacar que el máximo periodo generado puede ser (2k – 1) * 2m-1, y además puede generar hasta 2k-1 * 2m-1 ciclos diferentes con periodo máximo.

Otro generador muy utilizado por su alta calidad es el generador Mersenne twister que fue desarrollado por Makoto Matsumoto y Takuji Nishimura en 1997. El nombre proviene de que su longitud del periodo proviene de un número primo de Mersenne. (Mn = 2m-1 – 1). Dicho generador es utilizado a día de hoy en programas como Python, Ruby, Excel, C++, Mathlab entre otros, pues puede generar un periodo de 219937 – 1.

Nostalgia retro

Para terminar este artículo y como anécdota, durante los años 80 en tiempos del famoso Spectrum y Commodore 64, muchos de nosotros nos quedamos realmente maravillados ante la simpleza y la complejidad de los números aleatorios. En concreto, había una sola línea, en este caso para el BASIC de Commodore 64 que era la siguiente:

10 PRINT CHR$(205.5+RND(1)); : GOTO 10

Esta simple línea de código generaba maravillosos laberintos interminables. Muchos quedamos maravillados con lo que era posible generar simplemente con una sola linea de programación. Este simple programa define, como ningún otro, la maravillosa relación de los números aleatorios con la programación. Por cierto, hay incluso un libro (que podéis descargar desde aquí) hablando del impacto y lo maravilloso de esta simple línea de código.

Recuerda que este articulo es uno más de nuestra serie de Matemáticas del Machine Learning:

Escrito para LUCA por el matemático Fran Fenoll (@ffenoll16) y Fran Ramírez (@cyberhadesblog y @cybercaronte) del equipo de Ideas Locas CDCO de Telefónica).

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *