Films e motori (di raccomandazione)

Come fanno aziende come Netflix a scoprire cosa ci può piacere?

Image for post
Image for post

Introduzione.

Un elemento fondamentale di un moderno sito di commercio elettronico è il motore di raccomandazione, la componente del sistema che suggerisce ai clienti quali possono essere i prodotti o gli oggetti di maggiore interesse.

Ma come funziona e come può essere realizzato un motore di raccomandazione? Ed esiste una sola tecnica per realizzarlo, oppure, come possiamo immaginare, è possibile scegliere quale “anima” dare al nostro sito scegliendo su quale tecnica basare il suo motore di raccomandazione?

E, le aziende più famose, ad esempio Netflix, come hanno realizzato il loro motore di raccomandazione?

In questo articolo voglio esaminare alcune delle tecniche utilizzate ed arrivare ad indicare come, avendo i dati giusti a disposizione, oggi è possibile realizzare un tale motore con poche righe di codice Python.

Se, poi, vi interessa il cinema, spero vi troverete ulteriori spunti di interesse. Ho utilizzato per i miei esperimenti i dati di MovieLens.

Una formalizzazione del problema.

Da sempre, la matematica è il linguaggio che più mi riesce semplice da utilizzare. Per tale ragione, consentitemi di dedicare alcune righe per dare una formulazione matematica al problema.

Immaginiamo di avere un insieme C di clienti c ed un insieme I di oggetti o “item” di interesse. Per cominciare a fissare le idee supponiamo di non prevedere ingresso di nuovi clienti od item nel sistema.

I nostri clienti valutano le varie item (i film, nell’esempio di MovieLens) ed esprimono la loro valutazione attribuendo ad un sottoinsieme di item un rating. Il rating per definizione è un numero reale che, tanto per semplicità, possiamo immaginare compreso tra [0,5] (I nostri clienti attribuiscono da un minimo di 0 stelle ad un massimo di 5 stelle ed è possibile assegnare mezze stelle).

Nelle ipotesi fatte i ratings dei clienti sono rappresentabili da una matrice

R(c,i)

ove c è il cliente che ha espresso un rating per l’item i. Le righe corrispondono ai clienti e le colonne alle item da valutare.

Ovviamente, non tutti gli elementi di questa matrice sono valorizzati.

Il nostro obiettivo è di fornire una previsione affidabile per i rating per i quali la matrice R(c, i) non è valorizzata, ovvero di trovare la migliore approssimazione possibile per la funzione di utilità:

u = u(c, i), CxI -> R

che fornisce un rating per qualsiasi valore di c ed i.

Un altro concetto che ci risulterà utile nel seguito è il concetto di funzione di similitudine.

Dati due clienti c1 e c2 una funzione di similitudine è una funzione che ad ogni coppia di clienti (c1, c2) associa un numero reale positivo, che misura quanto i due clienti sono simili.

sim(c1, c2), CxC -> R

La matrice R(c, i) la possiamo leggere da un file di dati. Ci è sufficiente avere un Id per l’utente, un Id per l’item ed il rating. Ad esempio, nel caso di films, un file in cui ogni riga contiene:

userId, MovieId, Rating

Possibili approcci alla soluzione del problema.

Esistono differenti possibili approcci per affrontare questo problema. Per il seguito della nostra trattazione noi assumiamo, come punto di partenza, che un insieme di clienti abbia espresso un rating per un insieme di item.

Alcuni autori hanno proposto anche una tassonomia delle possibili soluzioni.

Le tecniche si classificano in (si veda [1]):

  • Content-based: in questo caso si utilizzano una serie di attributi noti degli utenti e delle “item”
  • Collaborative-flltering: in questo caso per prevedere il rating che un cliente attribuirebbe ad un item (laddove l’elemento R(c,i) non è presente nella matrice) si identifica un sottoinsieme di clienti “simili” che hanno espresso rating per l’item di interesse.
  • Ibride, ottenute mediante una combinazione di tecniche appartenenti alle prime due classi
Classificazione delle tecniche per sviluppare sistemi di raccomandazione.

(la figura è tratta dal rif. [1])

Collaborative filtering.

Il termine Collaborative Filtering non indica un unico algoritmo, ma piuttosto un concetto abbastanza generale.

L’idea alla base del Collaborative Filtering si può intuire considerando il seguente esempio: supponiamo di avere l’insieme C dei clienti e di poter definire un criterio per stabilire che due clienti c1 e cj sono abbastanza simili (una funzione di similitudine). Vogliamo prevedere il rating che il cliente c1 attribuirebbe all’item X

R = R(c1, X)

