Anatomie des systèmes de recommandation. Première partie

Je travaille en tant que data scientist chez CleverDATA . Nous sommes engagés dans des projets d'apprentissage automatique, et l'une des demandes les plus fréquentes pour le développement de solutions marketing basées sur l'apprentissage automatique est le développement de modèles de recommandation.

Dans cet article, je vais parler des systèmes de recommandation, essayer de donner l'aperçu le plus complet des approches existantes et expliquer du doigt le fonctionnement des algorithmes. Une partie du matériel est basée sur un bon cours sur les systèmes de recommandation du laboratoire MovieLens (que la plupart des gens connaissent avec le même ensemble de données pour tester les recommandations), le reste est issu d'une expérience personnelle. L'article se compose de deux parties. Le premier décrit l'énoncé du problème et donne un aperçu des algorithmes de recommandation simples (mais populaires). Dans le deuxième article, je parlerai de méthodes plus avancées et de certains aspects pratiques de la mise en œuvre.

Source

Examen et énoncé du problème

La tâche du système de recommandation est d'informer l'utilisateur d'un produit qui pourrait le plus l'intéresser à un moment donné. Le client reçoit des informations et le service gagne de l'argent sur la prestation de services de qualité. Les services ne sont pas nécessairement des ventes directes des biens proposés. Le service peut également gagner sur des commissions ou simplement augmenter la fidélité des utilisateurs, ce qui se traduit ensuite par des revenus publicitaires et autres.

Selon le modèle commercial, les recommandations peuvent être sa base, comme, par exemple, avec TripAdvisor, ou peuvent être juste un service supplémentaire pratique (comme, par exemple, dans certains magasins de vêtements en ligne), conçu pour améliorer l'expérience client et rendre la navigation dans le catalogue plus confortable.

La personnalisation du marketing en ligne est une tendance évidente de la dernière décennie. Selon McKinsey , 35% des revenus d'Amazon ou 75% des revenus de Netflix proviennent des produits recommandés, et ce pourcentage devrait augmenter. Les systèmes de référence sont ce qu'il faut offrir au client pour le rendre heureux.

Pour illustrer toute la variété des services de recommandation, je vais donner une liste des principales caractéristiques avec lesquelles vous pouvez décrire tout système de recommandation.

1. Objet de la recommandation - ce qui est recommandé.
   
   Il y a beaucoup de variété ici - il peut s'agir de marchandises (Amazon, Ozon), d'articles (Arxiv.org), d'actualités (Surfingbird, Yandex.Zen), d'images (500px), de vidéos (YouTube, Netflix), de personnes (Linkedin, LonelyPlanet), de musique (Last.fm, Pandora), listes de lecture, etc. En général, vous pouvez recommander n'importe quoi.
   
2. Le but de la recommandation est pourquoi elle est recommandée.
   
   Par exemple: acheter, informer, former, nouer des contacts.
   
3. Le contexte de la recommandation est ce que l'utilisateur fait en ce moment.
   
   Par exemple: regarder des marchandises, écouter de la musique, parler avec les gens.
   
4. La source de la recommandation est qui recommande:
   
   - audience (note moyenne des restaurants sur TripAdvisor),
   - Utilisateurs intéressés
   - communauté d'experts (parfois lorsqu'il s'agit d'un produit complexe, comme par exemple le vin).
   
5. Le degré de personnalisation .
   
   Recommandations non personnelles - lorsque vous êtes recommandé comme tout le monde. Ils permettent un ciblage par région ou par heure, mais ne prennent pas en compte vos préférences personnelles.
   
   Une option plus avancée est lorsque les recommandations utilisent les données de votre session actuelle. Vous avez regardé plusieurs produits, et au bas de la page on vous propose des produits similaires.
   
   Les recommandations personnelles utilisent toutes les informations disponibles sur le client, y compris l'historique de ses achats.
   
6. La transparence
   
   Les gens font davantage confiance à la recommandation s'ils comprennent exactement comment elle a été reçue. Il y a donc moins de risques de se heurter à des systèmes "sans scrupules" qui promeuvent des biens payés ou placent des biens plus chers plus haut dans le classement. En outre, un bon système de recommandation lui-même devrait être en mesure de gérer les avis achetés et les tricheurs des ventes.
   
   Soit dit en passant, les manipulations ne sont pas non plus intentionnelles. Par exemple, lorsqu'un nouveau blockbuster est publié, la première chose que les fans y font est, en conséquence, la note peut être considérablement surestimée pendant les deux premiers mois.
   
