Matrix factorization

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.^[1] 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.^[2]

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.^[3] Si noti che, nonostante il nome, FunkSVD non utilizza la decomposizione ai valori singolari SVD. I rating predetti possono essere calcolati come ${\displaystyle {\tilde {R}}=HW}$, dove${\displaystyle {\tilde {R}}\in \mathbb {R} ^{utenti\times item}}$ è la matrice di interazioni utente-item, ${\displaystyle H\in \mathbb {R} ^{utenti\times fattorilatenti}}$ contiene i fattori latenti dell'utente e ${\displaystyle 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:

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

È possibile variare il potere espressivo del modello cambiando il numero di fattori latenti. È stato dimostrato^[4] che una matrix factorization con un solo fattore latente è equivalente a un algoritmo most popular o top popular (es. raccomando gli item più popolari, senza alcuna personalizzazione). Aumentare 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:

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

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

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.^[6][7] 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:

${\displaystyle {\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.^[8]

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. È stato dimostrato che questa formulazione è quasi equivalente ad un modello di tipo SLIM^[9], ossia un recommender item-item model based.

${\displaystyle {\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 ${\displaystyle {\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.^[10]

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

${\displaystyle {\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 è ${\displaystyle {\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^[11] o informazioni di tipo collaborativo e content^[12][13][14]

Deep-Learning Matrix factorization

Negli ultimi anni sono stati proposti un cospicuo numero di algoritmi neurali o basati su deep-learning, alcuni dei quali generalizzano il tradizionale problema di Matrix factorization tramite una architettura neurale non lineare^[15]. Sebbene il deep-learning sia stato applicato in molteplici scenari: context-aware, sequence-aware, tagging su social network etc. la sua reale efficacia quando applicato ad un semplice problema di Collaborative filtering è stata messa in dubbio. Una analisi sistematica di pubblicazioni che propongono nuovi algoritmi di deep-learning o neurali applicati ad un problema di raccomandazioni top-k, pubblicati in conferenze di alto livello (SIGIR, KDD, WWW, RecSys), ha mostrato come, mediamente, meno del 40% degli articoli abbia risultati riproducibili, con un minimo del 14% in alcune conferenze. Complessivamente, lo studio identifica 18 articoli, solo 7 dei quali hanno risultati riproducibili e ben 6 di tali algoritmi possono essere superati da tecniche molto più semplici e vecchie, quando ottimizzate correttamente. L'articolo evidenzia diversi potenziali problemi nella ricerca scientifica attuale nel settore dei sistemi di raccomandazione e invita a rafforzare le pratiche sperimentali utilizzate.^[16] Osservazioni simili sono state presentate anche nel caso dei sistemi di raccomandazioni basati su sequenze.^[17]