Factorisation de matrices pour les systèmes de recommandation

La Factorisation de matrices pour les systèmes de recommandation est une des méthodes utilisées par les services en ligne comme Netflix afin d'accélérer la recherche de recommandations de contenu pour les utilisateurs.

Dû à l'explosion sur Internet de la quantité de données numériques concernant des sujets tous plus divers et variés tels que des vidéos, des articles, des images, etc., ainsi qu'à la vaste palette de profils utilisateurs désirant accéder à des informations de la façon la plus précise possible, la nécessité d’élaborer des systèmes de recommandation efficaces est apparue d'elle même. Un exemple parlant est le site de streaming vidéo Netflix, qui compte plus de 60 millions d’utilisateurs dans plus de 60 pays, et possède un catalogue estimé à plus de 100 millions d’heures de visionnage. Les performances de leur système de recommandation est un enjeu majeur pour cette entreprise, d’où la création d’un concours qui a permis aux participants de gagner 1 million de dollars afin d’améliorer leur système de recommandation.

Pour être le plus efficace possible, le système de recommandation doit avoir le plus large éventail de choix de recommandation possible, et de nombreuses données par utilisateur du service (ce qu’il a aimé, ce qu’il a détesté, ce qu’il a mis de côté pour plus tard, etc.), afin de pouvoir recommander au mieux un utilisateur. L'efficacité de ces systèmes est ainsi fortement corrélée à leur capacité à manipuler des grandes quantités de données et à leur faculté à fournir les meilleurs recommandations pour un utilisateur donné. Afin de réduire la taille de stockage de la matrice, il pourra être intéressant de se concentrer sur une matrice creuse. Malheureusement, une recherche sur une matrice creuse de grande taille sera considérée plus importante en calcul et en temps qu’une recherche sur une matrice creuse de plus petite taille, et pourrait réduire considérablement la qualité de service du système.

Système de recommandation

Description

Un système de recommandation est un système virtuel dont le but premier est d'aider un utilisateur $u$ à prendre une décision concernant un item $i$. Le système de recommandation doit donc, au vu des informations laissées par l'utilisateur et de ses choix précédents, lui conseiller des items qui ont une grande chance de l'intéresser. Un tel système peut donc être représenté par une fonction qui, à un couple ($utilisateur$, $item$) associe une note correspondant à l'intérêt que pourrait porter l'utilisateur à l'item. Si on note cette fonction $r$, on a :

$r:U\times I\rightarrow \mathbb {R}$ où $U$ est l'ensemble des utilisateurs et $I$ l'ensemble des items.

À l'aide de ce formalisme, on peut exprimer les objets suivants :

• $r_{ui}$ qui vaut la note effective qu'a donné l'utilisateur $u$ à l'item $i$
• ${\hat {r}}_{ui}$ qui vaut une prédiction du système de recommandation concernant la note que l'utilisateur $u$ donnerait à l'item $i$
• $U_{i}$ qui représente l'ensemble des utilisateurs qui ont noté l'item $i$
• $I_{u}$ qui représente l'ensemble des items notés par l'utilisateur $u$

Filtrage de contenu

Le filtrage de contenu (ou content-based filtering en anglais) est amplement détaillé sur la page Recommender system.

Le principe de recommandation par filtrage de contenu consiste à construire un profil pour chaque utilisateur ainsi que pour chaque item, à l'aide de mots-clés. Il s'agira ensuite d'associer à un utilisateur les items qui lui correspondent le mieux, en se référent à ses préférences (son profil) ainsi qu'à son historique.

La première étape consiste à transformer le profil d'un item en vecteur de valeurs. Pour cela, l'algorithme le plus utilisé est l'algorithme tf-idf. Ensuite, le système crée un vecteur de poids $v_{u}$ pour chaque utilisateur : chacun des poids de ce vecteur représente l'importance que donne l'utilisateur à une caractéristique particulière d'un item. Le système peut déterminer ces poids à l'aide des différentes formes de retours de l'utilisateur (typiquement un bouton like/dislike).

