Comment prédisons-nous l'avenir de la recherche Yandex: des corrections de bugs aux requêtes de découverte

Les gens ne formulent pas toujours leurs requêtes avec précision, les moteurs de recherche devraient donc les y aider. Mon nom est Sergey Yudin, je dirige un groupe d'analyse des fonctionnalités de recherche dans Yandex. Chaque jour, nous améliorons quelque chose grâce à l'apprentissage automatique. L'année dernière, nous avons développé une technologie qui prévoit les intérêts humains.

Avec un expert de mon équipe Anastasia GaidashenkoavgaydashenkoJe vais expliquer aux lecteurs de Habr comment fonctionne cette technologie, je décrirai l'architecture et les algorithmes appliqués. Vous apprendrez également en quoi la prédiction de la prochaine demande diffère de la prédiction des futurs intérêts humains.

Que veut l'utilisateur?

Voyons comment les technologies Yandex aident à résoudre des problèmes, en utilisant l'exemple d'un utilisateur imaginaire. Supposons qu'il imprime «enregistrer le ticket» dans la zone de recherche. Que veut-il trouver? Pour en savoir plus sur l'accumulation de billets, ou avait-il simplement tort?



Oui, il a été scellé. Il ne veut pas économiser, mais acheter un billet. Yandex l'a compris, le tuteur l'a aidé dans cela - un système qui corrige les demandes mal saisies . Mathématiquement, ce système maximise la probabilité d'une requête correctement saisie, à condition que l'utilisateur ait saisi le texte. Ce problème est résolu dans Yandex depuis plus de dix ans. Et pas seulement dans la recherche.

Ainsi, notre utilisateur imaginaire a saisi la demande «acheter un billet». À ce stade, un sjest entre en jeu .(ou suggestions de recherche). Sajest aide l'utilisateur à formuler la demande, à la compléter correctement.



Notre sajest a parcouru un long chemin. Il y a quelques années, nous avons compliqué la tâche. Je voulais montrer non seulement l'achèvement le plus logique de la demande, mais aussi prédire quelle demande cet utilisateur entrerait à la fin et démarrer sa prérendante avant le clic. Si vous souhaitez savoir comment cela fonctionne, vous pouvez consulter Habré .

Notre utilisateur imaginaire sélectionne la fin de la demande parmi une série de conseils: il s'avère qu'il cherchait des billets pour la galerie Tretiakov. Ainsi, le système de recommandation a terminé sa première tâche - il a aidé l'utilisateur à formuler une demande .

Cette tâche est terminée, mais l'utilisateur a encore des questions. Que cherchera-t-il ensuite? Peut-être qu'il veut savoir comment se rendre à la galerie? Oui, il imprime Lavrushinsky par 10 pour vérifier l'adresse.



Pouvons-nous prévoir cette demande? Oui. Et nous faisons cela depuis un certain temps. Il existe un tel bloc - «Également demandé» à la fin du numéro. Il montre les requêtes que les gens demandent généralement après avoir entré dans le champ de recherche. C'est en elle que nous verrons notre demande avec l'adresse de la galerie Tretiakov.



Nous maximisons la probabilité d'une demande soumise à une précédente demande de l'utilisateur. Le système a terminé la deuxième tâche - a prédit la prochaine demande .

Et puis quelque chose de très intéressant se produit. L'utilisateur imprime la demande «quand puis-je visiter la galerie Tretiakov gratuitement». Cette demande est différente des autres, va à l'encontre de la tâche utilisateur, résout une tâche orthogonale.



Mais réfléchissons: si nous cherchions des billets pour la galerie, que souhaiterions-nous voir comme recommandation? Un grand nombre de personnes aimeraient savoir qu'il n'est peut-être pas nécessaire d'acheter un billet. Il s'agit de la troisième partie de la tâche, la plus difficile et la plus intéressante - recommander quelque chose de nouveau et d'utile à l'utilisateur. Quelque chose à laquelle il n'avait pas encore pensé.

Nous appelons ces demandes découverte. Nous apprenons à les identifier dans nos journaux de recherche, à les enregistrer et à les recommander à la fin du problème. Et c'est précisément la tâche nouvelle et révolutionnaire sur laquelle nous travaillons activement actuellement. À une personne qui achète des bâtons scandinaves, Yandex peut recommander une demande sur la façon de les ramasser en hauteur. Si une personne voyage souvent, alors elle sera peut-être intéressée par la requête de recherche "où aller sans visa". Etc.



La formulation mathématique du problème dans ce cas ressemblera à ceci: nous ne maximisons pas la probabilité de la prochaine demande, mais la probabilité d'un clic sur la demande, que nous recommandons à l'utilisateur en fonction de sa session précédente.

Comment ça fonctionne?

Voyons comment notre système de recommandations est mis en œuvre, quelle architecture se cache derrière. Mais pour commencer, nous déterminerons ce que nous voulons généralement obtenir du système de recommandation.

1. Recommandations utiles! Bien sûr, nous voulons que les demandes que nous recommandons à l'utilisateur correspondent à ses intérêts. Ils doivent être utiles et pertinents.

2. Évolutivité. Nous espérons que le système sera bon: il y aura de plus en plus d'utilisateurs et le nombre de demandes augmentera. Et nous voulons augmenter la couverture de ceux sur lesquels nous pouvons faire des recommandations.

