Chi non ha mai giocato a cow-boy e indiani? E chi, da da bambino, non si è mai appuntato una stella da sceriffo sul petto?
Sicuramente saprete che, nel Far West, il bandito per antonomasia era Jesse James: ricordo che nel mio kit c'era anche il suo manifesto con tanto di “WANTED” e di “REWARD”.
Quello che, probabilmente, i non addetti ai lavori ignorano è che uno dei più famosi problemi in Teoria della probabilità è quello del “Multi-Armed Bandit”, ossia del “Bandito Multiarmato” chiamato, anche, “Bandito Bayesiano”.
E, considerato che sono un appassionato di “Data Science”, riponiamo, ma solo per un momento, i “classici” e dedichiamoci, un pochino, alla Statistica.
E, considerato che sono un appassionato di “Data Science”, riponiamo, ma solo per un momento, i “classici” e dedichiamoci, un pochino, alla Statistica.
Cercherò di raccontarvelo in modo semplice e sommario, ma quello del “Bandito” è un framework potente, molto utilizzato per ottimizzare il guadagno nei problemi di allocazione delle risorse.
Spostiamoci, idealmente, a Las Vegas, il regno del gioco d'azzardo e delle slot machine …. La slot machine è chiamata, infatti, “One-Armed Bandit”, perché ha una leva e prende i soldi delle persone.
Supponiamo di avere davanti a noi molte slot machine, ciascuna con una probabilità di vincita diversa e sconosciuta: il nostro obiettivo è quello di elaborare una strategia che ci consenta di massimizzare le vincite dato un certo numero di giocate.
Spostiamoci, idealmente, a Las Vegas, il regno del gioco d'azzardo e delle slot machine …. La slot machine è chiamata, infatti, “One-Armed Bandit”, perché ha una leva e prende i soldi delle persone.
Supponiamo di avere davanti a noi molte slot machine, ciascuna con una probabilità di vincita diversa e sconosciuta: il nostro obiettivo è quello di elaborare una strategia che ci consenta di massimizzare le vincite dato un certo numero di giocate.
La prima scelta che dovremo fare è se concentrare i nostri sforzi (e i nostri soldi) su una determinata macchina oppure se provare a trovare macchine migliori (“exploitation versus exploration”).
Rispolveriamo il Teorema di Bayes, ossia:P(A|B) = P(B|A) * P(A) / P(B)
P(A|B) è la probabilità di A dato B
P(B|A) è la probabilità di B dato A
P(A) è la probabilità “a priori” di A (ossia non tiene conto di B)
P(B) è la probabilità “a priori” di B (ossia non tiene conto di A)
e rinfreschiamo, inoltre, la distribuzione Beta:
f(x;α,β)=xα-1 (1-x)β-1 / Β( α,β)
(La distribuzione Beta è una distribuzione di probabilità continua definita da due parametri α e β sull'intervallo [0,1]. Trova applicazione soprattutto nella statistica bayesiana.)
Prima di approcciare le diverse strategie, introduciamo, però, il concetto di “Regret” (“Rammarico”).
Poiché non sappiamo come le macchine sono state configurate e, quindi, quali sono le diverse probabilità di vincita, prima di aver effettuato un numero n di prove per ciascuna macchina tirando la rispettiva leva non possiamo individuare la macchina che ci consentirà di massimizzare le nostre vincite.
Il “Regret” è, quindi, quello che non abbiamo guadagnato non tirando sin dall'inizio la leva giusta: vogliamo massimizzare il guadagno anche durante la fase di apprendimento.
L'alternativa è quella di ridurre la fase di esplorazione e puntare su una macchina che non necessariamente sarà quella più remunerativa, dato che non abbiamo fatto il numero adeguato di prove, ma questa scelta, se da un lato può ridurre il “Regret” iniziale, è probabile che conduca ad un “Regret” totale maggiore.
L'alternativa è quella di ridurre la fase di esplorazione e puntare su una macchina che non necessariamente sarà quella più remunerativa, dato che non abbiamo fatto il numero adeguato di prove, ma questa scelta, se da un lato può ridurre il “Regret” iniziale, è probabile che conduca ad un “Regret” totale maggiore.
Vediamo, ora, le diverse strategie...
Approccio “ε Greedy” (“ε Avido”) : dopo un certo numero di prove (ad es. 1000) , impostiamo un valore per ε (ad es. 0,05) e sfruttiamo la migliore opzione per il valore 1 - ε (95% ) del tempo continuando ad esplorare le altre opzioni randomicamente per il valore ε (5%) del tempo; ad ogni intervallo temporale, riscegliamo l'opzione che massimizza la vincita.
Approccio “Upper Confidence Bounds” (Limiti di fiducia superiore): l'esplorazione randomica ci offre la possibilità di sperimentare opzioni relativamente alle quali non abbiamo sufficienti informazioni ma, d'altro canto, ci espone al rischio, proprio a causa della randomicità, di tirare la leva di una macchina che sappiamo, per esperienza precedente, non essere molto remunerativa.
Al fine di evitare questa inefficienza, un approccio potrebbe essere quello di ridurre, gradualmente, il valore di ε, mentre un altro potrebbe essere quello dell' ”ottimismo” nei confronti delle macchine per le quali non abbiamo ancora un valore stimato della remuneratività sufficientemente attendibile, o, per meglio dire, quello di favorire l'eplorazione di quelle macchine che hanno un maggiore potenziale.
Di fatto, ad ogni intervallo, selezioniamo la macchina che ha il valore più alto ottenuto sommando la ricompensa stimata ed il valore del limite di fiducia superiore.
Dove:
Qt(a)=valore stimato attuale della ricompensa della macchina
t=intervalli temporali
Nt(a)=numero di volte in cui tiro la leva della macchina; all'aumentare del numero delle prove, il valore del limite di fiducia superiore si riduce.
Approccio “Thompson Sampling” (Campionamento di Thompson): l'idea di base è di presupporre una semplice distribuzione a priori dei parametri della distribuzione delle vincite di ciascuna macchina e, ogni volta, tirare la leva della macchina che ha la probabilità più alta a posteriori di essere la macchina migliore. Ogni volta che tiriamo la leva, otteniamo un'ulteriore osservazione che va ad aggiornare i parametri della distribuzione Beta.
Proviamo a spiegarlo più empiricamente.
Ipotizziamo di avere davanti a noi 3 macchine: all'inizio, ovviamente, non sappiamo nulla e facciamo un certo numero di prove, ad es. 200, per ciascuna di esse e registriamo i risultati ottenuti. Per farla semplice, abbiamo, per ogni macchina, una lista con le vincite e una con le perdite che sono, poi, i parametri della distribuzione Beta. A questo punto, scegliamo la macchina che ha la più alta probabilità di vincita in base alla distribuzione Beta e tiriamo la leva: se otteniamo una ricompensa, aggiorniamo la lista delle vincite, altrimenti aggiorniamo la lista delle perdite. Reiteriamo e scegliamo la macchina che ha la più alta probabilità di vincita in base alla distribuzione Beta con i parametri aggiornati e così via, fino a quando non riteniamo i dati in nostro possesso sufficienti per stabilire su quale macchina dobbiamo scommettere.
Proviamo a spiegarlo più empiricamente.
Ipotizziamo di avere davanti a noi 3 macchine: all'inizio, ovviamente, non sappiamo nulla e facciamo un certo numero di prove, ad es. 200, per ciascuna di esse e registriamo i risultati ottenuti. Per farla semplice, abbiamo, per ogni macchina, una lista con le vincite e una con le perdite che sono, poi, i parametri della distribuzione Beta. A questo punto, scegliamo la macchina che ha la più alta probabilità di vincita in base alla distribuzione Beta e tiriamo la leva: se otteniamo una ricompensa, aggiorniamo la lista delle vincite, altrimenti aggiorniamo la lista delle perdite. Reiteriamo e scegliamo la macchina che ha la più alta probabilità di vincita in base alla distribuzione Beta con i parametri aggiornati e così via, fino a quando non riteniamo i dati in nostro possesso sufficienti per stabilire su quale macchina dobbiamo scommettere.
Ovviamente, questa non è, né doveva esserlo, una trattazione completa e rigorosa; in primis, essendoci un'abbondante letteratura in proposito, un ulteriore contributo sarebbe assolutamente inutile et, in secundis, essendo questo blog prevalentemente indirizzato a chi ha l'hobby delle materie umanistiche, l'obiettivo era quello di incuriosire e di rendere determinati concetti intuibili “urbi et orbi”. E, allora, vediamo come risolvevano gli antichi il “problema del bandito”.
Da Fedro, libro V:
Duo cum incidissent in latronem milites, unus profugit, alter autem restitit et vindicavit sese forti dextera.
Latrone excusso timidus accurrit comes stringitque gladium, dein reiecta paenula "Cedo" inquit "illum; iam curabo sentiat quos attemptarit."
Tunc qui depugnaverat:
"Vellem istis verbis saltem adiuvisses modo; constantior fuissem vera existimans.
Nunc conde ferrum et linguam pariter futilem. Ut possis alios ignorantes fallere, ego, qui sum expertus quantis fugias viribus, scio quam virtuti non sit credendum tuae."
Illi adsignari debet haec narratio,qui re secunda fortis est, dubia fugax.
Essendosi due soldati imbattuti in un bandito, uno fuggì, l'altro oppose resistenza e si difese con la forza del suo braccio.
Una volta che il bandito fu sconfitto, il commilitone pavido accorse e con la spada in mano, gettato via il mantello, disse: “Lasciami solo con lui; gli farò vedere che uomini ha osato attaccare!”.
Allora, quello che aveva combattuto:
“Preferivo che almeno con queste parole mi avessi incoraggiato poco fa; avrei potuto essere più risoluto, considerandole vere. Adesso riponi sia la spada che la lingua, ugualmente inutile. Forse puoi ingannare gli altri che non ti conoscono,ma io, che ti ho visto fuggire con tanta forza, so che non si deve credere alla tua virtù.
Questo racconto va applicato a chi è coraggioso quando tutto va bene ma pronto alla fuga quando le cose si mettono male.
Evidentemente, il soldato pavido aveva approcciato un po' troppo alla lettera la scelta dell'“esplorazione”.