Pour déterminer si un item est susceptible de convenir à un utilisateur, une méthode simple consiste à comparer la moyenne des valeurs du vecteur $v_{u}$ avec la moyenne des valeurs du vecteur de l'item. D'autres approches plus complexes utilisent des méthodes d'apprentissage automatique afin d'estimer la probabilité que l'utilisateur aime l'item.

Cette méthode a le désavantage de devoir absolument collecter diverses informations sur l'utilisateur afin de construire son profils. De plus, cette méthode est item-dépendante, c'est-à-dire qu'elle est plus efficace lorsque l'on recommande des items qui sont similaires à ceux déjà notés par l'utilisateur.

Filtrage collaboratif

Le principe de recommandation par filtrage collaboratif consiste à récolter et analyser les actions et comportements passés d'un utilisateur afin de pouvoir prédire une liste d'items qui pourraient lui correspondre. Ce principe se base en fait sur les items que d'autres utilisateurs, proches de ce dernier, ont appréciés (en termes de goût).

Illustration d'un filtrage collaboratif

Le filtrage collaboratif utilise deux types de retours de l'utilisateur :

• les retours explicites tels que les boutons like/dislike, les classements ou les notes,
• les retours implicites obtenus en analysant le comportement de l'utilisateur comme ses recherches, la fréquence à laquelle il s'intéresse à un item ou encore les sujets qu'il évoque sur les réseaux sociaux.

Théoriquement, un utilisateur ne pourra pas avoir noté l’ensemble des items si celui-ci est trop grand. La matrice utilisant ainsi les retours explicites sera donc creuse, contrairement à celle utilisant les retours implicites qui sera de forte densité.

Il existe deux modèles de filtrage collaboratif :

• le modèle des voisins qui se base sur les relations entre items ou entre utilisateurs. La relation entre items permet de proposer à l'utilisateur des items qui ressemblent à ce qu'il a déjà aimé. La relation entre utilisateur permet de proposer à l'utilisateur des items qui sont appréciés par des autres utilisateurs qui lui sont proches (toujours en ce qui concerne le goût).
• le modèle des facteurs latents qui caractérisent à la fois les items et les utilisateurs par des « facteurs » (entre 20 et 100). Ces facteurs peuvent représenter divers éléments, par exemple pour un film : « la quantité d'action », « la dose d'humour », « la profondeur des personnages », ou des dimensions beaucoup plus obscures et non descriptibles.

Contrairement à la méthode de filtrage de contenu, cette méthode ne dépend pas des types des items : elle permet de recommander des items partiellement connus ou totalement différents de ce que l'utilisateur a déjà noté. Cependant ce principe souffre tout de même de quelques lacunes à savoir le départ à froid (il faut bien commencer par récolter quelques données), le passage à l'échelle (les calculs peuvent devenir énormes avec beaucoup d'items et d'utilisateurs) et la disparité des données (si le système contient des millions d'items, un item en particulier risque d'être finalement très peu représenté). C'est pour combler ces désavantages que des méthodes d'apprentissage, et notamment la factorisation de matrice, sont utilisés.

Mise en œuvre de la factorisation de matrice dans les systèmes de recommandations

La factorisation de matrice, ou décomposition de matrice, consiste à décomposer une matrice en plusieurs autres matrices. Pour approximer la matrice observée, il suffira de calculer le produit de ces matrices. Ce produit aboutit à la matrice prédite. Mathématiquement, nous avons une matrice $M$, représentant chaque notation effectuée par un utilisateur $u$ pour un item $i$. Ainsi, la dimension de la matrice est $\lVert U\rVert \times \lVert I\rVert$.

Afin de comprendre l'intérêt de la factorisation de matrice pour les systèmes de recommandation, voici un simple cas nous permettant de l’illustrer :

« Prenons un système de recommandation tel que le service Netflix. Il est à noter que, si un utilisateur de ce service n’a pas pu noter les $i$ items mis à sa disposition, cette matrice est creuse. L'un des problèmes majeurs dans cet exemple est la quantité de données inutiles que la matrice contient. Le fait qu'elle soit creuse introduit beaucoup de relations $item/utilisateur$ nulles qui nécessitent d'être évaluées lors des traitements. Ceci a pour conséquence de ralentir le système. De plus, il est nécessaire de stocker ces relations nulles, ce qui constitue un réel gaspillage de mémoire. »

