Ora, perché dovremmo preoccuparci dei Sistemi di Raccomandazione…? ft. Una breve introduzione a Thompson Sampling

Ora, perché dovremmo prestare attenzione ai Sistemi di Raccomandazione...? ft. Una breve introduzione a Thompson Sampling

Una serie continua sul sistema di raccomandazione

Oggi mi sono colto di nuovo, per l’ennesimo giorno di fila, ad avere nella mano una scatola di cena intatta mentre sfoglio Netflix alla ricerca di uno show da guardare mentre mangio. Il mio feed è pieno di troppe raccomandazioni di romanzi asiatici e film americani sul passaggio all’età adulta, probabilmente basate su una o due serie di queste categorie che ho guardato un mese o due fa. “Qui non c’è niente da vedere…”– ho sospirato leggendo tutte le sinossi, sentendomi sicuro di poter prevedere come si svilupperà la trama. Ho tirato fuori il mio intrattenimento alternativo di fiducia, Tiktok, pensando inconsciamente che probabilmente dovrò “Non interessato” alcuni video e “Mi piace”, “Salva” altri per…raccomandare all’algoritmo di inviarmi oggi un nuovo flusso di contenuti.

I sistemi di raccomandazione (RecSys) possono essere considerati algoritmi così stabiliti, che sono stati profondamente inseriti nella nostra vita di tutti i giorni, al punto che, su una scala da 1 a Chat-GPT, sembra quasi una tendenza degli anni ’80 sia per il mondo accademico che per quello non accademico. Tuttavia, non è certo un algoritmo perfetto. Le sfide etiche, sociali, tecniche e legali che derivano dall’utilizzo di un’app di raccomandazione non sono mai state al centro della ricerca (come accade per la maggior parte degli altri prodotti tecnologici…). L’ingiustizia di gruppo selezionato e la violazione della privacy sono esempi delle preoccupazioni più diffuse legate ai RecSys che le aziende che li hanno implementati non hanno ancora affrontato completamente. Inoltre, esistono molti altri problemi più subdoli a cui raramente viene data una riflessione sufficiente, tra cui la perdita di autonomia nel processo decisionale di un individuo. Un RecSys “potente” può senza dubbio spingere gli utenti in una determinata direzione [2], facendoli acquistare, guardare, pensare, credere a qualcosa che non avrebbero fatto se non fossero stati soggetti a tale manipolazione.

Pertanto, voglio scrivere una serie durante il mio percorso universitario in cui inizio a imparare e approfondire i RecSys, i loro punti di forza e le loro lacune…da zero! E penso che possa iniziare a parlare di film e…Thompson Sampling!

Thompson Sampling

Thompson Sampling (TS) è uno degli algoritmi fondamentali non solo nella letteratura sui sistemi di raccomandazione, ma anche nell’apprendimento per rinforzo. È senza dubbio un modo migliore per i test A/B nell’ambito dell’apprendimento online, come spiegato chiaramente da Samuele Mazzanti in questo straordinario articolo. In termini semplici, nel contesto della raccomandazione di film, TS cerca di identificare il miglior film da raccomandarmi che massimizzerà la probabilità che io clicchi per guardarlo. Può farlo in modo efficace utilizzando relativamente pochi dati poiché consente di aggiornare i parametri ogni volta che mi osserva cliccare o non cliccare su un film. In parole povere, questa caratteristica dinamica consente a TS di tener conto, oltre alla mia cronologia di visione e alle serie segnate come preferite, di fattori in tempo reale come la navigazione o i risultati di ricerca nell’app che sto utilizzando al momento per fornirmi la migliore suggerimento adatto. Tuttavia, in questo tutorial per principianti, esamineremo solo un’analisi semplificata di seguito.

• Questa AI Paper ha mosse Come i modelli di linguaggio si adattano all’apprendimento attraverso il rinforzo offline con i passi di danza di ‘LaMo’ e l’apprendimento a poche prove
• Cybersecurity e Intelligenza Artificiale nel cuore del Summit Cyber del Texas
• Sfruttare gli LLM per completare i grafi di conoscenza delle raccomandazioni

Andiamo ancora più a fondo!

Consideriamo questi 3 film, che, per quanto straordinari possano essere, ho, in modo controverso, una mia personale classifica. Di questi 3 film, immaginiamo che ce ne sia uno che rivedrei al 100% se comparisse nel mio feed, uno che probabilmente non rivedrò (5%) e uno per cui c’è una probabilità del 70% che lo guarderò ogni volta che lo vedo. Chiaramente, TS non ha queste informazioni su di me in precedenza e il suo obiettivo è imparare il mio comportamento in modo da raccomandarmi il film che sa che sicuramente cliccherò per guardarlo.

