Recommendation system: come Netflix decide cosa consigliarti di vedere

Recommendation system, che sarà mai? Ormai tutte le piattaforme digitali lo utilizzano in maniera più o meno evidente, tuttavia spesso non si sa cosa sia e come funzioni.

Con questo articolo mi sono posto l’obiettivo di approfondire questa tematica personalmente e provare a chiarirla con qualche esempio 🙂

Recommendation system

Partiamo da qualche situazione pratica, ti sarà infatti già capitato di andare su Netflix o su Amazon e trovarti voci del tipo “Consigliati per te..”, oppure “Guarda questo visto che hai già visto quello“. Altre modalità con cui vengono effettuate le raccomandazioni sono nella forma “Molti che hanno comprato X hanno comprato Y“, tipici soprattutto di Amazon.

E tu ogni volta ti chiedi, ma come è possibile che sappiano così bene i miei gusti? Quando mi consigliano delle cose, mi piacciono veramente. Come fanno? 🙂

Beh, dietro a questo sistema di raccomandazioni ci sono algoritmi molto complessi, perfezionati nel tempo e che apprendono mano a mano che tu utilizzi le piattaforme su cui sono implementati.

Sì, infatti ti sarai reso conto che affinchè inizino a consigliarti prodotti che effettivamente ti piacciono, è necessario che tu utilizzi la loro piattaforma per un certo tempo.

Si tratta di Machine Learning, una delle tematiche più interessanti del momento.

Vediamo cos’ha da dirci Wikipedia in merito a questo Machine Learning:

L’apprendimento automatico (anche chiamato machine learning dall’inglese), rappresenta un insieme di metodi sviluppati negli ultimi decenni in varie comunità scientifiche con diversi nomi come: statistica computazionale, riconoscimento di pattern, reti neurali artificiali, filtraggio adattivo, teoria dei sistemi dinamici, elaborazione delle immagini, data mining, algoritmi adattivi, ecc; che “fornisce ai computer l’abilità di apprendere senza essere stati esplicitamente programmati”.

Inizia a farsi un po’ più di chiarezza? Praticamente alla base di Netflix, Amazon e tanti altri servizi ci sono algoritmi che tengono traccia delle tue azioni e, comparandole con quelle degli altri utenti, apprendono i tuoi gusti e sono sempre più in grado, mano a mano che utilizzi la loro piattaforma, di consigliarti con precisione.

E’ spettacolare se ci pensi, quasi come un tuo amico quando ti consiglia di iniziare una nuova serie TV, sapendo che hai già visto “How I Met Your Mother” e ti è piaciuto, per esempio 🙂

La differenza è che chi te lo sta consigliando non è un umano, quindi ci sembra impossibile.

Ma vediamo di andare oltre le apparenze, analizzando come la matematica abbia un ruolo fondamentale in questa fase di previsione ed interpretazione delle preferenze personali 😉

I due tipi di recommendation system

Fin’ora ci siamo occupati di scoprire dove e come veniamo a contatto con questo recommendation system. Vediamo però in che modalità agisce questo sistema e come facciano, senza addentrarci troppo nei dettagli, a scoprire i nostri gusti.

Innanzitutto ti sarai reso conto che i sistemi di raccomandazione si possono dividere in due tipologie, che basano i loro studi su due differenti soggetti:

  • sulle tue precedenti azioni e preferenze (magari voti che hai dato a determinati prodotti, o anche solo prodotti che hai visto)
  • sulle preferenze di “clienti” simili a te in termini di gusti

Nella prima classe di algoritmi, si basa tutto sul tenere traccia dei tuoi click, dei tuoi commenti, delle tue votazioni o anche del tempo che hai trascorso su un determinato prodotto/video. In base a ciò, vengono stilate delle classifiche di ciò che più ti è piaciuto, delle caratteristiche di questi prodotti, dei loro prezzi e di altre loro qualità.

In parallelo gli algoritmi possono accedere alla lista di tutti gli altri prodotti, con relative caratteristiche e pareri degli utenti, consigliandoti quelli più affini alle tue preferenze fin’ora registrate.

Facciamo un esempio molto semplice. Tu hai comprato un libro di matematica, diciamo per esempio “L’ultimo teorema di Fermat” su Amazon.

Che cos’hai fatto quindi scoprire ad Amazon? Beh, molte cose di te. Ovviamente si suppone che la tua scelta sia stata coerente con i tuoi gusti, trascuriamo per il momento il caso che tu lo stia comprando per fare un regalo, in cui la situazione si complicherebbe (infatti questi non sarebbero i tuoi gusti, ma quelli di un tuo amico 😉 ).

Che cosa sa Amazon di te dopo questo acquisto? Probabilmente ti piace la matematica, ti piace leggere, ti piace informarti sui grandi teoremi e matematici della storia. Non dimenticare inoltre che Amazon ha tracciato anche i tuoi click prima di acquistare questo libro, quindi probabilmente ha visto che eri indeciso tra questo e altri libri di divulgazione matematica. Il che non fa che rafforzare le sue conoscenze appena acquisite.

Ovviamente qui sto banalizzando notevolmente il processo di riconoscimento delle preferenze, trascurando completamente che per effettuare delle previsioni sia necessario un campione statistico ben più ampio di un singolo acquisto/visita ad una pagina. Ma per il momento ritengo sia sufficiente, mi interessa chiarire i meccanismi che superficialmente regolano questi sistemi.

Per andare oltre c’è sempre tempo 😉

Ah, ma se provi a guardare la pagina di vendita del libro (ti basta cliccare sul titolo del libro poche righe più in su), noterai che ti compare anche la seguente voce:

“Quali altri articoli acquistano i clienti, dopo aver visualizzato questo articolo?”.

Sotto a tale titolo, troverai una lista di 3-4 libri affini a quello che stai acquistando. Eccoci alla seconda tipologia di recommendation system. Quello basato sugli interessi di utenti che, in passato, hanno dimostrato di essere simili a te in termini di preferenze.

Alla base del meccanismo basato sulla combinazione delle preferenze di tutti gli utenti, vi è un utilizzo massivo di matrici, matrici di enormi dimensioni! Per velocizzare i calcoli e le analisi, gli elaboratori utilizzano strumenti quali la riduzione in valori singolari (SVD) o altre procedure, così da trascurare alcune righe e colonne approssimando le matrici a delle matrici più semplici.

Se sei interessato a questa tematica, potresti iniziare da qualche video su Youtube e poi informarti su Google, magari più avanti troverai qualcosa anche su questo sito 😉

Ecco qui un paio di video interessanti, sono in inglese ma molto comprensibili:

Scomposizione in valori singolari (SVD) : Link

L’algebra del Pagerank di Google: Link

Vediamo, ai fini pratici, come vengono utilizzate le matrici in questa analisi delle preferenze. Per farlo, utilizzerò un esempio semplificato della realtà.

L’esempio sarà inerente a Netflix. Supponiamo di avere solo 4 utenti iscritti e 3 serie TV. Supponiamo inoltre che non tutti e 4 abbiano visto tutte le 3 Serie TV. Ci poniamo l’obiettivo di scoprire se gli utenti potrebbero essere interessati a guardare le Serie mancanti, se potrebbero essere affini ai loro gusti.

Per semplicità supponiamo che ogni utente abbia assegnato una votazione dall’1 al 5 ad ogni Serie TV che ha guardato, in base alle sue preferenze.

Ovviamente questa casistica è super-semplificata, nonostante ciò dovremo usare una matrice 4×3 per analizzarla. Immagina le dimensioni delle matrici con cui Amazon e Netflix hanno effettivamente a che fare quotidianamente 😉

Registriamo quindi sulle righe i 4 utenti, sulle colonne le serie TV. Nelle varie entrate della nostra matrice, andremo a mettere le votazioni assegnate dagli utenti (se ti interessa scoprire qualcosa in più sulle matrici, ecco qui un’articolo che avevo scritto qualche tempo fa: Le matrici: cosa sono e qualche importante utilizzo ).

Ovviamente saranno presenti delle entrate vuote, visto che ogni utente non ha visto almeno una Serie TV di quelle disponibili.

Sulla base della somiglianza delle preferenze tra utenti, vorremmo prevedere che voto darebbero gli utenti mancanti alle Serie TV che non hanno ancora visto, così da sapere se potrebbero piacere loro o no.

Ecco quella che potrebbe essere una matrice delle preferenze:
Recommendation System
Ora proviamo  ad analizzare questa semplice tabella, che escludendo la prima riga e colonna diventa una bellissima “matrice delle preferenze”.
Potrebbe interessare Luca la serie TV “Tredici”? Beh, dura a dirsi dato che a lui è piaciuto “Narcos”, differentemente dagli altri che l’hanno visto. Tuttavia è concorde agli altri rispetto a “Sherlock”, dobbiamo quindi capire a quale di queste due, la Serie TV che deve ancora vedere, è più affine. Diciamo che l’esempio non è dei migliori 🙂
Però probabilmente a Luca non piacerebbe vedere “Tredici” dato che Sara ha detto che le piace moltissimo, mentra ha votato con un misero ‘2’ “Narcos”, che invece piaceva a Luca.
Ovviamente questa analisi non è per niente consistente a livello statistico e degna di un’intelligenza artificiale, ma è un ragionamento che, se basato su un campione di Serie TV e utenti molto più vasto, può essere molto efficace.
Per questa introduzione, un po’ approssimativa, alle due tipologie di recommentation system utilizzate attualmente, penso sia sufficiente. Vediamo, giusto per curiosità, nel prossimo paragrafo come si è arrivati all’algoritmo attuale di Netflix e alcuni riferimenti autorevoli nel caso tu voglia approfondire, cosa che ti consiglio vivamente (ricordati che questa è la direzione verso cui stiamo andando, intelligenza artificiale e machine learning sono il futuro 😉 ).

Netflix prize e alcuni riferimenti autorevoli

Alle origini, Netflix basava i suoi affari sul noleggio di DVD e videogiochi prenotabili online ma inviati in seguito a casa. Già al tempo vi era una bozza di sistema di raccomandazioni, basato su alcuni algoritmi più semplici degli attuali, basato semplicemente sulle loro preferenze passate.

Il miglioramento di queste infrastrutture vede il picco nel momento in cui Netflix si è lanciata nel mondo dello streming online, in quanto in questo contesto la raccolta dei dati era molto più immediata e inconsapevolmente gli utenti inviavano molte più informazioni. Ora non solo potevano accedere allo storico dei film noleggiati, ma ogni singolo click è tracciabile!

Nel 2006 l’azienda ha lanciato un concorso, avente 1 milione di dollari in premio, per chi ofsse riuscito a rendere più preciso il recommendations system utilizzato fino a quell’anno, rendendo così il potenziale dell’azienda molto superiore (rendendola più “umana”).

In termini matematici, loro avevano l’obiettivo di diminuire l’errore commesso consigliando un determinato film ad un dato utente. Questa è l’unica formuletta dell’articolo, ma la ritengo utile:

RMSE

L’RMSE è una metrica utilizzata spesso per valutare l’efficacia dei metodi predditivi, in caso non ti interessi approfondire, ti basti sapere che è un indice di accuratezza dell’algoritmo.