consideriamo allora un insieme N di clienti cj “simili a c1”, che hanno espresso un rating per X, e valutiamo R(c1, X) facendo la media dei rating espressi dai vari clienti cj

R(cj, X)

dove attribuiamo ad ogni rating un peso tanto maggiore quanto più cj è simile a c1.

L’idea, in estrema sintesi, è che se c1 e cj hanno espresso rating vicini per altre item allora è molto più probabile che il rating di c1 per X sia vicino al rating espresso da cj, piuttosto che al rating espresso da un cliente c preso a caso.

Nelle tecniche dette “Memory based” le previsioni fornite dal motore sono basate sulla memoria passata, ovvero sulla storia delle preferenze espresse in passato dai clienti del sistema. In sintesi, si fa un’assunzione importante: se gli utenti in passato si sono comportati in un certo modo anche nel futuro si comporteranno in modo simile. E’ l’idea che esistano delle regolarità che si conservano nel tempo. E’ un assunzione forte, che definisce anche i limiti di tali tecniche (ad esempio, non si hanno elementi per calcolare i rating per nuovi clienti, che non hanno ancora espresso rating, oppure per nuove item, non ancora valutate).

Come vediamo dalla figura di sopra possiamo identificare nell’ambito delle tecniche “memory based” due approcci di Collaborative Filtering: User-based ed Item-based.

Collaborative Filtering User-based.

Per essere precisi quello descritto sopra, che secondo me è anche il più intuitivo (per noi che ovviamente prendiamo il punto di vista degli esseri umani) , è l’approccio User-based.

Nell’approccio user-based per prevedere il rating che il cliente cx esprimerà per l’item iy individuiamo un insieme (N) di clienti “simili a cx” che hanno espresso rating per l’item y.

La stima per il rating sarà:

R(cx, iy) = ∑ sim(cx, cj) * R(cj, iy)/∑ sim(cx, cj)

ove la somma è estesa a tutti i clienti simili a cx, appartenenti all’insieme N.

Rimane da precisare:

  • come è definita la funzione di similitudine sim(cx, cj)
  • come è definito l’insieme N

Per la funzione di similitudine, una delle scelte più usate utilizza la correlazione (il coefficiente di correlazione di Pearson) tra i ratings. Quanto più i ratings di cx e cj sono correlati, tanto maggiore è la similitudine. Intuitivo.

Per la definizione dell’insieme N, si può procedere o definendo una soglia per la similitudine (prendiamo solo gli altri clienti per cui sim(cx, cj) > soglia), oppure definiamo un numero N di “clienti vicini o simili”. In entrambi i casi abbiamo un iper-parametro del modello, da sottoporre a tuning.

Collaborative filtering Item-based

Nell’approccio item-base consideriamo le item simili a quella per cui dobbiamo stimare il rating.

In questo caso come funzione di similitudine

sim(ix, ij)