Nell’algoritmo TS, il flusso di lavoro principale procede come segue:

1. Azione: TS mi suggerisce un film specifico, tra centinaia di altri
2. Risultato: Decido che il film sembra abbastanza interessante per me e clicco per guardarlo, o lo trovo noioso e clicco fuori dalla pagina dopo aver letto la sinossi
3. Ricompensa: Può essere considerata come il numero di “punti” che TS ottiene se faccio clic per guardare un certo film o che TS manca se non faccio clic. Nelle impostazioni di base per la raccomandazione di film o annunci, possiamo considerare la ricompensa come un equivalente del risultato, quindi 1 clic sul film = 1 punto!
4. Aggiornamento delle conoscenze: TS registra la mia scelta e aggiorna la sua convinzione su quale film è il mio preferito.
5. Ripeti il passaggio 1 (può essere all’interno della mia sessione di navigazione corrente o a cena il giorno successivo), ma ora con alcune conoscenze aggiuntive sulle mie preferenze.

Esplorazione/Sfruttamento

Questo è il termine più utilizzato in questa letteratura ed è anche ciò che differenzia TS e altri algoritmi correlati. Il punto 5 è dove entra in gioco questa logica. Nel mondo di TS, tutto ha un certo grado di incertezza. Il fatto che io beva un caffè latte tre volte e un matcha cinque volte in una settimana non significa necessariamente che preferisco il matcha al caffè latte, e se fosse solo quella settimana (e in media bevo più caffè latte che matcha ogni settimana)? Per questa ragione, tutto in TS è rappresentato da un tipo di distribuzione, piuttosto che da singoli numeri.

All’inizio, TS ovviamente ha molta incertezza sulle mie preferenze per i film, quindi la sua priorità è esplorare questo aspetto dandomi molte diverse suggerimenti di film per osservare la mia risposta alle proposte. Dopo alcuni clic e salti, TS può individuare i film su cui tendo a fare clic e i film che non offrono benefici, acquisendo così maggior fiducia su quale film propormi la prossima volta. È a questo punto che TS inizia a sfruttare le opzioni altamente gratificanti, dove mi mostra spesso il film che clicco per guardare, ma lascia comunque spazio per ulteriori esplorazioni. La fiducia aumenta man mano che arrivano ulteriori osservazioni, che, nei casi semplici, raggiunge il punto in cui il lavoro di esplorazione diventa minimo poiché TS ha già molta fiducia da sfruttare nella raccomandazione che offre molte ricompense.

L’esplorazione vs lo sfruttamento sono spesso definiti come il compromesso o il dilemma perché troppa esplorazione (cioè una scarsa eliminazione delle scelte a basso valore nonostante già sufficienti prove per sapere che tali scelte non sono ottimali) comporta molte perdite, mentre troppo sfruttamento (cioè eliminare troppe opzioni troppo rapidamente) porta a eliminare erroneamente l’azione ottimale.

Le distribuzioni: Beta-Bernoulli

Come nel grafico del matcha-caffè latte sopra, TS lavora con diversi tipi di distribuzioni per capire la nostra preferenza per diverse opzioni. Nei casi più semplici di film (e anche pubblicità), usiamo spesso la combinazione Beta-Bernoulli.

La distribuzione Bernoulli è una distribuzione discreta in cui ci sono solo due possibili risultati: 1 e 0. La distribuzione Bernoulli consiste in un solo parametro, che indica la probabilità di una variabile, diciamo Y, che sia 1. Quindi, se diciamo Y~ Bern(p), e ad esempio, p = 0.7, ciò significa che Y ha il 0.7 probabilità di assumere il valore 1 e 1-p = 1-0.7 = 0.3 probabilità di essere 0. Pertanto, la distribuzione Bernoulli è adatta per modellare la ricompensa (anche il risultato nel nostro caso) perché la nostra ricompensa ha solo un risultato binario: cliccato o non cliccato.