7. Le format de la recommandation .
   
   Cela peut être une fenêtre pop-up, une liste triée apparaissant dans une section spécifique du site, un ruban en bas de l'écran ou autre chose.
   
8. Des algorithmes
   
   Malgré les nombreux algorithmes existants, ils se résument tous à plusieurs approches de base, qui seront décrites plus loin. Les plus classiques sont les algorithmes basés sur le résumé (non personnel), basés sur le contenu (modèles basés sur la description du produit), le filtrage collaboratif (filtrage collaboratif), la factorisation matricielle (méthodes basées sur la décomposition matricielle) et quelques autres.
   

Source

La matrice dite de préférence est au centre de tout système de recommandation. Il s'agit d'une matrice, sur un axe dont tous les clients du service (Utilisateurs) sont mis de côté, et sur l'autre, les objets de la recommandation (Items). À l'intersection de certaines paires (utilisateur, article), cette matrice est remplie de notes (notes) - il s'agit d'un indicateur connu de l'intérêt de l'utilisateur pour ce produit, exprimé sur une échelle donnée (par exemple, de 1 à 5).


Les utilisateurs n'évaluent généralement qu'une petite partie des produits figurant dans le catalogue, et la tâche du système de recommandation est de résumer ces informations et de prédire l'attitude du client vis-à-vis d'autres produits dont on ne sait rien. En d'autres termes, vous devez remplir toutes les cellules vides de l'image ci-dessus.

Les modes de consommation des gens sont différents et il n'est pas nécessaire de recommander de nouveaux produits. Vous pouvez afficher des positions répétées, par exemple, pour reconstituer le stock. Selon ce principe, deux groupes de produits sont distingués.

• Répétable . Par exemple, des shampooings ou des rasoirs qui sont toujours nécessaires.
  
• Unique . Par exemple, des livres ou des films qui sont rarement ré-acquis.
  

