Blog divulgativo sulla matematica applicata

Come Netflix capisce il film che volete vedere: Matematica, Machine Learning e Serie Tv

Quale sarà il prossimo film che ameremo su Netflix o il prossimo video che guarderemo su Youtube? E la prossima canzone su Spotify? Siamo proprio sicuri che i nostri gusti siano esattamente nostri?

Il fatto che i computer riescano a proporci prodotti in linea con i nostri gusti, a prima vista può sembrare assurdo, ma in realtà tutto è permesso da semplici (si fa per dire) algoritmi. In questo post faremo una breve introduzione sulle tecniche che si celano dietro tali sistemi detti recommendation systems.

unnamed

Un po' di anni fa, quando il web non era ancora parte integrante della nostra quotidianità, ricevevamo consigli su film, libri, musica, viaggi e quant'altro, prevalentemente in due modi:

  • Dalle persone a noi vicine, che possiamo considerare come un tipo di consiglio personale e modellato sui nostri gusti ma dallo spettro abbastanza ristretto, nel senso che in questo modo è più complicato incontrare cose distanti da noi (banalizzando un po', i nostri amici hanno gusti simili ai nostri);
  • Dai mass media, pensiamo ad esempio alla pubblicità sui giornali o in TV, si tratta senza dubbio di un suggerimento non personale ma a spettro ampio poiché ci mette a conoscenza di cose distanti da noi.

Oggi, invece,  la tecnologia sta radicalmente trasformando le nostre abitudini: viviamo in un mondo sempre più connesso e digitalizzato in cui gli smartphone, i wereable, i pc, i social network, la tessera dei trasporti pubblici...ogni nostra singola attività crea una grande quantità di dati. Ci fa riflettere il fatto che l'80% dei dati esistenti sia stato creato soltanto nell'ultimo paio di anni e che ogni giorno se ne creino sempre di più, nell'ordine del milione di Petabyte.

L'enorme quantità di informazioni disponibili rappresenta una grande opportunità di sviluppo non solo per l'informatica, la matematica, l'ingegneria e tutte quelle branche che mescolandosi formano la scienza dei dati, ma anche per le aziende, che ne stanno approfittando per offrire un servizio migliore al cliente aumentando i ricavi. L'Internet Of things, o addirittura l'Internet Of Everythings, sta portando una vera e propria rivoluzione sia nei servizi, sia nel mondo del manifacturing: la cosiddetta Industria 4.0.  Non a caso si dice che  i dati siano il nuovo petrolio.

Un esempio pratico molto interessante di questi sviluppi è quello dei recommendation system, ossia un insieme di algoritmi in grado di capire cosa ci può piacere. È il mezzo mediante il quale le campagne di marketing su larga scala riescono ad essere anche mirate e personalizzate, unendo i pregi del consiglio di un amico a quelli della pubblicità di massa. Un buon recommendation system, o sistema di raccomandazione/suggerimento, deve:

  • essere personalizzato, in modo da essere rilevante per l'utente;
  • essere diversificato, in modo da raggiungere tutti i possibili gusti dell'utente;
  • sorprendere l'utente, non presentando prodotti che l'utente conosce già o che avrebbe conosciuto da solo;
  • espandere i gusti dell'utente.

Daft_punk_racc

Il Netflix Prize

Nel 1997, il core business di Netflix consisteva nel noleggio di DVD e videogiochi prenotabili on-line e recapitati direttamente a casa. In quegli anni aveva già messo in piedi un sistema di algoritmi per inviare agli utenti consigli su nuovi titoli basati sullo storico delle loro preferenze. Ma fu con il lancio della piattaforma per la trasmissione di film in streaming che tali algoritmi divennero la chiave per le strategie aziendali. Infatti, mentre in precedenza gli unici dati a disposizione erano quelli relativi ai DVD noleggiati, adesso si ha accesso ad informazioni molto più dettagliate: i film visti, le serie TV iniziate, quelle iniziate e mai finite, quelle divorate, quelle riprese dopo tanto tempo...in pratica possiam arrivare a registrare ogni singolo click dell'utente!

Nel 2006 l'azienda statunitense indisse un concorso con un premio di un milione di dollari, regole complete qui, per chi fosse riuscito a migliorare l'accuratezza di Cinematch, il recommendation system utilizzato all'epoca. In dettaglio lo scopo era di abbattere del 10% il Root Mean Squared Error calcolato sui voti predetti. In due parole l'RMSE è una metrica spesso utilizzata per testare algoritmi predittivi e consiste nel calcolare la radice quadrata del rapporto tra la somma dei quadrati della differenza tra predizione e voto reale misurato e il numero di campioni considerati:

 \mbox{RMSE} =\sqrt{\sum\frac{(voto\ reale - voto\ predetto)^2} N}

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.

classifica_Netflix_Prize

Il problema da un punto di vista matematico.

Cominciamo a fare un po' di ordine. Il problema consiste nel predire il voto di un utente su un nuovo prodotto sulla base dello storico dei suoi acquisti o, più in generale, della sua attività on-line, al fine di determinare una lista di prodotti affini ai gusti dell'utente stesso. I dati chiave per questo tipo di problema sono:

  •  gli utenti o users;
  •  i prodotti o items;
  •  i voti o le preferenze, detti ratings.

Vale la pena spendere un commento sull'ultimo elemento poiché la modalità con cui viene espressa una preferenza può variare significativamente da sistema a sistema. Infatti possono essere dei like, voti da uno a cinque o su una qualsiasi altra scala, oppure addirittura una semplice interazione dell'utente con il prodotto.

Definiamo U l'insieme degli user e I l'insieme degli item. Fissato un utente u\in U, I_u è l'insieme dei prodotti che l'user ha acquistato, o meglio, per cui ha espresso una preferenza; viceversa, U_i è l'insieme degli utenti che hanno votato il prodotto i\in I. Introduciamo inoltre \textbf{R}, la matrice dei voti detta ratings matrix, in cui l'elemento r_{i,j} rappresenta il giudizio espresso dall'utente i in merito al prodotto j. Ovviamente questa matrice sarà piena di buchi e di punti interrogativi, pensiamo ai nostri voti sugli articoli in vendita su Amazon...il rapporto tra quelli votati e quelli non votati è praticamente zero. Lavorare con questo tipo di matrici e con molti coefficienti ignoti è un ostacolo enorme, che per il momento trascuriamo per non complicarci troppo la vita, accontentandoci di sapere che è qui che può entrare in gioco la decomposizione ai valori singolari. La situazione canonica, estremamente semplificata, utilizzando una scala di voti da 1 a 5 è come questa sotto

\begin{matrix}&Mr. Robot & Stranger\ Things & Friends & Westworld\\Alice & 5 & 4 & & 2 \\Bob & 1 & 2 & 5 & \\Carla & 4 & & 3 & 5\\Davide & & 5 & 1 & 1\end{matrix}

L'obiettivo è chiaro. Predire il voto che ogni utente (Alice, Bob, Carla e Davide) potrebbe dare sulla serie TV (Mr. Robot, Stranger Things, Friends, Westworld) che non ha ancora visto. Se guardiamo un secondo la tabella ci accorgiamo intuitivamente che basandoci sui voti passati Alice ha gusti più simili a Carla o a Davide piuttosto che a Bob, quindi ci aspettiamo che il suo voto su Friends (l'unica che non ha ancora votato) sarà intorno al 2-3. Quattro utenti per quattro prodotti si può fare anche a occhio, ma pensate al numero di film disponibili su Netflix o a tutti i prodotti venduti su Amazon e moltiplicateli per gli utenti iscritti: serve un algoritmo intelligente (e anche efficiente da un punto di vista computazionale) per predire i voti mancanti di ogni utente. Gli articoli con i voti stimati più alti saranno suggeriti all'utente. Tale procedimento prende il nome di User-User Collaborative Filtering.

