De l'heuristique à l'apprentissage automatique: suggestions de recherche dans Citymobil

salut! Je m'appelle Mikhail Dyachkov et chez Citymobil je fais du machine learning. Aujourd'hui, je vais vous parler de notre nouvel algorithme pour générer des suggestions de recherche pour les destinations finales. Vous apprendrez comment une tâche apparemment simple s'est transformée en un scénario intéressant, avec l'aide duquel, nous l'espérons, nous avons réussi à rendre la vie des utilisateurs un peu plus facile. Nous continuons à suivre de près le travail du nouvel algorithme et le peaufinerons par la suite afin de maintenir la qualité du classement à un niveau élevé. Pour tous les utilisateurs, nous lancerons l'algorithme dans les prochaines semaines, mais nous sommes déjà prêts à parler du long voyage que nous avons parcouru de l'heuristique à l'algorithme d'apprentissage automatique et à son déploiement.



Je pense qu'il vaut la peine de commencer par décrire la vision du monde idéale d'un scénario de commande de taxi du point de vue de l'interface utilisateur. J'aimerais que notre application comprenne où / où / quand / par quelle voiture l'utilisateur souhaite quitter. Dans cet article, nous examinerons notre solution pour répondre à la question «où».



L'un des éléments centraux du premier écran (celui que l'utilisateur voit après la connexion) est les suggestions de recherche. Dans l'équipe de recherche géographique, nous les appelons "sajests" (de la suggestion anglaise). Ils offrent à l'utilisateur les adresses de route finales (points «B») à partir de son historique de voyage en fonction de l'emplacement actuel de la broche (c'est-à-dire le point de chute) et de l'heure sans entrer une requête de recherche. Nous essayons d'aider l'utilisateur à passer une commande "en un clic" à l'aide de sagests. Dans la version actuelle de l'application cliente iOS, les sajests ressemblent à ceci: la recherche géographique







, en raison des algorithmes de génération des résultats de recherche, peut affecter l'une des métriques produit les plus importantes pour l'application cliente, comme le temps passé à commander un taxi ( Time to order , ou T2O ), ainsi que le nombre d'actions que le client a prises pour former une commande ( Actions à commander , ou A2O). Par conséquent, nous avons décidé de développer un algorithme qui permettra de prédire les points finaux les plus probables de l'itinéraire (points «B») pour un endroit et une heure donnés.

Heuristique

