Quando preferire Thompson Sampling rispetto ai test A/B

When to prefer Thompson Sampling over A/B testing.

Un’approfondita spiegazione del “Thompson Sampling”, un’alternativa più efficiente al test A/B per l’apprendimento online

Immagina di avere due annunci tra cui scegliere: quello rosso e quello blu. Naturalmente, vorresti mostrare ai tuoi utenti l’annuncio con il tasso di clic più alto.

Ma come si fa a scoprire quale annuncio ha il tasso di clic più alto?

L’approccio più comune per rispondere a questa domanda è fare un test A/B. Ciò implica separare alcuni utenti e mostrare il primo annuncio alla metà di essi e il secondo annuncio all’altra metà. Alla fine, è possibile calcolare il tasso di clic di ciascuna alternativa e selezionare la migliore.

Supponiamo che, alla fine del test A/B, si abbiano i seguenti risultati:

• 12 Modelli Mentali per la Scienza dei Dati
• Rendered.ai integra NVIDIA Omniverse per la generazione di dati sintetici.
• I grandi modelli di lingua sono influenzati da pregiudizi. La logica può aiutare a salvarli?

La versione blu è chiaramente superiore a quella rossa: un tasso di clic dell’18% contro un tasso di clic dell’11%. Ma ciò significa che abbiamo perso molte opportunità: avremmo potuto mostrare l’annuncio blu a molti più utenti e quindi avremmo potuto ottenere molti più clic.

D’altra parte, cosa succederebbe se interrompessimo l’esperimento molto presto, diciamo dopo soli 20 utenti?

Sappiamo intuitivamente che, dopo 20 utenti, i risultati non sono abbastanza affidabili per inviare la variante che funziona meglio a tutti gli utenti.

In generale, il problema dei test A/B è che:

• se separiamo troppi utenti, perdiamo opportunità sulle varianti meno performanti;
• se separiamo troppo pochi utenti, il test è inconcludente.

In altre parole, i test A/B sono inefficienti perché sono troppo statici. Idealmente, avremmo bisogno di un sistema intelligente in grado di apprendere dinamicamente man mano che ottiene più dati.

Questo sistema dovrebbe:

• esplorare le diverse alternative quando i risultati sono troppo piccoli per essere affidabili;
• sfruttare i risultati quando cominciano a diventare abbastanza affidabili, inviando sempre più traffico all’alternativa che funziona meglio.

Buone notizie: un tale sistema esiste ed è chiamato Thompson Sampling.

Usare le distribuzioni di probabilità invece dei numeri

L’approccio che abbiamo visto sopra ha cercato di valutare ogni alternativa con un singolo numero: il suo tasso di clic. Il problema con questo approccio è che un singolo numero non esprime l’incertezza associata all’ stima stessa.

Per risolvere questo problema, il Thompson Sampling propone di utilizzare una distribuzione di probabilità completa anziché un singolo numero.

L’obiettivo della distribuzione di probabilità è di esprimere l’incertezza sull’ stima della metrica.

Una volta che abbiamo le nostre distribuzioni – una per ogni alternativa – il Thompson Sampling funziona estrarre un numero casuale da ciascuna distribuzione. Poi, viene mostrata all’utente l’alternativa associata al numero più alto.

Che scopo ha fare questo? Beh, l’idea è che se le distribuzioni esprimono un’alta incertezza, l’esito dipende molto dalla casualità.

In altre parole, meno confidenza abbiamo nella nostra convinzione, più il sistema esplorerà diverse alternative. Al contrario, all’aumentare della fiducia, il sistema sfrutterà sempre di più l’alternativa con le migliori prestazioni.

Vediamo due distribuzioni di probabilità che potrebbero essere ottenute dai risultati che abbiamo visto sopra.

Se provi ad estrarre numeri casuali da queste due distribuzioni, scoprirai che il numero estratto dalla distribuzione rossa è maggiore del numero estratto dalla distribuzione blu il 24% delle volte. Ciò dimostra numericamente la nostra intuizione che la differenza non è ancora statisticamente significativa.

Ma dopo 10.000 impressioni?

Adesso siamo molto sicuri che la pagina blu funzioni meglio della pagina rossa. Ed infatti, è praticamente impossibile che il numero estratto dalla distribuzione rossa sia maggiore di quello estratto dalla distribuzione blu.

Quale distribuzione dovrei usare?

Nel nostro esempio, poiché abbiamo un risultato binario (clic o mancato), la distribuzione più indicata è la distribuzione Beta. La cosa interessante della Beta è che si basa interamente su due parametri, a e b che possono essere interpretati in modo molto semplice:

• a : numero di successi (nel nostro caso il numero di clic).
• b : numero di fallimenti (nel nostro caso il numero di mancati clic).

Il valore atteso della distribuzione è a / (a + b), che è la nostra quantità di interesse: il tasso di click-through.

La distribuzione Beta è anche disponibile in Scipy ed è quindi molto facile da calcolare:

import numpy as npfrom scipy import stats# input: number of clicks and number of missesclicks = 1misses = 4# get 1000 equally spaced points between 0 and 1 for plotting purposesx = np.linspace(start = 0, stop = 1, num = 1_000)# calculate probability distribution function of betabeta_pdf = stats.beta(a = clicks, b = misses).pdf(x = x)

Facciamo alcuni esempi. Prendiamo un tasso di clic del 20%: cosa succede alla distribuzione Beta quando il numero di impressioni aumenta?

