Décomposition en valeurs singulières vs factorisation matricielle dans les systèmes de recommandation

Clarifier la confusion entre ces méthodes

Photo par Evan Dennis sur Unsplash

Récemment, après avoir regardé le cours d’apprentissage automatique du professeur Andrew Ng dans la classe des systèmes de recommandation, je me suis senti très mal à l’aise de ne pas comprendre le fonctionnement de la factorisation matricielle.

Je sais que parfois, le calcul en machine learning est très obscur. C’est mieux si on y pense comme une boîte noire, mais ce modèle était très «magique» pour mes standards.

Dans de telles situations, j'essaie généralement de chercher sur Google davantage de références pour mieux comprendre le concept. Cette fois, j'ai été encore plus confus. Alors que le professeur Ng a appelé l'algorithme «factorisation matricielle (à faible facteur)», j'ai trouvé une nomenclature différente sur Internet: la décomposition en valeurs singulières.

Ce qui m'a le plus troublé, c'est que la décomposition en valeurs singulières était très différente de celle enseignée par le professeur Ng. Les gens ont continué à suggérer qu'ils étaient tous les deux la même chose.

Dans ce texte, je vais résumer mes conclusions et essayer de dissiper une partie de la confusion que ces termes peuvent causer.

Systèmes de recommandation

Les systèmes de recommandation (RS) ne sont que des moyens automatisés de recommander quelque chose à quelqu'un. De tels systèmes sont largement utilisés par les entreprises de commerce électronique, les services de streaming et les sites Web d’information. Cela aide à réduire les frictions des utilisateurs lorsqu'ils essaient de trouver quelque chose qui leur plaît.

RS n’est certainement pas une nouveauté: elles sont présentées depuis au moins 1990. En fait, une partie du battage publicitaire récent de Machine Learning peut être attribuée à l’intérêt suscité par RS. En 2006, Netflix a fait sensation en sponsorisant un concours visant à trouver le meilleur RS pour leurs films. Comme nous le verrons bientôt, cet événement est lié au désordre de la nomenclature qui a suivi.

La représentation matricielle

Il y a de nombreuses façons pour une personne de recommander un film à quelqu'un. Une stratégie qui s’est révélée très efficace consiste à traiter les cotes de cinéma comme une matrice Utilisateurs x Films de la manière suivante:

Créé avec https://sheetsu.com/

Dans cette matrice, les points d'interrogation représentent les films qu'un utilisateur n'a pas évalués. La stratégie consiste alors à prévoir ces évaluations d’une manière ou d’une autre et à recommander aux utilisateurs les films qu’ils aimeront probablement.

Factorisation Matricielle

Les gars qui ont participé au concours Netflix (notamment Simon Funk) ont pris conscience que les évaluations des utilisateurs n’étaient pas des suppositions aléatoires. Les rapporteurs suivent probablement une logique en pondérant les choses qu’ils aiment dans un film (une actrice ou un genre) par rapport à des choses qu’ils n’aiment pas (longue durée ou de mauvaises blagues), puis ils créent une partition.

Ce processus peut être représenté par une formule linéaire du type suivant:

où xₘ est un vecteur de colonne avec les valeurs des caractéristiques du film m et θ est un autre vecteur de colonne avec les pondérations que l'utilisateur u attribue à chaque caractéristique. Chaque utilisateur a un ensemble de poids différent et chaque film a un ensemble de valeurs différent pour ses caractéristiques.

Il s'avère que si nous fixons arbitrairement le nombre de caractéristiques et ignorons les notations manquantes, nous pouvons trouver un ensemble de valeurs de pondération et de caractéristiques qui créent une nouvelle matrice avec des valeurs proches de la matrice de notations d'origine. Cela peut être fait avec une descente de gradient, très semblable à celle utilisée dans la régression linéaire. Au lieu de cela, nous optimisons maintenant deux ensembles de paramètres (poids et caractéristiques) en même temps.

En utilisant le tableau que j'ai donné en exemple ci-dessus, le résultat du problème d'optimisation générerait la nouvelle matrice suivante:

Notez que la matrice résultante ne peut pas être une copie exacte de la matrice originale dans la plupart des jeux de données réels, car dans la vie réelle, les utilisateurs ne font pas de multiplications ni de sommations pour évaluer un film. Dans la plupart des cas, le classement n’est qu’un sentiment instinctif qui peut également être affecté par toutes sortes de facteurs externes. Nous espérons néanmoins que la formule linéaire est un bon moyen d’exprimer la logique principale qui sous-tend les évaluations des utilisateurs.