Tra le proposte più innovative ci fu quella del team BellKor’s Pragmatic Chaos, che nel 2009 si aggiudicò il premio con un cocktail letale di 107 algoritmi e oltre 2000 ore di lavoro.netflix prize

Riferimenti autorevoli per eventuali approfondimenti:

Libri:

  • Learning from Data: Link
  • The Elements of Statistical Learning: Data Mining, Inference, and Prediction: Link
  • Hands-On Machine Learning: Link

Risorse:

  • Informazioni sull’algoritmo vincente e sul Netflix Prize: Link
  • Interessante corso “Master Recommender Systems”: Link
  • Creazione guidata Recommendation System con Python: Link
  • Video introduttivo ai Recommendation Systems: Link
  • Recommendation System, lezione sul Machine Learning: Link
  • Machine Learning: cos’è e perchè è importante: Link
  • The Netflix Recommender System: Algorithms, Business Value, and Innovation: Link

Distanti ma vicini: alla scoperta del concetto di distanza

Nella vita quotidiana si incorre spesso in discorsi che, se analizzati più nel profondo, possono risultare errati o poco precisi.

Con ‘poco precisi’, intendo da un punto di vista matematico. Spesso vengono coinvolti infatti concetti con una certa superficialità, solitamente perchè non è necessario coinvolgere precisazioni superiori dato che ci si capisce e ciò è sufficiente.

Alcune cose infatti vengono approfondite solo dagli addetti ai lavori, solo da chi cerca appositamente chiarezza a riguardo. Ma, nonostante ciò, anche chi si interessa ad approfondire non ha motivi per essere così rigoroso nel linguaggio comune. Vediamo in questo articolo un esempio di queste situazioni, in cui talvolta qualche precisazione in più non guasterebbe.

distanza

Il concetto di distanza è proprio uno di quelli, quando si parla di distanza tra due posti, tra due persone o tra qualsiasi coppia di oggetti, si sottintende sempre una cosa…stiamo parlando di distanza euclidea.

Cosa vuol dire distanza euclidea? Come fanno due cose ad essere distanti e vicine allo stesso tempo? Perché usiamo naturalmente la distanza euclidea e non altre? Quali altre distanze usiamo senza accorgercene?

Queste sono tutte domande che ho citato per alimentare la tua curiosità, con calma le svilupperemo nel corso dei prossimi paragrafi.

Partiamo con questa trattazione mettendo un po’ d’ordine ed introducendo qualche formalismo matematico, come piace a noi

Per non complicarci eccessivamente la vita, cerchiamo di ragionare come se ci trovassimo su un piano. Questa approssimazione non è per niente assurda se ci si concentra su una zona della terra abbastanza ristretta, così da essere ben approssimabile con un piano.

Bene, ora diciamo distanza un’applicazione (funzione) che manda qualsiasi coppia di punti del piano nella loro distanza, un numero reale non negativo.

Una volta definito su un piano un insieme di punti P, possiamo definire in modo molto rigoroso questa funzione come

d\colon P\times P \to \mathbb{R}

A,B \to d(A,B).

Essa gode di alcune proprietà interessanti. Innanzitutto essa è uguale a zero se e soltanto se, presi due punti qualsiasi dell’insieme di partenza, essi coincidono. Inoltre essa è simmetrica, detti cioè A e B due punti del piano e ‘d’ la funzione di distanza, d(A,B)=d(B,A). Ossia la distanza di due punti non varia al variare del ‘verso di percorrenza’.

L’ultima proprietà che voglio citarti, e forse la più importante, è la disuguaglianza triangolare. In termini pratici essa formalizza il seguente intuitivo concetto, presi tre punti sul piano A, B, C è più breve il percorso per andare da A a C direttamente, piuttosto che passare anche da B.

In termini più formali, d(A,B)+d(B,C)\geq d(A,C). Non voglio perdermi troppo su ciò, anche se meriterebbe, ma ti consiglio di riflettere su alcune proprietà dei triangoli alla luce della disuguaglianza triangolare

Giusto per completezza, ci tengo a dirti che una distanza viene spesso chiamata metrica e che un insieme di elementi, dotato di una metrica (su esso ben definita) viene detto spazio metrico.

Scarica un PDF con 50 giochi logici (con soluzione)

Scarica un PDF con 50 giochi logici (con soluzione) e ricevi quotidianamente un’email riguardo la matematica (articoli, libri, film…). Ti basta inserire la tua email qui sotto 😉

Che cos’è la distanza euclidea?

La distanza euclidea è quella con la quale sei abitualmente portato a ragionare..i motivi di questo fatto sono principalmente due:
1. È intuitiva e pratica
2. È facile da visualizzare

Da un punto di vista formale, questa distanza è detta metrica L2. Ma non è niente di strano, solo un nome 😉

Da un punto di vista pratico, la distanza euclidea è il cammino più breve che congiunge due punti del piano. Breve nel senso naturale del termine, ossia quello che misura meno se lo si valuta con metro o righello.

Nel piano le distanze euclidee tra coppie di punti sono ‘realizzate’ dai segmenti che li congiungono.

Per determinare la distanza tra due punti nel piano si applica infatti banalmente il teorema di Pitagora. Vediamo come…

Prendiamo due punti nel piano di coordinate (a,b) (x,y). La loro distanza euclidea sarà \sqrt{(x-a)^2+(y-b)^2}. Se provi a farti un semplice disegno su carta o su geogebra, con x-a e y-b stiamo indicando la lunghezza di base e altezza di un triangolo rettangolo avente tra i vertici i due punti da noi introdotti.

Il terzo vertice, per completezza, sarà di coordinate (x,b).

Ma che altre possibili distanze ci sono?!