Come ci aspettavamo, all’aumentare del numero di utenti, i risultati diventano sempre più certi: ciò si traduce in una distribuzione sempre più concentrata intorno al valore atteso: il 20%.

In altre parole, lavorando con distribuzioni di probabilità ci permette di assegnare una misura quantitativa di certezza alla nostra valutazione qualitativa.

Perché non la distribuzione Normale?

Se hai seguito il corso di Statistica 101, potresti chiederti: “Aspetta un attimo. Secondo il Teorema del Limite Centrale, se abbiamo prove indipendenti dovremmo usare la distribuzione Normale. Quindi perché stiamo usando la distribuzione Beta?”

Effettivamente, questo è un buon punto. Vediamo come calcolare la funzione di probabilità sia della distribuzione Beta che della Normale in Python.

import numpy as npfrom scipy import stats# input: number of clicks and number of missesclicks = 1misses = 4# compute n and click raten = clicks + missesclick_rate = clicks / n# get 1000 equally spaced points between 0 and 1 for plotting purposesx = np.linspace(start = 0, stop = 1, num = 1_000)# calculate the probability distribution function of betabeta_pdf = stats.beta(a = clicks, b = misses).pdf(x = x)# calculate the probability distribution function of normalnormal_pdf = stats.norm(  loc = click_rate,   scale = np.sqrt(click_rate * (1 - click_rate) / n)).pdf(x = x)

Ripetiamo questo processo per diversi numeri di utenti e confrontiamo le due distribuzioni:

Come si può vedere, la distribuzione Beta e la distribuzione Normale diventano sempre più simili man mano che il numero di impressioni cresce. E diventano praticamente la stessa cosa dopo soli 50 cicli.

Quindi, utilizzare la distribuzione Beta o quella Normale non farebbe molta differenza. Questa è una grande notizia perché significa che – grazie al CLT – possiamo sempre utilizzare la distribuzione Normale, indipendentemente dalla metrica che scegliamo.

Thompson Sampling al lavoro

Facciamo un esempio per vedere il Thompson Sampling al lavoro.

Vogliamo testare 4 versioni di una pubblicità: grigia, rossa, verde e blu. Supponiamo di conoscere anche il tasso di clic reale per ciascuna versione.

Come nel paragrafo precedente, useremo la distribuzione Beta. Ma abbiamo bisogno di un piccolo aggiustamento. Poiché i parametri per Beta ( a e b ) devono essere strettamente maggiori di 0, nel caso in cui almeno uno tra a e b sia zero, allora aggiungeremo 1 a ciascuno di essi.

import numpy as npdef draw_from_beta(clicks, misses):  """Estrae un numero casuale da Beta."""    if min(clicks, misses) == 0:    clicks += 1    misses += 1    return np.random.beta(a=clicks, b=misses)

Per ogni nuovo utente, dobbiamo fare quanto segue:

1. In base al conteggio corrente di clic e mancate per ciascuna variante, ottenere la corrispondente distribuzione Beta.
2. Estrarre un numero dalla distribuzione di ciascuna variante ottenuta al punto 1.
3. Mostrare all’utente la variante associata al numero più alto.
4. Aggiornare il contatore con l’esito ottenuto sull’utente corrente (clic o mancata).

Vediamo una rappresentazione grafica di questo processo per i primi 1.000 utenti:

Come si può vedere, dopo 100 iterazioni, la nostra credenza non è ancora allineata con la verità: il valore atteso della variante verde è maggiore della blu. Ma questo è solo dovuto al caso. Man mano che l’esperienza si accumula, le nostre stime convergeranno alla verità. Ciò significa che:

• la media della distribuzione sarà più vicina al tasso reale;
• la deviazione standard della distribuzione sarà sempre più vicina a zero.

Vediamo come queste due grandezze evolvono durante le prime 400 iterazioni.

Come abbiamo visto, dopo 1.000 impressioni questo è il risultato:

Il Thompson Sampling è così efficace che, dopo soli 1.000 cicli, ha già concentrato il 50,6% delle visualizzazioni sulla migliore alternativa (blu) e il 37,7% sulla seconda migliore (verde).

Al contrario, cosa succederebbe se usassimo l’approccio A/B testing, inviando ogni alternativa allo stesso numero di utenti? Mostrare ogni annuncio a 250 utenti produrrebbe il seguente risultato:

Usando il Thompson Sampling abbiamo 145 clic, con l’A/B testing invece abbiamo 135 clic. Ciò significa il 7,4% in più di clic grazie al Thompson Sampling! E la differenza diventerebbe ancora più grande se effettuassimo più iterazioni.

Conclusioni

Il Thompson Sampling è perfetto per l’apprendimento online perché affronta in modo efficiente il dilemma esplorazione/sfruttamento.

Lo fa assegnando una distribuzione di probabilità ad ogni variante che deve essere testata. La distribuzione ha lo scopo di esprimere l’incertezza associata alla stima.

Il fatto che il Thompson Sampling si adatti dinamicamente alla conoscenza accumulata dalle iterazioni precedenti lo rende più efficiente dell’A/B testing.

Per esempio, abbiamo visto un esempio con 4 varianti e – in soli 1.000 cicli – il Thompson Sampling è stato in grado di ottenere il 7% in più di clic rispetto all’A/B testing.

Tutto il codice usato per questo articolo può essere trovato in questo notebook.

Grazie per la lettura! Spero che abbiate apprezzato questo articolo. Se volete, aggiungetemi su Linkedin!