L'exemple peut-être repris pour les plus gros services du Web, comme Amazon, Google ou encore Facebook. Grâce à la factorisation de matrice, ces différents systèmes peuvent représenter leur structure de données de façon plus concise et pertinente, afin d’atteindre des temps de traitement bien plus compétitif, et une économie de l’espace de stockage.

Types de factorisation de matrice

La méthode SVD

Une méthode bien connue pour identifier les caractéristiques dans une matrice est la Décomposition en Valeurs Singulières (ou SVD). Or, la méthode SVD n’est pas recommandée dans le cas des matrices creuses, au risque de sur-considérer les données. Remplacer les données manquantes par des données générées n’est pas une bonne idée, étant donné que cela biaisera les données collectées et déduites et que cela consommera plus de mémoire de stockage en la transformant en matrice de forte densité.

Ainsi, ces éléments découragent l’utilisation de la méthode SVD pour les systèmes de recommandation.

La méthode des facteurs latents

Le modèle de facteurs latents représente les items et les utilisateurs par des vecteurs de caractéristiques de même taille. C’est la technique de « rétrocontrôle » (ou « feedback » dans la littérature scientifique) qui va fournir deux manières d’obtenir des informations sur les utilisateurs : explicite et implicite.

Grâce aux préférences déterminées avec le rétrocontrôle, on obtient les vecteurs de caractéristiques des utilisateurs. Chaque item possède un vecteur de caractéristiques qui lui est propre. Ainsi, plus la correspondance entre les caractéristiques d’un utilisateur avec celles d’un item est grande, plus la recommandation sera considérée comme pertinente. Mathématiquement, on détermine $K$ facteurs latents, liés aux données de $U$ et $I$.

Le but étant de décomposer la matrice $M$ en deux matrices $P$ et $Q$ de dimensions respectives $\lVert U\rVert \times K$ et $\lVert I\rVert \times K$.

Ainsi, la matrice initiale $M$ pourra être approchée par le produit matriciel $P\times Q^{T}$. La prédiction sur la correspondance entre les caractéristiques de $u$ et $i$ se calcule de la façon suivante : ${\hat {r}}_{ui}=q_{i}^{T}p_{u}$, où $q_{i}$ est le vecteur de caractéristique pour l’item $i$ et $p_{u}$ celui associé à utilisateur $u$.

Détermination des vecteurs caractéristiques

Pour apprendre les vecteurs de facteurs latents ($p_{u}$ et $q_{i}$), on minimise la différence entre le produit de ces vecteurs et le résultat contenu dans la matrice initiale.

Mathématiquement, cela se traduit par :

${\underset {q_{i},p_{u}}{min}}{\underset {u,i\in \kappa }{\sum }}(r_{ui}-{\hat {r}}_{ui})^{2}+\lambda (\lVert q_{i}\rVert ^{2}+\lVert p_{u}\rVert ^{2})$

Où $\kappa$ est l'ensemble de toutes les paires ($u$,$i$) pour lesquelles $r_{ui}$ est connue, $\lambda$ est un hyperparamètre choisi et où le terme $\lambda (\lVert q_{i}\rVert ^{2}+\lVert p_{u}\rVert ^{2})$ est une régularisation qui permet de ne pas surestimer les données observées.

Cet apprentissage peut se faire à travers deux méthodes d'apprentissage :

• la descente de gradient stochastique,
• les moindres carrés alternés.

Apprentissage avec la descente de gradient stochastique

La méthode de descente de gradient stochastique est la plus simple à mettre en place, et la plus rapide. Elle consiste à associer une erreur de prédiction à chaque cas de test, et la minimiser.

Mathématiquement, cela se traduit par : $e_{ui}=r_{ui}-{\hat {r}}_{ui}$, où $e_{ui}$ est le résultat de la différence entre le résultat final et le résultat prédit. Ainsi, l’apprentissage se fera sur la distribution des caractéristiques présentes dans chaque vecteur, pour les matrices $U$ et $I$, et l’on mettra à jour itérativement les paramètres $q_{i}$ et $p_{u}$.