Forse lo scorso paragrafo ti è sembrato poco utile, dato appunto che naturalmente ragioni in questi termini e molto probabilmente non hai mai visto una distanza che non sia quella euclidea.

Piuttosto che spiattellarti davanti agli occhi una lista di altre distanze/metriche preferisco costruirle con calma insieme a te, partendo da degli esempi.

La metrica del Taxi

Iniziamo con la METRICA DEL TAXI che, come dice il nome, si basa su ciò che i tassisti, soprattutto a New York (o in città in cui il sistema stradale forma delle griglie sulla città), utilizzano per stabilire la strada più breve da percorrere per andare da un punto A ad un punto B della città. Prova per un attimo a pensare, avendo una città con le strade messe a griglia, con i palazzi nelle aree delimitate dalle strade, come sceglieresti la strada migliore da fare per andare da A a B? Sicuramente non collegheresti i due punti con un segmento, dato che non esiste una strada che ti congiunge i due punti con questo percorso (certo, sto escludendo il fatto che tu abbia un aereo supponi di doverti muovere in auto, bici, monopattino o a piedi). Ovviamente misureresti il percorso più breve muovendoti sulle strade…bene allora stai ragionando non con la metrica euclidea, ma con la metrica del taxi, talvolta detta 1-distanza.

In termini più formali, detta ‘d’ la 1-distanza, e dati due punti A=(a,b) e B=(x,y) si ha che d(A,B)=|x-a|+|y-b|..preferisco non approfondire ancora questa parte, ma ti consiglio di farti qualche esempietto su carta che va sempre bene.

Una metrica mista

Vediamo ora un’altra metrica particolare che spesso si usa. Ti è mai capitato di definire una meta ‘distante’ se si trovava oltre una certa soglia da te concepita come ‘distante’? Mi spiego meglio, diciamo di trovarci in un punto A della città e di avere due mete B e C. Ora, ti è mai capitato di definire sia B che C distanti nonostante magari in linea d’aria B disti 100km mentre C 300km?

Immagino di sì, infatti noi siamo spesso portati a semplificare, quindi oltre una certa soglia non ci interessa la precisione ma la praticità…non ci importa quindi non precisare che C è PIÙ DISTANTE di B da A. Bene, la metrica discreta fa proprio questo.

Supponiamo per esempio che oltre il raggio dei 50km diciamo una meta distante. Bene, allora definiamo una metrica discreta ‘d’ come segue:
* se in linea d’aria la distanza è minore di 50km allora d(A,B)=0
* altrimenti d(A,B)=1.

Volendo possiamo definire A e B vicine se la loro distanza discreta è 0, distanti altrimenti.

La metrica discreta

Poi ancora più particolare è la metrica discreta, in cui tutti i punti distano 1 a meno di scegliere due punti coincidenti. La praticità e la frequenza con cui quotidianamente si usa questa distanza è abbastanza bassa, ma a volte può capitare…

Altre distanze interessanti sono le p-distanze (di cui la metrica euclidea e del taxi fanno parte) che sono così definite:
Siano dati due punti A=(a,b) B=(x,y), si ha che detta ‘d’ la p-distanza, d(A,B)=((x-a)^p + (y-b)^p)^{1/p} il cui caso limite è la distanza infinito.

La distanza infinito di A da B è \max{|x-a|,|y-b|}, per il momento penso siano sufficienti queste introduzioni, giusto da mettere in chiaro che noi abitualmente ragioniamo in termini di distanza euclidea (2-distanza) ma essa è solo una tra le tante.

Come fanno due cose ad essere distanti e vicine allo stesso tempo?

Ormai la risposta a questa domanda, che poteva sembrare stravagante qualche minuto fa, mi sembra quasi ovvia.

Infatti la domanda è poco precisa dopo aver visto come non esista una sola distanza. Per esempio possiamo prendere due oggetti distanti, in linea d’aria 1000km (rispetto alla comune 2-distanza), rispetto alla distanza discreta saranno distanti 1 (quindi possiamo dirli vicini) e rispetto alla distanza euclidea sono invece molto distanti Semplice, no?!

Scarica un PDF con 50 giochi logici (con soluzione)

Scarica un PDF con 50 giochi logici (con soluzione) e ricevi quotidianamente un’email riguardo la matematica (articoli, libri, film…). Ti basta inserire la tua email qui sotto 😉

Teoria dei giochi – Introduzione, equilibrio di Nash e primi esempi

Che cos’è un gioco? Un gioco, in termini matematici, non è niente di diverso da un gioco come siamo abitualmente soliti definirli. Tuttavia i giochi matematici racchiudono una classe di situazioni molto più ampie dei comuni giochi cooperativi e non, a cui abbiamo giocato tutti qualche volta.

Teoria dei giochi

Prima di passare alla definizione più teorica, preferisco che tu abbia in testa almeno un esempio di gioco, così da riportare ciò che scriverò al tuo caso. Alcuni giochi sono il pari e dispari, una partita di scacchi, una decisione tra andare al teatro o allo stadio (magari tra marito e moglie), la scelta del gusto del gelato e tutte situazioni ad esse simili.

Si può andare anche più nel complesso come nel caso delle strategie applicate in guerra, ci sono molte trattazioni a riguardo, ma molto più avanzate rispetto alle basi che vedremo qui di seguito.

Si definisce gioco qualsiasi interazione tra due o più oggetti/partecipanti le cui sorti dipendono dalle scelte di questi.

E’ quindi un gioco una qualsiasi situazione in cui va effettuata una decisione, va eseguita un’azione e ciò che accade al termine dell’interazione tra i partecipanti dipende dalle scelte fatte da essi.

