Come e perché i computer lanciano dadi caricati
Ecco un esercizio ingannevolmente semplice: inventare un numero di telefono casuale. Sette cifre in una sequenza, scelte in modo tale che ogni cifra sia ugualmente probabile e che la scelta di una cifra non influisca sulla successiva. Le probabilità sono che non puoi. (Ma non credetemi: gli studi degli anni '50 rivelano quanto matematicamente non siamo casuali, anche se non lo riconosciamo.)
Non prenderlo a cuore. Neanche i computer generano casualità. Non dovrebbero: il software e l'hardware del computer funzionano con logica booleana, non con probabilità. "La cultura dell'informatica è incentrata sul determinismo", ha dichiarato Vikash Mansinghka , che gestisce il Probabilistic Computing Project presso il Massachusetts Institute of Technology, "e che si presenta praticamente a tutti i livelli".
Ma gli informatici vogliono programmi in grado di gestire la casualità perché a volte è quello che richiede un problema. Nel corso degli anni, alcuni hanno sviluppato nuovi algoritmi eleganti che, sebbene non generino essi stessi numeri casuali, offrono modi intelligenti ed efficienti per usare e manipolare la casualità. Uno degli sforzi più recenti viene dal gruppo di Mansinghka al MIT, che presenterà un algoritmo chiamato Fast Loaded Dice Roller , o FLDR, alla conferenza internazionale online sull'intelligenza artificiale e le statistiche di agosto.
In poche parole, FLDR utilizza una sequenza casuale per simulare perfettamente il lancio di un dado caricato. (O una moneta pesata o un mazzo di carte truccato.) "Mostra come trasformare un lancio di monete perfettamente casuale in un lancio di monete parziale", ha detto il matematico Peter Bierhorst dell'Università di New Orleans. Bierhorst non ha contribuito alla ricerca ma descrive la premessa alla base del successo di FLDR come "avvincente".
FLDR non ti darà un vantaggio in Monopoli o aumenterà le tue probabilità ai tavoli di craps di Las Vegas. Ma i suoi creatori affermano che suggerisce un modo per integrare numeri casuali in software e hardware, che sono costruiti per essere deterministici. Incorporare questo tipo di incertezza aiuterà le macchine a fare previsioni simili all'uomo e simulare meglio i fenomeni che si basano su probabilità come il clima o i mercati finanziari.
La casualità è un concetto più complicato di quanto sembri. Nelle sequenze di numeri casuali, dove non esiste un modello riconoscibile, ogni cifra ha la stessa probabilità di apparire. Pi in sé non è un numero casuale, ad esempio, ma le cifre di pi sono ritenute casuali in questo modo (ciò che i matematici descrivono come "normale"): ogni numero intero compreso tra 0 e 9 appare circa lo stesso numero di volte.
Anche se puoi trovare un "generatore di numeri casuali" su Google, la casualità pura non è ciò che ottieni. I processori, i motori di ricerca e i generatori di password di oggi utilizzano approcci "pseudocasuali" abbastanza vicini per la maggior parte degli scopi. Sono generati secondo formule complicate, ma in teoria se conoscessi la formula, probabilmente potresti predire la sequenza.
Gli scienziati hanno cercato di costruire la casualità effettiva nelle macchine per almeno 80 anni. (Prima di allora, numeri casuali provenivano da vecchi standbys come dadi lanciati, palline numerate raccolte da una borsa ben miscelata o altri esercizi meccanici. Nel 1927, uno statistico campionò i dati del censimento per produrre una tabella di 40.000 cifre casuali.)
Le prime fonti di numeri casuali erano macchine fisiche. La prima macchina generatrice di numeri casuali è stata ideata dagli statistici britannici Maurice George Kendall e Bernard Babington Smith, che la descrissero nel 1938. La macchina fu collocata in una stanza buia, dove faceva girare un disco diviso in 10 pezzi uguali a forma di cuneo etichettato da 0 a 9. Quando qualcuno toccava un tasto a intervalli irregolari, un breve lampo al neon o una scintilla illuminavano il disco in modo che sembrasse congelarsi, con un solo numero visibile. Una macchina successiva, chiamata Ernie, usava invece il rumore del segnale nei tubi al neon; a partire dal 1957 scelse i numeri vincenti in una lotteria britannica.
Più recentemente, per sequenze veramente casuali, afferma Bierhorst, gli scienziati informatici devono guardare a fenomeni naturali come la radiazione cosmica di fondo o i comportamenti imprevedibili dei sistemi quantistici. "Ci sono processi casuali in natura che possono essere sfruttati che sono davvero imprevedibili", ha detto. "L'elettrone che schiva a sinistra oa destra non sa nemmeno cosa farà prima."
Ma la casualità può portarti solo così lontano. Alla fine degli anni '40, i fisici iniziarono a generare numeri casuali per adattarsi a una data distribuzione di probabilità. Tali strumenti – una versione teorica del lancio di un dado caricato – potrebbero essere utilizzati in modo più accurato per modellare situazioni del mondo reale, come il flusso del traffico o le reazioni chimiche. Nel 1976, i pionieristici scienziati informatici Donald Knuth e Andrew Yao introdussero un algoritmo che poteva usare una serie di numeri casuali per produrre campionamenti casuali di qualsiasi matrice di risultati ponderati. "Era l'algoritmo più efficiente in termini di tempo che si potesse arrivare", ha detto Feras Saad , uno studente di dottorato nel laboratorio di Mansinghka che ha guidato il nuovo lavoro su FLDR.
Sfortunatamente, Saad afferma che l'algoritmo fa un compromesso che è ben noto agli scienziati informatici: molte applicazioni che eseguono rapidamente usano molta memoria e le applicazioni che usano poca memoria possono avere un tempo di esecuzione lungo. L'algoritmo di Knuth e Yao rientra nella prima categoria, rendendolo elegante ma troppo intensivo in termini di memoria per qualsiasi uso pratico.
Ma la scorsa primavera, Saad ha individuato una soluzione intelligente. Si rese conto che quando i pesi su un dado si sommavano a una potenza di 2, l'algoritmo era efficiente sia nel tempo che nella memoria. Quindi, per un dado a sei facce, immagina che le probabilità di far rotolare i numeri da 1 a 6, rispettivamente, siano ponderate su 1, 2, 3, 4, 5 e 1. Ciò significa che la probabilità di tirare un 1, ad esempio, è 1/16 e la probabilità di ottenere un 2 è 2/16. Poiché i pesi si sommano a una potenza di 2 – 16 è 2 4 – l'algoritmo per questo sistema è efficiente in termini di tempo e memoria.
Ma immagina che i pesi siano invece 1, 2, 3, 2, 4, 2, che equivalgono a 14. Poiché 14 non è una potenza di 2, l'algoritmo Knuth-Yao richiede molta più memoria. Saad si rese conto che avrebbe potuto includere un peso aggiuntivo in modo che raggiungessero sempre una potenza di 2. In questo caso, avrebbe semplicemente aggiunto un'altra faccia ipotetica – una con peso 2 – in modo che i pesi fossero aggiunti a 16. Se l'algoritmo ne avesse scelto uno delle facce originali, il valore è stato registrato. Se ha scelto la faccia extra, il valore è stato scartato e l'algoritmo è stato eseguito di nuovo.
Questa è la chiave dell'efficienza di FLDR, che lo rende uno strumento potente nelle simulazioni: la quantità di memoria aggiuntiva necessaria per i rulli aggiuntivi è minima rispetto alla pesante memoria normalmente richiesta nell'originale.
FLDR rende efficiente l'algoritmo Knuth-Yao e suggerisce modi per migliorare un'ampia gamma di applicazioni. Le simulazioni dei cambiamenti climatici, le previsioni sulla resa delle colture, le simulazioni del comportamento delle particelle, i modelli dei mercati finanziari e persino il rilevamento di detonazioni sotterranee di armi nucleari dipendono da numeri casuali nelle distribuzioni di probabilità ponderate. I numeri casuali costituiscono anche la spina dorsale degli schemi di crittografia che proteggono i dati inviati su Internet.
Mansinghka afferma che il FLDR può anche aiutare i ricercatori a trovare modi per integrare la probabilità nei processori di computer, il fulcro del lavoro del suo laboratorio presso il MIT. L'algoritmo potrebbe aiutare a informare la progettazione di librerie software e nuove architetture hardware in grado di generare numeri casuali e usarli in modo efficiente. Sarebbe una drammatica deviazione dalle deterministiche macchine booleane a cui siamo abituati.
"Potremmo essere ben posizionati per integrare la casualità nei mattoni del software e dell'hardware", ha affermato.
Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all’URL https://www.quantamagazine.org/how-and-why-computers-roll-loaded-dice-20200708/ in data Wed, 08 Jul 2020 15:00:16 +0000.