Utente:MaurizioFD/Matrix factorization (sistema di raccomandazione)

La Matrix factorization (MF), o fattorizzazione di matrice, è una classe di algoritmi collaborative filtering usata nei sistemi di raccomandazione. Gli algoritmi di matrix factorization operano decomponendo la matrice di interazioni user-item nel prodotto di due matrici rettangolari dalla dimensionalità inferiore.  Questa famiglia di metodi divenne nota durante la Netflix Prize challenge, grazie alla sua efficacia dimostrata da Simon Funk in un post sul suo blog datato 2006.

Tecniche

L'idea alla base della matrix factorization è di rappresentare utenti e item in uno spazio latente di dimensionalità inferiore. Dall'iniziale proposta di Simon Funk risalente al 2006 una moltitudine di varianti sono state proposte. Alcune delle più note e semplici sono illustrate nelle sezioni seguenti.

Funk SVD

L'algoritmo originale proposto da Simon Funk nel suo blog post fattorizzava la matrice dei rating user-item come il prodotto di due matrici rettangolari dalla dimensionalità inferiore, la prima ha una riga per ogni utente mentre la seconda una colonna per ogni item. La riga associata ad uno specifico utente e la colonna associata ad uno specifico item è detta contenere i suoi fattori latenti. Si noti che, nonostante il nome, FunkSVD non utilizza la decomposizione ai valori singolari SVD. I rating predetti possono essere calcolati come  ${\tilde {R}}=HW$, dove${\tilde {R}}\in \mathbb {R} ^{utenti\times item}$ è la matrice di interazioni utente-item, $H\in \mathbb {R} ^{utenti\times fattorilatenti}$ contiene i fattori latenti dell'utente e $W\in \mathbb {R} ^{fattorilatenti\times item}$ i fattori latenti dell'item.

Nello specifico, la predizione del rating che l'utente u darà all' item i è calcolata come:

${\tilde {r}}_{ui}=\sum _{f=0}^{nfattori}H_{u,f}W_{f,i}$

E' possibile variare il potere espressivo del modello cambiando il numero di fattori latenti. E' stato dimostrato  che una matrix factorization con un solo fattore latente è equivalente ad un algoritmo most popular o top popular  (es. raccomando gli item più popolari, senza alcuna personalizzazione). Aumentar il numero di fattori latenti permette di migliorare la personalizzazione, quindi la qualità delle raccomandazioni, finchè il loro numero diventerà troppo alto e il modello incorrerà in overfitting. Una strategia comune per evitare l'overfitting è di aggiungere dei termini di regolarizzazione alla funzione obiettivo. FunkSVD fu sviluppato per la predizione di rating, pertanto rappresenta le interazioni utente-item come valori numerici.

Nel complesso, FunkSVD minimizza la funzione obiettivo seguente:

${\underset {H,W}{\operatorname {arg\,min} }}\,\|R-{\tilde {R}}\|_{\rm {F}}+\alpha \|H\|+\beta \|W\|$

Dove $\|.\|_{\rm {F}}$ è la norma frobenius mentre le altre norme possono essere frobenius o meno a seconda di cosa funzioni meglio per quello specifico contesto.

SVD++

Sebbene FunkSVD riesca a fornire raccomandazioni di buona qualità, la sua capacità di gestire solo interazioni user-item esplicite numeriche costituisce una limitazione. I sistemi di raccomandazione utilizzati al giorno d'oggi devono riuscire a sfruttare tutti i tipi di interazione, sia espliciti (es. ratings numerici) che impliciti (es. likes, acquisti, preferiti). SVD++ fu sviluppato per prendere in considerazione anche interazioni di tipo implicito.  Inoltre rispetto a  FunkSVD, SVD++ considera anche il bias di item e utente.

Nello specifico, la predizione del rating che l'utente u darà all' item i è calcolata come:

${\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{nfattori}H_{u,f}W_{f,i}$

SVD++ ha però alcuni svantaggi, il principale è il non essere model-based, ciò significa che, se un nuovo utente si iscrive, l'algoritmo non è in grado di raccomandargli nulla a meno che l'intero modello sia riaddestrato. Nonostante il sistema possa aver raccolto alcune interazioni per quell'utente, i suoi fattori latenti non sono comunque disponibili e quindi nessuna raccomandazione può essere calcolata. Ciò è un esempio di cold-start, ossia il sistema di raccomandazione non riesce a gestire efficacemente nuovi item o utenti, pertanto sono necessarie delle misure ad-hoc.

Una possibilità per affrontare il cold start è di modificare SVD++ in modo che diventi model-based, affinchè possa gestire più agevolmente nuovi item o utenti.

Come menzionato in precedenza in SVD++ non sono disponibili i fattori latenti per nuovi utenti, pertanto è necessario rappresentarli in modo diverso. I fattori latenti dell'utente rappresentano la sua preferenza per i corrispondenti fattori latenti dell'item, pertanto i fattori latenti dell'utente possono essere stimati in base alle sue passate interazioni. Se il sistema è in grado di raccogliere delle interazioni, allora è possibile stimare i suoi fattori latenti. Si noti che questo non risolve completamente il problema del cold-start, in quanto il sistema di raccomandazione comunque richiede delle interazioni per i nuovi utenti, ma almeno non è più necessario riaddestrare l'intero modello ogni volta. E' stato dimostrato che questa formulazione è quasi equivalente ad un modello di tipo SLIM, ossia un recommender item-item model based.

${\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{nfattori}{\biggl (}\sum _{j=0}^{nitem}r_{uj}W_{j,f}{\biggr )}W_{f,i}$

In questa formulazione, il recommender item-item recommender corrispondente sarebbe ${\tilde {R}}=RS=RW^{\rm {T}}W$. Pertanto la similarity matrix S è simmetrica.

Asymmetric SVD

Asymmetric SVD cerca di conservare i vantaggi di SVD++ pur essendo model based, quindi in grado di gestire nuovi utenti purchè essi abbiano almeno qualche interazione.  Rispetto alla versione model based di SVD++ la matrice di fattori latenti H è sostituita da Q, in quanto è diverso quanto si vuole rappresentare, la preferenza dell'utente come funzione dei suoi rating.

Nello specifico, la predizione del rating che l'utente u darà all' item i è calcolata come:

${\tilde {r}}_{ui}=\mu +b_{i}+b_{u}+\sum _{f=0}^{nfattori}\sum _{j=0}^{nitem}r_{uj}Q_{j,f}W_{f,i}$

In questa formulazione, il recommender item-item recommender corrispondente è ${\tilde {R}}=RS=RQ^{\rm {T}}W$. Poichè le matrici Q e W sono diverse, la matrice di similarità S sarà asimmetrica, da ciò deriva il nome del modello.

Matrix factorization ibrido

Recentemente molti altri modelli di fattorizzazione sono stati sviluppati per sfruttare il sempre crescente volume e varietà di interazioni e casi d'uso. Gli algoritmi ibridi di matrix factorization sono in grado di fondere interazioni implicite ed esplicite  o informazioni di tipo collaborativo e content 

Vedi anche

• Collaborative filtering
• Sistema di raccomandazione

Categoria:Sistemi informativi