Per incuriosirti un po’ ecco uno spezzone di un film che secondo me tutti devono vedere almeno una volta:

Possiamo categorizzare i giochi in funzione delle loro proprietà e modalità di sviluppo. Intanto partiamo con una prima distinzione: giochi in forma normale e giochi in forma estesa.

Non voglio appesantire fin da subito questo articolo, quindi direi che è il momento di un esempio, così da inquadrare un po’ ciò di cui stiamo parlando.

Pari e dispari

Il pari e dispari è un gioco a cui tutti, almeno una volta, hanno giocato. Vediamo come sia possibile descrivere questo gioco:

  1. I partecipanti sono 2
  2. Ogni giocatore ha 6 possibili mosse. Deve scegliere uno tra i seguenti numeri: 0,1,2,3,4,5.
  3. Ogni giocatore, prima di iniziare a giocare, ha deciso se “preferisce” Pari o Dispari e le due scelte devono essere l’una diversa dall’altra (se io scelgo pari, tu per forza avrai dispari) .

L’esito della partita dipende dal risultato della somma dei numeri scelti, in contemporanea, dai due giocatori. Supponiamo per comodità, che il Giocatore 1 vince in caso esca Pari e il 2 in caso esca Dispari.

Una volta determinate queste caratteristiche, seguono immediatamente alcune conseguenze. Per esempio, questo è un gioco in cui non esiste il pareggio. Infatti non esistono altre possibilità, ogni numero naturale è Pari o Dispari, per cui uno dei due partecipanti necessariamente vince.

Hanno entrambi la stessa probabilità di vittoria, infatti ciascuno vince in 2 casi su 4 (indicando con P e D la scelta pari e dispari, le coppie ordinate di possibili esiti sono infatti queste 4 PP,PD,DD,DP).

Bene, per ora non approfondiamo oltre l’esempio. Lo riprenderemo più avanti parlando di Equilibrio di Nash. Detto ciò, notiamo come in questo gioco particolare, i giocatori muovono contemporaneamente, è quindi un gioco in forma NORMALE.

Altra caratteristica di questi giochi, è che i giocatori non possono stringere accordi vincolanti nel corso della partita. Possono però comunicare prima che essa inizi.

Per vincolanti intendo che non si può condizionare la scelta dell’avversario con accordi più o meno vantaggiosi, facendo sì che se l’avversario non seguisse l’accordo verrebbe punito per questo. Ogni tipo di comunicazione deve precedere la partita, come se si telefonassero i giocatori prima di iniziare a giocare per decidere le regole e le modalità con cui il gioco si svilupperà.

Giochi in forma normale e giochi in forma estesa

Queste due categorie di giochi, fanno parte della classe dei giochi non cooperativi. Ossia giochi durante i quali non è possibile dialogare e contrattare. Tutto ciò che regola il gioco viene modellizzato prima che esso inizi (regole, turni e quant’altro).

Nei giochi in forma normale, i giocatori muovono simultaneamente, lo stesso numero di volte. I giochi in forma estesa, invece, si sviluppano nel tempo. In essi non tutti i giocatori muovono necessariamente insieme e lo stesso numero di volte.

Nei giochi in forma normale, quindi, i giocatori non possono muovere conoscendo ciò che gli altri hanno fatto, diversamente dai giochi in forma estesa, come gli scacchi.

Come abbiamo visto con l’esempio precedente, ogni giocatore ha alcune preferenze. Esse possono essere precisate con dei Payoff, dei premi che variano in valore in funzione delle preferenze dei giocatori stessi.

Nell’esempio del pari e dispari, se io scelgo Pari si può supporre che lo faccia perchè ha la possibilità di vincere più soldi in caso di vittoria. Diciamo quindi Payoff il premio che io vinco in caso si verifichi una data sequenza di scelte da parte dei giocatori.

Segue che ogni gioco in forma normale/estesa può essere descritto definendo i partecipanti, le mosse che hanno a disposizione (le modalità in cui esse vanno fatte, nel caso dei giochi in forma estesa) e i Payoff.

Per rappresentare un gioco in forma normale si utilizzano solitamente le tabelle a doppia entrata, mentre per rappresentare i giochi estesi si è soliti utilizzare degli alberi.

Si potrebbe dire molto di più riguardo a queste due branche di giochi, ma per il momento preferisco lasciare solo due immagini in cui penso vengano chiariti molti dettagli. Magari in separata sede, dedicherò un articolo più dettagliato a questa parte.

Gioco in forma estesa

Gioco in forma estesa (albero)

Dilemma del prigioniero

Gioco in forma normale (tabella doppia entrata)

Cos’è un equilibrio di Nash

La teoria dei giochi deve moltissimo a John Nash, grande matematico a cui è stato anche dedicato un film negli ultimi anni (‘A beautiful mind’). Se ti interessano i film sulla matematica ecco qui un articolo che fa per te: I 5 migliori film sulla matematica

A lui è dovuto il concetto di equilibrio all’interno di un gioco. In parole povere, per equilibrio si intende una situazione in cui nessuno dei giocatori ha interesse a cambiare la scelta fatta.

Se hai osservato con attenzione le immagini qui sopra, avrai senz’altro notato che per giungere ad ogni payoff, è necessaria una specifica sequenza di mosse, di scelte dei giocatori. Bene, se quando si è giunti ad un payoff, tutti i giocatori non hanno motivi per pentirsi della sequenza di scelte fatte, allora siamo in un equilibrio.

In quali situazioni un giocatore potrebbe ‘pentirsi’ delle scelte fatte e volerle cambiare? Quando è consapevole che ha ‘vinto’ meno di ciò che potenzialmente avrebbe potuto vincere.