La distribuzione Beta viene utilizzata per modellare le mie preferenze sui film secondo la TS. La distribuzione Beta richiede due parametri, alfa e beta, che vengono spesso interpretati come il numero di successi e fallimenti, rispettivamente, e entrambi devono essere ≥ 1. Pertanto, è adatta utilizzare la distribuzione Beta per modellare il numero di volte che faccio clic per guardare un film e il numero di volte che lo salto. Diamo un’occhiata a un esempio. Qui, queste sono 3 diverse distribuzioni Beta che rappresentano 3 film, su 10 osservazioni, quindi il numero totale di clic e salti per tutti e 3 i film è lo stesso (10), ma i tassi di clic e salto sono diversi. Per il film 1, faccio clic per guardare 2 volte (alfa = 2) e salto 8 volte (beta = 8); per il film 2, faccio clic per guardare 5 volte e salto 5 volte; per il film 3, faccio clic per guardare 8 volte e salto 2.

Secondo il grafico, si può vedere che la probabilità di guardare di nuovo il film 2 raggiunge il picco intorno al 50%, mentre questa probabilità per il film 1 è molto più bassa, ad esempio. Possiamo pensare alle curve qui come la probabilità di probabilità (di guardare di nuovo un film) e quindi la distribuzione Beta è ideale per rappresentare la convinzione di TS sulle mie preferenze cinematografiche.

L’algoritmo

In questa sezione, ti aiuterò a comprendere chiaramente l’implementazione e la metodologia dell’algoritmo. Innanzitutto, ecco un frammento dell’algoritmo di Thompson Sampling, in pseudocodice e in Python. Il pseudocodice è tratto da un incredibile libro su TS, chiamato Un tutorial su Thompson Sampling [Russo, 2017].

Scomponiamolo!

Modello di campionamento

Il primo passo dell’algoritmo consiste nel “indovinare” quanto mi piace ciascuno dei film. Come illustrato nella sezione precedente, la mia preferenza per ogni film può essere rappresentata utilizzando le curve Beta come quelle nella Fig. 2, di cui TS non ha conoscenza preliminare e sta cercando di capire come sono fatte queste curve Beta. Nel t = 1 (primo round), TS può iniziare supponendo che ho una preferenza uguale per tutti e 3 i film, cioè un numero uguale di clic e salti (e le mie 3 curve Beta avranno lo stesso aspetto).

Le tre distribuzioni qui sono quelle che p è nel pseudocodice della Fig. 3. Da ciascuna di queste distribuzioni, TS campionerà un valore, rappresentato da theta, per aiutare nella selezione dell’azione nel passaggio successivo.

Seleziona e applica azione

In questo passaggio, TS sceglie l’azione da eseguire (ad esempio, scegli un film da consigliare) in base al campionamento dei valori di theta, prendendo il più grande. Prendiamo di nuovo come esempio la Figura 2. Diciamo che abbiamo solo 2 film: solo il film 1 e il film 3. L’idea di utilizzare il theta più grande per selezionare un’azione è che se le distribuzioni vere hanno poca sovrapposizione e quasi certamente mi piace di più un film rispetto all’altro nel nostro caso, allora è molto improbabile che il theta campionato per il film 1 sia più grande di quello del film 3. Allo stesso modo, se consideriamo solo il film 2 e il film 3, possiamo vedere che ora abbiamo più sovrapposizioni tra le distribuzioni. Tuttavia, se continuiamo a campionare più valori di theta per abbastanza round, allora possiamo osservare che la proporzione di theta del film 3 > theta del film 2 è più grande del contrario, e TS avrà abbastanza informazioni per concludere che il film 3 è la migliore “azione” da intraprendere. In generale, questo è anche il motivo per cui più distinte sono le distribuzioni vere sconosciute, meno round di esperimenti sono necessari affinché TS capisca quale azione o braccio sia il più ottimale.

Dopo aver applicato l’azione scelta, TS riceverà una risposta da me, ovvero se faccio clic per guardare il film o meno. Questo risultato, come indicato in precedenza, è considerato anche la nostra ricompensa per l’azione corrispondente. TS registrerà questo risultato osservato e lo utilizzerà per aggiornare la sua convinzione sulle mie preferenze cinematografiche nel passaggio successivo.

Aggiornamento della distribuzione

Nella descrizione della distribuzione Beta sopra, abbiamo stabilito che la distribuzione Beta è caratterizzata dal numero di successi e di fallimenti. Più volte faccio clic su un determinato film, più la moda della sua distribuzione beta si sposta verso 1 e viceversa, più salto la raccomandazione, più si sposta verso 0. Pertanto, l’aggiornamento della convinzione su un dato film, dopo che è stato suggerito e una risposta è stata registrata, consiste semplicemente nell’aggiungere uno al parametro alfa o beta della distribuzione beta del film, a seconda che il film sia stato cliccato o saltato.