Si le produit ne peut pas être explicitement attribué à l'une des classes, il est logique de déterminer l'admissibilité des achats répétés individuellement (quelqu'un va au magasin uniquement pour un beurre d'arachide d'une certaine marque, et pour quelqu'un, il est important d'essayer tout ce qui est dans le catalogue).

Le concept d '"intérêt" est également subjectif. Certains utilisateurs n'ont besoin que de choses de leur catégorie préférée (recommandations prudentes), tandis que quelqu'un, au contraire, est plus sensible aux produits ou groupes de produits non standard (recommandations risquées). Par exemple, l'hébergement vidéo ne peut recommander à l'utilisateur que de nouveaux épisodes de sa série préférée, et peut périodiquement lui lancer de nouveaux spectacles ou même de nouveaux genres. Idéalement, vous devez choisir une stratégie pour afficher séparément les recommandations pour chaque client, en utilisant la modélisation d'une catégorie de clients.

Les évaluations des utilisateurs peuvent être obtenues de deux manières:

• notes explicites - l'utilisateur met la note du produit, laisse un avis, aime la page,
  
• évaluations implicites - l'utilisateur n'exprime pas explicitement son attitude, mais une conclusion indirecte peut être tirée de ses actions: il a acheté le produit - cela signifie qu'il l'aime, lit la description depuis longtemps - cela signifie qu'il y a de l'intérêt, etc.
  

Bien sûr, les préférences explicites sont meilleures - l'utilisateur lui-même dit qu'il l'aimait. Cependant, dans la pratique, tous les sites n'offrent pas la possibilité d'exprimer explicitement leur intérêt, et tous les utilisateurs ne le souhaitent pas. Les deux types de notation sont le plus souvent utilisés en même temps et se complètent bien.

Il est également important de distinguer les termes Prédiction (prédire le degré d'intérêt) et la Recommandation elle-même (montrant la recommandation). Ce qu'il faut montrer et comment le montrer est une tâche distincte qui utilise les estimations obtenues à l'étape de prédiction, mais peut être implémentée de différentes manières.

Parfois, le terme «recommandation» est utilisé dans un sens plus large et fait référence à toute optimisation, qu'il s'agisse d'une sélection de clients pour le publipostage, de la détermination du prix d'offre optimal ou simplement du choix de la meilleure stratégie de communication avec le client. Dans l'article, je me limite à la définition classique de ce terme, dénotant le choix du produit le plus intéressant pour le client.

Recommandations non personnalisées

Commençons par des recommandations non personnalisées, car elles sont les plus faciles à mettre en œuvre. En eux, l'intérêt potentiel de l'utilisateur est simplement déterminé par la note moyenne du produit: "Tout le monde l'aime, alors vous l'aimerez." La plupart des services fonctionnent sur ce principe lorsque l'utilisateur n'est pas connecté au système, par exemple le même TripAdvisor.

Les recommandations peuvent être affichées de différentes manières - comme une bannière sur le côté de la description du produit (Amazon), à la suite d'une demande triée par un paramètre spécifique (TripAdvisor), ou d'une autre manière.

Les évaluations de produits peuvent également être affichées de différentes manières. Cela peut être des étoiles à côté du produit, le nombre de likes, la différence entre les votes positifs et négatifs (comme cela se fait généralement sur les forums), la proportion de notes élevées ou même un histogramme de notes. Les histogrammes sont le moyen le plus informatif, mais ils ont un inconvénient - ils sont difficiles à comparer les uns aux autres ou à trier lorsque vous devez répertorier des produits.

Problème de démarrage à froid

Un démarrage à froid est une situation typique où suffisamment de données n'ont pas encore été accumulées pour que le système de recommandation fonctionne correctement (par exemple, lorsqu'un produit est nouveau ou acheté rarement). Si la note moyenne est calculée par les estimations de seulement trois utilisateurs (igor92, xyz_111 et oleg_s), une telle évaluation ne sera clairement pas fiable, et les utilisateurs le comprennent. Souvent, dans de telles situations, les notes sont ajustées artificiellement.

La première consiste à afficher non pas la valeur moyenne, mais la moyenne lissée (Damped Mean). La signification est la suivante: avec un petit nombre de notes, la note affichée est plus encline à une sorte d'indicateur "moyen" sûr, et dès qu'un nombre suffisant de nouvelles notes est rassemblé, l'ajustement "moyen" cesse de fonctionner.

Une autre approche consiste à calculer les intervalles de confiance pour chaque note. Mathématiquement, plus il y a d'estimations, moins il y a de variation de la moyenne et, par conséquent, plus de confiance dans son exactitude. Et en tant que note, vous pouvez afficher, par exemple, la limite inférieure de l'intervalle (Low CI Bound). Dans le même temps, il est clair qu'un tel système sera assez conservateur, avec une tendance à sous-estimer les notes des nouveaux produits (à moins, bien sûr, que ce soit un succès).

Étant donné que les estimations sont limitées à une certaine échelle (par exemple, de 0 à 1), la manière habituelle de calculer l'intervalle de confiance est mal applicable ici: en raison des queues de distribution qui vont à l'infini et de la symétrie de l'intervalle lui-même. Il existe une manière alternative et plus précise de le calculer - Wilson Confidence Interval . Dans ce cas, des intervalles asymétriques approximativement de ce type sont obtenus.


Dans l'image ci-dessus, la note horizontale de la note moyenne est tracée, et la verticale est l'écart autour de la moyenne. La couleur indique différentes tailles d'échantillon (évidemment, plus l'échantillon est grand, plus l'intervalle de confiance est petit).

Le problème du démarrage à froid est tout aussi pertinent pour les recommandations non personnalisées. L'approche générale ici consiste à remplacer ce qui ne peut pas être compté pour le moment par diverses heuristiques (par exemple, remplacer par une note moyenne, utiliser un algorithme plus simple ou ne pas utiliser de produit du tout jusqu'à ce que les données soient collectées).

Pertinence des recommandations

Dans certains cas, il est également important de considérer la «fraîcheur» de la recommandation. Cela est particulièrement vrai pour les articles ou les messages du forum. Les nouvelles entrées devraient souvent atteindre le sommet. Pour ce faire, utilisez des facteurs d'amortissement. Vous trouverez ci-dessous quelques formules pour calculer le classement des articles sur les sites de médias.

