Dans les applications de prévision du monde réel, il est difficile de trouver un équilibre entre précision et rapidité. Nous pouvons atteindre une grande précision en exécutant de nombreux modèles et combinaisons de configurations et nous gagnons en rapidité en exécutant des modèles rapides et peu coûteux en termes de calcul. Chez DoorDash, nous explorons un certain nombre de modèles et de combinaisons de configurations pour prévoir la demande sur notre plateforme. Cependant, le défi consiste à construire un modèle de prévision qui soit très précis tout en fonctionnant rapidement et à moindre coût. Pour répondre à ce compromis entre précision, rapidité et coût, notre équipe de prévision a construit un nouveau modèle appelé ELITE (Ensemble Learning for Improved Time-series Estimation). Ce nouveau modèle utilise des modèles d'ensemble pour les prévisions au lieu d'optimiser un modèle individuel, ce qui permet de combiner des modèles efficaces d'un point de vue informatique afin d'améliorer la précision globale.
Nous expliquons ici comment nous avons développé cette approche de modèle d'ensemble pour :
- maintenir la précision tout en réduisant considérablement le temps d'exécution, ce qui permet de générer des prévisions sur des cibles à haute dimensionnalité.
- générer des économies considérables en termes de coûts de calcul :
- l'application d'un cadre de formation efficace sur le plan informatique.
- l'optimisation des paramètres de l'infrastructure afin d'adapter le processus de formation au cluster Ray, qui a également été utilisé par OpenAI pour la formation GPT.
- réduire l'effort de maintenance en créant un cadre hautement automatisé pour échanger n'importe quel modèle.
Limites des prévisions à l'aide d'une filière de modèles individuels
In recent years, forecasting models have advanced from traditional time series frameworks to increasingly complex deep learning architectures in order to capture the volatile dynamics of real-world scenarios. However, subjectively picking a single model to make accurate forecasts for every target is unrealistic. Therefore, in many industrial practices, a forecasting toolbox applies a selection framework to explore a wide range of models and configurations, carefully evaluating each model's performance on each target before generating final forecasts from the best performer. The configuration space includes not only model parameters, but also options for processing data such as data cleaning, transforming, and outlier handling as well as causal factors, including holidays, weather, or promotions. At DoorDash, we've built a forecast factory to enable these functionalities.
But this type of forecasting pipeline is limited by its computational burden. Beyond the complexity of training increasingly complicated model structures, configuration combinations grow exponentially when we add an additional option to each entry. For example, suppose we have 10 configs and each config has two options, meaning we have 210 combinations. When we add an additional option to a single config, the config combinations increase by 29. As a result, we must search exhaustively, for instance via a grid search, over thousands of config combinations for each forecasting target, consuming hours of execution time and hundreds of dollars in computational cost per run. Moreover, a rolling window cross-validation process must be applied to evaluate each model's forecasting performance. Although this grid search method maintains high accuracy for a wide range of forecasting targets, it also significantly increases both runtime and computation costs as we support more use cases.
Chez DoorDash, les prévisions sont générées pour des cibles très granulaires, ce qui rend l'exécution de modèles de prévision plus coûteuse en termes de calcul, voire prohibitive. Par exemple, nous avons des dizaines de milliers de cibles lorsque nous faisons des prévisions sur les délais de livraison dans les expériences de commutation afin de créer des covariables pour la réduction de la variance. Mais les limites de calcul pourraient bloquer ces cas d'utilisation en raison de la longueur inacceptable des temps d'exécution ou des coûts élevés des clusters. Ces limites ont motivé le développement d'un nouveau cadre de prévision qui pourrait réduire le budget de calcul tout en maintenant une grande précision.
L'idéal serait d'utiliser un seul modèle de prévision, mais ces modèles ont leurs propres limites qui les rendent difficiles à utiliser seuls :
- Unrealistic assumptions: The model structure may have been simplified with assumptions that are not easily satisfied. For example, a single seasonality assumption would not be able to meet reality's complex multiple seasonality patterns - inherent to a seven-day week or 52 weeks in a year.
- Une force biaisée : Certains modèles peuvent ne présenter des avantages qu'à des stades particuliers de l'horizon de prévision. Par exemple, un modèle doté de processeurs pour les conditions météorologiques extrêmes peut être plus performant lorsque les conditions météorologiques changent brusquement, mais moins performant lorsque les tendances et la saisonnalité sont normales. Ces limites deviennent particulièrement critiques dans les prévisions à long terme, car les tendances et les modèles déviants s'accumulent tout au long de l'horizon de prévision.
- Instabilité générale: Les prévisions issues d'un seul modèle sont relativement moins stables. Elles peuvent produire des modèles de forte augmentation/diminution ou des valeurs extrêmes qui s'avèrent peu fiables d'un point de vue commercial.
Passer à un modèle d'ensemble pour obtenir le meilleur des deux mondes
Pour résoudre ce problème de prévision dans le monde réel, nous avons proposé une approche d'apprentissage d'ensemble par empilement temporel. L'idée est la suivante : Au lieu de s'appuyer sur un seul modèle, nous empilons une autre couche sur les modèles candidats de base (apprenants), en créant un ensemble de leurs résultats pour obtenir les prévisions finales. Comme le montre la figure 1 ci-dessous, la conception de ce cadre applique deux couches de parallélisation pour maximiser l'efficacité du calcul et permettre un choix arbitraire des modèles de la couche de base et de la couche d'ensemble.
Cette approche de la mise en œuvre a offert plusieurs avantages sous la forme d'une plus grande précision, d'une meilleure efficacité et d'un meilleur coût, d'une meilleure extensibilité et de risques opérationnels moindres, comme cela est expliqué en détail ci-dessous.
Amélioration de la précision
Le modèle d'ensemble par empilement présente moins de biais que n'importe quel modèle de base unique et pourrait même être plus performant que la moyenne des modèles bayésiens. Intuitivement, chaque base d'apprentissage a des atouts pour capturer le modèle temporel à des périodes discrètes le long de l'horizon de prévision. Le modèle d'ensemble par empilement combine leurs prévisions pour tirer parti des avantages de chaque base, ce qui permet d'obtenir des prévisions plus précises. Par exemple, notre équipe a mené des expériences sur le volume de commandes hebdomadaires dans plusieurs milliers de sous-marchés DoorDash ; les résultats ont montré qu'ELITE était environ 10 % plus précis que le meilleur modèle unique.
En fait, le modèle d'ensemble que nous proposons répond de manière satisfaisante aux limites de performance de la prévision à l'aide d'un seul modèle dans chaque aspect discuté dans la section précédente. L'établissement de prévisions à partir de plusieurs modèles affaiblit les hypothèses de structure de modèle imposées pour chaque modèle unique ; l'utilisation d'un modèle d'ensemble extrait les points forts, ce qui permet aux prévisions combinées de tirer pleinement parti des meilleurs résultats aux différents stades de la prévision. En outre, avec divers modèles de base, le modèle d'ensemble produit des valeurs prévisionnelles plus stables.
Amélioration de l'efficacité et réduction des coûts
Le cadre d'ensemble temporel proposé élimine la nécessité d'une validation croisée par fenêtre roulante, ce qui réduit à la fois le temps d'exécution et les coûts de calcul. Une expérience portant sur nos prévisions les plus complexes a permis de réduire le temps d'apprentissage du modèle de plusieurs heures à quelques minutes et de diminuer les coûts de calcul de plus de 80 %. Le cadre d'ensemble permet également de débloquer des objectifs complexes, y compris nos tâches de prévision à la granularité la plus élevée. Par exemple, chez DoorDash, nous utilisons les prévisions pour soutenir l'expérimentation de la réduction de la variance pour le délai de livraison au niveau très granulaire de l'aiguillage, alors que le cadre de recherche de la grille n'a pas réussi à terminer dans un délai acceptable.
Plus de modularité et d'extensibilité
As we built a standardized module wrapper in the ensemble modeling framework, our implementation improved flexibility by supporting any user-defined model. Additionally, the model accepted external features, which means it can support machine learning and deep learning models that require them. This framework also provides valuable information for investigating base models by tracking how their forecasts contribute to the ensemble forecasts. Such base model diagnostic analysis helps model developers better understand how each base model captures a target's changing patterns.
Réduction de la maintenance du système et des risques
ELITE doesn't select the best model performer from base models, which avoids the extra effort of training each model repeatedly on a sequence of run dates along the historical timeline. This simplifies what otherwise can be a complicated model validation process, reducing maintenance efforts. Because the construction of ELITE only relies on the estimated effect from each base learner, we sharply reduce the number of times we need to train base models. This reduced burden also improves system stability in distributed jobs, reducing the risk of hitting computational limits.
Bâtiment ELITE
Nous résumons ci-dessous les principaux composants impliqués dans la construction de notre solution d'ensemble du point de vue du flux de travail et de l'architecture du modèle.
Designing ELITE's workflow
As shown in Figure 1, our ensemble model solution applies a two-layer - base and ensemble - architecture. The idea is to use forecasts from the base layer to create a set of features to fit the model in the ensemble layer. In particular, the base model forecast features could be combined with other external features such as causal factors or any other correlated variables to feed into the top-layer machine learning model. In this way, variations in the forecasting target could be fully captured by its temporal expectations under various time series model assumptions as reflected in base model forecasts as well as by factors from other sources through external features.
Nous avons créé le prévisionniste d'ensemble en suivant les étapes suivantes, que nous détaillons ci-dessous :
- Choisir un ensemble d'apprenants de base
- Application d'une stratégie de validation croisée k-fold temporelle par empilement pour générer des prévisions à partir d'apprenants de base afin d'adapter le prévisionniste d'ensemble de la couche supérieure
- Choix et ajustement du modèle de la couche supérieure et établissement des prévisions finales
Comment nous avons choisi les apprenants de base
La capacité de prévision d'ELITE dépend de son potentiel d'adoption de différents apprenants de base. La plateforme de prévision centralisée de DoorDash prend en charge un large éventail de modèles et de configurations candidats.
En plus d'intégrer des modèles de prévision provenant de progiciels existants tels que statsmodels, prophet et lightgbm, nous personnalisons les modèles en introduisant de nombreuses configurations. Ces configurations comprennent à la fois les structures sous-jacentes du modèle (y compris les configurations internes telles que les tendances additives ou multiplicatives, la saisonnalité ou les hypothèses d'erreur), ainsi que les options de traitement des séries temporelles pour les configurations externes, y compris la manière de traiter les valeurs manquantes et les valeurs aberrantes, et la manière d'ajuster les impacts des vacances, de la météo ou des promotions. Ces options flexibles constituent une source importante de modèles pour ELITE.
Ensemble model forecast accuracy can be improved by promoting diversity among the base models. To support this, we developed a standardized model wrapper layer to further incorporate new models, an approach we'll discuss in more detail below. We plan future research into other options for improving accuracy, such as penalizing base model complexity.
Validation croisée temporelle k-fold par empilement
Il est essentiel d'estimer l'effet de chaque modèle de base lors de la création du prévisionniste d'ensemble. Comme le montre la figure 2, nous estimons l'effet du modèle de base par le biais d'un cadre de validation croisée temporelle k-fold qui ajuste un modèle sur les observations par rapport aux prévisions empilées pour chaque bloc de validation. Dans ce cadre de validation croisée temporelle, l'ordre temporel des données est préservé.
La procédure de validation croisée k-fold temporelle par empilement suit les étapes suivantes :
- Diviser l'ensemble de données en n segments
- Dans chaque segment, créer k-plis et
- Ajuster chaque apprenant de base avec les données des périodes de formation
- Recueillir les prévisions et les données réelles pour chaque apprenant de base à partir des périodes de test.
- Empiler les prévisions et les données réelles pour chaque apprenant de base généré à l'étape 2 et les ajuster dans la couche d'ensemble pour obtenir l'effet, ou le poids, de chaque apprenant de base.
Choix d'un apprenant d'ensemble
When fitting the ensemble model layer, the selection of models should be based on the number of independent variables - base models - and the data sample size, or stacked observations. A large number of base learners and sufficient data would favor more complex model structures. It is important to choose models that are not sensitive to correlated samples, especially for temporal data. Our architecture allows for flexibility in selecting models with different levels of complexity, ranging from linear regression to neural networks.
Mise en œuvre de l'architecture ELITE
Pour mettre en œuvre cette conception d'ensemble, nous avons intégré le cadre à notre base de code Forecast Factory. Nous avons décomposé le processus de formation d'ELITE en composants clés, tels que la formation des apprenants de base, la validation croisée temporelle k-fold et la formation de la couche d'ensemble, et nous avons créé une classe de modèle d'ensemble qui incorpore chacune de leurs implémentations. Nous avons ensuite créé une classe d'exécution générique pour exécuter le flux de travail de prévision d'ensemble. Cette classe d'exécution peut facilement être héritée et adaptée à n'importe lequel de nos travaux de prévision existants. Avec cette mise en œuvre, nous pouvons appliquer un cadre de parallélisation imbriquée ; la conception nous permet également de faire des choix de modèles dans les couches de base et d'ensemble au sein de notre architecture. Dans la section suivante, nous expliquons comment cette conception offre des avantages significatifs en termes d'efficacité et de généralisation, en particulier lorsqu'il s'agit d'objectifs de prévision à forte granularité.
Parallélisation imbriquée sur le cluster Ray
Pour maximiser l'efficacité du travail de prévision, nous avons mis en œuvre un cadre de parallélisation imbriquée dans notre conception de modélisation d'ensemble afin de générer simultanément des prévisions pour un grand nombre de cibles. Comme le montre la figure 3, notre cadre de parallélisation imbriquée implique la formation parallèle de chaque cible dans la couche externe et la formation parallèle de chaque apprenant de base dans la couche interne. Sans ce cadre, la formation séquentielle de millions de modèles de prévision individuels prendrait beaucoup de temps et serait prohibitive sur le plan informatique.
To provide a stable distributing environment and fully utilize the benefits of our nested parallelization across nodes on both layers, we adopted Ray, a new distributed training framework that makes scaling easier. With KubeRay, we launched the Ray clusters on our in-house Kubernetes infrastructure and maximized our ensemble model's efficiency, significantly reducing both execution time and computation cost.
Choix de modèles flexibles grâce à des modèles génériques
Notre architecture offre également l'avantage de la généralisation dérivée de la conception générique de notre modèle de base et des wrappers de modèles d'ensemble. Notre cadre de mise en œuvre normalisé nous permet non seulement d'intégrer des modèles provenant de progiciels d'apprentissage automatique, d'apprentissage profond ou de prévision existants, mais aussi de permettre aux utilisateurs de créer des classes de modèles personnalisées en fonction de leurs besoins spécifiques.
Le cas d'utilisation DoorDash
Here we will present two DoorDash use cases to demonstrate our ensemble model's performance.
Le premier cas concerne les prévisions hebdomadaires du volume des commandes afin de permettre la planification financière et opérationnelle pour plusieurs milliers de sous-marchés. Nous explorons des milliers de combinaisons différentes de modèles et de configurations pour chaque sous-marché ; chaque combinaison correspond à un apprenant de base. Comme le montre le tableau 1, nous avons observé une amélioration significative de l'efficacité et de la précision avec ELITE par rapport à la recherche en grille. Nous avons obtenu une réduction de 78 % et 95 % du temps d'exécution et du coût de calcul respectivement, ainsi qu'une amélioration de 12 % de la précision MAPE.
Amélioration en % d'ELITE par rapport à la recherche en grille | |||
Type de grappe | Temps d'exécution | Coût de la grappe | Précision (MAPE) |
Etincelle | 83% | 96% | 12% |
Ray* | 78% | 95% |
*Notez que les pourcentages d'amélioration indiqués dans le tableau 1 comparent ELITE à la recherche en grille sur le même type de cluster. Cependant, l'exécution d'ELITE sur Ray réduit le temps d'exécution et le coût par rapport à l'exécution d'ELITE sur Spark, comme le montre le tableau 2.
Le deuxième cas d'utilisation concerne notre prévision du délai de livraison, qui sert d'exemple pour soutenir la réduction de la variance de l'expérimentation. Cette prévision est faite au niveau de l'unité de commutation, qui est notre unité de randomisation de l'expérimentation. Compte tenu du nombre d'unités de commutation à cinq chiffres chez DoorDash, la recherche par grille n'a pas pu fournir une solution réalisable dans un budget de calcul et des contraintes de temps raisonnables. Cependant, ELITE a généré ces prévisions très granulaires en une heure et 20 minutes avec une réduction de la variance de 10 % par rapport à l'utilisation d'une série chronologique historique à décalage multiple, par exemple, CUPED.
Pour des prévisions aussi granulaires, nous aimerions souligner la capacité d'amélioration de l'efficacité générée par la combinaison de notre algorithme d'ensemble et de l'infrastructure Ray. La charge de calcul minimale obtenue par l'algorithme d'ensemble nous a permis d'exécuter le modèle sur des clusters Ray petits et peu coûteux. Par conséquent, en plus de débloquer la tâche de prévision de la recherche en grille, nous avons également réduit notre temps d'exécution et notre coût de calcul en passant des clusters Spark à Ray, comme le montre le tableau 2.
Temps d'exécution par rapport à Spark | Coût du cluster par rapport à Spark | |
Amélioration par Ray | 50% | 93% |
Inconvénients d'ELITE
Despite all of the advantages, there are a few drawbacks to using ensemble models that we plan to address as we develop further improvements in accuracy. Although ELITE improves forecasting accuracy over a single model in most common scenarios, its ability to handle extreme cases is inferior to a single highly specialized model. The deficiency comes from the single model's ability to capture a particular extreme pattern; when its forecasts are combined with others that are less representative of that pattern, accuracy drops. On the other hand, as shown in Figure 4, highly diverse base learner combinations provide high accuracy for most common scenarios, comprehensively covering the variation from as many directions as possible.
Pour un scénario extrême, la précision augmente à mesure que le modèle se spécialise (dans le sens inverse de l'axe des abscisses) et diminue à mesure que le modèle s'assemble (dans le sens de l'axe des abscisses). En revanche, pour un scénario courant, la précision augmente à mesure que le modèle devient plus ensembliste (le long de l'axe des x) et diminue à mesure que le modèle devient plus spécialisé (le long de la direction inverse de l'axe des x).
Pour contrer ces préférences conflictuelles sur les modèles spécialisés et d'ensemble lors du traitement de différents modèles de données, nous prévoyons de nous concentrer sur l'exploration de moyens plus intelligents pour créer un ensemble d'apprenants de base afin de trouver un équilibre dans les compromis de précision globale. Nous prévoyons ensuite d'optimiser notre utilisation de la capacité d'un apprenant individuel à évaluer les situations extrêmes tout en continuant à maintenir la diversité des modèles pour garantir la précision et la robustesse dans les scénarios les plus courants.
Tirer les leçons de l'amélioration de l'efficacité de l'exécution
Pour conclure, nous aimerions vous faire part de quelques observations que nous avons faites lors de l'élaboration de notre modèle d'ensemble.
L'importance du choix et de la configuration du backend
L'infrastructure dorsale joue un rôle crucial dans l'élaboration de solutions d'apprentissage automatique efficaces et fiables. Comme nous l'avons découvert lors de notre exécution initiale du cadre de parallélisation imbriquée avec le backend Spark sur les clusters Spark, nous avons rencontré des difficultés de débogage avec des journaux non informatifs sur le nœud pilote.
Bonnes pratiques de mise en œuvre
Un remaniement constant peut conduire à des gains d'efficacité significatifs et constitue une pratique de programmation idéale, en particulier lors du développement d'un code qui inclut des structures de parallélisation compliquées. Au début de notre implémentation parallèle, par exemple, nous avons passé directement l'objet entier de la classe (self) à de nombreuses méthodes parallélisées, ce qui a entraîné des ralentissements inacceptables dans la distribution des données et les exécutions. Cependant, après un remaniement visant à minimiser les données et les objets passant par ces méthodes parallélisées, nous avons obtenu une amélioration de l'efficacité de plus de six fois.
Conclusion
The proposed ensemble framework is applicable not only to the specific forecasting problem we addressed but also to any forecasting system that requires a heavy model selection process. It also serves as a powerful machine learning system where time series forecasting features such as weather could be included in addition to stacked model predictions. By establishing ensemble connections between base models, the proposed framework offers the flexibility to support both machine learning and forecasting use cases, resulting in higher accuracy and efficiency benefits - without the need for a complex deep learning pipeline.
Remerciements
We truly appreciate all the help and support from the DSML forecasting and MLP forecasting teams - Swaroop Chitlur, Ryan Schork, Chad Akkoyun, Hien Luu and Cyrus Safaie who made this collaborative project possible and successful. Many thanks to Joe Harkman, Robert Kaspar and Stas Sajin, who shared incredibly valuable insights and suggestions in the design review of this work. Our appreciation also goes to the experimentation platform team partners Bhawana Goel, Caixia Huang, Yixin Tang and Stas Sajin for their efforts and collaboration discussing and onboarding the use cases. Finally, many thanks to the Eng Enablement team for continuous support, review, and editing on this article.