Etude bibliographique des systèmes de recommandation à base de factorisation de matrices

Publié le dimanche 01 novembre 2020 à 22:25 , mis à jour le mardi 03 novembre 2020
17 mins

Nous avons initié en 2020 le développement du projet thelia.ai qui est une extension IA pour le logiciel de e-commerce thelia (également développé par OpenStudio). Parmi les fonctionnalités IA intégrées dans thelia.ai, nous proposons plusieurs systèmes de recommandation.

Après une courte introduction pour présenter les différents types de recommandations, je ferai un tour d’horizon des principales publications scientifiques concernant les systèmes de recommandations à factorisation de matrices.

Les descriptions détaillées du fonctionnement des méthodes nécessitent des connaissances en algèbre linéaire.

Recommandation de produits

Le succès des moteurs de recommandation est indéniable. Que ce soit pour recommander des vidéos ou des produits, on les retrouve partout. Comme nous l’avons vu plus haut, les catalogues sont de plus en plus importants et posent au consommateur le problème que l’on nomme « le paradoxe du choix » (Le problème a été soulevé dans le livre de Barry Schwartz ) : plus il y a de choix proposés, plus il est difficile pour un consommateur de décider quel produit acheter (pour des raisons de « disponibilité d’esprit », et moins le taux de transformation est élevé. Ainsi, un moteur de recommandations peut être considéré comme un « vendeur », qui permet au client d’optimiser sa navigation dans le site pour atteindre automatiquement les produits qu’il recherche, le soulageant ainsi d’une laborieuse exploration.

Plus il y a de choix proposés, plus il est difficile pour un consommateur de décider quel produit acheter

C’est pourquoi, le moteur de recommandation doit être pertinent ! Les produits recommandés doivent tenir compte du profil de l’utilisateur et du contexte. Les dernières années ont vu l’intégration de nouvelles données dans les méthodes de prédiction en complément des données explicites (typiquement les avis clients sur des produits) : des données implicites (produits consultés, produits achetés, …), des données contextuelles (heure, saison, météo, …), des données séquentielles (timeline des recherches effectuées, des pages consultées ou des actes d’achats) et des données sociales (issues des réseaux sociaux, intégrant la notion de “confiance”). La satisfaction du client pour un moteur de recommandation est directement corrélée avec le taux de conversion sur les produits proposés.

Du point de vue du décideur en charge d’un site e-commerce, une fois qu’un nouveau système de recommandation est proposé, le meilleur indicateur de la pertinence de celui-ci sera obtenu en réalisant un A/B testing “in situ” entre un système existant (déjà en place sur le site e-commerce) et le nouveau système de recommandation qui doit le remplacer .

IA et systèmes de recommandation

L’intelligence artificielle est très présente dans les systèmes de recommandation.

Nous passerons rapidement sur les premières méthodes empiriques des plus proches voisins, pour présenter en détail une méthode de machine learning : la factorisation de matrices, dont les matrices de facteurs latents sont construites par apprentissage.

Filtrage sur le contenu et filtrage collaboratif

Avant de décrire plus en détail les contributions de l’intelligence artificielle dans ce domaine, prenons quelques instants pour présenter le fonctionnement des moteurs de recommandation. Il en existe deux types : les recommandations basées sur les contenus et les recommandations basées sur un filtrage collaboratif. Dans le premier cas, il s’agit de proposer à l’utilisateur des produits dont les contenus sont similaires aux produits qu’il a consulté ou qu’il a précédemment acheté (dépendamment des données d’entrées utilisées dans le moteur de recommandation). Les préférences de l’utilisateur servent à construire un modèle, lequel permet ensuite de proposer des produits qui sont proches de son profil. On construit une matrice des interactions entre l’utilisateur et le catalogue de produits. Cette matrice est incomplète, puisque tous les produits du catalogue n’ont pas d’interaction avec l’utilisateur. Notez qu’en l’absence d’historique concernant l’utilisateur (lorsque la matrice des interactions est vide ; ce cas est nommé cold start), on peut lui proposer les produits les plus populaires (éventuellement on peut tenir compte de son contexte connu, comme le pays d’où il se connecte, l’heure ou la saison et présenter les produits les plus vendus pour dans ce contexte particulier).

La seconde méthode, appelée “filtrage collaboratif”. Cette méthode assez ancienne a été mise au point en 1992 par quatre chercheurs du Xerox Palo Alto Research Center (PARC) , consiste à proposer les produits plébiscités par d’autres utilisateurs dont le profil est similaire. L’intérêt de cette approche est que les caractéristiques des produits ne sont pas utilisées pour effectuer la recommandation. C’est un point très important, qui donne à ce type de système un réel avantage sur un système basé sur le contenu. En effet, le système peut réaliser des recommandations sur des types de produits très différents.

Comparaison du filtrage basé sur le contenu et du filtrage collaboratif – Source
Illustration des deux types de filtrage collaboratif – Source

Il existe deux variantes à cette méthode, selon que l’on s’intéresse aux utilisateurs de “profil similaire” (user-based ou user-user) ou aux utilisateurs ayant recommandé des “contenus similaires” (item-based ou item-item). Cette méthode a plusieurs limites. Premièrement, pour bien fonctionner, elle nécessite une base de donnée importante. La seconde limite survient lors du cold start d’un nouvel utilisateur (ou d’un utilisateur non connecté), ou d’un nouveau produit. Dans ces cas, la méthode échoue car il ne lui est pas possible de trouver d’utilisateurs similaires (ou de recommandations d’utilisateurs associés à ce produit).

C’est pourquoi il est fréquent de trouver des systèmes hybrides dans les systèmes de recommandation déployés en ligne. Ces systèmes utilisent les deux types méthodes vues précédemment en tirant le meilleur de chacune. Plus généralement, il existe des centaines de systèmes de recommandation dérivés des deux types principaux, qu’il est d’usage de combiner entre eux avant de générer la liste des produits recommandés. Plusieurs techniques peuvent être utilisées pour combiner les méthodes entre elles , comme par exemple : la pondération (chaque méthode est pondérée dans le résultat final, selon son efficacité), le switching pour appliquer une méthode ou une autre selon les cas, le mixage des résultats de chaque méthode (la liste des produits recommandés comporte alors un assortiment des résultats de chaque méthode), en cascade (une méthode sert à affiner le classement de la méthode précédente), l’augmentation de caractéristiques (une méthode est préalablement utilisée pour générer les caractéristiques utilisées par la deuxième), ou enfin de type meta-level (la première méthode génère un modèle qui est ensuite utilisé comme donnée d’entrée par la seconde).

Principaux algorithmes de filtrage collaboratif

La première approche historique pour réaliser les recommandations de type « filtrage collaboratif »est la méthode des k-plus proches voisins. Elle consiste à prédire une la valeur d’un point en fonction de la distance qui la sépare de ses voisins. Soit un point x_q, la méthode consiste à choisir ses k plus proches voisins en considérant la moyenne des valeurs f des plus proches voisins :

\hat{f}(x_{q}) = \frac{\sum_{i=1}^{k}f(x_{i})}{k}

Le défaut de cette méthode est sa complexité en O(n^2) lors de la phase d’exécution pour réaliser les recommandations. Les limites de cette méthode sont rapidement atteintes, lorsque les bases contiennent plusieurs centaines de milliers d’éléments.
Pour résoudre ce problème, une solution proposée consiste à construire une représentation des données dans un espace réduit sous-jacent, lequel servira de modèle pour réaliser les prédictions dans cet espace réduit aux dimensions constantes. C’est une approche basée sur un modèle (« model-based »). On nomme cette méthode « Factorisation de Matrice », car elle consiste à décomposer la matrice des « interactions » (recommandations « utilisateurs -> produits »), en un produit de plusieurs matrices.

Les méthodes de type factorisation de matrices

Cette opération ressemble à l’opération mathématique de décomposition en valeurs singulières (SVD). Cette méthode ancienne, développée par Eugenio Beltrami en 1873, généralise la décomposition en vecteurs propres d’une matrice. Soit M la matrice de dimension m\times n contenant les interactions, on cherche une décomposition en un produit des matrices U de dimension m\times m, de la matrice diagonale rectangulaire \Sigma de dimension m\times n (dont les coefficients contiennent les valeurs singulières de M), et la transposée de V de dimension n\times n, alors la décomposition est définie ainsi :

M = U\cdot\Sigma\cdot V^\top


Cependant, dans le cas d’un système de recommandation de type filtrage collaboratif, les données sont fragmentées (les matrices sont dites « creuses » : pour chaque utilisateur, on ne dispose que de quelques interactions entre cet utilisateur et les produits du catalogue. La matrice « utilisateurs->produits » étant incomplète, les méthodes algébriques ne peuvent être utilisées en l’état pour réaliser la décomposition.

M_{m \times n} = \begin{pmatrix} i_0 & ? & ? & ? & ? & ? & ? & ? \\ 
? & ? & ? & ? & i_1 & ? & ? & ? \\ 
? & i_2 & ? & ? & ? & ? & ? & ? \\ 
? & ? & ? & ? & ? & ? & i_3 & ? \\ 
? & ? & i_4 & ? & ? & i_5 & ? & ? \\ 
? & ? & i_6& ? & ? & ? & ? & ? \\ 
? & ? & ? & ? & ? & ? & ? & i_7 \\ 
? & i_8 & i_9 & ? & ? & ? & ? & ? \\ 
? & ? & ? & ? & ? & ? & i_{10} & ? \end{pmatrix}

L’intuition qui a guidé les premiers systèmes de recommandation était d’effectuer préalablement une réduction de dimensionalité sur la matrice fragmentée des interactions, en réalisant une approximation de rang faible, afin d’obtenir une matrice de plus petite dimension, mais dense. L’idée étant de pouvoir ensuite réaliser une décomposition SVD.

Il existe des dizaines de méthodes de factorisation de matrices qui dérivent de la décomposition SVD. Nous en avons sélectionné quelques-unes dont nous allons faire une description détaillée.

Principe de la factorisation de matrice. Source

La méthode Funk SVD

Cette méthode constitue une avancée majeure dans les systèmes de recommandations. Elle est également nommée « approche des facteurs latents « . Elle consiste à extraire des caractéristiques à partir des interactions observées sous la forme de vecteurs. Elle a été présentée pour la première fois en 2007 par Simon Funk, un développeur indépendant candidat du concours Netflix. La communication a été réalisée par Simon Funk directement sur son blog.

Soit I le nombre d’utilisateurs, J le nombre de produits et K le nombre de facteurs latents. On notera dans le document avec un accent circonflexe les données prédites. Supposons que l’on souhaite réaliser une approximation de la matrice des interactions R, nommée \hat{R} sous la forme d’un produit de deux matrices U de dimension I \times K et V de dimension J \times K :

\hat{R} \approx U \cdot V^\top

Notez que à la différence de l’équation précédente la matrice diagonale \Sigma est absorbée dans la matrice des facteurs latents des utilisateurs.} Alors la prédiction d’un utilisateur concernant un produit pourra être exprimée sous la forme :

\hat{r}_{ij} = u_{i1}v_{j1} + u_{i2}v_{j2} \dots u_{ik}v_{jk}\\
\hat{r}_{ij} = \sum{k=1}^K u_{ik} v_{jk} = u^\top _i v_j

Soit u_i le facteur latent associé à l’utilisateur i, et v_j le facteur latent associé au produit j. On définit u_{ik} comme l’affinité d’un utilisateur i pour le concept k, ainsi que v_{jk} comme l’affinité d’un produit j avec le concept k.

Le principe de cette méthode est d’apprendre les valeurs des matrices de facteurs latents U et V en comparant les interactions réelles r_{ij} avec les valeurs prédites \hat{r}_{ij}.

Soit \mathfrak{R} l’ensemble des interactions. On définit l’erreur d’apprentissage d’une interaction e_{ij} = r_{ij} - \hat{r}{ij}, et l’erreur moyenne avec la fonction d’erreur quadratique J comme étant la moitié de la somme des carrés des déviations entre valeurs prédites et valeurs réelles. Il s’agit en réalité de la moitié de l’erreur quadratique au carré. On utilise cette astuce pour simplifier les calculs de dérivées qui vont suivre. Minimiser une fonction de perte ou la moitié du carré de cette fonction étant équivalent.

J = \frac{1}{2} \sum{(i,j) \in \mathfrak{R}} \left (e_{ij} \right )^2 = \frac{1}{2} \sum_{(i,j) \in \mathfrak{R}} \left ( r_{i,j} - \sum_{k=1}^K u_{ik} v_{jk} \right )^2

On va donc chercher les valeurs de U et V qui minimisent la fonction de perte. Pour minimiser la fonction de perte on applique une descente de gradient après avoir préalablement initialisé aléatoirement les poids des matrices U et V. La descente de gradient va consister à chaque étape à réaliser deux séries de dérivées partielles sur l’erreur \frac{1}{2} e_{i,j}^2, relativement à U et à V, afin de déterminer le gradient de de la fonction de perte au point (i,j) :

\frac{ \partial } {\partial u_{ik}} \frac{1}{2} e_{ij}^2 = \sum_{j:(i,j) \in \mathfrak{R}} \left ( r_{ij} - \sum_{s=1}^K u_{is} v_{js} \right ) \left (-v_{jk} \right ) \\
\frac{ \partial} { \partial v_{jk}} \frac{1}{2} e_{ij}^2 = \sum_{i:(ij) \in \mathfrak{R}} \left ( r_{ij} - \sum_{s=1}^K u_{is} v_{js} \right ) \left ( -u_{ik} \right )

Notons que même si la déscente de gradient est une méthode efficace, il existe d’autres méthodes d’optimisation qui peuvent être appliquées ici, telles que « Alternating Least Squares (ALS) » qui présente d’ailleurs plusieurs avantages dont le fait d’être plus stable puisque non dépendante de l’initialisation aléatoire des matrices U et V .

Le gradient nous indique la variabilité de la fonction d’erreur au voisinage du point (i,j). Il peut être négatif (l’erreur décroît), positif (l’erreur croît), ou nul (point d’inflexion). On modifie alors les poids des matrices U et V inversement à la valeur du gradient et dépendamment du taux d’apprentissage \alpha :

u_{ik}^{\prime} = u_{ik} + \alpha \cdot \sum_{j:(i,j) \in \mathfrak{R}} e_{ij} \cdot v_{jk} \\
v_{jk}^{\prime} = v_{jk} + \alpha \cdot \sum_{i:(i,j) \in \mathfrak{R}} e_{ij} \cdot u_{ik}

Nous pouvons également appliquer une descente stochastique de gradient dont le principe est d’appliquer à chaque étape, la fonction de perte sur une seule donnée d’entrée (choisie selon une distribution initiale aléatoire), afin d’améliorer la vitesse d’apprentissage. Dans ce cas le calcul des dérivées partielles par rapport à u et à v est simplifié :

\frac{ \partial} { \partial u_{ik}} \frac{1}{2} e_{ij}^2 = −e_{ij} \cdot v_{jk}\\
\frac{ \partial} { \partial v_{jk}} \frac{1}{2} e_{ij}^2 = −e_{ij} \cdot u_{ik}

Ce qui nous donne la fonction de mise à jour suivante :

u_{ik}^{\prime} = u_{ik} + \alpha \cdot e_{ij} \cdot v_{jk}\\
v_{jk}^{\prime} = v_{jk} + \alpha \cdot e_{ij} \cdot u_{ik}

Du fait de la fragmentation des données, il y a un risque important de “sur-interpréter” les données présentes. C’est pour cette raison qu’une régularisation de facteur \lambda est généralement ajoutée :

v_{jk}^{\prime} = v_{jk} + \alpha \cdot (e_{ij} \cdot u_{ik} - \lambda \cdot v_{jk})

Finalement nous obtenons deux matrices U et V qui permettent de prédire la valeur inconnue d’une interaction, quelque soit l’utilisateur et le produit. La prédiction de l’utilisateur i et le produit j s’exprime comme suit :

\hat{r}_{ij} \approx u_i^\top v_j

La méthode SVD++

La méthode Funk SVD a fait l’objet d’améliorations régulières depuis 10 ans. Une évolution notable introduit deux améliorations importantes. D’une part, elle intègre un biais b_{ij} dans le calcul de la prédiction :

\hat{r}_{ij} = b_{ij} + \sum_{k \in R(j)} (r_{ik} - b_{ik}) v_{jk}

Le biais b_{ij} sert à normaliser la valeur prédite en tenant compte de la déviation standard. Elle est calculée à partir de la moyenne des interactions \mu, de la déviation de l’utilisateur i par rapport aux autres utilisateurs b_i et de la déviation du produit par rapport aux autres produits b_j (biais de popularité):

b_{ij} = \mu + b_i + b_j

Les utilisateurs ont une façon très différentes d’attribuer une note à un produit, selon leur caractère et leur culture. Certaines populations notent plus sévèrement que d’autres. La même note ne représentera pas la même satisfaction chez un utilisateur généreux et optimiste que chez un utilisateur de profil plus râleur. Pour cette raison il est important d’intégrer un biais par utilisateur dans la phase d’apprentissage.

D’autre part, la méthode SVD++ permet de prendre en compte des données implicites dans le calcul des recommandations. On, définit une nouvelle matrice N telle que N(u) contient toutes les interactions implicites de l’utilisateur u. On modifie l’équation en pondérant la contribution des matrices R et N en fonction du nombre d’éléments \vert R(i) \vert et du nombre d’éléments \vert N(i)\vert :

\hat{r}_{ij} = b_{ij} + \vert R(i) \vert^{-\frac{1}{2}}\sum_{k \in R(i)} (r_{ik} - b_{ik})v_{jk} + \vert N(i)\vert^{-\frac{1}{2}}\sum_{k \in N(i)} c_{jk}

Les données explicites sont typiquement des « ratings » – c’est à dire des notes explicitement données – réalisés par les utilisateurs sur des produits, alors que les données implicites sont par exemple les produits consultés ou les produits achetés, pour lesquels on déduit implicitement que l’utilisateur les recommande.

Toutefois la méthode SVD++ reste une méthode qui ne permettra pas de traiter correctement un nouvel utilisateur. Non seulement à cause du problème du démarrage à froid (cold start), mais également parce que les facteurs latents sont déterminés pour les utilisateurs existants, mais sont inconnus pour un nouvel utilisateur. En l’état il faudrait « re-factoriser » les matrices pour tout nouvel utilisateur. Ce problème a contribué à l’émergence d’une nouvelle catégorie de systèmes de recommandation basés sur un modèle (model-based) dont la première implémentation est une déclinaison de SVD++ nommée SVD asymetrique.

La méthode SVD asymétrique

Cette méthode diffère de la précédente car elle n’utilise qu’une seule matrice de facteurs latents (la matrice V relative aux produits). La matrice U est remplacée par deux matrices construites uniquement à partir des interactions réelles de l’utilisateur (et non pas d’un modèle comme dans le cas d’une matrice de facteurs latents). Dans ce sens, la méthode est asymétrique, puisqu’elle s’exprime à la fois par une fonction liée au comportement de l’utilisateur basée sur une recherche des plus proches voisins, mais également par un modèle lié aux produits. Cette solution offre l’avantage de ne pas avoir à « réapprendre » le modèle lorsque de nouvelles interactions d’utilisateurs sont créées.

On construit préalablement une matrice intermédiaire normalisée F à partir de la matrice des interactions R.

Voici un exemple de matrice F construite à partir d’une matrice R :

R : \begin{pmatrix}
4 & ? & 2 & ? \\
? & 1 & 1 & 2 \\
4 & ? & ? & ? \\
? & 3 & ? & 1
\end{pmatrix} \Rightarrow F : \begin{pmatrix}
1/\sqrt{2} & 0 & 1/\sqrt{2} & 0 \\
0 & 1/\sqrt{3} & 1/\sqrt{3} & 1/\sqrt{3} \\
1/\sqrt{1} & 0 & 0 & 0 \\
0 & 1/\sqrt{2} & 0 & 1/\sqrt{2}
\end{pmatrix}


La matrice F de dimension m \times n est introduite dans la factorisation – multipliée par une matrice Y de dimension n \times k – pour remplacer la matrice U des facteurs latents d’utilisateurs. L’équation se réécrit alors :

\hat{R} \approx [F \cdot Y] \cdot V^\top

La phase d’apprentissage consistera à renseigner les matrices Y et V, en réalisant une descente stochastique de gradient, avec régularisation . Soit e_{ij} = r_{ij} - \hat{r_{ij}} l’erreur de prédiction et I_i les produits pour lesquels l’utilisateur i a effectué une recommandation explicite, la descente de gradient s’exprime formellement ainsi :

v_{jk}^{\prime} = v_{jk} + \alpha \left ( e_{ij} \cdot \left [\sum_{h \in I_i} \frac{y_{hk}}{\sqrt{\lvert I_i \rvert}} \right ] - \lambda \cdot v_{jk} \right ) \\y_{hk}^{\prime} = y_{hk} + \alpha \left ( \frac{e_{ij} \cdot v_{jk}}{\sqrt{\lvert I_i \rvert}} - \lambda \cdot y_{hk} \right )

La prédiction quant-à-elle est définie par l’équation suivante :

\hat{r}_{ij} = \mu + b_i + b_j + \sum_{k=1}^K \left ( u_{ik} + \sum \frac{y_{hk}}{\sqrt{\lvert I_i \rvert}}\right ) \cdot v_{jk}

La méthode Time-SVD++

Il s’agit là encore d’une amélioration de la méthode initiale Funk SVD. On cherche à tenir compte de la temporalité des données pour effectuer les recommandations. Assez logiquement nous étendons donc l’équation en ajoutant une nouvelle variable t.

La prédiction \hat{r}_{ij}(t) s’écrit :

 \hat{r}_{ij}(t) = \mu + b_i(t) + b_j(t) + \sum_{k=1}^K \left ( u_{ik}(t) + \sum \frac{y_{hk}}{\sqrt{\lvert I_i \rvert}}\right ) \cdot v_{jk}

Les fonctions b_i(t), b_j(t) et u_{ik}(t) remplacent les variables b_i, b_j et u_{ik}. Elles sont devenues des fonctions temporelles, qu’il faut définir judicieusement. Derrière le concept de temporalité dans un moteur de recommandation de produit se trouvent plusieurs idées. La première est que le comportement d’un utilisateur varie avec le temps (biais de notation optimiste/pessimiste b_i). De plus, ses centres d’intérêts d’hier ne sont pas toujours ses préférences d’aujourd’hui (u_{ik}). Les biais sur les produits évoluent aussi : les « produits phares » changent régulièrement (biais b_j).

L’ajout du paramètre de temps t dans la méthode SVD a pour conséquence l’augmentation de la dimension de la matrice des données et donc l’augmentation de la fragmentation des données. Ce problème s’inscrit dans ce qui est nommé « fléau de la dimensionalité » . Il est donc essentiel de disposer d’une base de donnée importante afin de prévenir au maximum les risques de sur-interprétation. Une matrice à n>2 dimensions se nomme un tenseur d’ordre n.

L’ajout d’une donnée contextuelle, dans le système de recommandation augmente la complexité des opérations de factorisation. Nous étudierons plus loin ce type de méthodes nommée factorisation de tenseurs.

La méthode Sparse Linear (SLIM)

Cette méthode consiste à réaliser une approximation de la matrice R des interactions implicites entre les utilisateurs et les produits, sous la forme d’une factorisation, dont la particularité est d’introduire une matrice W. La matrice W est une matrice creuse agrégée :

\hat{R} = RW

L’apprentissage de la matrice W consiste à réaliser une minimisation de la fonction suivante :

\frac{1}{2} \lVert R - RW \rVert^2_{Fro} + \frac{\beta}{2} \lVert W \rVert^2_{Fro} + \alpha \lVert W \rVert_1

Avec

\lVert W \rVert_1 = \sum_{i=1}^n\sum_{j=1}^n \vert w_{ij}\vert

Notons plusieurs évolutions de cette méthode :

  • Higher-Order Sparse LInear Method (HOSLIM) : elle introduit la notions d’achats combinés : il s’agit des produits qui sont régulièrement achetés ensemble, comme par exemple un téléphone est souvent accompagné d’une housse et d’une vitre de protection.
  • Contextual Sparse LInear Method (CSLIM) : Introduction du contexte dans la factorisation.

Factorisation probabiliste de matrice (PMF)

Nous avons vu jusqu’à présent des méthodes utilisant l’algèbre linéaire. Voici une approche différente, nommée Analyse sémantique latente probabiliste (PLSA) , qui s’appuie sur la théorie des probabilités.

L’idée est de considérer que les préférences des utilisateurs suivent une loi de probabilité. Nous pouvons exprimer la probabilité qu’un produit j soit interagi par un utilisateur i par rapport aux lois de probabilités de K facteurs latents (que nous pourrions considérer comme des caractéristiques latentes de produits).

P(j \vert i) = \sum_{k \in K} P(j \vert {k}) P(k \vert i)

Ici P(j \vert {k}) représente la probabilité qu’un produit j possède un facteur latent k. P(k \vert i) représente la probabilité qu’un facteur latent k soit interagi par un utilisateur i.

On peut donc exprimer la matrice R des interactions en fonction de deux facteurs latents U et V :

R = U . V^\top

Avec U représentant l’ensemble des K facteurs latents des utilisateurs, tel que 0 < k < K et pour tout utilisateur i, U_{ik} = P(k \vert i). De même, V correspondant à l’ensemble des K facteurs latents des produits, est construite de telle sorte que pour tout produit j, V_{jk} = P(j \vert k).

Deux modèles de PMF, avec et sans contraintes

En supposant que la distribution suit la loi normale, nommée \mathcal N, il est possible d’étendre le modèle pour réaliser des prédictions. La loi normale ou loi gaussienne est définie par l’équation suivante :

\mathcal N(x, \mu, \sigma^2) = \frac1{\sigma \sqrt{2\pi}}\operatorname e^{-\frac12\left(\frac{x-\mu}{\sigma}\right)^2}

\sigma représentant la variance des données et \mu représentant la moyenne des données.

Soit \hat{r_{ij}} l’interaction prédite entre l’utilisateur i et le produit j. On nomme U et V les facteurs latents des utilisateurs et des produits, et \sigma^2 la variance. La moyenne \mu_{ij} est déterminée par le produit vectoriel du facteur latent de l’utilisateur i par le facteur latent du produit j. La prédiction peut donc se calculer ainsi :

\hat{r_{ij}} \sim \mathcal N(R_{ij} \vert U_iV_j^\top, \sigma^2)

Nous pouvons généraliser la fonction sur la matrice R des interactions :

P(R \vert U,V,\sigma^2) = \prod_{i=0}^N \prod_{j=0}^M \left [ \mathcal N \left ( R_{ij} \vert U_iV_j^\top,\sigma^2 \right ) \right ]^{I^{ij}}

Avec I_{ij} = 1 si l’interaction (i,j) est observée, et I_{ij} = 0 sinon.

Décomposition HOSVD

Alors que dans les méthodes précédentes nous avons vu que la matrice des interactions pouvait s’exprimer sous la forme d’une factorisation de deux matrices U et V, nous allons introduire dans cette nouvelle section la notion de contexte. Nous introduisons une nouvelle matrice de données contextuelles que l’on nommera C.

Le contexte peut représenter diverses informations, telles que : la localisation géographique de l’utilisateur, les conditions météorologiques, à la saison, le jour de la semaine, la présence de mouvements sociaux ou d’évènements sportifs particuliers, ou les informations sociales de l’utilisateur … Ces données peuvent être disponibles dans le profil de l’utilisateur sur un réseau social et utilisées avec son accord. Les possibilités sont nombreuses. L’incidence du contexte dans le comportement des utilisateurs est très importante et un système de recommandation avancé devra intégrer des informations contextuelles.

La problématique de factorisation de matrices vu précédemment était une factorisation à 2 dimensions (on utilise le terme recommandation 2D). Chaque type de donnée contextuelle ajoutant une nouvelle dimension, on passe alors à une factorisation à n dimensions :

\hat{R} = U \cdot V \cdot C_1 \cdot \cdots \cdot C_n

Voici un exemple de nouvelle matrice R obtenue avec une dimension supplémentaire ajoutée (type de jour : jour de semaine, week-end, ou vacances) :

Modèle multi-dimensionnel de recommandation

Comme évoqué précédemment le problème de fragmentation des données est considérablement aggravé pour chaque nouvelle dimension ajoutée au système.

La figure ci-dessus illustre l’opération de factorisation d’un tenseur à 3 dimensions (en réalité le nombre de dimension est bien supérieur, mais de tels tenseurs ne peuvent pas être illustrés). On parle alors de HOSVD pour Higher Order Singular Value Decomposition. On remarquera que la décomposition est effectuée en 3 matrices nommées U, V et C, ainsi qu’un tenseur central nommé S. Les matrices représentent respectivement les facteurs latents des utilisateurs, des produits et des contextes.

La factorisation de tenseurs permet donc d’ajouter efficacement plusieurs dimensions contextuelles et son implémentation est relativement similaire à la factorisation de matrices vue précédemment. En ajoutant des données contextuelles elle surpasse en général les méthodes de recommandation 2D.

Pour détailler l’opération de décomposition HOSVD, nous nous appuyons sur la méthode décrite par .

Notation : on note T \times_M M le produit du tenseur T dans la direction de la matrice M.
T_1 \otimes T_2 est le produit tensoriel du tenseur T_1 avec le tenseur T_2.
M_{i:} est le vecteur contenant la ième ligne de la matrice M.
d_U, d_V et d_C représentent respectivement le nombre de facteurs latents par utilisateur, par produit, et par contexte.

Illustration d’une factorisation de tenseur à 3 dimensions.

Soit R le tenseur représentant l’ensemble des interactions contextualisées entre des utilisateurs et des produits. La recommandation \hat{r}_{ijc} correspondant à l’utilisateur i, pour le produit j, dans le contexte c peut se formuler selon la décomposition suivante :

\hat{r}_{ijc} = S \times_U U_{i:} \times_V V_{j:} \times_C C_{c:}

Soit J la fonction de perte définie par :

J = \frac{1}{2} \sum \left (\hat{r}_{ijc} - r_{ijc} \right )^2 = \sum \frac{1}{2} e^2_{ijc}

La dérivée partielle de \frac{1}{2} e^2_{ijc} par rapport à \hat{r}_{ijc} s’écrit :

 \frac{\partial}{\partial \hat{r}_{ijc}} \frac{1}{2} e^2_{ijc} = \hat{r}_{ijc} - r_{ijc}

Soit \frac{1}{2}e^2_{ijc} l’erreur au point (i,j,c). La descente stochastique du gradient est effectuée simultanément sur les facteurs U_{i:}, V_{j:}, C_{c:}, et le tenseur S :

\frac{\partial}{\partial U_{i:}} \frac{1}{2} e^2_{ijc} = (\hat{r}_{ijc} - r_{ijc}) \cdot S \times_V V_{j:} \times_C C_{c:}\\
\frac{\partial}{\partial V_{j:}} \frac{1}{2} e^2_{ijc} = (\hat{r}_{ijc} - r_{ijc}) \cdot S \times_U U_{i:} \times_C C_{c:}\\
\frac{\partial}{\partial C_{c:}} \frac{1}{2} e^2_{ijc} = (\hat{r}_{ijc} - r_{ijc}) \cdot S \times_U U_{i:} \times_C C_{j:}\\
\frac{\partial}{\partial S} \frac{1}{2} e^2_{ijc} = (\hat{r}_{ijc} - r_{ijc}) \cdot S \cdot U_{i:} \otimes V_{j:} \otimes C_{c:}

Compte tenu de la fragmentation des données, il est nécessaire d’appliquer une régularisation sur S, U, V et C. On note respectivement \lambda_S, \lambda_U, \lambda_V et \lambda_C leurs paramètres de régularisation. On utilise la norme L_2 (également appelée norme de Frobenius). Soit \alpha le taux d’apprentissage, on obtient la mise à jour suivante à chaque étape de la descente stochastique du gradient :

U_{i:}^\prime = U_{i:} - \alpha \lambda_U U_{i:} - \alpha \frac{\partial}{\partial U_{i:}} \frac{1}{2} e^2_{ijc}\\
V_{j:}^\prime = V_{j:} - \alpha \lambda_V V_{j:} - \alpha \frac{\partial}{\partial V_{j:}} \frac{1}{2} e^2_{ijc}\\
C_{c:}^\prime = C_{c:} - \alpha \lambda_C C_{c:} - \alpha \frac{\partial}{\partial C_{c:}} \frac{1}{2} e^2_{ijc}\\
S^\prime = S - \alpha \lambda_S S - \alpha \frac{\partial}{\partial S} \frac{1}{2} e^2_{ijc}

Références

Bellman, R. (1984). Dynamic programming. Princeton Univ. Pr.
Christakopoulou, E., & Karypis, G. (2014). HOSLIM: Higher-Order Sparse LInear Method for Top-N Recommender Systems. In V. S. Tseng, T. B. Ho, Z.-H. Zhou, A. L. P. Chen, & H.-Y. Kao (Eds.), Advances in Knowledge Discovery and Data Mining (Vol. 8444, pp. 38–49). Springer International Publishing. https://doi.org/10.1007/978-3-319-06605-9_4
Hofmann, T. (2013). Probabilistic Latent Semantic Analysis. ArXiv:1301.6705 [Cs, Stat]. http://arxiv.org/abs/1301.6705
Salakhutdinov, R., & Mnih, A. (2007). Probabilistic Matrix Factorization. Proceedings of the 20th International Conference on Neural Information Processing Systems, 1257–1264. http://dl.acm.org/citation.cfm?id=2981562.2981720
Yancheng Jia, Changhua Zhang, Qinghua Lu, & Peng Wang. (2014). Users’ brands preference based on SVD++ in recommender systems. 2014 IEEE Workshop on Advanced Research and Technology in Industry Applications (WARTIA), 1175–1178. https://doi.org/10.1109/WARTIA.2014.6976489
Cao, J., Hu, H., Luo, T., Wang, J., Huang, M., Wang, K., Wu, Z., & Zhang, X. (2015). Distributed Design and Implementation of SVD++ Algorithm for E-commerce Personalized Recommender System. In X. Zhang, Z. Wu, & X. Sha (Eds.), Embedded System Technology (Vol. 572, pp. 30–44). Springer Singapore. https://doi.org/10.1007/978-981-10-0421-6_4
Srebro, N., & Jaakkola, T. (2003). Weighted Low-rank Approximations. Proceedings of the Twentieth International Conference on International Conference on Machine Learning, 720–727. http://dl.acm.org/citation.cfm?id=3041838.3041929
Ning, X., & Karypis, G. (2011). SLIM: Sparse Linear Methods for Top-N Recommender Systems. 2011 IEEE 11th International Conference on Data Mining, 497–506. https://doi.org/10.1109/ICDM.2011.134
Karatzoglou, A., Amatriain, X., Baltrunas, L., & Oliver, N. (2010). Multiverse recommendation: n-dimensional tensor factorization for context-aware collaborative filtering. Proceedings of the Fourth ACM Conference on Recommender Systems - RecSys ’10, 79. https://doi.org/10.1145/1864708.1864727
Jain, P., Netrapalli, P., & Sanghavi, S. (2012). Low-rank Matrix Completion using Alternating Minimization. ArXiv:1212.0467 [Cs, Math, Stat]. http://arxiv.org/abs/1212.0467
Aggarwal, C. C. (2016). Recommender Systems. Springer International Publishing. https://doi.org/10.1007/978-3-319-29659-3
Robbins, H., & Monro, S. (1951). A stochastic approximation method. Annals of Mathematical Statistics, 22, 400–407.
Zheng, Y., Mobasher, B., & Burke, R. (2014). CSLIM: contextual SLIM recommendation algorithms. Proceedings of the 8th ACM Conference on Recommender Systems - RecSys ’14, 301–304. https://doi.org/10.1145/2645710.2645756
Del Buono, N., & Politi, T. (2005). A Continuous Weighted Low-Rank Approximation for Collaborative Filtering Problems. In S. Singh, M. Singh, C. Apte, & P. Perner (Eds.), Pattern Recognition and Data Mining (Vol. 3686, pp. 45–53). Springer Berlin Heidelberg. https://doi.org/10.1007/11551188_5
Burke, R. (2002). Hybrid Recommender Systems: Survey and Experiments. User Modeling and User-Adapted Interaction, 12(4), 331–370. https://doi.org/10.1023/A:1021240730564
Adomavicius, G., & Tuzhilin, A. (2008). Context-aware recommender systems. Proceedings of the 2008 ACM Conference on Recommender Systems - RecSys ’08, 335. https://doi.org/10.1145/1454008.1454068
Takács, G., Pilászy, I., Németh, B., & Tikk, D. (2007). Major components of the gravity recommendation system. ACM SIGKDD Explorations Newsletter, 9(2), 80. https://doi.org/10.1145/1345448.1345466
Koren, Y. (2008). Factorization meets the neighborhood: a multifaceted collaborative filtering model. Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD 08, 426. https://doi.org/10.1145/1401890.1401944
Hofmann, T. (2017). Probabilistic Latent Semantic Indexing. ACM SIGIR Forum, 51(2), 211–218. https://doi.org/10.1145/3130348.3130370
Goldberg, D., Nichols, D., Oki, B. M., & Terry, D. (1992). Using collaborative filtering to weave an information tapestry. Communications of the ACM, 35(12), 61–70. https://doi.org/10.1145/138859.138867
Hu, Y., Koren, Y., & Volinsky, C. (2008). Collaborative Filtering for Implicit Feedback Datasets. 2008 Eighth IEEE International Conference on Data Mining, 263–272. https://doi.org/10.1109/ICDM.2008.22
Schwartz, B. (2006). Le paradoxe du choix: comment la culture de l’abondance éloigne du bonheur. M. Lafon.
Sarwar, B., Karypis, G., Konstan, J., & Reidl, J. (2001). Item-based collaborative filtering recommendation algorithms. Proceedings of the Tenth International Conference on World Wide Web  - WWW ’01, 285–295. https://doi.org/10.1145/371920.372071