Supponiamo quindi di arrivare ad un punto in cui il gioco si conclude, io ho effettuato due mosse che chiamo M1 e M2. Il mio avversario ha fatto L1 e L2. Mi rendo conto che in tali circostanze vincerei 10€. Supponiamo per un momento che il mio avversario faccia le stesse esatte mosse, ora mi chiedo: avrei potuto vincere di più di 10 se avessi fatto mosse diverse da M1 e M2?

In caso di risposta affermativa, allora non sono in una situazione di equilibrio, altrimenti dovrei fare la stessa verifica anche nella direzione opposta, così da verificare se esso sarebbe solo un equilibrio per me o anche per il mio avversario.

Prima di proseguire alla ricerca di un equilibrio in un esempio molto famoso, vorrei tornare un attimo sul pari e dispari. Esso è infatti un gioco senza equilibri di Nash se si gioca solo con strategie pure.

Specifichiamo quindi due cose: cosa si intende per strategie pure e perchè in quel caso non ci sono equilibri?

Per strategie pure si intende che le scelte vengono effettuate sulle possibilità a disposizione, non vengono lasciate al caso. Si parla invece di strategie miste in situazioni dove per esempio si lancia un dado che ha probabilità P che esca la faccia ‘6’, se uscisse un 6 allora sceglierei pari, altrimenti dispari.

In tal caso si può dimostrare che se P=1/2, ed entrambi i giocatori scegliessero tra Pari e Dispari con lo stesso metodo, allora saremmo in un equilibrio. Comunque ho già programmato di scrivere un articolo interamente dedicato all’interazione dei questi giochi con la probabilità, così da avanzare nella conoscenza della teoria dei giochi con casistiche più interessanti.

Perchè non ci sono quindi equilibri puri nel pari e dispari? Beh, è molto intuitivo, infatti in ogni possibile Payoff in cui mi posso trovare al termine del gioco, supponendo che ogni giocatore giochi per vincere, uno dei due giocatori avrà sempre interesse a cambiare la scelta perchè solo in tal caso potrebbe vincere. Non ci troveremmo quindi mai in una situazione di equilibrio.

Vediamo qui sotto un gioco molto famoso, lo utilizzeremo per comprendere meglio il concetto di equilibrio.

Il dilemma dei prigionieri

Il dilemma del prigioniero è un gioco proposto negli anni cinquanta del XX secolo da Albert Tucker come problema di teoria dei giochi. Oltre ad essere stato approfonditamente studiato in questo contesto, il “dilemma” è anche piuttosto noto al pubblico non tecnico come esempio di paradosso.

Il dilemma in sé, anche se usa l’esempio dei due prigionieri per spiegare il fenomeno, può descrivere altrettanto bene la corsa agli armamenti, proprio degli anni cinquanta, da parte di USA e URSS (i due prigionieri) durante la guerra fredda.

Ecco qui la tabella a doppia entrata in cui può essere sintetizzato il gioco.

 

Dilemma del prigioniero

 

In breve, la situazione è questa:

Ci sono due prigionieri a cui viene data la possibilità di confessare. Se entrambi lo fanno, trascorreranno 5 anni a testa in prigione. Se solo uno dei due lo farà, l’altro ne trascorrerà 10 in prigione. Se nessuno dei due confessasse, trascorrerebbero solamente 2 anni a testa in prigione. (gli anni possono variare, l’importante è il concetto dietro a questa trattazione)

E’ chiaro che se mettessero il proprio interesse prima di tutto, senza valutare bene la situazione, finirebbero entrambi a farsi 5 anni in prigione. Confessando infatti avrebbero la possibilità di essere liberati. Peccato che ciò accadrebbe solo se non lo facessero entrambi.

Qual è quindi secondo te l’equilibrio di Nash di questo gioco?

Apparentemente quindi converrebbe ad entrambi non confessare, dato che il totale degli anni trascorsi in prigione sarebbero soltanto 4. Tuttavia se analizzi il tutto dal punto di vista del singolo giocatore, confessare risulta senz’altro la scelta da essi preferita.

Infatti se il giocatore 1 confessa, allora anche al 2 conviene confessarlo dato che altrimenti si beccherebbe 10 anni di prigione.

Se invece il giocatore 1 non confessasse, comunque al giocatore 2 converrebbe confessare dato che, in tali circostanze, uscirebbe indenne dalla prigione.

Lo stesso ragionamento può essere ripetuto supponendo fissata la scelta del giocatore 2 e verificando come, in qualsiasi caso convenga scegliere di confessare anche al giocatore 1.

Infatti si può notare come confessare è strategia dominante per entrambi, è la scelta preferita da entrambi i giocatori indipendentemente da ciò che accade nel gioco stesso.

L’equilibrio è quindi (confessa,confessa) ed è qui che nasce un paradosso, infatti nelle loro migliori scelte vanno a trascorrere in galera più anni di quanti ne avrebbero potuti trascorrere se avessero potuto accordarsi.

Se infatti fossero entrambi certi che l’altro giocatore avesse scelto di non confessare, avrebbero potuto trascorrere solo 2 anni in prigione a testa. Ora invece ne trascorreranno 5 a testa, ma saranno comunque “contenti” delle loro scelte in quanto esse, indipendentemente dalle scelte dell’altro giocatore, garantivano il miglior risultato.

Conclusione di questa introduzione alla teoria dei giochi

Per questa introduzione è tutto, spero di essere riuscito a descrivere i fondamenti della teoria dei giochi in maniera abbastanza chiara. Se non altro, spero di averti incuriosito e di averti fatto venir voglia di cercare altre informazioni online a riguardo.