L'un des développeurs backend de l'équipe de recherche géographique (Vasilesk, bonjour!) est venu avec une heuristique assez simple pour générer des sajests qui fonctionnait à la fois pour le point de départ "A" et le point final "B". Il faut tout de suite noter que l'heuristique ne fonctionnait pas sur l'historique de voyage de l' utilisateur, mais sur l'historique des clics sur les résultats de recherche, ce qui posait quelques problèmes. Ces objets que nous appelons "pics" (de l'anglais. Le médiator ). L'heuristique ressemblait à ceci:

1. Pour l'utilisateur actuel, nous prenons tous ses sommets historiques.
2. Nous les filtrons, laissant ceux avec la même cible (de / d'où).
3. , , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
4. , , , , , .
5. , , 3:00 14:00, , .
6. - (), , - .
7. .

Cet algorithme a fonctionné pendant un certain temps et était généralement bon pour les MVP (nous parlerons des métriques un peu plus tard), mais il présentait un certain nombre d'inconvénients. En plus de la logique plutôt primitive du travail, il ne reposait pas sur les déplacements, mais sur les choix de l'utilisateur. Pour cette raison, les utilisateurs obtiennent parfois des résultats de recherche non évidents. Et aussi, en raison de la manière «spécifique» de stocker l'historique des pics, il était assez difficile d'effectuer des analyses rapides. Sur cette base, nous avons décidé d'essayer d'appliquer l'apprentissage automatique. Ensuite, nous examinerons la formulation des problèmes de classement et réduirons notre problème à une classification binaire.

Énoncé du problème de classement

Avant de parler de fonctionnalités, de métriques et d'un modèle, nous devons déterminer le type de problème que nous essayons de résoudre. Allons-y de manière itérative et essayons d'abord de formuler une formulation générale du problème de classement. Cela ressemble à ceci:



$$$X$ - beaucoup d'objets.



$$$X^l = \{x_1, \dots, x_l \}$ - échantillon de formation. 



$$$i \prec j$ - ordre correct par paires $$$(i, j)$



Objectif: construire une fonction de classement $$$a: X \rightarrow ℝ$, avec lequel 

$$

$$i \prec j ⇒  a(x_i) < a(x_j)$$

Formulons maintenant la tâche de classement des résultats de recherche par requête. Il diffère du problème de classement général en ce qu'au lieu de l'ensemble général des objets que nous devons trier, deux ensembles apparaissent$$$D$ et $$$Q$ - de nombreux documents et demandes de renseignements.



$$$D$ - collecte de documents (réponses).



$$$Q$ - beaucoup de demandes.



$$$D_q \subseteq D$ - l'ensemble des documents trouvés par la requête q.



$$$X = Q \times D$ - les objets sont des paires "demande, document": $$$x \equiv (q, d), q \in Q, d \in D_q$



$$$Y$ - un ensemble ordonné de cotes (cotes).



$$$y(q, d): X \rightarrow Y$- scores de pertinence.



Plus le score est élevé$$$y(q, d)$, plus le document est pertinent $$$d$ demande $$$q$...



L'ordre correct est défini uniquement entre les documents trouvés par la même requête$$$q$: 

$$

$$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$$

Dans notre tâche de recommander des points de terminaison d'itinéraire, l'ensemble des évaluations est binaire. Pour l'utilisateur, l'adresse suggérée peut être pertinente ou non (à l'exclusion des cas avec une route complexe avec plusieurs points d'extrémité). Si nous considérons la tâche dans le contexte de l'utilisateur, alors$$$q$- une demande au service, qui contient l' identifiant du client, la géolocalisation, la date et l'heure;$$$D_q$- de nombreux points de terminaison historiques "B" pour les voyages de l'utilisateur (nous ne faisons que des suggestions basées sur les adresses des voyages passés). Et chaque réponse valable$$$d \in D_q$ sur demande $$$q$ peut être soit pertinent pour l'utilisateur (à partir du point actuel et à l'heure actuelle, l'utilisateur doit se rendre exactement ici) ou non pertinent.



Par souci d'exhaustivité, il ne reste plus qu'à décrire le processus de création d'un échantillon de paires demande-réponse avec une cible. Considérez, pour simplifier, un client qui a effectué 5 voyages. Classons ces voyages du tout premier au dernier. Pour le premier voyage, nous ne savons rien des voyages de l'utilisateur, nous ne pouvons donc pas lui proposer un sagest en utilisant l'algorithme d'apprentissage automatique décrit (l'heuristique pour les nouveaux utilisateurs fonctionne ici). Pour le deuxième voyage, nous connaissons la destination finale dès le premier voyage et nous pouvons proposer cette adresse à l'utilisateur s'il réussit la procédure de post-traitement (situé à plus de 1 km de l'emplacement actuel, dans la même région, etc.). Pour le troisième voyage, nous pouvons déjà avoir un à deux sadgets possibles,si l'adresse de fin du deuxième voyage était la même que l'adresse de fin du premier et si les adresses de fin étaient différentes, respectivement. Si le sajest coïncidait avec le point final "B" (c'est-à-dire qu'il tombait dans le même hexagone de taille fixe), alors nous définissons 1 comme cible, sinon - 0. Selon cet algorithme, nous formons toutes sortes de paires de la forme "demande - réponse (possible) "Pour chaque client.



Ainsi, nous avons réduit le problème de classement à un problème de classification binaire. Nous pouvons maintenant parler de mesures d'évaluation de la qualité.

Métrique

Dans le classement des problèmes, une métrique qui montre la proportion de réponses correctes à partir de documents $$$D_q$ jusqu'au sommet $$$n$ liste de classement sur demande $$$q$sont appelés Precision @ n . Nous sommes intéressés par Precision @ 1/2/3 , car le taux de clics total pour les trois premières positions est d'environ 95%. En même temps, il n'y a qu'une seule adresse finale correcte (naturellement, si l'utilisateur veut partir pour une adresse de son historique), par conséquent, cette métrique affichera simplement la proportion de cas où le point final correct "B" tombe dans les 1/2/3 premières adresses qui a suggéré notre algorithme.



Rappelez-vous que dans notre problème$$$Y = \{0, 1\},\; y(q, d)$ - pertinence, $$$a(q, d)$Est la fonction de classement requise. Alors Precision @ n peut s'écrire:

$$

$$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$$

Signes et modèle

Les fonctionnalités du modèle dans notre problème peuvent être divisées en plusieurs blocs:

• Pour document uniquement $$$d \in D_q$ (adresse finale, point "B").
• Sur demande uniquement $$$q$ (adresse de départ, point "A").
• Commun à demander et documenter $$$(q, d)$ (itinéraire de "A" à "B").
• Général pour l'utilisateur.

Voici quelques exemples pour chacun d'eux.



Exemples de signes uniquement pour le document (point "B"):

1. Nombre de voyages au point "B" au cours des K derniers jours.
2. Nombre de trajets jusqu'au point "B" par jour de la semaine et heure de la journée.
3. Quand était le voyage précédent au point «B».
4. Indiquez que le voyage précédent a été effectué au point "B".
5. Le point «B» est-il une adresse / domicile / travail choisi.

Exemples de caractéristiques sur demande uniquement $$$q$ ( «» + /):

1. , .
2. «».
3. «» K .
4. «» .
5. «» //.
6. / $$$q$.
7. «».

, $$$(q, d)$ ( «» “”):

1. , .
2. .
3. .

:

1. K .
2. .
3. Statistiques historiques des déplacements (moyenne, quantiles, distance médiane du trajet, etc.).

En conséquence, nous avons plus de 100 fonctionnalités qui décrivent une paire d'objets "demande-document". Puisque nous voulons maximiser la précision @ 1/2/3 , il est logique que nous devions prédire la probabilité de déplacement d'un utilisateur vers une destination spécifique et classer les candidats possibles en fonction de la probabilité obtenue. Nous avons essayé différents algorithmes et différentes fonctions de perte, et avons opté pour le renforcement du gradient sur les arbres et la perte de log . Les résultats obtenus au moment de l'utilisation de l'heuristique:

Production

Naturellement, avant de proposer des algorithmes, des fonctionnalités et des modèles d'entraînement complexes, vous devez réfléchir à la manière dont tout cela fonctionnera en combat sous charge, sans oublier la mise à l'échelle. Après nous être réunis avec l'équipe de développement backend, nous avons esquissé un aperçu de l'apparence de notre service. Nous avons décidé d'encapsuler le modèle d'apprentissage automatique entraîné dans le cadre Web en attente d'asynchronisation Sanic, auquel le service de recherche enverra des requêtes. En plus de la mise à l'échelle verticale, nous avons implémenté la possibilité de déployer sur plusieurs machines. Les demandes adressées au service seront envoyées à l'URL de l'équilibreur de charge, puis un proxy vers telle ou telle machine à l'aide de l'algorithme Round-robin se produira. Après avoir implémenté le premier prototype du service, nous avons réalisé que nous pouvions réduire considérablement le volume de requêtes dans MySQL. Puisque tout décalage de la broche avec le choix du point d'alimentation est une nouvelle demande de recherche, et donc à notre service, nous avons pensé pouvoir stocker un cache avec l'historique de voyage de l'utilisateur pendant N minutes à partir du moment de la demande à Redis. Grâce à cela, nous avons réduit la charge sur la base trois fois. En conséquence, le schéma de service peut être représenté comme suit:







Nous stockons les demandes au service et ses réponses dans ElasticSearch, et nous transférons et surveillons les métriques responsables de la stabilité du travail dans NewRelic.



Le workflow général de notre service:

1. Le service de recherche envoie une demande au service d'indices de recherche.
2. L'équilibreur sélectionne l'une des machines et lui envoie cette requête.
3. À l'intérieur de la machine, la demande est envoyée à l'un des travailleurs ouverts ou entre dans la file d'attente.
4. À l'intérieur du travailleur:
   1. Nous validons la demande entrante.
   2. Nous faisons une demande dans Redis, s'il n'y a pas d'historique des commandes pour l'utilisateur, alors nous allons à MySQL et écrivons les données reçues dans Redis.
   3. Nous effectuons un prétraitement des données de base et collectons des fonctionnalités pour le modèle.
   4. Nous le faisons en predict_proba()fonction de tous les sajests générés et les trions par "probabilité".
   5. Nous effectuons un post-traitement supplémentaire des données et formons la réponse.
   6. Nous renvoyons la réponse au service de recherche.

Et après?

Maintenant, nous testons activement notre modèle en utilisant des tests de commutation afin de tirer des conclusions et de mettre en œuvre des modules complémentaires supplémentaires à l'algorithme pour améliorer la qualité du classement. À l'avenir, nous essaierons d'ajouter des fonctionnalités supplémentaires au modèle et, en collaboration avec les concepteurs de produits, préparerons une nouvelle solution pour «l'affichage» des creux. Bien sûr, ce serait formidable si notre application elle-même comprenait où / quand / où / par quelle voiture l'utilisateur veut quitter. Nous travaillons dans tous les sens pour qu'une commande de taxi soit réellement effectuée en un clic.