Factorisation de matrices pour les systèmes de recommandation

Un système de recommandation est un système virtuel dont le but premier est d'aider un utilisateur ${\displaystyle u}$ à prendre une décision concernant un item ${\displaystyle 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 (${\displaystyle utilisateur}$, ${\displaystyle item}$) associe une note correspondant à l'intérêt que pourrait porter l'utilisateur à l'item. Si on note cette fonction ${\displaystyle r}$, on a :

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

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

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

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

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 ${\displaystyle 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 ${\displaystyle 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.

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[1] tels que les boutons like/dislike, les classements ou les notes,
• les retours implicites[1] obtenus en analysant le comportement de l'utilisateur comme ses recherches[8], 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[1] 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[1] 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[7] ou totalement différents de ce que l'utilisateur a déjà noté[7]. 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[9], sont utilisés.

Une méthode bien connue pour identifier les caractéristiques dans une matrice est la Décomposition en Valeurs Singulières (ou SVD)[10]. 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.

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 ${\displaystyle K}$ facteurs latents, liés aux données de ${\displaystyle U}$ et ${\displaystyle I}$.

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

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

Pour apprendre les vecteurs de facteurs latents (${\displaystyle p_{u}}$ et ${\displaystyle 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 :

${\displaystyle {\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ù ${\displaystyle \kappa }$ est l'ensemble de toutes les paires (${\displaystyle u}$,${\displaystyle i}$) pour lesquelles ${\displaystyle r_{ui}}$ est connue, ${\displaystyle \lambda }$ est un hyperparamètre choisi et où le terme ${\displaystyle \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.

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 : ${\displaystyle e_{ui}=r_{ui}-{\hat {r}}_{ui}}$, où ${\displaystyle 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 ${\displaystyle U}$ et ${\displaystyle I}$, et l’on mettra à jour itérativement les paramètres ${\displaystyle q_{i}}$ et ${\displaystyle p_{u}}$.

Cette méthode consiste à apprendre les vecteurs ${\displaystyle p_{u}}$ et ${\displaystyle 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 ${\displaystyle p_{u}}$,
2. Trouver une meilleure valeur pour ${\displaystyle q_{i}}$ avec la méthode des moindres carrés,
3. Fixer ${\displaystyle q_{i}}$ avec la valeur trouvée en 2.,
4. Trouver une meilleure valeur pour ${\displaystyle 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é.

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 ${\displaystyle 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[11], la formule basique est la suivante.

La formule introduit trois variables[1] :

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

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

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

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

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

L’apprentissage revient à minimiser l’équation suivante[1] :

${\displaystyle {\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})}$

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[12]. 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 »[12] :

• 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[1], 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.