Skip to content

Blog


Utilisation de la distribution Gamma pour améliorer les prévisions d'événements à longue traîne

6 avril 2022

|
Pratik Parekh

Pratik Parekh

Zhe Jia

Zhe Jia

Pour DoorDash, il est essentiel de pouvoir prédire les événements à longue traîne liés aux délais de livraison afin de s'assurer que les commandes des consommateurs arrivent à temps. Les événements à longue traîne sont des cas rares où les prédictions de temps sont très éloignées des temps réels et ces événements ont tendance à être coûteux. Bien que nous ayons déjà amélioré les prédictions d'événements de longue traîne (comme expliqué dans cet article précédent) en modifiant notre fonction de perte et en ajoutant des signaux en temps réel, nous voulions améliorer encore les prédictions en utilisant une approche de pondération de l'échantillon inverse basée sur la distribution gamma pour donner plus de poids aux événements de longue traîne lors de l'apprentissage du modèle. Dans cet article, nous expliquerons en détail comment nous avons utilisé la distribution gamma pour améliorer les performances du modèle.

L'importance de prédictions précises sur la longue traîne

Avant d'aller plus loin, rappelons rapidement pourquoi l'exactitude des estimations de livraison (ETA) de DoorDash est si importante. L'ETA (heure estimée d'arrivée) est une promesse faite au consommateur quant à l'heure à laquelle la commande arrivera à sa porte. Une sous-estimation se traduit par une très mauvaise expérience de commande (une livraison tardive) et une sur-estimation (une estimation plus élevée) peut amener les consommateurs à ne pas passer de commande ou à se faire livrer avant d'être chez eux pour la recevoir. En outre, les délais de livraison sont difficiles à prévoir, notamment en raison de la grande variabilité des temps de préparation des commandes, des conditions de circulation routière, de la disponibilité des Dashers (chauffeurs-livreurs) et du temps nécessaire pour trouver un parking et se rendre à une adresse résidentielle. L'imprévisibilité de ces éléments est à l'origine d'événements coûteux de longue traîne. Pour améliorer ces estimations, il est important de modéliser la distribution et d'adapter la fonction de perte afin de mieux pénaliser les événements de longue traîne (à la fois les prédictions précoces et les prédictions tardives). 

Trouver la meilleure distribution pour modéliser les délais de livraison

Dans notre précédent article, nous avons expliqué que nous pouvions modifier la fonction de perte et ajouter des signaux en temps réel à notre modèle d'apprentissage automatique pour en améliorer la précision. Pour itérer et améliorer ces ajustements, nous voulions utiliser la fonction de perte qui reproduit notre distribution des délais de livraison aussi précisément que possible.

Nous avons exploré plusieurs distributions avant de trouver la meilleure, comme le montre la figure 1. Commençons par un bref examen des distributions couramment utilisées :

  • Les distributions normales sont couramment utilisées dans les sciences naturelles et sociales pour représenter des variables aléatoires à valeur réelle dont la distribution est inconnue, parce qu'elles sont symétriques, mathématiquement faciles et qu'elles s'adaptent à un large éventail d'événements. Vous connaissez peut-être cette distribution grâce au théorème central limite très fondamental. 
  • Les distributions log-normales sont utilisées pour modéliser des phénomènes dont la queue droite est plus grosse et qui ne prennent que des valeurs positives (pas de queue gauche). Par exemple, dans les épidémies hautement transmissibles, comme le SRAS en 2003, le nombre de cas hospitalisés est une distribution log-normale. En économie, le revenu de 97 à 99 % de la population est distribué selon une loi log-normale.
  • Les distributions Gamma sont utilisées pour modéliser des phénomènes ayant une longue queue sur le côté droit. Par exemple, la taille des demandes d'indemnisation suit une distribution Gamma, tout comme la quantité de précipitations accumulées au cours d'une période donnée.
Figure 1. Comparaison entre la distribution réelle des délais de livraison et les distributions couramment observées. 