L'idea è semplice e intuitiva, per nulla immediata da applicare quando entrano in gioco gli enormi dataset in un ambiente di produzione reale.

User-User Collaborative Filtering

Abbiamo bisogno di un indicatore che rappresenti la somiglianza tra due utenti. Cerchiamo dunque una funzione s:U\times U\to \mathbb{R} che prenda in input due utenti e restituisca un numero reale rappresentante la loro similarità. La definizione di questa funzione è un elemento fondamentale per la buona riuscita di un sistema di suggerimento, ne segue dunque, a seconda dei casi, una moltitudine di definizioni differenti, ognuna con i suoi vantaggi e svantaggi. Ne vediamo un paio molto semplici.

Il primo indicatore detto indice di correlazione di Pearson consiste nel rapporto tra la covarianza delle due variabili e il prodotto delle due varianze, cioè:
\begin{equation}
s(u,v)=\frac{\sum_{i\in I_u\cap I_v} (r_{u,i}-\bar r_u)(r_{v,i}-\bar r_v)}
{\sqrt{\sum_{i\in I_u\cap I_v} (r_{u,i}-\bar r_u)^2}\sqrt{\sum_{i\in I_u\cap I_v} (r_{v,i}-\bar r_v)^2}},
\end{equation}
dove con \bar r_u intendiamo la media sui voti totali espressi dall'utente u.
In pratica la correlazione è un indicatore statistico che misura come e quanto due variabili aleatorie varino insieme. Più il valore s(u,v) è vicino al valore massimo 1, più le due variabili sono correlate e quindi gli utenti u e v sono simili.

