Reservoir Sampling

Un modello per l'assistenza clienti impara da messaggi che arrivano uno dopo l'altro. Vuoi conservarne alcuni per le ripetizioni future, ma hai solo quattro posti in memoria. Non sai nemmeno quanti messaggi arriveranno ancora: venti o due milioni.

Tenere i primi quattro? Allora la memoria conosce solo l'inizio. Tenere sempre gli ultimi quattro? Allora conosce solo la fine. Un'estrazione equa di «quattro dal totale» richiederebbe di conservare tutto oppure di conoscere in anticipo il numero di messaggi. La domanda è: come dare a ogni messaggio la stessa probabilità, con un numero fisso di posti e un flusso di lunghezza ignota?

Il Reservoir Sampling è un modo per mantenere un campione casuale di dimensione fissa durante un unico passaggio su dati di cui non conosciamo in anticipo la quantità. Dopo ogni nuovo messaggio la memoria, qui chiamata serbatoio, contiene un campione casuale equo di tutto ciò che è arrivato fino a quel momento. La versione più semplice, l'Algorithm R, è descritta da Vitter, Random Sampling with a Reservoir, §2, che la attribuisce ad Alan Waterman.

La ricetta in due passi

1. I primi quattro messaggi entrano in memoria senza estrazione.
2. Il messaggio numero $t$ (il quinto, il sesto e ogni successivo) entra in memoria con probabilità $4/t$. Se è entrato, sostituisce uno dei quattro salvati, scelto a caso.

Il quinto messaggio entra quindi con probabilità 4/5, il centesimo con probabilità 4/100. I nuovi messaggi hanno una probabilità di entrare sempre più bassa, ma i vecchi sono già stati esposti molte volte al rischio di essere scartati, e i due effetti si compensano esattamente. Verifichiamolo dopo il quinto messaggio. Entra con probabilità 4/5. Il primo messaggio esce solo se il quinto è entrato (4/5) ed è finito proprio al suo posto (1/4), cioè con probabilità 1/5. Resta con probabilità 4/5: la stessa del quinto. Dopo $t$ messaggi ciascuno di essi è in memoria con probabilità $4/t$.

Una probabilità uguale non è una garanzia

Nell'esperimento il flusso ha 20 messaggi. Diciotto riguardano la consegna e due, il nono e il quindicesimo, riguardano i resi. Ogni avvio fa scorrere un flusso del genere 2000 volte e conta quanto spesso una data posizione è rimasta in memoria alla fine. Le estrazioni sono vere, quindi i risultati differiscono ogni volta di una frazione di punto percentuale.

Con il Reservoir Sampling ogni barra vale circa il 20%, cioè 4/20. Allo stesso tempo, nella maggior parte delle esecuzioni nessuno dei due resi resta in memoria. Il valore esatto è 3060/4845, cioè circa il 63%: tante sono, fra tutte le quaterne scelte tra 20 messaggi, quelle composte soltanto dai diciotto messaggi sulla consegna. Il metodo è equo verso i singoli messaggi, ma non si preoccupa che ogni categoria abbia un rappresentante.

Dove tutto questo conta

Nell'addestramento con ripetizioni il Reservoir Sampling è talvolta il modo in cui si scrive nel buffer: non occorre conoscere la lunghezza del flusso né i confini tra i compiti. Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, algoritmo 2 lo usano proprio così. Nei loro esperimenti su compiti con immagini funzionava bene, tranne che con memorie molto piccole, dove dal buffer sparivano le classi precedenti; in quel caso andavano meglio le strategie che curano una rappresentazione uguale delle classi (§4.4). È un risultato per la classificazione di immagini, non per gli LLM.

L'algoritmo in sé non riguarda il machine learning. Il lavoro di Vitter del 1985 descrive l'estrazione di record da un nastro magnetico di lunghezza ignota e propone varianti più veloci che, invece di estrarre a ogni record, calcolano quanti record saltare. I messaggi dei clienti e il flusso di 20 posizioni sono un esempio mio.

• Experience Replay ha bisogno di un buffer con vecchi esempi; il Reservoir Sampling è uno dei modi per decidere che cosa vi entra.
• Continual Learning presuppone l'apprendimento da un flusso di dati con memoria limitata, cioè una situazione in cui non si può conservare tutto.
• Catastrophic Forgetting [Polski] può aggravarsi quando da una memoria piccola escono tutti gli esempi di una vecchia categoria.

Testo e illustrazione sono stati preparati con l'aiuto dell'AI. Il flusso di messaggi e la dimostrazione sono un esempio didattico mio e semplificato; l'illustrazione è una metafora, non uno schema dell'algoritmo.