Exemple de calcul de notation dans le magazine Hacker News:

où U = votes positifs, D = votes négatifs et P (pénalité) - ajustement supplémentaire pour la mise en œuvre d'autres règles commerciales

Calcul des notes dans Reddit:

où U = nombre de votes pour, D = nombre de votes contre, T = moment de l'enregistrement. Le premier terme estime la «qualité d'enregistrement» et le second fait une correction pour le temps.

De toute évidence, il n'existe pas de formule universelle et chaque service invente la formule qui résout le mieux son problème - elle est vérifiée empiriquement.

Recommandations basées sur le contenu

Les recommandations personnelles suggèrent l'utilisation maximale des informations sur l'utilisateur lui-même, principalement sur ses achats précédents. L'une des premières était l'approche de filtrage basée sur le contenu. Dans le cadre de cette approche, la description du produit (contenu) est comparée aux intérêts de l'utilisateur obtenus à partir de ses précédentes notations. Plus le produit répond à ces intérêts, plus l'intérêt potentiel de l'utilisateur est évalué. L'exigence évidente ici est que tous les produits du catalogue doivent avoir une description.

Historiquement, le sujet des recommandations basées sur le contenu a souvent été des biens avec une description non structurée: films, livres, articles. Ces signes peuvent être, par exemple, des descriptions textuelles, des critiques, des castings et plus encore. Cependant, rien n'empêche l'utilisation de signes numériques ou catégoriels ordinaires.

Les caractéristiques non structurées sont décrites de manière typique pour les vecteurs de texte dans l'espace des mots ( modèle vectoriel-espace ). Chaque élément d'un tel vecteur est une caractéristique qui caractérise potentiellement l'intérêt de l'utilisateur. De même, un produit est un vecteur dans le même espace.

Lorsque l'utilisateur interagit avec le système (par exemple, il achète des films), les descriptions vectorielles des biens qu'il achète sont combinées (résumées et normalisées) en un seul vecteur et, ainsi, un vecteur de ses intérêts est formé. De plus, il suffit de trouver un produit dont la description est la plus proche du vecteur d'intérêt, c'est-à-dire résoudre le problème de trouver n voisins les plus proches.

Tous les éléments ne sont pas également significatifs: par exemple, les mots alliés, évidemment, ne portent aucune charge utile. Par conséquent, lors de la détermination du nombre d'éléments correspondants dans deux vecteurs, toutes les mesures doivent d'abord être pesées par leur signification. Cette tâche est résolue par la transformation TF-IDF , bien connue dans Text Mining , qui attribue plus de poids à des intérêts plus rares. La coïncidence de ces intérêts est plus importante pour déterminer la proximité de deux vecteurs que la coïncidence des vecteurs populaires.


Le principe TF-IDF s'applique ici également aux attributs nominaux ordinaires, tels que, par exemple, genre, réalisateur, langue. TF - une mesure de l'importance de l'attribut pour l'utilisateur, IDF - une mesure de la "rareté" de l'attribut.

Il existe toute une famille de transformations similaires (par exemple, BM25 et similaires), mais en substance, elles répètent toutes la même logique que TF-IDF: les attributs rares devraient avoir plus de poids lors de la comparaison des produits. L'image ci-dessous montre comment le poids du TF-IDF dépend du TF et de l'IDF. L'axe horizontal le plus proche est DF: fréquence d'attribut parmi tous les produits, l'axe horizontal le plus éloigné est TF: logarithme de fréquence d'attribut de l'utilisateur.


Quelques points qui peuvent être pris en compte lors de la mise en œuvre.

• Lorsque vous formez une présentation de produits dans un espace vectoriel, au lieu de mots individuels, vous pouvez utiliser des bardeaux ou des n-grammes (paires de mots consécutifs, triplets, etc.). Cela rendra le modèle plus détaillé, mais davantage de données seront nécessaires pour la formation.
  
• À différents endroits de la description du produit, le poids des mots clés peut différer (par exemple, une description de film peut consister en un titre, une brève description et une description détaillée).
  
• Les descriptions de produits de différents utilisateurs peuvent être pondérées différemment. Par exemple, nous pouvons donner plus de poids aux utilisateurs actifs qui ont de nombreuses notes.
  