correlation

Un altro approccio consiste nel considerare gli utenti come vettori \textbf r_u \in \mathbb{R}^{|I|}, in cui la componente i-esima rappresenta il voto espresso dall'utente u in merito al prodotto i (r_{u,i}=0 se l'user u non ha votato l'item i).
Per calcolare la somiglianza tra due user possiamo considerare il coseno dell'angolo racchiuso tra i due vettori:
\begin{equation}
\label{coseno}
s(u,v)= \frac{\textbf{r}_u\cdot\textbf{r}_v}{\vert\vert \textbf r_u \vert\vert\ \vert \vert\textbf r_v \vert\vert },
\end{equation}
dove \textbf{r}_u\cdot\textbf{r}_v=\sum_{i=1}^{\vert I\vert}r_{u,i}r_{v,i} e \vert\vert\textbf r_v \vert\vert = \sqrt{\textbf{r}_u\cdot \textbf{r}_u} è la norma euclidea. Come prima, più il valore s(u,v) si avvicina ad 1 più i due utenti possono essere considerati simili.

Come calcoliamo le previsioni sui nuovi prodotti?

Per ora abbiamo tra le mani un solo strumento: una funzione che per qualche motivo, più o meno chiaro, esprime il grado di similarità tra due utenti. Vediamo come utilizzarla per predire p_{u,i}, ossia il voto che l'utente u tenderebbe a dare sul prodotto i. Introducendo l'insieme N=U-\left\{u\right\}, possiamo definire

\begin{equation}\label{previsioni}
p_{u,i}=\bar r_u+ \frac{\sum_{v\in N}s(u,v)(r_{v,i}-\bar r_v)}{\sum_{v\in N}\left| s(u,v) \right|},
\end{equation}
dove come sopra \bar r_v, rispettivamente \bar r_u, rappresenta la media dei voti espressi dall'utente v, rispettivamente r_v:
\begin{equation*}
\bar r_v:=\frac{\sum_{j\in I_v} r_{v,j}}{\left| I_v\right|}.
\end{equation*}

Con quanti degli 86 milioni di utenti su Netflix ci aspettiamo un elevato grado di similarità? Pochissimi. Per questo motivo non è conveniente estendere la sommatoria \eqref{previsioni} a tutto l'universo degli utenti come appena fatto. È più sensato e meno dispendioso ridurla ad un sottoinsieme di utenti N che superino una certa soglia di similarità fissata a priori:

\begin{equation*}
N:=\left\{v\in U \mbox{ tali che } s(u,v)> costante \right\}.
\end{equation*}

L'Equazione \eqref{previsioni} può essere raffinata facendo entrare in gioco la deviazione standard \sigma_u di ogni utente u per compensare le differenze di voto e la distanza dalla media.

Una media pesata come quella appena introdotta non è l'unico meccanismo presente in letteratura per questo tipo di previsioni, ma è senza dubbio la più semplice e comune.

Un esempio

Facciamo un esempio supponendo di avere i dati degli utenti Alice, Bob, Carla, Davide (A, B, C, D) come nella tabella predente e di voler predire il voto di Alice sulla serie TV Friends sfruttando la definizione introdotta nell'Equazione \eqref{coseno}.

Cominciamo con il calcolare la similarità tra A e gli altri utenti sfruttando la definizione di correlazione di Pearson:
\begin{equation*}
s(A,B)=0,35\ \ s(A,C)=0,63 \ \ s(A,D)=0,63.
\end{equation*}

Inciso: vorrei far notare che se avessimo cercato un modo di riempire la matrice sopra con voti a caso ed ottenere una similarità tra due utenti uguale fino alla seconda cifra decimale non ci saremmo mai riusciti...è stato solo un caso!

A questo punto possiamo calcolare

\begin{equation*}
p_{A,F}=\bar r_A+\frac{s(A,B)(r_{B,F}-\bar r_B)+s(A,C)(r_{C,F}-\bar r_C)+s(A,D)(r_{D,F}-\bar r_D)}{\vert s(A,B)+s(A,C)+s(A,D)\vert}
\end{equation*}
ossia
\begin{equation*}
p_{A,F}=3,67+\frac{0,35*2,33+0,63*(-1)+0,63*(-1,34)}{\vert 0,35+0,63+0,63\vert}=3,26.
\end{equation*}
Ne deduciamo che Alice tenderà ad esprimere un voto intorno al 3 per la serie TV Friends. In questo piccolo esempio abbiamo scelto di considerare tutti gli utenti presenti, tuttavia per rendere l'algoritmo più leggero e veloce avremmo potuto tralasciare il contributo di Bob, tenendo soltanto quello dei due più simili ad Alice.