Infatti ci sono interi corsi, video online gratuiti, ti rimane solo da trovarli ed imparare, detto ciò ho già anticipato che questo non sarà l’ultimo articolo relativo a questa tematica. Infatti la teoria dei giochi mi interessa parecchio e quando ho del tempo ne approfitto per continuare ad esplorarla. Quindi aspettati nuovi articoli in futuro 😉

Al prossimo articolo

Davide

Il commesso viaggiatore… Alla scoperta della Programmazione Lineare

Amazon riceve decine di milioni di nuovi ordini ogni giorno. Un numero che solo a pensarlo può dare un senso di stordimento.

Mettiamoci nei panni di uno dei servizi di spedizione a cui questa grande compagnia si appoggia. Il flusso di pacchi da gestire è enorme e per aumentare al massimo il profitto bisogna trovare un modo per ridurre al minimo il percorso di ogni spedizioniere.

Qui salta fuori il famoso problema del “Commesso viaggiatore”, ossia come trovare il tragitto più breve che passi per un insieme finito di punti nello spazio.

In questo post cercheremo di cogliere la reale complessità del problema e di risolverlo andando così… alla scoperta della Programmazione Lineare.

Il commesso viaggiatore

Cos’è il Travelling Salesman Problem?

Nell’introduzione abbiamo visto come il problema che stiamo analizzando nasca da un contesto prettamente concreto. Per cercare di capire come risolverlo la prima cosa da fare è sempre la stessa: fare conoscenza con il problema. Per fare questo, solitamente, i matematici non seguono alla lettera le regole del galateo, ma si mettono a dividere tutto in pezzi e a dare un nome ad ogni componente.

Noi da aspiranti matematici faremo lo stesso!

Definiamo quindi un insieme contenente tutti i punti da raggiungere, P = \{ p_{1} ,  ... , \ p_{n} \} e un insieme T che rappresenti i possibili tragitti con la loro lunghezza: n=t_{ij} \in T se esiste un percorso che va da p_{i} a   \ p_{j} di lunghezza n.

Utilizzando il vettore \vec{x}, di cui ogni componente rappresenta un tragitto all’interno del percorso considerato (vedremo poi meglio come è fatto), definiamo una funzione \tau: \vec{x} \ \rightarrow \mathbb{R} che assegna ad ogni percorso la sua lunghezza.

Il problema si può ora vedere in modo più formale come: trovare il vettore \vec{x}  tale per cui \tau (\vec{x})  sia minimo.

Forse tutto questo matematichese ti ha confuso un po’, ma se provi a rileggere il tutto con attenzione ti accorgerai che non abbiamo fatto altro che riscrivere in formula il problema di prima.

Ora puoi dire che come era scritto inizialmente era molto più semplice (e ti daremmo ragione), ma questa nuova veste dà al quesito un aspetto più trattabile da un punto di vista matematico/computazionale.

Per trovare una soluzione al problema del commesso viaggiatore andiamo a scoprire uno degli strumenti più potenti nel campo dell’ottimizzazione lineare: la Programmazione Lineare.

Preliminari alla Programmazione Lineare

Prima di riuscire a riscrivere il problema dobbiamo introdurre il concetto di funzione lineare.

Diciamo funzione lineare una funzione del tipo f ( x_1 , ... \ , x_n ) = \sum_{j=1}^{n} a_{j} \times x_{j} dove a_j \in \mathbb{R} .

Guardandola bene possiamo capire che il termine lineare significa semplicemente che l’argomento della funzione è di primo grado.

Analogamente diciamo che un vincolo è lineare se è nella forma \sum_{j=1}^{n} a_{j} \times x_{j} \le b dove a_j e b \in \mathbb{R} .

Ricerchiamo l’ottimo con la PL

A questo punto vogliamo esprimere un percorso tramite il vettore \vec{x} . Come facciamo?

Una possibile soluzione è la seguente: definiamo una variabile per ogni possibile tragitto. Ad esempio x_{ij} identifica il tragitto dal punto p_i  al punto p_j . Ora poniamo x_{ij} uguale a 1 se il tragitto è compreso nel percorso considerato, 0 altrimenti.

Ricordandoci del significato di  T possiamo finalmente costruire la nostra tanto sudata funzione lineare \tau(\vec{x}) = \sum_{i=1}^{n} \sum_{j=1}^{n} t_{ij} \times x_{ij} .

Ci resta soltanto da porre delle condizioni che obblighino il percorso analizzato a passare per tutti i punti.

Ne servono 3!

\sum_{i=1}^{n}  x_{ij} = 1 \  \forall j \in \{1 , ... , n\} , ossia ogni punto ha solo un percorso “entrante” …

\sum_{j=1}^{n}  x_{ij} = 1 \  \forall i \in \{1 , ... , n\} , ossia ogni punto ha solo un percorso “uscente”….

e

x_{ij} \in \{ 0 , 1 \} , ossia le uniche possibilità sono utilizzare un tragitto (1) o non considerarlo (0).

(Per correttezza si dovrebbe utilizzare una quarta condizione per evitare la presenza di sottocircuiti non connessi che però qui tralasciamo per semplicità).

Formalizzazione del problema del commesso viaggiatore

Riassumendo tutto quello che abbiamo detto il Travelling Salesman Problem diventa:

min \sum_{i=1}^{n} \sum_{j=1}^{n} t_{ij} \times x_{ij} 

sotto le condizioni

\sum_{i=1}^{n}  x_{ij} = 1 \ \forall j \in \{1 ,  ... , n\}

\sum_{j=1}^{n}  x_{ij} = 1 \  \forall i \in \{1 , ... , n\} 

x_{ij} \in \{ 0 , 1 \}

Molto bene… E ora?

