Comment Yandex.Taxi prédit le temps de livraison des voitures à l'aide de l'apprentissage automatique

Imaginez que vous deviez appeler un taxi. Vous ouvrez l'application, vous voyez que la voiture arrivera dans environ sept minutes, cliquez sur "Commander" - et ... la voiture est à 15 minutes de vous, le cas échéant. D'accord, désagréable?

Sous la coupe, nous parlerons de la façon dont les méthodes d'apprentissage automatique aident Yandex.Taxi à mieux prédire l'ETA (heure d'arrivée estimée - heure d'arrivée prévue).



Rappelons tout d'abord que l'utilisateur voit dans l'application avant de commander:



Sur la carte, le bleu indique les points optimaux pour monter à bord d'un taxi. Pin rouge - le point auquel l'utilisateur appelle un taxi. L'épingle affiche la durée de la voiture. Dans un monde parfait. Mais dans le monde réel, d'autres personnes à proximité s'appellent également une voiture via l'application Yandex.Taxi. Et nous ne savons pas quelle voiture ira à qui, car ils ne sont distribués qu'après commande. Si la voiture a déjà été affectée, pour les prévisions, nous utiliserons le routage et le temps Yandex.Maps lors du déplacement sur le chemin optimal. Cette fois (éventuellement avec une petite marge), nous montrerons à l'utilisateur immédiatement après la commande. La question demeure: comment prédire l'ETA avant de commander?

Et ici, l'apprentissage automatique apparaît. Nous faisons une sélection avec les objets et les bonnes réponses et apprenons à l'algorithme à deviner la réponse en fonction des caractéristiques de l'objet. Dans notre cas, les objets sont des sessions utilisateurs, les réponses sont le temps après lequel la voiture est effectivement arrivée. Les signes de l'objet peuvent être des paramètres numériques connus avant la commande: le nombre de conducteurs et d'utilisateurs de l'application à côté de la broche, la distance aux véhicules de service les plus proches et d'autres valeurs potentiellement utiles.

Pourquoi est-ce important

Dans un monde idéal, les gens font tout à l'avance et planifient toujours leur temps avec précision. Mais nous vivons dans le monde réel. Si une personne est en retard au travail ou, pire, à l'aéroport, il est important pour elle de comprendre si elle sera à temps pour partir et se rendre à destination.
Lorsqu'il décide quoi commander, le futur passager est guidé, entre autres, par le temps d'attente. Cela peut être très différent dans différentes applications pour appeler un taxi et dans différents tarifs d'une même application. Pour que l'utilisateur ne regrette pas le choix, il est très important de montrer l'ETA exact.

Tout semble simple. Trouvez plus de panneaux, entraînez un modèle, comme CatBoost, prédisez le temps avant l'arrivée de la voiture - et vous pouvez vous arrêter là. Mais l'expérience montre qu'il vaut mieux ne pas se précipiter et réfléchir soigneusement, puis le faire.

Dans un premier temps, nous ne doutions pas qu'il fût nécessaire de prévoir le temps dans lequel le conducteur arriverait réellement à l'utilisateur. Oui, nous ne savons pas avec certitude quelle voiture sera attribuée avant la commande. Mais nous pouvons prédire l'ETA en utilisant des données non pas sur un pilote spécifique, mais sur les pilotes à proximité de la commande. Bien entendu, la prévision doit être suffisamment honnête pour que l'utilisateur puisse planifier l'heure.

Mais que signifie «honnête»? Après tout, tout algorithme de prévision est mauvais ou seulement statistiquement bon. Il y a à la fois des résultats réussis et franchement mauvais, mais vous devez "faire la moyenne" pour ne pas dévier de manière significative des bonnes réponses. Il faut comprendre que "en moyenne" est différent. Par exemple, la moyenne est d'au moins trois concepts statistiques: attente, médiane et mode. L'image du magnifique livre de Darrell Huff «Comment mentir en utilisant les statistiques» montre parfaitement la différence:



Nous voulons que le modèle fasse en moyenne peu d'erreurs. Selon la valeur de la «moyenne», il existe deux options pour évaluer la qualité des prévisions. La première option consiste à montrer à l'utilisateur l'attente mathématique du temps avant l'arrivée du taxi. En conséquence, un modèle sera formé qui minimise le carré moyen de l'erreur de prévision (Mean Squared Error, MSE):

$$

$$MSE = \ frac {1} {n} \ sum_ {i = 1} ^ {n} (y_i - \ hat {y} _i) ^ 2 \ rightarrow min$$

Ici $$$y_i$ - bonnes réponses, $$$\ chapeau {y} _i$ - prévisions de modèles.

Une autre option ne doit pas être confondue avec les prévisions ETA principalement dans une direction, vers le haut ou vers le bas. Dans ce cas, nous montrerons à l'utilisateur la médiane de la répartition du temps avant l'arrivée du taxi. En conséquence, un modèle sera formé qui optimise le module moyen de l'erreur de prévision (Mean Absolute Error, MAE):

$$

$$MAE = \ frac {1} {n} \ sum_ {i = 1} ^ {n} | y_i - \ hat {y} _i | \ rightarrow min$$

Mais nous avons réalisé que nous prenions un peu d'avance sur nous-mêmes.

Repenser l'énoncé du problème

Après le rendez-vous, nous savons quel type de voiture va à l'utilisateur, ce qui signifie que nous pouvons estimer son temps de trajet sur Yandex.Maps. Cette heure est indiquée dans la broche après la commande. D'une part, nous avons maintenant plus d'informations et les prévisions seront plus précises, mais, d'autre part, il s'agit également d'une estimation avec une erreur.

C'était le hic dans la tâche de broche ETA. Bien que le conducteur ne soit pas affecté, il est nécessaire de prévoir exactement l'heure à laquelle le routage Yandex.Mart s'affichera, et non l'heure réelle avant la livraison de la voiture.