To quantify the similarity of each distribution with our empirical target distribution, we used the Kolmogorov-Smirnov test (K-S test). The statistics of K-S test results can be used to indicate the similarity between two given distributions. It ranges from zero to one, where zero means totally different and one means exactly the same. Typically, K-S test statistic output <0.05 is used to reject the hypothesis that the two given distributions are the same. From the K-S test result in Table 1, we found both log-normal and gamma almost perfectly fit our empirical distribution. In practice, these two distributions are often used to model the same phenomena. For our use case, we decided to go for the gamma distribution to model delivery estimates. In the following section, we explain the fundamental characteristics of the gamma distribution and why they suit the problem we are trying to solve.

Nom de la distributionStatistiques du test K-S
Normal0.512
Skew normal (asymétrique)0.784
Log-normal 0.999
Gamma0.999
Tableau 1. Résultats du test K-S pour différentes distributions du délai de livraison réel.

Restez informé grâce aux mises à jour hebdomadaires

Abonnez-vous à notre blog d'ingénierie pour recevoir régulièrement des informations sur les projets les plus intéressants sur lesquels notre équipe travaille.

Qu'est-ce que la distribution gamma ?

Les distributions Gamma ont été utilisées pour modéliser des variables continues qui sont toujours positives et ont des distributions asymétriques. Elle est souvent utilisée pour décrire le temps qui s'écoule entre des événements indépendants ayant des intervalles de temps moyens constants entre eux, tels que les chutes de pluie, les demandes d'indemnisation, les temps d'attente, etc. En oncologie, la distribution par âge de l'incidence du cancer suit souvent la distribution gamma, tandis que les paramètres de forme et de taux prédisent, respectivement, le nombre d'événements conducteurs et l'intervalle de temps qui les sépare. Dans les secteurs des transports et des services, la distribution gamma est généralement utilisée pour estimer le temps d'attente et le temps de service.

La fonction de distribution gamma a deux paramètres : un paramètre de forme et un paramètre de taux (figure 2). Le paramètre de forme α représente le nombre d'événements indépendants que nous modélisons. Lorsque le paramètre de forme (α) est égal à un, la distribution gamma devient une distribution exponentielle. Ainsi, la distribution gamma est essentiellement la somme de plusieurs distributions exponentielles. Dans notre cas, le paramètre de forme (α) est égal à quatre, ce qui donne le meilleur ajustement à la courbe de distribution du délai de livraison réel. Étant donné que le délai de livraison est déterminé par de nombreux facteurs, la valeur α n'indique pas nécessairement qu'il existe quatre événements indépendants. Elle peut impliquer que les événements sous-jacents qui déterminent la forme de la distribution gamma sont équivalents à quatre événements indépendants. Toutes choses étant constantes par ailleurs, l'augmentation entraîne le déplacement du pic de la courbe de la fonction de densité de probabilité (PDF) vers le côté droit. 

Le paramètre de taux β représente le temps moyen entre ces événements. Si tout le reste reste inchangé, la réduction du paramètre de taux (ce qui signifie l'augmentation du paramètre d'échelle) fera qu'il faudra plus de temps pour observer le même nombre d'événements, d'où une courbe PDF plus plate.

Figure 2. Courbes PDF de la distribution Gamma avec différents paramètres. 

La PDF de la distribution gamma est donnée par l'équation (1).

Maintenant que nous comprenons la distribution gamma, la question se pose de savoir comment nous pouvons l'utiliser pour modéliser les poids des échantillons dans notre processus de formation.

Utiliser la distribution gamma pour faire de meilleures prédictions

Pour obtenir de meilleures prédictions sur les événements de longue traîne à faible fréquence, nous voulons permettre au modèle d'apprendre plus d'informations à partir de ces événements. Pour ce faire, nous attribuons un poids plus important à ces événements au cours du processus d'apprentissage du modèle. Nous utilisons une fonction de pondération pour attribuer un poids aux différents points de données. Voici les étapes que nous avons suivies :

  1. Tout d'abord, nous trouvons la distribution gamma la mieux ajustée pour les données relatives à la durée de livraison. Dans notre cas, nous avons trouvé que α=4 et β =1 avaient le meilleur ajustement.
  2. Ensuite, nous avons fixé la fonction de pondération inversement proportionnelle à la densité de probabilité de la distribution gamma pour permettre au modèle de tirer des enseignements des rares événements à longue queue. 
  3. Nous avons divisé les échantillons de données d'apprentissage en deux groupes au niveau de la densité maximale (le Mode). Le groupe situé à gauche du pic de densité a un délai de livraison plus court, et le groupe situé à droite a un délai de livraison plus long. 
  4. Les poids d'échantillonnage des points de données sont ajustés différemment pour les échantillons situés à gauche et à droite du pic, en fonction des contraintes de l'entreprise. Cela permet de tenir compte de la précocité et de la tardiveté. 