3. Facilité de mise en œuvre.Nous supposons que notre système fonctionnera toujours et nous ne voulons pas le réécrire plusieurs fois. Le système devrait être facile à mettre en œuvre, afin que nous puissions l'améliorer plus tard, non pas en lançant une nouvelle version, mais en améliorant la version actuelle.

Après avoir décidé de nos souhaits, voyons comment vous pouvez leur donner vie.

Nous avons une base de données de découverte - une base de données de requêtes qui peuvent sembler intéressantes et utiles à nos utilisateurs. Mais si nous commençons à classer toute cette base, nous n'aurons pas assez de puissance de calcul. Les utilisateurs ont de nombreuses demandes, ils sont divers, donc nous devons d'abord filtrer cette base de données.



Le filtrage peut être effectué par différentes méthodes. Dans Yandex, nous utilisons kNN (k-voisins les plus proches) pour cela- L'algorithme de classification de base en apprentissage automatique, appelé «recherche du plus proche voisin». En utilisant cet algorithme, nous voulons filtrer la base de données: sélectionnez les requêtes les plus proches de ce qui peut intéresser l'utilisateur. Pour ce faire, nous voulons comparer la demande de l'utilisateur et les demandes que nous sommes prêts à recommander dans l'espace vectoriel.

Mais pour rassembler ces demandes dans un espace vectoriel, nous devons également trouver quelque chose. Par exemple, vous pouvez utiliser DSSM (Deep Structured Semantic Model) - une sorte de boîte noire qui peut traduire différentes entités dans un espace vectoriel. Initialement, cette approche a été proposée dans un article de Microsoft. Mais Yandex l'a déjà assez fortement adapté à ses tâches et est loin de l'idée originale. Si vous êtes intéressé à en savoir plus à ce sujet, alors les informations peuvent être trouvées, par exemple, dans l'article sur l'algorithme de recherche Palekh .



La prochaine étape est le classement. Lorsque nous avons une liste de demandes proches de ce qui pourrait intéresser l'utilisateur, nous voulons comprendre ce qui sera le plus intéressant pour lui et ce qui le sera moins.

Par exemple, nous avons sélectionné 100 requêtes. Il est peu probable que l'utilisateur fasse défiler les 100. Vous devez sélectionner le top 5 et le recommander. Pour ce faire, nous attribuons des notes à nos demandes. Nous obtenons ces estimations en fonction de la probabilité d'un clic sur une demande que nous recommandons à l'utilisateur en fonction de sa session précédente.

Comment obtient-on la probabilité du prochain clic? Notre système est déjà opérationnel, nous collectons donc simplement les commentaires des utilisateurs - et améliorons ainsi progressivement notre système de recommandations.



Maintenant que nous avons passé en revue toutes les étapes séparément, revenons au début et mettons tout cela ensemble. Total: l'utilisateur vient à nous avec une demande, et nous avons une sorte de base de recommandations. Nous prenons cette base de données et la filtrons, recevant les demandes que nous voulons organiser et recommander à l'utilisateur.



Rappelons maintenant que nous avons généralement formulé des souhaits pour notre système de recommandations. Et voyons comment nous pouvons les implémenter dans l'architecture résultante.

Par exemple, nous voulions une évolutivité en termes d'amélioration de la base. Notre méthode d'implémentation possède toutes les propriétés nécessaires à une telle mise à l'échelle. Nous ne devons pas garder la base entière en mémoire: dès que la base se dilate tellement qu'elle ne tient pas sur un cluster, nous pouvons la diviser en deux. Et si auparavant nous avons parcouru un cluster avec kNN et sélectionné les 100 premiers, que nous classerons, maintenant nous pouvons parcourir deux clusters séparément et sélectionner, par exemple, les 50 premiers de chacun. Ou, en général, décomposez les clusters par thèmes et marchez avec kNN uniquement sur les thèmes souhaités.

Pour augmenter le nombre d'utilisateurs, vous pouvez simplement ajouter une puissance de calcul supplémentaire et traiter chacun séparément, car dans notre architecture, il n'y a pas d'endroits où nous devrions garder tous les utilisateurs en mémoire en même temps.

Dans certaines autres approches, il existe des endroits qui filtrent, par exemple, lors de la décomposition d'une matrice. La décomposition matricielle est une autre approche utilisée dans les recommandations. En fait, Yandex l'utilise également, mais pas pour le filtrage, mais comme fonctionnalités supplémentaires pour la formation, car il y a encore beaucoup d'informations utiles à analyser.

Des fonctionnalités supplémentaires, de nouveaux algorithmes et d'autres méthodes peuvent être appliqués au reste de l'architecture. Lorsque le système est opérationnel, nous pouvons commencer à l'améliorer.

Où ça marche?

Une telle architecture a déjà été mise en œuvre dans Yandex, et en comparaison avec les reformulations habituelles, lorsque nous avons essayé de conseiller à l'utilisateur de connaître l'adresse de la galerie Tretyakov, nous pouvons déjà vous conseiller comment vous rendre à la galerie Tretyakov sans attendre en ligne ou même gratuitement.



Il s'agit d'un nouveau niveau d'interaction entre le moteur de recherche et les utilisateurs. Nous ne corrigeons pas seulement les erreurs et complétons les demandes, mais apprenons à prédire les intérêts d'une personne et à lui offrir quelque chose de nouveau. Ce sera peut-être la recherche de l'avenir. Qu'est-ce que tu penses?