I sistemi di raccomandazione sono una classe di sistemi che implicano la predizione delle risposte dell'utente a delle opzioni, o in generale, le preferenze di un utente rispetto a specifici oggetti (items) sulla base delle preferenze espresse in passato. L'idea principale dietro i sistemi di raccomandazione è la seguente:
- L'utente interagisce con gli oggetti;
- In base a tali oggetti, il sistema crea un modello di preferenze per l'utente;
- Il modello permette di predire la reazione dell'utente a nuovi oggetti;
- Il sistema cerca quali oggetti sono potenzialmente interessanti per l'utente;
- Il sistema raccomanda oggetti interessanti all'utente;
Esistono due principali gruppi di sistemi di raccomandazione:
- Sistemi content-based, che effettuano suggerimenti ad un utente sulla base delle proprietà di altri item con cui l'utente ha interagito.
- Sistemi collaborative filtering, che effettuano suggerimenti ad un utente sulla base degli item piaciuti ad utenti ad esso simili.
Lo spazio limitato dei negozi fisici spinge i negozianti all'esposizione della merce più popolare, che risulta vendibile con maggiore frequenza. Tale scelta emargina prodotti di nicchia, come film di autori novelli o dischi di band underground. Un sistema di raccomandazione prende in considerazione un numero di prodotti maggiore di almeno 2 o 3 ordini di grandezza rispetto a quelli esposti in un negozio fisico.
Gli articoli sono generalmente caratterizzati da una distribuzione a coda lunga per la quale solo un piccolo insieme di articoli ha maggiore popolarità, mentre un ampio insieme di articoli costituisce una nicchia, che spesso non è nemmeno conosciuta dai clienti. Mentre i negozi fisici tendono a utilizzare tutto lo spazio sugli scaffali per posizionare gli articoli più popolari, i negozi digitali non soffrono di tale problema e possono spingere verso una maggiore variabilità dei contenuti. Di conseguenza, c'è un insieme di prodotti poco popolari che si possono trovare solo online, non convenienti da vendere in un negozio fisico.
I rivenditori digitali possono facilmente esplorare la distribuzione a coda lunga perché non hanno alcun vincolo fisico (spazio sugli scaffali), ma come fanno a far conoscere agli utenti i prodotti di cui non sono a conoscenza perché non sono abbastanza popolari? Lo strumento più ambito a questo scopo è il sistema di raccomandazione, che può guidare gli utenti da un item popolare ad uno meno popolare con caratteristiche simili.
Un sistema di raccomandazione necessita di molti dati per funzionare correttamente. Più informazioni si conoscono sulle preferenze degli utenti, più è accurata la predizione. In alcuni contesti, ad esempio nell'informazione e nei social media, un sistema di raccomandazione può essere utilizzato ai fini di consenso e propaganda per orientare gli utenti verso un'opinione: può scaturire una mancanza di opinione critica sui fatti.
Sia
- rating compreso tra
$0-5$ stelle - rating normalizzato compreso in
$[0,1 ]$ - rating binario
${0, 1}$ (mi piace, non mi piace)
Un sistema di raccomandazione si basa su un insieme di preferenze conosciute espresse da utenti per oggetti o item, che può essere rappresentato da una matrice di utilità
Essa rappresenta la conoscenza esistente del sistema sulla relazione tra utenti ed articoli ed è perlopiù sparsa poiché un generico utente recensisce / interagisce con pochi item. Un sistema di raccomandazione vuole predire i valori di rating inesistenti della matrice.
Quando progettiamo un sistema di raccomandazione, incontreremo due problemi principali: la popolazione della matrice di utilità e la predizione di rating non ancora conosciuti.
Se la matrice di utilità è vuota, è impossibile effettuare delle raccomandazioni. Ci sono due metodi pincipali per popolare la matrice di utilità: metodo esplicito e metodo implicito. I due approcci possono essere utilizzati in contemporanea.
L'approccio esplicito consiste nel chiedere all'utente di recensire gli item (i.e. Netflix ai nuovi utenti). Tuttavia, questo approccio stanca ed infastidisce facilmente gli utenti, che potrebbero cambiare piattaforma o inserire suggerimenti casuali. Inoltre, le valutazioni sono generalmente influenzate dal fatto che sono fornite da persone disposte a fornirle (che di solito è una piccola parte dell'intero gruppo di utenti).
L'approccio implicito fa inferenza dal comportamento dell'utente. Ad esempio lo storico delle visite a certi item, lo storico degli acquisti, le interazioni con l'oggetto etc. In generale, lo storico di ricerca è utilizzato per fare inferenza sulle categorie di item di interesse.
L'idea principale dietro i sistemi Content-Based è quella di raccomandare all'utente
- Raccomandare film con gli stessi attori, dello stesso regista o dello stesso genere.
- Raccomandare news con contenuto simile (i.e. politica, cucina, sport)
Step 1. Dato un utente, il punto di partenza è costituito dagli item da esso recensiti. Ogni item è descritto da vari attributi. Per ogni item recensito viene costruito un profilo, ovvero un vettore di valori dove ogni valore è riferito ad un attributo. Ipotizziamo che gli item siano film, allora gli attributi possono essere i vari generi (thriller, romantico, horror, azione, etc).
Step 2. Viene costruito uno user profile (profilo dell'utente) a partire dai profili degli item recensiti, che rappresenti il grado medio di preferenza dell'utente rispetto ai vari attributi. Ad esempio, l'utente potrebbe preferire film di azione e romantici e valutare negativamente gli horror.
Step 3. Dato un item non ancora recensito dall'utente, viene generato il profilo dell'item e confrontato con lo user profile. Da una certa nozione di similarità tra profili si inferisce se all'utente possa piacere o meno l'item.
I problemi più rilevanti sono: la scelta delle proprietà principali, la costruzione del profilo utente, il calcolo della similarità tra due profili.
Si supponga che tra le
Per ogni item
Il profilo di un item descrive quali proprietà contiene un item. Le proprietà rappresentano categorie, tag o parole chiave che è possibile associare ad un item. Se gli item fossero dei film, gli attributi potrebbero essere i generi, il regista, l'anno di uscita e/o gli attori. Nel caso dei testi è possibile calcolare lo score TF-IDF delle parole e utilizzare le
Come descritto precedentemente, se la feature è presente nell'item, allora viene contrassegnata con
Partendo dalle valutazioni già effettuate dall'utente su altri item, occorre aggregare in qualche modo le valutazioni che riguardano item che condividono la stessa proprietà. La funzione di aggregazione più semplice è la media delle valutazioni.
Poniamoci nel caso binario in cui l'elemento della matrice è asserito con 1 se è stato valutato positivamente. Supponiamo che vi siano
Il profilo dell'utente
Quando la matrice di utilità non è binaria, ha senso normalizzare gli elementi della matrice di utilità per il loro valore medio. In questo modo, le valutazioni al di sotto della media avranno un punteggio negativo, mentre valutazioni sopra la media avranno un punteggio positivo. Questo metodo si adatta inoltre in base agli utenti: utenti più critici avranno medie più basse e rating bassi ma sopra la media avranno comunque un punteggio positivo (simmetricamente per utenti più gentili).
Definiamo preventivamente la media delle valutazioni dell'utente
Dopodiché possiamo costruire il profilo dell'utente
Per calcolare la similarità tra profili è possibile utilizzare qualsiasi misura di similarità tra vettori. La misura più utilizzata è la similarità del coseno, che equivale al coseno dell'angolo formato dai due vettori. Dati due vettori di
I sistemi Content-Based non richiedono confronti con altri utenti, sono facili da interpretare e promuovono gli item non popolari. Tuttavia, individuare le proprietà adatte per costruire i profili degli item può essere difficile e risulta impossibile eseguire delle previsioni su nuovi utenti che non hanno ancora valutato alcun item. Allo stesso modo, risulta impossibile eseguire predizioni su item che contengono proprietà non valutate dall'utente. Un altro difetto marcato è la overspecialization: si tende a consigliare solo oggetti simili tra loro, senza proporre all'utente nuove scelte.
Un famoso approccio al problema della raccomandazione di item per un nuovo utente che non ha effettuato nessuna valutazione, consiste nel calcolare la baseline
L'idea principale dietro ai Collaborative Filters è la seguente: gli item da suggerire all'utente
Ipotizziamo di voler predire la valutazione dell'utente
Il profilo dell'utente in questo caso è rappresentato dalla corrispondente riga nella matrice
Siano
$v$ e$u$ due vettori, il coefficiente di Pearson$\rho(v,u)$ corrisponde esattamente alla similarità del coseno calcolata sui vettori ridotti del loro valore medio$\cos(v-\bar{v}, u-\bar{u})$ .
Applicare la similarità del coseno direttamente sulle righe della matrice introdurrebbe un bias, dal momento in cui il valore 0 non corrisponde ad una valutazione negativa, bensì neutra. Occorre quindi normalizzare, ovvero centrare i valori di rating rispetto al valore 0, in modo che rating bassi risultino negativi e rating alti positivi. Ciò può essere ottenuto sottraendo il rating medio dell'utente a tutte le valutazioni che ha effettuato.
Esempio: ipotizziamo di avere la seguente matrice sparsa di utilità. Ipotizziamo di voler stimare la valutazione dell'utente 4 rispetto all'item 4. Consideriamo gli utenti che hanno già valutato l'item 4, che risultano essere gli utenti 2,3 e 5.
Normalizziamo i profili degli utenti 2, 3, 4 e 5 sottraendo la media degli item valutati a tutte le valutazioni e poniamo a 0 (valutazione neutra) tutti gli item non valutati.
Calcoliamo la similarità del coseno tra l'utente 4 e gli utenti 2,3 e 5 e, supponendo che
Supponiamo che la matrice
Si consideri l'utente
Tale schema differisce dai sistemi content-based in quanto il profilo dell'item non è costruito attraverso gli attributi dell'item stesso, bensì attraverso le valutazioni degli utenti nella matrice di utilità. Nella pratica, i sistemi Item-Item funzionano meglio poiché gli utenti tendono ad avere preferenze diverse.
Supponiamo di voler predire la valutazione
Le due strategie comportano un trade-off tra efficienza ed accuratezza. Lo schema basato sulla similarità degli item è più informativo e permette di ottenere predizioni più affidabili. Questo poiché vi sono generalmente più item che utenti nella matrice di utilità ed è più facile trovare item dello stesso genere che utenti a cui piacciono solo item di un certo genere (il profilo di un utente è quasi univoco).
Lo schema basato sulla similarità tra utenti è tuttavia più efficiente se vogliamo predire tutti i rating dell'utente
I sistemi Collaborative Filtering lavorano con tutti gli utenti, anche aventi proprietà diverse. Non è necessaria una selezione di proprietà o feature sugli item. Tuttavia, non è possibile eseguire predizioni su nuovi utenti o riguardanti nuovi item. Nella pratica, i sistemi di raccomandazione sono ibridi, ovvero una combinazione tra le due tecniche.
I sistemi di raccomandazione lavorano solitamente su una matrice di utilità di grandi dimensioni, con un elevato numero di utenti ed item. In un contesto in cui subentrano i Big Data, i problemi principali sono:
- L'efficienza: operazioni svolte su matrici e vettori di grandi dimensioni.
- Problema della dimensionalità: in uno spazio ad elevate dimensioni, i punti tendono ad essere tutti equidistanti gli uni dagli altri, rendendo complesso il calcolo della similarità.
Occorre quindi adottare delle tecniche di dimensionality reduction (riduzione della dimensionalità), che permettono ai sistemi di raccomandazione di operare con matrici e vettori più piccoli.
Una tecnica naive per provare a ridurre la dimensionalità è il clustering. Se due o più item hanno caratteristiche simili, allora potrebbero far parte di uno stesso cluster. L'idea è quella di disporre i cluster sulle colonne della matrice di utilità, anziché gli item.
L'entry
Supponiamo che esista un insieme relativamente piccolo di feature di item ed utenti che determinano la valutazione della maggior parte di utenti per la maggior parte di item. Queste feature, riprendendo l'idea del clustering, sosno rappresentative di intere categorie o gruppi di feature.
L'idea è quella di utilizzare delle tecniche di decomposizione o fattorizzazione di matrici (che esprimono una matrice come prodotto di due o più matrici). Le tecniche di fattorizzazione permettono di fattorizzare una matrice
- Come prodotto di due matrici di dimensione, rispettivamente,
$m \times r \text{ ed } r \times n$ . - Come prodotto di tre matrici di dimensione, rispettivamente,
$m \times r \text{, } r \times r, r \times n$
Alcune scomposizioni d'esempio sono la decomposizione LU, la decomposizione UV, la singular value decomposition (SVD), etc.
La SVD è una tecnica di decomposizione spettrale di una matrice
-
$U$ è una matrice unitaria di dimensione$m \times r$ -
$\Sigma$ è una matrice diagonale di dimensione$r \times r$ , i cui elementi sulla diagonale sono non negativi -
$V$ è una matrice unitaria di dimensione$n \times r$
Ricordiamo che una matrice
- La decomposizione esiste sempre.
- Gli elementi di
$\Sigma$ vengono chiamati valori singolari di$M$ . - Il numero di valori singolari non nulli (diagonale di
$\Sigma$ ) corrisponde al rango di$M$ . - Le colonne della matrice
$U$ sono chiamate vettori singolari di sinistra. - Le colonne della matrice
$V$ sono chiamate vettori singolari di destra. - I vettori singolari di sinistra di
$M$ sono gli autovettori della matrice$MM^T$ - I vettori singolari di destra di
$M$ sono gli autovettori della matrice$M^TM$ - I valori singolari di
$M$ non nulli sono le radici quadrate degli autovalori non nulli di$MM^T$ ed$M^TM$
Trovare la decomposizione SVD di una matrice consiste nel trovare autovettori ed autovalori delle matrici
Sia
Nell'ambito dei sistemi di raccomandazione SVD può essere applicata per velocizzare il sistema, trasformando la matrice
La decomposizione SVD permette di mappare dati dallo spazio degli utenti e degli item allo spazio delle categorie e viceversa. Riprendendo la definizione della scomposizione: $$ M = U\Sigma V^T $$ Dove in questo caso:
- U è una matrice unitaria formata da
$m$ utenti ed$r$ categorie -
$\Sigma$ è una matrice diagonale di dimensioni$r \times r$ , con elementi della diagonale non negativi -
$V$ è una matrice unitaria formata da$n$ item ed$r$ categorie.
Usando SVD possiamo calcolare le predizioni di un utente per tutti gli item mediante un prodotto di matrici.
- Sia
$x$ un utente ed$X$ il vettore di lunghezza$n$ contenente i rating correnti su tutti gli item (se il rating per un item non è conosciuto poniamo 0). - Si moltiplica
$X$ per$V$ , il che equivale a mappare i rating correnti dallo spazio originale a quello delle categorie. Sia$Y = XV$ . - Si moltiplica
$Y$ per$V^T$ , il che equivale a ri-mappare i valori dallo spazio delle categorie allo spazio originale. Sia$R = YV^T$ - Il vettore
$R$ contiene le predizioni dei rating di$x$ su tutti gli item.
Consideriamo un nuovo utente
Proseguiamo calcolando il rango della matrice
Mappiamo adesso
E ri-mappiamo
Con il seguente risultato:
Un sistema di raccomandazione può essere visto come un classificatore o un predittore. Se conosciamo i valori reali di rating, possiamo valutare la qualità del sistema confrontando i valori predetti con quelli reali. Nei casi in cui la matrice di utilità è binaria (like / not like), o nel caso in cui non è rilevante predire il valore esatto di rating ma semplicemente se è positivo o negativo, è possibile utilizzare le tecniche standard viste per la classificazione (precision, recall, accuracy, TPR, FPR, etc.).
Se siamo invece interessati a predire il valore esatto, possiamo utilizzare tecniche standard per valutare la qualità di un predittore. La misura più utilizzata è il Root Mean Square Error (RMSE):
$$
\text {RMSE} (\hat R, R) = \sqrt{\frac{\sum_{i=1}^{|\hat R|} (\hat R_i - R_i)^2}{|\hat R|}}
$$
Dove