Abbiamo dato una veste molto elegante al nostro problema, ma come lo risolviamo?

Il bello della programmazione lineare è proprio questo, “non ci interessa”!

Una volta scritto il problema secondo questo formalismo è sufficiente delegarlo ad un buon risolutore.

Qui trovate una spiegazione di come risolvere problemi del genere utilizzando Excel.

Per capire cosa succede all’interno di questi applicativi bisognerebbe aprire una lunghissima e complessa parentesi sul metodo del simplesso. Lascio ai più curiosi l’occasione di approfondire (poi se serve un aiuto scriveteci pure 🙂 ).

Il lato oscuro del commesso viaggiatore

Siamo quasi alla fine e sembra ormai che per i servizi di spedizione il problema delle consegne sia stato risolto. Tutto va bene finché il numero di punti di consegna non aumenta e il nostro metodo non riesce più a fornire una soluzione.

La modellizzazione che abbiamo fatto è infatti NP-completa e quindi il tempo di esecuzione del nostro metodo cresce in modo non polinomiale (e quindi MOLTO velocemente) al crescere del numero di punti analizzati.

E’ proprio questa difficoltà che apre lo scenario ad altre tecniche di risoluzione. L’ideale sarebbe trovare un algoritmo polinomiale, ma non sappiamo ancora se questo è possibile (l’argomento della NP vs P è stato accennato recentemente qui).

Per ora sembra che, nel caso in cui il percorso debba passare per un numero elevato di punti, non si possa trovare la soluzione ottima al problema del commesso viaggiatore in tempi ragionevoli. In pratica quindi si deve abbandonare la speranza di trovare l’ottimo ed accontentarsi di una sua approssimazione.

Futuri viaggi del commesso

Entriamo così nel mondo dell’euristica dove si va a cercare di trovare dei buoni candidati per ottenere l’ottimo utilizzando tecniche di tipo probabilistico/stocastico.

Queste metodologie sono molto interessanti e suggestive. Nel futuro andremo quindi a richiamare il nostro commesso per partire con lui in un nuovo viaggio… alla scoperta del Calcolo Stocastico!

Come abbiamo visto in questo articolo spesso molti problemi della vita quotidiana vengono affrontati facendo uso del sapere matematico.

Questo mi fa pensare che chi dedica la vita allo studio della matematica non sia poi così folle!

Spero che l’articolo ti sia piaciuto, a presto 😉

Marco

Caffè matematico n° 2 – Il cubo di Rubik – Il gioco del Demonio

Benvenuti a questo secondo caffè matematico: oggi parliamo un po’ di algebr… ehm, del cubo di Rubik! Dato che il tempo a disposizione è poco (il tempo di un caffè appunto 😉 ) sarò breve, ma l’argomento è molto interessante e merita di essere approfondito, pertanto prometto di scriverne al riguardo tra non molto ;).

Cubo di Rubik

Il cubo di Rubik

Praticamente tutti conoscono il famosissimo cubo del professore Ernő Rubik. Esso è probabilmente il gioco più venduto della storia ed è considerato da coloro che non sono mai riusciti a risolverlo un vero rompicapo.

Ma cosa vuol dire effettivamente risolverlo? Beh, matematicamente si potrebbe dire che il problema è ben posto, cioè che la soluzione esiste ed è unica. Essa altro non è che il procedimento algoritmico che riesce a permutare i singoli blocchetti in modo che su tutte le facce compaia un solo colore, diverso per tutte e 6 le facce.

Un po’ di algebra

Ma in quanti modi differenti si possono permutare le facce del cubo? Beh, facciamo un po’ di calcoli… Ci sono 3 strati verticali e 3 orizzontali in ogni faccia e possono essere ruotati singolarmente 3 volte, fino a tornare alla posizione originaria. Dunque siamo già a 3x3x3 possibilità di modificarlo. Tutto questo va considerato per 6 facce. Giusto? SBAGLIATO! Attenzione! Se ruotate una faccia, anche tutte quelle intorno vengono di conseguenza modicate! Trovare tutte le possibili permutazioni non è purtroppo così facile come sembra…

Si potrebbe andare avanti parecchio, ma meglio se vi do la soluzione… Si può dimostrare che il numero di configurazioni differenti che un cubo di Rubik può assumere è dato da:

227314537211=43252003274489856000,

cioè circa 0.4*1020. Immaginiamo che per guardare ogni possibile configurazione ci voglia un secondo. 60 fanno un minuto. Per 60 e siamo a un’ora e così via… Se adesso dividiamo 43252003274489856000 per i secondi che ci sono in un anno, otteniamo 1370 miliardi. Il nostro Universo ha poco meno di 14 miliardi di anni, la terra 4. Il sole ne brucerà per circa altri 5. Insomma, riuscire ad elencare tutte le configurazioni di un cubo di Rubik sembra un’impresa assolutamente impossibile.

Giochi senza frontiere

Questo fatto però non deve scoraggiarci: per trovare la soluzione al rompicapo infatti non è necessario conoscere tutte le possibili configurazioni, ma basta saper destreggiarsi tra un po’ di esse con sufficiente abilità. Tra le tante soluzioni che si possono trovare in rete, tutte quante hanno come denominatore comune l’approccio algoritmico: non importa avere un’idea geniale e ogni volta rimettersi a pensarne una nuova: basta solo osservare la configurazione in cui il cubo si trova e procedere algoritmicamente sistemando gruppi di tasselli alla volta.

Attualmente nessuno riesce a farlo in meno di 4 secondi e 73. Voi ci siete mai riusciti? In quanto?

A mercoledì prossimo con il prossimo caffè 😉

Au revoir

Erik

ceterum censeo festascienze esse facendam