Il semblerait, quelle absurdité: au lieu de la valeur exacte, prendre une autre prévision comme objectif? Mais cela a du sens, et voici pourquoi. Sur le chemin de vous, la voiture désignée peut persister. Le conducteur s'est retrouvé dans une situation dangereuse sur la route, dans un embouteillage dû à un accident ou est sorti pour acheter de l'eau. De tels retards sont difficiles à prévoir. Ils créent un bruit supplémentaire dans la variable cible, en raison de quoi la tâche déjà difficile de prédire l'ETA dans la broche devient encore plus difficile.

Comment se débarrasser du bruit? Prédisez la variable cible lissée - le temps qui s'affiche après l'attribution de la machine en fonction de l'itinéraire vers l'utilisateur.

Telle est la logique du point de vue des entreprises: vous ne pouvez de toute façon pas passer le temps sur la route le long du chemin optimal depuis ETA, mais les retards supplémentaires peuvent être réduits en travaillant avec les conducteurs.

Métriques, données, modèle et formation de qualité

Nous avons découvert que pour ETA dans la broche, il est nécessaire de prédire non pas l'heure réelle, mais l'heure qui sera reçue après que la machine soit affectée le long de l'itinéraire. Parmi les deux métriques de qualité, MAE et MSE, nous avons choisi MAE. Du point de vue de l'intuitivité de la prévision, il est peut-être plus logique d'évaluer l'espérance moyenne (MSE) plutôt que la médiane (MAE). Mais MAE a une fonctionnalité intéressante: le modèle est plus résistant aux valeurs aberrantes parmi les exemples de formation.

Les panneaux sont divisés en groupes:
- construit par l'heure actuelle;
- géo (coordonnées, distance au centre ville et objets significatifs sur la carte);
- pin (combien et quelles voitures sont à proximité, leur densité calculée différemment);
- statistiques sur la zone (comme d'habitude nous faisons des erreurs, combien nous prédisons);
- des données sur les conducteurs les plus proches (combien de temps ils atteignent, combien le premier est plus proche que le second, etc.).

Bien sûr, CatBoost a été formé sur ces panneaux. L'argument décisif était que le renforcement du gradient mis en œuvre dans CatBoost sur des arbres équilibrés s'est longtemps imposé comme une méthode d'apprentissage automatique très puissante, et la méthode de codage des fonctionnalités catégorielles dans CatBoost paie régulièrement pour nos tâches. Une autre fonctionnalité intéressante de la bibliothèque est l'apprentissage rapide sur le GPU.

Maintenant, quelques mots sur les modèles qui ont été comparés. L'ETA initial (avant d'être spécifié par machine learning) a été calculé en fonction du temps pendant lequel la machine la plus proche de l'utilisateur pourrait arriver. Le modèle actuel (utilisé dans l'application maintenant) est ce qui s'est avéré être fait à l'aide de l'apprentissage automatique et de quoi traite cet article. De plus, un nouveau modèle sera bientôt déployé en production. Elle utilise un ordre de grandeur de fonctionnalités plus importantes pour résoudre le problème. Le tableau ci-dessous montre les mesures de qualité de ces modèles sur des données historiques. Soit dit en passant, nous avons encore beaucoup de plans - venez aider .

Qualité de prédiction de validation ETA *



* Pourcentage (entre parenthèses indique le changement par rapport à l'ETA d'origine).

L'apprentissage automatique nous a permis de gagner environ deux secondes, soit 3,4% de l'écart moyen prévu. Et dans le nouveau modèle - près d'une autre seconde, un total de 4,5%. Mais à partir de ces chiffres, il est difficile de comprendre que l'ETA s'est considérablement améliorée. Pour ressentir les avantages de l'apprentissage automatique, vous devez faire attention à la dernière colonne. Misses avec une prévision de plus de 5 minutes est devenu 19,2%, et dans le nouveau modèle - même 23,2% de moins! Soit dit en passant, de telles erreurs ne se produisent que dans 3 et 2,8% des cas dans les modèles utilisant l'apprentissage automatique.

Résumé

Nous avons spécifié l'ETA dans la broche principalement afin de fournir aux utilisateurs une prévision fiable. Mais, bien sûr, avec toute application du machine learning en entreprise, il est impératif d'évaluer l'effet économique. Et comprendre s'il est comparable au coût de construction et de mise en œuvre de modèles. Après le test A / B en ligne, il s'est avéré que nous, en utilisant l'apprentissage automatique, avons reçu une augmentation statistiquement significative de la conversion d'une commande en voyage (après tout, une commande peut être annulée) et une augmentation de la conversion d'une session utilisateur en commande.

Dans les deux cas, nous parlons d'un effet de l'ordre de 0,1 point de pourcentage. Cela, en passant, ne contredit pas la signification statistique: sur nos volumes de données, même une telle différence est détectée de manière fiable en 2 à 4 semaines. Et avec la pertinence commerciale, en fait, tout n'est pas mal non plus: il s'est avéré que les coûts de clarification de l'ETA repoussent l'augmentation de la conversion en quelques mois seulement.

En conséquence, nous avons obtenu un cas utile et illustratif. Le raffinement de l'ETA dans la broche est devenu une histoire instructive sur la sélection rigoureuse de la variable cible. Côté produit, c'est un exemple très motivant: nous avons amélioré l'application et constaté que les utilisateurs l'appréciaient. Nous espérons que l'ETA raffiné aidera nos passagers plus souvent à rencontrer des réunions, des trains et des avions.

PS Si vous êtes intéressé par d'autres technologies Yandex.Taxi, nous vous recommandons un article sur la tarification dynamique , que mon collègue a récemment publié.