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

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 x₀ que tenga 2n cifras.

El algoritmo en reglas generales consiste en los siguientes pasos:

1. Coger un valor inicial denominado semilla x₀ de 4 dígitos.
2. Elevar dicho número al cuadrado x_²0 y obtener sus 4 cifras centrales x₁.
3. Se genera 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:

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 aX_k+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 x₀ = 17, a = 6, b = 5, m = 38

xk	a	b	axk+b	m	mod m	x{k+1}
17	7	5	124	36	16	16
16			117		9	9
9			68		32	32
32			229		13	13
13			96		24	24
24			173		29	29
29			208		28	28
28			201		21	21
21			152		8	8
8			61		25	25
25			180		0	0
0			5		5	5
5			40		4	4
4			33		33	33
33			236		20	20
20			145		1	1
1			12		12	12
12			89		17	17
17			124		16	16
16			117		9	9

Los números pseudoaleatorios, los obtenemos:

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:

Donde:

• M = 2^m , 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 (2^k – 1) * 2^m-1, y además puede generar hasta 2^k-1 * 2^m-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. (M_n = 2^m-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 2¹⁹⁹³⁷ – 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:

• Las Matemáticas del Machine Learning ¿Qué debo saber?
• Las Matemáticas del Machine Learning: explicando la Regresión Lineal (I)
• Las Matemáticas del Machine Learning: Ejemplos de Regresión Lineal (II) y Multilineal.
• Las Matemáticas del Machine Learning: Ejemplos de Regresión Lineal (III) y Multilineal. Contraste y Fiabilidad.
• Las Matemáticas del Machine Learning: Ejemplos Regresión Lineal (IV y último). Implementación en lenguaje R
• Las Matemáticas del Machine Learning: Redes Neuronales (Parte I)
• Las Matemáticas del Machine Learning: Redes Neuronales (Parte II)
• Las matemáticas del Machine Learning: Funciones de activación
• Las matemáticas del Machine Learning: el mecanismo de Backpropagation
• Las matemáticas del Machine Learning: Números aleatorios y dónde encontrarlos (Parte I)

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).