OK, nous avons maintenant une matrice approximative. Mais comment diable cela nous aide-t-il à prédire les notes manquantes? N'oubliez pas que pour construire la nouvelle matrice, nous avons créé une formule permettant de renseigner toutes les valeurs, y compris celles manquantes dans la matrice d'origine. Donc, si nous voulons prédire le classement manquant d'un utilisateur sur un film, nous prenons simplement toutes les valeurs caractéristiques de ce film, multiplions par tous les poids de cet utilisateur et additionnons tout. Ainsi, dans mon exemple, si je veux prédire le classement de Movie 1 par l’utilisateur 2, je peux effectuer le calcul suivant:

Pour clarifier les choses, nous pouvons dissocier les θ et les x et les placer dans leurs propres matrices (disons P et Q). C'est effectivement une factorisation matricielle, d'où le nom utilisé par le professeur Ng.

Cette factorisation matricielle est fondamentalement ce que Funk a fait. Il a obtenu la troisième place du concours Netflix, attirant beaucoup l’attention (ce qui est un cas intéressant, une troisième place étant plus célèbre que les gagnants). Son approche a été reproduite et améliorée depuis lors et est toujours utilisée dans de nombreuses applications.

Décomposition en valeur singulière

Entrez la décomposition en valeurs singulières (SVD). La SVD est une manière élégante de factoriser une matrice en trois autres matrices (A = UΣVᵀ). La manière dont la SVD est réalisée garantit que ces 3 matrices possèdent de belles propriétés mathématiques.

Il existe de nombreuses applications pour SVD. L’une d’entre elles est l’analyse en composantes principales (ACP), qui consiste à réduire un jeu de données de la dimension n à la dimension k (k

Je ne vous donnerai pas plus de détails sur les SVD parce que je ne me connais pas. Le fait est que ce n’est pas la même chose que nous l’avons fait avec la factorisation matricielle. La meilleure preuve est que SVD crée 3 matrices alors que la factorisation matricielle de Funk n'en crée que 2.

Alors, pourquoi SVD continue à apparaître chaque fois que je recherche des systèmes Recommender? J'ai dû creuser un peu, mais j'ai fini par trouver des trésors cachés. Selon Luis Argerich:

Les algorithmes de factorisation de matrice utilisés pour les systèmes de recommandation essaient de trouver deux matrices: P, Q tel que P * Q correspond aux valeurs CONNUES de la matrice d’utilité.
Ce principe est apparu dans le fameux document SVD ++ «La factorisation à la rencontre du voisinage» qui a malheureusement utilisé le nom «SVD ++» pour un algorithme qui n’a absolument aucune relation avec le SVD.

Pour mémoire, je pense que Funk, et non les auteurs de SVD ++, a d’abord proposé la factorisation de matrice mentionnée pour les systèmes de recommandation. En fait, SVD ++, comme son nom l’indique, est une extension du travail de Funk.

Xavier Amatriain nous donne une image plus grande:

Commençons par souligner que la méthode habituellement appelée «SVD» utilisée dans le contexte des recommandations n’est pas à proprement parler la décomposition mathématique en valeurs singulières d’une matrice, mais plutôt un moyen approximatif de calculer l’approximation de bas rang de la matrice. en minimisant la perte d'erreur au carré. Une méthode plus précise, bien que plus générique, serait la factorisation matricielle. La version initiale de cette approche dans le cadre du prix Netflix a été présentée par Simon Funk dans son célèbre article de blog Try This at Home. Il est important de noter que l’approche de la «vraie SVD» a bien été appliquée à la même tâche des années auparavant, sans grand succès pratique.

Wikipedia a également des informations similaires enfouies dans son article sur la factorisation de matrice (systèmes de recommandation):

L'algorithme original proposé par Simon Funk dans son billet de blog a factorisé la matrice de classement utilisateur-produit comme le produit de deux matrices de dimension inférieure, la première comporte une ligne pour chaque utilisateur, tandis que la seconde comporte une colonne pour chaque élément. La ligne ou la colonne associée à un utilisateur ou à un élément spécifique est appelée facteur latent. Notez que, malgré son nom, dans FunkSVD, aucune décomposition en valeurs singulières n’est appliquée.

Résumer:

1. La SVD est une technique mathématique quelque peu complexe qui factorise les matrices dans trois nouvelles matrices et a de nombreuses applications, notamment PCA et RS.

2. Simon Funk a appliqué une stratégie très intelligente au concours Netflix de 2006, en factorisant une matrice en deux autres et en utilisant la descente de gradient pour trouver des valeurs optimales de caractéristiques et de poids. Ce n’est pas une SVD, mais il a quand même utilisé ce terme pour décrire sa technique.

3. Le terme le plus approprié pour décrire ce que Funk a fait est la factorisation matricielle.

4. En raison des bons résultats et de la notoriété qui en a résulté, on appelle encore cette technique SVD, car c’est ainsi que l’auteur l’a nommée.

J'espère que cela aide à clarifier un peu les choses.