Questo metodo di aggiornamento dei parametri semplice e interpretabile è il motivo per cui la distribuzione Beta Bernoulli è un modello TS molto comune.

Risultato e discussione

Tornando allo scenario descritto all’inizio dell’articolo. Siamo nel processo di indovinare quale dei 3 film sia il più ottimale da consigliarmi, a condizione che uno lo guardi al 100%, uno abbia il 70% di probabilità di essere cliccato e l’altro solo il 5% di probabilità (ancora una volta, questa conoscenza è sconosciuta a TS). La prima riga mostra due punti di partenza diversi per la simulazione, che ci permetteranno di osservare se possiamo raggiungere gli stessi risultati finali con diverse credenze iniziali.

Dalla Figura 6, possiamo vedere che la risposta finale a quale film sia il mio preferito assoluto è il film 1 – PARASITE (mi dispiace per i fan di Marvel)!!

Come possiamo vedere, il percorso di esplorazione dei due casi è diverso, nel senso che le supposizioni iniziali Beta(1, 1) portano a un’arrivo più veloce del film che si crede sia il mio preferito. Basta T=10 round per capire che TS sta chiaramente sfruttando il film 1, implicando che TS ha suggerito il film 1 e ha ottenuto click da me, per cui la sua distribuzione beta si sposta verso destra, quindi il theta campionato dalle distribuzioni aggiornate supera i suoi concorrenti, garantendo lo sfruttamento. Questo sfruttamento si manifesta già con T=5 round, ma secondo il grafico corrispondente, c’è ancora molta sovrapposizione tra la beta del film 1 e 3, le cui mode non sono del tutto distinte, il che significa che TS non è ancora completamente certo che il film 1 sia l’azione ottimale.

D’altra parte, le credenze iniziali di Beta(2, 3) risultano nel fatto che TS necessita di più round per arrivare al film 1 (T=20). Anche a T=10, c’è ancora molta incertezza tra il film 1 e il film 3, ed è osservato che, a causa della casualità nel campionamento di theta, può risultare che il film 3 venga sfruttato come opzione ottimale. Questo esperimento mostra che la conoscenza iniziale di ogni azione può svolgere un ruolo nella velocità con cui viene rilevato il braccio ottimale, argomento su cui possiamo approfondire in futuri articoli.

È importante notare che se le distribuzioni effettive dei film sono quasi identiche (supponiamo che il film 1 e il film 3 abbiano rispettivamente un tasso di clic del 100% e del 98%), TS è molto probabilmente destinato a non identificare l’azione ottimale perché la proporzione dei theta campionati da una distribuzione superiore a quelli dell’altra sarà divisa. Pertanto, se per caso il film 3 avesse più “theta più grandi”, allora TS sfrutterebbe maggiormente questa opzione, portando a identificarla erroneamente come l’azione ottimale.

Un’altra nota importante ricavata dall’esperimento è che TS è buono solo nel dirci quale è l’azione migliore, ma non può darci informazioni sulle opzioni rimanenti. Ciò accade perché nel corso del processo di esplorazione, TS eliminerà rapidamente le opzioni che non vengono ritenute ottimali, quindi TS smette di ricevere ulteriori informazioni su queste azioni e di conseguenza non fornisce la corretta classifica tra le azioni oltre quella migliore.

Conclusioni

In questo articolo, abbiamo avuto l’opportunità di esplorare di più l’algoritmo del Thompson Sampling e di lavorare attraverso una simulazione di raccomandazione di film. Il Thompson Sampling coinvolge principalmente le distribuzioni e la conoscenza precedente nel fornire una previsione, che è un concetto centrale nei modelli bayesiani, di cui ho intenzione di parlare di più nei prossimi articoli. Se sei arrivato alla fine di questo articolo, grazie per il tuo tempo e spero che questo tutorial ti abbia dato una comprensione bilanciata, sia tecnica che intuitiva, di questo algoritmo! Se hai ulteriori domande, non esitare a contattarmi tramite il mio LinkedIn, sarò felice di connetterci e rispondere ad esse!

Riferimenti:

[1] Quali sono i potenziali rischi e sfide dei sistemi di raccomandazione in diversi ambiti e contesti?

[2] Sistemi di raccomandazione e le loro sfide etiche

[3] Quando è preferibile il “Thompson Sampling” rispetto ai test A/B