si preferisce prendere la “cosine similarity” (https://en.wikipedia.org/wiki/Cosine_similarity).

Anche in questo caso il rating è calcolato, questa volta facendo una media su un insieme di item simili ed utilizzando come sempre come peso la similarità.

Impiego delle reti neurali.

Ero un po’ indeciso sullo scrivere questa sezione. Non perchè la ritenga di poco interesse, anzi. Ma perchè piuttosto penso che richiederebbe uno spazio assai ampio.

Come scelta, quindi provo a spiegare ad alto livello l’approccio. Magari dedicherò un altro articolo all’approfondimento.

L’approccio tradizionale (non basato su reti neurali) parte da algoritmi predefiniti, di cui si calcolano i parametri in base ai dati disponibili (è, in fondo, questo l’addestramento). Con le reti neurali l’algoritmo è più generale. Definiamo l’architettura della rete e quindi lo “spazio delle ipotesi”, ma in questo spazio l’insieme delle funzioni rappresentabili è assai ampio. La singola funzione è “decisa” dalla rete durante l’apprendimento.

Un approccio possibile, semplice ma che da ottimi risultati, è il seguente: immaginiamo di codificare un cliente ed un film utilizzando due dizionari. Noi vogliamo “combinare” cliente e film per calcolare il rating R(c, i).

Dopo la codifica, trasformiamo ciascuno dei due “id” in un vettore di embedding, usando una tecnica che è molto usata nel campo del NLP. Con gli embedding noi proiettiamo il cliente (ed il film) in uno spazio vettoriale denso, che assumiamo della stessa dimensionalità. La “matrice di embedding” sia per i clienti che per i film è appresa dalla rete a partire dai milioni di esempi che abbiamo a disposizione. Vogliamo che clienti simili abbiano vettori di embedding simili (Eux) e film simili vettori simili (Emx).

Poi, combiniamo “in qualche modo” i vettori Eux ed Emx per ottenere il rating previsto. Con il solito approccio, addestriamo la rete in modo che i rating previsti siano il più possibile vicini ai rating espressi dai clienti. Possiamo usare il MSE come loss function.

Image for post
Image for post

Un esempio è disponibile qui: https://keras.io/examples/structured_data/collaborative_filtering_movielens/

E’ possibile trovare una spiegazione su come estrarre gli embeddings al link: https://developers.google.com/machine-learning/crash-course/embeddings/obtaining-embeddings

Un dataset molto interessante: MovieLens.

Se si vogliono compiere esperimenti interessanti un dataset ricco ed utile è MovieLens.

MovieLens contiene i rating espressi per migliaia di films da alcune decine di migliaia di utenti. MovieLens è gestito da GroupLens, un gruppo di ricerca dell’Università del Minnesota.

E’ possibile scaricare da Internet diferenti versioni di questo dataset. le versioni differiscono, oltre che per l’anno di raccolta dei dati, per il numero di recensioni che contengono.

Esiste una versione ridotta, che contiene soltanto circa 100000 recensioni (https://grouplens.org/datasets/movielens/100k/).

E’ possibile scaricare una versione che contiene circa 10 milioni di recensioni (https://grouplens.org/datasets/movielens/10m/)

Per i miei test ho utilizzato una versione più completa (https://grouplens.org/datasets/movielens/25m/) che contiene circa 25 milioni di recensioni espresse da 162000 utenti per circa 62000 film. Esplorare questo dataset per chi ama il cinema è veramente molto interessante.

Oltre ad utilizzare questo dataset per il mio studio sullo sviluppo di un motore di raccomandazione, ho anche effettuato un insieme di analisi, utilizzando PySpark e SparkSQL.

Vi interessa sapere quali sono i venti film che hanno ricevuto più recensioni ed i migliori rating? Ecco il risultato:

Image for post
Image for post

Infine, riallacciandoci ai ragionamenti fatti in precedenza, il file

ratings.csv

del dataset contiene, appunto, i seguenti dati

userId, movieId, rating

e quindi consente di ottenere, rapidamente, la matrice R(c, i) di cui abbiamo parlato in precedenza.

Netflix?

Parlando di films, ritorna in mente la domanda posta nell’introduzione dell’articolo: come ha fatto Netflix?

In realtà, non conosco la risposta con precisione. Probabilmente vi sono elementi dei suoi algoritmi che sono tenuti segreti. Ma Netflix sicuramente ha fatto ricorso a tecniche sofisticate di Machine Learning. In passato, per migliorare il suo motore ha anche lanciato una competizione su Kaggle, con un premio di ben un milione di dollari (wow!!). Alcune informazioni, anche se un po’ datate, si possono trovare nel rif. [3].

Il dataset utilizzato per quella competizione può essere consultato e scaricato al link: https://www.kaggle.com/netflix-inc/netflix-prize-data. In quel caso Netflix aveva fornito 100 milioni di ratings, espressi da 500000 utenti. Un insieme impressionante di dati.

Una nota interessante a riguardo parla dell’algoritmo SVD. (Singular Value Decomposition): https://sifter.org/~simon/journal/20061211.html

Surprise: una libreria Python.

Veniamo a come implementare concretamente un motore di raccomandazione, basato sulle tecniche descritte. Per il linguaggio Python il primo approccio da seguire è verificare se vi sono disponibili librerie che implementano gli algoritmi descritti.

Una libreria che ho testato, il cui nome è appunto Surprise, è veramente una bella sorpresa.

Contiene l’implementazione di numerosi algoritmi ed è ben documentata. Contiene anche alcune versioni limitate di alcuni dei dataset più usati in tale campo, tra cui ovviamente MovieLens, e nella documentazione sono riportati alcuni benchmark.

Con Surprise è abbastanza semplice addestrare un motore di raccomandazione, se abbiamo a disposizione i rating espliciti (la matrice R(c, i)).

Il codice seguente, estratto dalla documentazione di Surprise, mostra come implementare SVD sul dataset MovieLens (100K).

from surprise import SVD
from surprise import Dataset
from surprise.model_selection import cross_validate

# Load the movielens-100k dataset (download it if needed),
data = Dataset.load_builtin('ml-100k')

# We'll use the famous SVD algorithm.
algo = SVD()

# Run 5-fold cross-validation and print results
cross_validate(algo, data, measures=['RMSE', 'MAE'], cv=5, verbose=True)

Il risultato che si ottiene è un MAE di circa 0.73, che va confrontato con i ratings che appartengono al range [0.5,5]. Un risultato buono se si considera la dimensione limitata del dataset, che consente un tempo di addestramento di pochi minuti.

Un risultato migliore si può ottenere utilizzando il dataset MovieLens20m, ma l’addestramento richiede più tempo e capacità computazionale.

Per una sintetica descrizione dell’algoritmo SVD: https://surprise.readthedocs.io/en/stable/matrix_factorization.html#surprise.prediction_algorithms.matrix_factorization.SVD

MovieLens 20M.

Ovviamente, non ho resistito alla curiosità di provare con il dataset più grande e completo: quello che contiene circa 25 milioni di recensioni.

In questo caso ci vuole più tempo ed una capacità computazionale che il mio MacBook non può dare. Per questa ragione, ho utilizzato in Oracle Data Science una Notebook Session con 8 OCPU.

L’addestramento ha richiesto circa due ore (con CV=5). Il risultato è ottenuto è il seguente:

Image for post
Image for post

Il MAE è sceso a 0.599. Vuol dire che, per esempio, un rating previsto è 2.5 +/- 0.6.

Più dati si hanno e più si riescono a fare previsioni accurate, come molto spesso accade nel Machine Learning.

Scintilla, o meglio Spark.

Un approccio alternativo all’utilizzo delle GPU, quando si devono elaborare dataset di grandi dimensioni, è usare un ambiente cluster, con Apache Spark e la libreria Spark ML (o MLlib).

Spark ML contiene anche algoritmi per lo sviluppo di modelli di “recommendation”. In particolare mette a disposizione l’algortimo ALS.

Ho fatto alcuni test, sempre utilizzando il dataset MovieLens, per verificare le prestazioni sia i termini di velocità, sia in termini di accuratezza (misurata tramite il MSE) ed in un tempo relativamente breve si riescono ad ottenere buone prestazioni, anche se l’accuratezza è inferiore a quella che ho ottenuto con Tensorflow e le reti neurali.

Il tempo per lo sviluppo ed il test è stato abbastanza breve, alcune ore, ed utilizzando l’ambiente serverless DataFlow, disponibile su Oracle OCI, riesco ad effettuare il training (sempre dataset di 27 milioni di rating) in circa 4 min (utilizzando 5 OCPU).

Il RMSE migliore che ho ottenuto è 0.81, quindi un risultato del tutto comparabile con quello ottenuto (vedi sopra) con l’algoritmo SVD.

Anche per questa parte, prevedo di scrivere un articolo di approfondimento.

Approcci ibridi.

Mi piace pensare che oltre alle Reti Neurali gli approcci ibridi o di insieme (ensamble) siano una delle frontiere del Machine Learning.

Nel concreto, una domanda importante è: ma si possono sempre usare le tecniche Memory Based?

Ovvio, la risposta è no. Queste tecniche si basano sulle scelte effettuate dagli utenti nel passato. Quindi, non possono essere applicate “as-is” a films nuovi o utenti nuovi.

Per poter gestire l’ingresso di nuove “entry” (films, clienti) nel sistema, si ricorre ad approcci basati sulle caratteriche registrate di queste entry, quindi di tipo content-based. Unendo le tecniche l’approccio è sostanzialmente ibrido.

Conclusioni?

L’implementazione di un motore di raccomandazione è una delle applicazioni classiche dell’approccio della Data Science e del Machine (e Deep) Learning. E può sfruttare il fatto che per le aziende è relativamente semplice accedere a grandi dataset per l’addestramento. Inoltre, le nuove preferenze espresse dai clienti possono essere usate, in un processo continuo,per adeguare il motore. Potenza di Internet e dell’interazione online.

E’ ovvio che con l’enorme mole di dati a disposizione (pensiamo ai 100 milioni di rating di Netflix) si pensi di utlizzare reti neurali. Il problema qui è, come spesso, che servono implementazioni efficienti e tanta potenza per il training.

Spero di aver dato un insieme di informazioni utili, sopratutto per avviare bene gli approfondimenti successivi. Ho limitato la trattazione per non rendere l’articolo troppo lungo, ma penso di dedicare qualche altro articolo ai necessari approfondimenti, sopratutto per quanto riguarda l’uso delle reti neurali.

E, per chi ama i film ed il cinema, oltre alla Data Science, MovieLens è una fonte interessante.

Riferimenti

[1] Isinkaye et al, 2016, Recommendation Systems: Principles, methods and evaluation, https://www.researchgate.net/publication/283180981_Recommendation_systems_Principles_methods_and_evaluation

[2] Movielens, https://movielens.org/

[3] https://netflixtechblog.com/netflix-recommendations-beyond-the-5-stars-part-1-55838468f429

Written by

Born in the wonderful city of Naples, but living in Rome. Always curious about new technologies and new things. I work in a big Cloud Company.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store