Grâce à ce processus, nous avons réduit les retards de 20 minutes de 11 % (en valeur relative). En particulier, les parties à queue très longue ont été mieux prédites (figure 3). Le modèle entraîné par le poids gamma double le nombre de prédictions de queues longues par rapport à la méthode de l'erreur quadratique moyenne asymétrique (AMSE). Outre les excellents résultats obtenus, certaines caractéristiques de la distribution gamma nous ont permis d'ajuster efficacement notre fonction de perte afin d'intégrer les résultats commerciaux souhaités.

Figure 3 : Comparaison de l'AMSE et du PDF à poids gamma sur la distribution réelle des délais de livraison. Comparaison de l'AMSE et du PDF à poids gamma sur la distribution réelle des délais de livraison. 

Avantages de la personnalisation de la distribution gamma

Pour obtenir de meilleurs résultats commerciaux, le modèle doit faire des prédictions précises sur les bons événements de longue traîne et s'assurer que nous ne prévoyons pas trop de livraisons rapides. La nature des distributions gamma nous a aidés à atteindre ces deux objectifs, en permettant une distribution plus large des résultats de prédiction et une meilleure couverture de la précocité et de la longue traîne :

  • La ponctualité et le retard ont été mieux équilibrés en ajustant le poids en fonction de l'impact sur l'entreprise. 
  • La distribution AMSE permet de saisir les nuances de précocité et de retard, mais il est clair que la distribution gamma offre une couverture à queue beaucoup plus longue, comme vous pouvez le voir sur le graphique.
  • Cela dit, cette méthodologie présente certaines lacunes :
    • Nous devons accorder un ensemble supplémentaire de poids (gauche/droite) lors du recyclage à chaque fois.
    • Dans les scénarios de recyclage continu via des pipelines automatisés, le maintien d'un ensemble constant de poids à gauche et à droite peut entraîner une dégradation des performances du modèle si ces poids ne sont pas régulièrement affinés en fonction des données.

Conclusion

Nous avons amélioré les performances de prédiction pour les événements à longue queue en modifiant la fonction de perte avec une approche personnalisée de pondération des échantillons basée sur la distribution gamma. L'AMSE est une fonction de perte asymétrique conçue pour modéliser une distribution asymétrique. Elle capture les événements à longue queue qui suivent une distribution quadratique asymétrique. Toutefois, la distribution de la fonction de pondération basée sur la loi gamma est plus proche de la distribution réelle des délais de livraison et présente plus d'avantages que l'AMSE :

  • Par rapport à la fonction de perte AMSE, elle diminue plus lentement sur la partie longue de la queue.
  • La séparation de la fonction de pondération au niveau du mode de la distribution nous donne plus de flexibilité pour régler à la fois la précocité et le retard. 

Nous ne nous sommes pas arrêtés là et nous continuerons à explorer de nouvelles options pour améliorer la précision de nos estimations. Si vous êtes passionné par la création d'applications de ML qui ont un impact positif sur la vie de millions de commerçants, de Dashers et de clients, envisagez de rejoindre notre équipe.

About the Authors

  • Pratik Parekh
  • Zhe Jia

    Zhe Jia is a Machine Learning Engineer on Operational Excellence at DoorDash. His focus is on user support automation with LLM.

Emplois connexes

Job ID: 2915998
Localisation
Sao Paulo, Brazil
Département
Ingénierie
Localisation
Sunnyvale, CA
Département
Ingénierie
Localisation
Pune, Inde
Département
Ingénierie
Localisation
São Paulo, Brésil
Département
Ingénierie
Localisation
San Francisco, CA; Tempe, AZ
Département
Ingénierie