Je m'appelle Pavel Parkhomenko, je suis un développeur ML. Dans cet article, je voudrais parler de la structure du service Yandex.Zen et partager des améliorations techniques dont la mise en œuvre a permis d'augmenter la qualité des recommandations. À partir de cet article, vous apprendrez comment trouver les plus pertinents pour l'utilisateur parmi des millions de documents en quelques millisecondes seulement ; comment effectuer une décomposition continue d'une grande matrice (constituée de millions de colonnes et de dizaines de millions de lignes) afin que les nouveaux documents reçoivent leur vecteur en quelques dizaines de minutes ; comment réutiliser la décomposition matricielle utilisateur-article pour obtenir une bonne représentation vectorielle pour la vidéo.
Notre base de données de recommandations contient des millions de documents de formats variés : articles textuels créés sur notre plateforme et extraits de sites externes, vidéos, récits et articles courts. Le développement d’un tel service est associé à un grand nombre de défis techniques. En voici quelques uns:
- Divisez les tâches informatiques : effectuez toutes les opérations lourdes hors ligne et effectuez en temps réel uniquement une application rapide des modèles afin d'être responsable de 100 à 200 ms.
- Prenez rapidement en compte les actions des utilisateurs. Pour ce faire, il faut que tous les événements soient instantanément délivrés au recommandataire et influencent les résultats des modèles.
- Créez le flux de manière à ce que pour les nouveaux utilisateurs, il s'adapte rapidement à leur comportement. Les personnes qui viennent de rejoindre le système doivent sentir que leurs commentaires influencent les recommandations.
- Comprenez rapidement à qui recommander un nouvel article.
- Répondez rapidement à l’émergence constante de nouveaux contenus. Des dizaines de milliers d’articles sont publiés chaque jour, et nombre d’entre eux ont une durée de vie limitée (par exemple les actualités). C’est ce qui les distingue des films, de la musique et d’autres contenus de longue durée et coûteux à créer.
- Transférer les connaissances d’un domaine à un autre. Si un système de recommandation dispose de modèles formés pour les articles textuels et que nous y ajoutons de la vidéo, nous pouvons réutiliser les modèles existants afin que le nouveau type de contenu soit mieux classé.
Je vais vous dire comment nous avons résolu ces problèmes.
Sélection des candidats
Comment réduire de plusieurs milliers de fois le nombre de documents examinés en quelques millisecondes, sans pratiquement aucune dégradation de la qualité du classement ?
Supposons que nous ayons formé de nombreux modèles ML, généré des fonctionnalités basées sur eux et formé un autre modèle qui classe les documents pour l'utilisateur. Tout irait bien, mais vous ne pouvez pas simplement prendre et calculer tous les signes de tous les documents en temps réel, s'il existe des millions de ces documents, et les recommandations doivent être élaborées en 100 à 200 ms. La tâche consiste à sélectionner un certain sous-ensemble parmi des millions, qui sera classé pour l'utilisateur. Cette étape est généralement appelée sélection des candidats. Il y a plusieurs exigences pour cela. Premièrement, la sélection doit se faire très rapidement, afin de laisser le plus de temps possible au classement lui-même. Deuxièmement, après avoir considérablement réduit le nombre de documents à classer, nous devons préserver le plus complètement possible les documents pertinents pour l'utilisateur.
Notre principe de sélection des candidats a évolué et nous sommes actuellement parvenus à un schéma en plusieurs étapes :
Tout d’abord, tous les documents sont divisés en groupes et les documents les plus populaires sont extraits de chaque groupe. Les groupes peuvent être des sites, des sujets, des clusters. Pour chaque utilisateur, en fonction de son historique, les groupes les plus proches de lui sont sélectionnés et parmi eux sont extraits les meilleurs documents. Nous utilisons également l'index kNN pour sélectionner les documents les plus proches de l'utilisateur en temps réel. Il existe plusieurs méthodes pour construire un indice kNN ; la nôtre a mieux fonctionné (Graphiques hiérarchiques navigables du petit monde). Il s'agit d'un modèle hiérarchique qui permet de trouver les N vecteurs les plus proches pour un utilisateur à partir d'une base de données de plusieurs millions en quelques millisecondes. Nous indexons d’abord l’intégralité de notre base de données documentaires hors ligne. La recherche dans l'index étant assez rapide, s'il existe plusieurs intégrations fortes, vous pouvez créer plusieurs index (un index pour chaque intégration) et accéder à chacun d'eux en temps réel.
Nous disposons encore de dizaines de milliers de documents pour chaque utilisateur. C'est encore beaucoup pour compter toutes les fonctionnalités, donc à ce stade, nous utilisons le classement léger - un modèle de classement léger et lourd avec moins de fonctionnalités. La tâche consiste à prédire quels documents un modèle lourd aura en haut. Les documents ayant le prédicteur le plus élevé seront utilisés dans le modèle lourd, c'est-à-dire à la dernière étape du classement. Cette approche permet de réduire la base de données de documents considérée pour l'utilisateur de millions à des milliers en dizaines de millisecondes.
Étape ALS dans l'exécution
Comment prendre en compte les retours des utilisateurs immédiatement après un clic ?
Un facteur important dans les recommandations est le temps de réponse aux commentaires des utilisateurs. Ceci est particulièrement important pour les nouveaux utilisateurs : lorsqu'une personne commence tout juste à utiliser le système de recommandation, elle reçoit un flux non personnalisé de documents sur divers sujets. Dès qu'il effectue le premier clic, vous devez immédiatement en tenir compte et vous adapter à ses intérêts. Si vous calculez tous les facteurs hors ligne, une réponse rapide du système deviendra impossible en raison du retard. Il est donc nécessaire de traiter les actions des utilisateurs en temps réel. À ces fins, nous utilisons l'étape ALS au moment de l'exécution pour créer une représentation vectorielle de l'utilisateur.
Supposons que nous disposions d'une représentation vectorielle pour tous les documents. Par exemple, nous pouvons créer des intégrations hors ligne basées sur le texte d'un article en utilisant ELMo, BERT ou d'autres modèles d'apprentissage automatique. Comment obtenir une représentation vectorielle des utilisateurs dans un même espace en fonction de leurs interactions dans le système ?
Principe général de formation et de décomposition de la matrice utilisateur-documentAyons m utilisateurs et n documents. Pour certains utilisateurs, leur relation avec certains documents est connue. Ces informations peuvent ensuite être représentées sous forme d'une matrice mxn : les lignes correspondent aux utilisateurs et les colonnes correspondent aux documents. Puisque la personne n’a pas vu la plupart des documents, la plupart des cellules de la matrice resteront vides tandis que d’autres seront remplies. Pour chaque événement (j'aime, je n'aime pas, clic), une valeur est fournie dans la matrice - mais considérons un modèle simplifié dans lequel un j'aime correspond à 1 et une aversion correspond à -1.
Décomposons la matrice en deux : P (mxd) et Q (dxn), où d est la dimension de la représentation vectorielle (généralement un petit nombre). Ensuite, chaque objet correspondra à un vecteur de dimension D (pour un utilisateur - une ligne dans la matrice P, pour un document - une colonne dans la matrice Q). Ces vecteurs seront les plongements des objets correspondants. Pour prédire si un utilisateur aimera un document, vous pouvez simplement multiplier ses intégrations.
L'une des manières possibles de décomposer une matrice est l'ALS (Alternating Least Squares). Nous allons optimiser la fonction de perte suivante :
Ici rui est l'interaction de l'utilisateur u avec le document i, qi est le vecteur du document i, pu est le vecteur de l'utilisateur u.
Ensuite, le vecteur utilisateur optimal du point de vue de l'erreur quadratique moyenne (pour les vecteurs de documents fixes) est trouvé analytiquement en résolvant la régression linéaire correspondante.
C’est ce qu’on appelle « l’étape ALS ». Et l'algorithme ALS lui-même consiste à corriger alternativement l'une des matrices (utilisateurs et articles) et à mettre à jour l'autre, trouvant la solution optimale.
Heureusement, trouver la représentation vectorielle de l'utilisateur est une opération assez rapide qui peut être effectuée au moment de l'exécution à l'aide d'instructions vectorielles. Cette astuce permet de prendre immédiatement en compte les retours des utilisateurs dans le classement. La même intégration peut être utilisée dans l'index kNN pour améliorer la sélection des candidats.
Filtrage collaboratif distribué
Comment effectuer une factorisation matricielle distribuée incrémentale et trouver rapidement des représentations vectorielles de nouveaux articles ?
Le contenu n’est pas la seule source de signaux de recommandation. Une autre source importante est l’information collaborative. De bonnes caractéristiques de classement peuvent traditionnellement être obtenues à partir de la décomposition de la matrice utilisateur-document. Mais en essayant de faire une telle décomposition, nous avons rencontré des problèmes :
1. Nous avons des millions de documents et des dizaines de millions d’utilisateurs. La matrice ne tient pas entièrement sur une seule machine et la décomposition prendra très longtemps.
2. La plupart des contenus du système ont une durée de vie courte : les documents ne restent pertinents que quelques heures. Il est donc nécessaire de construire leur représentation vectorielle le plus rapidement possible.
3. Si vous construisez une décomposition immédiatement après la publication du document, un nombre suffisant d'utilisateurs n'aura pas le temps de l'évaluer. Par conséquent, sa représentation vectorielle ne sera probablement pas très bonne.
4. Si un utilisateur aime ou n'aime pas, nous ne pourrons pas en tenir compte immédiatement dans la décomposition.
Pour résoudre ces problèmes, nous avons implémenté une décomposition distribuée de la matrice utilisateur-document avec des mises à jour incrémentielles fréquentes. Comment ça marche exactement?
Supposons que nous ayons un cluster de N machines (N se compte par centaines) et que nous souhaitions effectuer une décomposition distribuée d'une matrice sur celles-ci qui ne tient pas sur une seule machine. La question est de savoir comment réaliser cette décomposition pour que, d'une part, il y ait suffisamment de données sur chaque machine et, d'autre part, pour que les calculs soient indépendants ?
Nous utiliserons l'algorithme de décomposition ALS décrit ci-dessus. Voyons comment exécuter une étape ALS de manière distribuée - le reste des étapes sera similaire. Disons que nous avons une matrice fixe de documents et que nous voulons construire une matrice d'utilisateurs. Pour ce faire, nous allons le diviser en N parties par lignes, chaque partie contiendra approximativement le même nombre de lignes. Nous enverrons à chaque machine les cellules non vides des lignes correspondantes, ainsi que la matrice des incorporations de documents (dans leur intégralité). Étant donné que sa taille n'est pas très grande et que la matrice du document utilisateur est généralement très clairsemée, ces données tiendront sur une machine ordinaire.
Cette astuce peut être répétée sur plusieurs époques jusqu'à ce que le modèle converge, en alternant les matrices fixes une à une. Mais même dans ce cas, la décomposition matricielle peut prendre plusieurs heures. Et cela ne résout pas le problème selon lequel vous devez recevoir rapidement les intégrations de nouveaux documents et mettre à jour les intégrations de ceux sur lesquels il y avait peu d'informations lors de la construction du modèle.
L'introduction de mises à jour incrémentielles rapides des modèles nous a aidés. Disons que nous avons un modèle actuellement formé. Depuis sa formation, il y a eu de nouveaux articles avec lesquels nos utilisateurs ont interagi, ainsi que des articles qui ont eu peu d'interaction pendant la formation. Pour obtenir rapidement les plongements de tels articles, nous utilisons les plongements utilisateur obtenus lors du premier grand entraînement du modèle et effectuons une étape ALS pour calculer la matrice du document à partir d'une matrice utilisateur fixe. Cela vous permet de recevoir des intégrations assez rapidement - quelques minutes après la publication du document - et de mettre souvent à jour les intégrations de documents récents.
Pour que les recommandations prennent immédiatement en compte les actions humaines, nous n'utilisons pas lors de l'exécution les intégrations d'utilisateurs obtenues hors ligne. Au lieu de cela, nous effectuons une étape ALS et obtenons le vecteur utilisateur réel.
Transfert vers une autre zone de domaine
Comment utiliser les retours des utilisateurs sur des articles texte pour construire une représentation vectorielle d'une vidéo ?
Au départ, nous recommandions uniquement des articles textuels, c'est pourquoi nombre de nos algorithmes sont adaptés à ce type de contenu. Mais lors de l’ajout d’autres types de contenus, nous avons été confrontés à la nécessité d’adapter les modèles. Comment avons-nous résolu ce problème à l’aide d’un exemple vidéo ? Une option consiste à recycler tous les modèles à partir de zéro. Mais cela prend beaucoup de temps, et certains algorithmes sont exigeants sur la taille de l'échantillon de formation, qui n'est pas encore disponible en quantité requise pour un nouveau type de contenu dans les premiers instants de sa vie sur le service.
Nous sommes allés dans l'autre sens et avons réutilisé les modèles de texte pour la vidéo. La même astuce ALS nous a aidés à créer des représentations vectorielles de vidéos. Nous avons pris une représentation vectorielle des utilisateurs basée sur des articles textuels et effectué une étape ALS en utilisant les informations de visualisation vidéo. Nous avons donc facilement obtenu une représentation vectorielle de la vidéo. Et au moment de l'exécution, nous calculons simplement la proximité entre le vecteur utilisateur obtenu à partir des articles texte et le vecteur vidéo.
Conclusion
Développer le cœur d’un système de recommandation en temps réel implique de nombreux défis. Vous devez traiter rapidement les données et appliquer des méthodes de ML pour utiliser efficacement ces données ; construire des systèmes distribués complexes capables de traiter les signaux des utilisateurs et de nouvelles unités de contenu en un minimum de temps ; et bien d'autres tâches.
Dans le système actuel, dont j'ai décrit la conception, la qualité des recommandations adressées à l'utilisateur augmente avec son activité et sa durée de séjour sur le service. Mais bien sûr, c’est là que réside la principale difficulté : il est difficile pour le système de comprendre immédiatement les intérêts d’une personne qui a peu d’interaction avec le contenu. Améliorer les recommandations pour les nouveaux utilisateurs est notre objectif principal. Nous continuerons à optimiser les algorithmes afin que le contenu pertinent pour une personne pénètre plus rapidement dans son flux et que le contenu non pertinent ne soit pas affiché.
Source: habr.com