Item-Item Collaborative Filtering

Il Collaborative Filtering appena descritto soffre di un grande problema: la scalabilità. In informatica, con scalabilità si intende la capacità di un sistema (software e/o hardware) di adattarsi (crescendo o decrescendo) in base alle richieste e alla disponibilità. L'algoritmo user-user C.F. non è scalabile nel senso che impiega troppo tempo, nella scala dei tempi dei servizi on-line, per elaborare i dati con il crescere degli utenti. Per aggirare questa difficoltà una idea può essere quella di adottare un algoritmo item-based Collaborative filtering. Non ci dilungheremo nei dettagli in quanto, per certi versi, è molto simile al precedente. L'idea di base è che se due prodotti tendono a piacere agli stessi utenti allora sono simili. La peculiarità che lo rende più versatile rispetto all'approccio precedente non è tanto quella di aver spostato il focus dall'utente al prodotto, ma la possibilità di calcolare la ratings matrix in batch offline. Infatti, in un sistema con molti più utenti che prodotti (situazione verosimile nella maggioranza dei casi), i voti degli utenti non influenzano nel breve periodo la similarità tra due item fissati. In questo modo non siamo costretti a lanciare l'algoritmo in real time dopo ogni attività fatta dall'utente, ma possiamo accontentarci del risultato calcolato poco tempo prima.

Netflix: ne è valsa la pena?

Una volta firmato l'assegno da 1 milione di dollari non rimane che mettere in produzione l'algoritmo vincente: nulla di più complicato. Infatti la soluzione proposta era basata su un insieme statico di soli 100 milioni di voti, mentre all'epoca il dataset reale ne aveva oltre 5 miliardi e cresceva di 4 milioni su scala giornaliera.

nflixwinners-520x341

Non è chiaro se questo investimento abbia effettivamente portato dei vantaggi all'azienda, tuttavia le lezioni tratte da questa esperienza sono state fondamentali per gli sviluppi futuri (oggi sembreranno idee scontate, ma hanno permesso a Netflix di diventare quello che è adesso). Tra le più importanti troviamo:

  • Flessibilità su dove e quando vengono svolte le elaborazioni. Vengono introdotte tre tipologie di elaborazione - online per processare le richieste, nearline per gli eventi, offline per i dati -  sviluppate  su diversi punti dell'architettura del sistema.
  • Algoritmi modulari in grado di adattarsi alle diverse esigenze.
  • Non fare affidamento soltanto sulle metriche durante i test.

nflx_consideration

Conclusioni

Con questo post non voglio lasciar pensare che Netflix, o comunque gli altri giganti nel  campo dell'intelligenza artificiale e machine learning come Google, Facebook, Youtube, Amazon, ecc. sfruttino effettivamente algoritmi e idee così semplici. Non ci andrebbero molto lontani e Jeffrey Dean inorridirebbe alla sola idea. Come potete vedere negli articoli segnalati in fondo, la soluzione vincente di 8 anni  fa consisteva di un sottile equilibrio di algoritmi ben più sofisticati. Giusto per citarne alcuni: k-nearest neighbor clustering, SVD, RBM, decision trees, il Maximum Margin Matrix Factorization, lo SBRAMF, ...

Queste righe vogliono essere soltanto un esempio di come la matematica risulti centrale in contesti apparentemente assai lontani. Ancora una volta, come negli altri miei post, ho scelto di non scendere estremamente nei dettagli degli argomenti trattati, un po' per lasciare fruibile la lettura, un po' perché sinceramente non sono un esperto. Mi scuso in anticipo per la superficialità nella trattazione, inoltre potrei aver commesso degli errori e vi prego di farmeli notare. Commenti e critiche sono sempre bene accetti per migliorare e, perché no, intavolare una discussione costruttiva.

Per i più curiosi...

  1. Una panoramica sull'architettura che rende possibile la Personalization e la Recommendation direttamente dal techblog di Netflix.
  2. Netflix Recommendations spiegata: part 1 & part 2.
  3. Un articolo introduttivo di Grouplens sul recommendation system.
  4. Y. Koren, The BellKor Solution to the Netflix Grand Prize, (2009).
  5. A. Tascher, M. Jahrer, R. Bell, The BigChaos Solution to the Netflix Grand Prize, (2009).
  6. M. Piotte, M. Chabbert, The Pragmatic Theory solution to the Netflix Grand Prize, (2009).
  7. Le slide di J. Basilico sugli ultimi punti di questo post.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination