Cenni teorici sulla generazione di numeri casuali

La generazione di numeri casuali risulta di fondamentale importanza nel machine learning e all’interno degli algoritmi di training. Quando i numeri casuali sono generati da un computer, essi vengono definiti pseudo casuali(PRNG – Pseudo Random Number Generator). Il termine “pseudo” deriva dal fatto che il computer è una macchia logicamente programmata che esegue delle istruzioni che possono solo simulare la casualità. Nonostante questa limitazione logica, i computer sono molto efficienti nella generazione di numeri casuali. Al fine di valutare la capacità di generare i numeri casuali si utilizzano due criteri:

  • Casualità
  • Sicurezza

Ai fini dell’applicazione all’intelligenza artificiale occorre tenere in considerazione la prima proprietà, la casualità. Il secondo criterio è molto importante per scopi crittografici; la generazione di numeri casuali per la crittografia prende il nome di CSPRNG(Cryptographically Secure Psedorandom Number Generator).
La generazione di numeri casuali produce una sequenza di numeri suddivisi in periodi. Ogni singolo periodo identifica una sequenza non ripetuta di numeri all’interno della sequenza totale. Il criterio di casualità è calcolato in base alla sequenza di numeri non casuali che identificano il singolo periodo.
A questo punto risulta importante identificare le differenze tra un PRNG e un CSPRNG; entrambi possiedono uno stato interno (internal state); nel caso in cui si venisse a conoscenza dello stato interno, si potrebbero prevedere tutti i numeri “casuali” successivi. La prima differenza tra i due generatori di numeri casuali è che con il PRNG è possibile rilevare lo stato interno analizzando la sequenza dei numeri generati, mentre, con il CSPRNG non è possibile rilevare lo stato interno se non dopo lunghissime analisi temporali dei numeri casuali.

Concetti sul PRNG

Esistono numerosi concetti importanti circa la PRNG. Questi concetti influiscono pesantemente sulla qualità dell’output fornito dall’algoritmo.

  • Seed(seme)
  • Iternal State(stato interno)
  • Period(periodo)

Il seed indentifica lo stato di partenza che l’algoritmo di generazione di numeri casuali deve assumere. Generando numeri casuali partendo dallo stesso seed, questi assumeranno la stessa sequenza; per questo motivo, generalmente, viene utilizzato un timestamp come seed.
L’internal state è composto dalle variabili che l’algoritmo di PRNG usa per generare i successivi numeri casuali. Infine, il periodo, è caratterizzato dalla lunghezza di ogni sequenza di numeri casuali. Raggiunto il limite del perido, l’algoritmo riprende a generare numeri casuali seguendo la sequenza precedente.

Tipi di distribuzione di numeri casuali

Generalmente, quando abbiamo la necessità di lavorare con numeri casuali, cerchiamo di ottenere dei valori ripetuti con la stessa frequenza, quindi, uniformemente distribuiti. La PRNG fornisce valori compresi tra 0 ed 1 tutti con la stessa probabilità.

Come è possibile notare, tutti i valori intermedi tra 0 ed 1 hanno all’incirca la stessa frequenza, questo comportamento viene chiamato “distribuzione uniforme”. Ovviamente è possibile scalare questi numeri a dei valori da noi desiderati, lavorando similmente alla normalizzazione:

random(min, max) = uniform_random()*(max-min)+min;

Attraverso questa equazione è possibile ottenere una distribuzione uniforme di numeri casuali con qualsiasi range.
In alcuni casi specifici risulta essere necessario generare numeri casuali che differiscano tra di loro di poche unità, in questo caso viene utilizzata la “distribuzione normale dei numeri casuali”.

Chiamata anche distribuzione Gaussiana, incrementa la probabilità di estrazione dei numeri prossimi allo 0. Ogni numero intero rappresenta la deviazione standard. Come mostrato dall’immagine i numeri prossimi ai margini del range hanno una probabilità molto bassa di essere estratti.
Di seguito una piccola implementazione in Python:

import matplotlib.pyplot as plt
import numpy as np
randoms = np.random.randn(10000)
plt.hist(test,25)
plt.show()

Alcuni linguaggi di programmazione non forniscono questo tipo di generazione di numeri casuali. Per sopperire a tale mancanza si utilizza la trasformazione di Box Muller che trasforma la generazione uniformemente distribuita nella generazione normalmente distribuita.

Roulette Wheel

Questa tecnica di generazione di numeri casuali consiste nella simulazione della roulette da casinò, impostando una percentuale di riuscita per ogni scelta. La Roulette Wheel è applicabile quando si ha la necessità di scegliere tra tre o più categorie.
Analizziamo un caso pratico; occorre generare dei numeri casuali che selezionino una delle tre categorie sottostanti assegnando loro una certa probabilità di estrazione:

  • Categoria 1( 80% )
  • Categoria 2( 10% )
  • Categoria 3( 10% )

Utilizzando la generazione dei numeri casuali uniformemente distribuiti( valori compresi tra 0 – 1 ) generiamo i numeri randomici e filtramoli attraverso dei semplici “if”, dove le condizioni di verità sono condizionate dalle percentuali di estrazione per ogni categoria:

if(0 < x < 0.8) Categoria 1
if(0.8 < x < 0.9) Categoria 2
if(0.9 < x < 1) Categoria 3

Algoritmi PRNG

Esistono differenti algoritmi di generazione di numeri casuali. Essi differiscono tra loro in base a due proprietà fondamentali, cuasualità e tempi di esecuzione.
Di seguito alcuni dei più importanti:

  • Linear Congruential Generator(Generatore Linear Congruenziale)
  • Multiply With Carry
  • Mersenne Twister[Coming Soon]
Linear Congruential Generator

Il generatore lineare congruenziale, meglio conosciuto come LCG, è uno degli algoritmi più utilizzati; esso infatti presenta in quasi tutti i linguaggi di sviluppo la sua relativa implementazione.
Questo algoritmo non è consigliato quando si ha la necessità di ottenere un elevata casualità dei numeri. L’equazione che descrive questo algoritmo è la seguente:

Di seguito vengono descritti i range applicabili per ogni variabile:

  •  m, 0 < m, Il modulo
  • a, 0 < a < m, Il moltiplicatore
  • c, 0 < c < c, L’incremento
  • X0, 0 <= X0 < m, Il seme(seed)

Ad ogni iterazione il seme viene aggiornato per la creazione di numeri casuali successivi,quindi, il seed successivo indica lo stato interno dell’algoritmo. I valori scelti per le variabili m, a e c hanno un forte impatto sulla casualità dei numeri generati da questa PRNG.

Di seguito una implementazione python di un LCG:

'''
Generatore lineare congruenziale(LCG)
Link: https://it.wikipedia.org/wiki/Generatore_lineare_congruenziale
Workflow image: https://upload.wikimedia.org/wikipedia/commons/0/02/Linear_congruential_generator_visualisation.svg
'''
 
import matplotlib.pyplot as plt
 
#Dichiaro il moltplicatore
a = 3
#Dichiaro l'incremento
c = 6
#Dichiaro il modulo
m = 5
#Dichiaro il seme(seed)
seed = 1
#Dichiaro le variabili temporanee per la modifica del seme per ogni iterazione
next_seed = 0
prev_seed = seed;
#Dichiaro il contenitore dei numeri casuali
randoms = []
 
for index in range(0,16):
    next_seed = (a * prev_seed + c) % m
    prev_seed = next_seed
 
    randoms.append(next_seed)
 
plt.plot(randoms)
plt.show()
Multiply With Carry

Questo algoritmo, conosciuto anche come MWC fu inventato da George Marsaglia al fine di generare numeri casuali con lunghi periodi. Il vantaggio di utilizzare MWC consiste nel fatto che esso lavora con operazioni matematiche tra interi il che aumenta la velocità di creazione di numeri casuali. Esso assomiglia molto all’algoritmo generatore di numeri lineari congruenziali, difatti utilizza il modulo ed il moltiplicatore.Di seguito l’equazione che genera numeri casuali secondo l’algoritmo MWC:

Il moltiplicatore è identificato dalla variabile a, mentre il modulo dalla variabile b.

Di seguito una implementazione python di un MWC:

'''
Multiply With Carry(MWC)
Link: https://en.wikipedia.org/wiki/Multiply-with-carry
'''
import random
#Definisco il buffer di elementi
max_Sequence_Elements = 100;
#Definisco il lag
r = 1
#Dichiaro il modulo o base
b = 2000
#Definisco il moltiplicatore
a = 122
 
carry =[0]*max_Sequence_Elements
seed = [0]*max_Sequence_Elements
 
carry[0] = random.randint(0,a)
seed[0] = r
 
print seed[0]
for index in range(1,max_Sequence_Elements):
    seed[index] = (a*seed[index-r]+carry[index-1]) % b
    carry[index] = (a*seed[index-r]+carry[index-1]) / b
    print seed[index]

Lascia un commento