Apprentissage avec les moindres carrés alternés

Cette méthode consiste à apprendre les vecteurs $p_{u}$ et $q_{i}$ en fixant de manière alternée la valeur d'un des deux vecteurs pour apprendre la valeur du second. En effet, en fixant la valeur d'un des vecteurs, le problème peut être résolu avec la méthode des moindres carrés classique. L'algorithme peut être résumé de la façon suivante :

1. Fixer $p_{u}$,
2. Trouver une meilleure valeur pour $q_{i}$ avec la méthode des moindres carrés,
3. Fixer $q_{i}$ avec la valeur trouvée en 2.,
4. Trouver une meilleure valeur pour $p_{u}$ avec la méthode des moindres carrés,
5. Recommencer en 1.

Cette méthode a l’avantage d’être parallélisable, et peut être utilisée pour les systèmes détenant des matrices à forte densité.

Résolution des problèmes résiduels

Problème des biais dans les données

Un problème récurrent pour la prédiction des notes sont les biais introduits par les utilisateurs ou les items. Ceux-ci pourraient fausser la prédiction $r_{ui}$. Par exemple, pour un système de recommandation de films, le biais introduit pourrait être le fait qu’un film reconnu ou excellent par la communauté verra sa note surestimée par les utilisateurs, alors qu’un film du même genre, mais un peu moins connu, recevra une note plus modérée. Quant aux utilisateurs, ils ont tous une personnalité qui leur est propre et peuvent donc attribuer facilement de très bonnes notes ou bien, à l’inverse, être beaucoup plus critiques.

Pour contrer ces biais, il faut les prendre en compte dans la prédiction. De nombreuses manières de procéder existent, la formule basique est la suivante.

La formule introduit trois variables :

• $\mu$, la moyenne des notes données sur l’ensemble des items par l’ensemble des utilisateurs,
• $b_{i}$, le biais introduit par l’item. Il s’agit de la différence entre $\mu$ et  l’ensemble des notes données à l’item $i$,
• $b_{u}$, le biais introduit par l’utilisateur. Il s’agit de la différence entre $\mu$ et l’ensemble des notes données par l’utilisateur $u$.

Le biais de la notation d’un item par un utilisateur :

$b_{ui}=\mu +b_{i}+b_{u}$

La prédiction corrigée avec la prise en compte du biais :

${\hat {r}}_{ui}=\mu +b_{i}+b_{u}+q_{i}^{T}p_{u}$

L’apprentissage revient à minimiser l’équation suivante :

${\underset {p*,q*,b*}{min}}{\underset {(u,i)\in \kappa }{\sum }}(r_{ui}-\mu -b_{u}-b_{i}-p_{u}^{T}q_{i})^{2}+\lambda (\lVert p_{u}\rVert ^{2}+\lVert q_{i}\rVert ^{2}+b_{i}^{2}+b_{i}^{2})$

Problème du « démarrage à froid »

Un problème des plus connus dans les systèmes de recommandation est lorsque l’on détient aucune ou peu d’informations sur un utilisateur. En effet, étant donné que le nombre d’items apprécié par cet utilisateur est faible ou nul, le système de recommandation ne pourra pas attribuer une grande pertinence aux résultats lors de la recommandation des données. C’est ce que l’on appelle le « démarrage à froid » (cold-start dans la littérature scientifique).

Typiquement, il y a 3 grands types de « démarrage à froid » :

• les recommandations pour les nouveaux utilisateurs,
• les recommandations pour les nouveaux items,
• les recommandations pour les nouveaux items, pour les nouveaux utilisateurs.

Ce problème est très connu, et plusieurs solutions existent pour chacun des types.

Une des solutions au problème de « démarrage à froid » pour les nouveaux utilisateurs est de passer par le rétrocontrôle implicite, afin d’obtenir indirectement des informations sur l’utilisateur, et pouvoir élargir la base de connaissance nécessaire sur ce dernier afin de le croiser avec les caractéristiques de la matrice.

Quant au problème de « démarrage à froid » concernant les nouveaux items, ceux-ci peuvent être directement évalués selon les correspondances avec les autres items, ce qui revient à filtrer les contenus.