Cos'è il metodo Alternating Least Squares nei sistemi di raccomandazione? E perché questo algoritmo funziona (intuizione dietro questo)?

Quando si usa un approccio di fattorizzazione della matrice per implementare un algoritmo di raccomandazione, si decompone la grande matrice utente/oggetto in fattori utente e fattori oggetto di dimensioni inferiori. Nell'approccio più semplice si può quindi stimare la valutazione dell'utente (o in generale la preferenza) moltiplicando questi fattori secondo la seguente equazione:

[math]r_{ui}^{'} =p_u^T q_i[/math] (1)

Per imparare questi fattori è necessario minimizzare la seguente funzione di perdita quadratica:

[math]argmin_{q,p}\sum_{u,i}{(r_{ui}-p_u^T q_i)^2}[/math] (2)

Nota che per semplicità sto omettendo i possibili bias nella prima equazione e la regolarizzazione in questa seconda.

In un approccio SGD (Stochastic Gradient descent), per ogni esempio nel dataset si calcola l'errore [math](r_{ui}-p_u^T q_i)[/math] e poi si aggiornano i parametri di un fattore nella direzione opposta del gradiente.

Alternating Least Squares (ALS) rappresenta un approccio diverso per ottimizzare la funzione di perdita. L'intuizione chiave è che si può trasformare il problema di ottimizzazione non convesso dell'equazione (2) in un "facile" problema quadratico se si fissa [math]p_u[/math] o [math]q_i[/math]. ALS fissa ciascuno di essi alternativamente. Quando uno è fissato, l'altro viene calcolato, e viceversa.

Ci sono due vantaggi principali di questo approccio. Primo, è molto facile da parallelizzare. In secondo luogo, quando si ha a che fare con insiemi di dati impliciti, che di solito non sono sparsi, SGD non è pratico (i tempi degli utenti possono facilmente essere dell'ordine di miliardi). ALS è una tecnica di ottimizzazione molto più efficiente in questi casi.

Riferimenti:

Collaborative Filtering for Implicit Datasets, Hu et. al
Matrix Factorization Techniques for Recommender Systems
Alternating Least Square for Personalized Ranking

Implementazioni:

ALS in Mahout
ALS in MLlib - Spark 1.4.1 Documentation
libFM include ALS per Factorization Machines