• De même, vous pouvez peser et produire. Plus la note moyenne d'un objet est élevée, plus son poids est important (similaire au PageRank ).
  
• Si la description du produit autorise des liens vers des sources externes, vous pouvez être confus et analyser également toutes les informations tierces liées au produit.
  

On peut voir que le filtrage basé sur le contenu répète presque complètement le mécanisme de correspondance requête-document utilisé dans les moteurs de recherche tels que Yandex et Google. La seule différence est sous la forme d'une requête de recherche - ici c'est un vecteur décrivant les intérêts de l'utilisateur, et il y a les mots-clés du document demandé. Lorsque les moteurs de recherche ont commencé à ajouter la personnalisation, la distinction s'est encore effacée.

Pour mesurer la proximité de deux vecteurs, la distance cosinus est le plus souvent utilisée.


Lorsqu'une nouvelle évaluation est ajoutée, le vecteur d'intérêts est mis à jour progressivement (uniquement pour les éléments qui ont changé). Lors du recomptage, il est logique de donner un peu plus de poids aux nouvelles estimations, car les préférences peuvent varier.

Filtrage collaboratif (option basée sur l'utilisateur)

Cette classe de systèmes a commencé à se développer activement dans les années 90. Dans le cadre de l'approche, des recommandations sont générées en fonction des intérêts d'autres utilisateurs similaires. Ces recommandations sont le résultat d'une «collaboration» de nombreux utilisateurs. D'où le nom de la méthode.

L'implémentation classique de l'algorithme est basée sur le principe de k voisins les plus proches. Sur les doigts - pour chaque utilisateur, nous recherchons k le plus similaire à lui (en termes de préférences) et complétons les informations sur l'utilisateur avec des données connues sur ses voisins. Donc, par exemple, si vous savez que vos voisins intéressés sont ravis du film "Blood and Concrete", et que vous ne l'avez pas regardé pour une raison quelconque, c'est une excellente occasion de vous offrir ce film pour une projection samedi.


L'image ci-dessus illustre le principe de la méthode. Dans la matrice des préférences, l'utilisateur est surligné en jaune pour lequel nous voulons déterminer les notes des nouveaux produits (points d'interrogation). Trois de ses voisins les plus proches sont surlignés en bleu.

La «similitude» est dans ce cas synonyme de «corrélation» des intérêts et peut être considérée de plusieurs façons (en plus de la corrélation de Pearson, il y a aussi une distance cosinus, il y a une distance Jacquard, une distance Hamming, etc.).

La mise en œuvre classique de l'algorithme a un inconvénient évident - il est mal applicable dans la pratique en raison de la complexité quadratique. , , ( ). , $$$O(n^2m)$, n — , m — . , 4TB.

. , :

• , (, ),
  
• , ,
  
• ( ALS).
  

, .

• ( , ).
  
• , .
  
  , , . , (, ). , , — .
  

( ), , -. , , n ( ).

MovieLens 30-50 25-100 . , , , , , .

— .

(scaling)

- – - , - – , .. , .

, (, , ).

:

• (mean-centering) — ,
  
  *
  
• (z-score) — ,
  
  * (.. , 6 ), .
  
• — , — .
  
  « » 2.5, 5, , , .
  

«» . . .

1. — , .
   
   
   
   
   — , .
   
   50 / min(50, Rating intersection) damping factor, .
   
2. 
   
   — , .. , . .
   
   
   
3. 
   
   . , — , .
   
   
   
   — , (.. ), . , .
   

— Trust-based recommendations, , «» . , , . .

, , . ( . explanation).

, (, ) , (confidence). , «Tell me more».

Par exemple:

• « … … ...».
• « … 4.5 5».

Résumé

Cela mettra fin à la première partie de l'article. Nous avons examiné l'énoncé général du problème, parlé de recommandations non personnelles, décrit deux approches classiques (filtrage basé sur le contenu et collaboratif), et abordé également le sujet de la justification des recommandations. En général, ces deux approches sont suffisantes pour construire un système de recommandation prêt pour la production. Dans la partie suivante, je poursuivrai l'examen et parlerai de méthodes plus modernes, y compris celles impliquant les réseaux de neurones et l'apprentissage en profondeur, ainsi que des modèles hybrides.