Au sein de l'équipe d'expédition de DoorDash, nous prenons des décisions et des itérations tous les jours, qu'il s'agisse de stratégies commerciales, de produits, d'algorithmes d'apprentissage automatique ou d'optimisations. Comme toutes ces décisions sont prises sur la base de résultats d'expériences, il est essentiel pour nous de disposer d'un cadre d'expérimentation avec de la rigueur et de la vélocité. Au cours des dernières années, nous avons établi le cadre Switchback comme base pour la plupart de nos expériences de répartition. En outre, nous avons exploré des méthodes ex post telles que la modélisation multiniveaux (MLM) pour améliorer la rigueur de l'expérience sous certaines hypothèses.
Dans cet article de blog, nous allons parler de l'utilisation d'une autre méthode statistique : Cluster Robust Standard Error (CRSE) dans le cadre Switchback. Nous présentons le problème de la corrélation des données à l'intérieur des clusters et montrons que la MLM peut être biaisée lorsque certaines hypothèses ne se vérifient pas. Nous examinons ensuite les différents types d'estimations de l'erreur standard robuste compte tenu des corrélations d'erreur, la manière dont nous les utilisons dans nos tests de commutation et les résultats de l'évaluation basés sur des simulations d'extrapolation par grappes (cluster-bootstrap). Enfin, nous expliquons comment nous utilisons CRSE dans Diff-in-Diff pour améliorer la rigueur, ainsi que quelques conseils et mises en garde que nous avons trouvés utiles dans la pratique.
Problème de regroupement
Introduction
Le regroupement est un phénomène selon lequel les individus sont groupés en grappes et les individus d'une même grappe sont corrélés. Par conséquent, lors de l'application pratique d'un modèle de régression, les erreurs sont indépendantes d'une grappe à l'autre, mais corrélées à l'intérieur d'une même grappe. Un exemple classique de regroupement est celui des régions géographiques, où les individus d'une même ville ou d'un même État sont corrélés. Chez DoorDash, le regroupement est très courant. Par exemple, les livraisons sont regroupées par région ou par heure, car les livraisons dans la même région/heure partagent des caractéristiques similaires comme la durée de la livraison, l'efficacité de la machine à laver, etc. Les commandes d'un même commerçant peuvent former une grappe parce qu'elles ont un temps de préparation des aliments similaire. Les livraisons effectuées par les mêmes dashers peuvent former une grappe parce qu'elles peuvent avoir un temps de déplacement ou de stationnement similaire.
Dans l'expérience de répartition, nous utilisons des tests de commutation qui randomisent sur des "unités" de temps régional, c'est-à-dire que toutes les livraisons et tous les Dashers dans chaque unité sont exposés au même type d'algorithme. La raison principale pour laquelle nous utilisons le switchback est de traiter les effets de réseau qui ont été élaborés dans l'article précédent du blog. Tests de recul et expérimentation aléatoire sous effets de réseau chez DoorDash.
Lorsque l'effet de traitement estimé souhaité se situe généralement au niveau de la prestation, le regroupement introduit des problèmes dans le modèle de régression, car les termes d'erreur sont corrélés au sein de chaque unité régionale-temporelle. La corrélation au sein de l'unité conduirait à une sous-estimation de l'erreur type et de la valeur p, et donc à un taux de faux positifs plus élevé. Dans l'un de nos précédents articles Rigueur de l'expérience pour l'analyse de l'expérience de rétrocessionNous avons donc mesuré quantitativement le degré de sous-estimation de l'erreur standard dans le cadre des MCO. Les résultats montrent que le taux de faux positifs peut atteindre 0,6 dans notre monde de commutation. Pour atténuer ce problème, nous devrons résoudre le problème de regroupement et donc estimer correctement l'erreur standard de l'effet du traitement.
Les pièges de l'utilisation du MLM
Pour résoudre le problème du regroupement, nous avons appliqué le modèle MLM à certaines expériences de commutation. Le modèle MLM, également connu sous le nom de modèle linéaire à effets mixtes, est un modèle statistique dont les paramètres peuvent être à effet fixe ou aléatoire, et peuvent varier à plus d'un niveau. Bien que les résultats des simulations montrent qu'il est beaucoup plus efficace que la plupart des autres modèles, le MLM ne s'applique pas à tous les scénarios d'expérience chez DoorDash. Pour certaines expériences, nous avons constaté que le MLM peut donner des résultats contradictoires par rapport aux estimations des MCO. Par exemple, l'estimateur MLM a produit un résultat statistiquement significatif de -0,22 pour l'effet de traitement, alors que la différence entre le traitement moyen et le contrôle moyen est de 0,26, ce qui est difficile à interpréter.
La principale raison pour laquelle la MLM peut donner un résultat biaisé est la mauvaise spécification du modèle. Dans la MLM, nous supposons que l'hétérogénéité est distribuée de manière aléatoire et normale, ce qui n'est pas toujours le cas dans la réalité. Lorsque cette hypothèse ne tient pas, le résultat peut être biaisé. Une représentation plus large de cette classe de méthodes peut être décrite en deux étapes : D'abord en ajoutant quelques contraintes et hypothèses supplémentaires lors de l'estimation de la corrélation des erreurs, puis en utilisant les MDFT pour estimer le modèle original. Le succès dépend de la capacité à estimer l'erreur de manière cohérente. Si toutes les hypothèses sont valables pour les données d'une expérience, ces approches basées sur un modèle ont généralement une grande puissance.
Chez DoorDash, les expériences de répartition sont très diverses, allant des effets temporels et de l'optimisation des itinéraires à l'ajustement des paramètres, de sorte qu'il n'y a généralement pas d'hypothèse unique qui s'applique à tous les cas. Par conséquent, pour une nouvelle expérience dont nous n'avons pas beaucoup de connaissances préalables, nous avons besoin d'une méthode "sans modèle" qui peut donner une estimation correcte de l'erreur standard sans nécessiter de spécification de la corrélation de l'erreur.
Erreur standard robuste en grappe
Introduction au CRSE
L'erreur standard robuste des grappes (CRSE) peut tenir compte de l'hétéroscédasticité et des corrélations au sein des grappes, tout en ne posant pas d'hypothèses fortes sur la corrélation des erreurs. Dans cette section, nous allons vous guider dans le développement de la CRSE à partir de la variance "nominale" des MCO qui nous est la plus familière.
A partir de la formule bien connue de la solution des MCO, nous pouvons écrire le bêta et la variance du bêta comme suit :
où Ω est la matrice de covariance des erreurs V(Ɛ|X).
Lorsque l'on suppose que les erreurs sont indépendantes et identiquement distribuées (iid), devient une matrice diagonale dont tous les éléments sont égaux à σ2. Nous pouvons alors obtenir la variance de l'effet de traitement estimé :
Lorsque les erreurs sont hétéroscédastiques, la matrice devient une matrice diagonale dont tous les éléments sont différents. Nous pouvons écrire la "viande" du "sandwich" comme ci-dessous, et la variance est appelée erreur standard conforme à l'hétéroscédasticité (HC).
En ce qui concerne l'erreur standard des grappes, nous admettons que les erreurs peuvent non seulement être hétéroscédastiques, mais aussi corrélées avec d'autres au sein de la même grappe. Compte tenu de cette structure, Ω devient une matrice bloc-diagonale, où 𝜺i est le vecteur d'erreur dans chaque grappe.
Et la "viande" du "sandwich" devient :
Où G est le nombre de grappes. Pour une meilleure illustration, voici une visualisation de la matrice de variance ΩPour ce faire, nous avons utilisé l'expérience de la rétrocession chez DoorDash comme exemple. Dans cet exemple simplifié, nous avons trois unités de temps régionales : San Francisco 13 heures, New York 15 heures et Los Angeles 4 heures. Dans chacune de ces trois unités, il n'y a que trois livraisons. D'après la définition de CRSE ci-dessus, les erreurs de livraison sont corrélées à l'intérieur des unités mais indépendantes d'une unité à l'autre.
Comme nous l'avons mentionné précédemment, les MCO, en négligeant la corrélation à l'intérieur des grappes, sous-estiment fortement la variance. La formule ci-dessous fournit une approximation utile de l'ampleur de l'estimation de la variance des MCO par défaut :
où le premier ρ est une mesure de la corrélation intra-cluster du régresseur, le second ρ est la corrélation d'erreur intra-cluster, et Ng est la taille moyenne des grappes.
Dans l'expérience de dispatch switchback, étant donné que le régresseur est le seau d'expérience et qu'il reste constant au sein d'un cluster, ils sont parfaitement corrélés. Les erreurs du modèle ont également une corrélation élevée car les livraisons au sein des unités spatio-temporelles ont des caractéristiques très similaires. Quant à la taille de la grappe, elle est considérablement élevée dans la région populaire pendant les heures de pointe. Par conséquent, dans notre cas, l'estimateur de variance par défaut des MCO est fortement biaisé à la baisse et beaucoup plus petit que le CRSE.
Simulation
Pour valider le fait que l'erreur standard robuste en grappe estime correctement l'erreur standard dans les expériences de répartition, nous avons exécuté une procédure de simulation dans laquelle nous attribuons un effet de traitement normal à 50 % des livraisons sélectionnées de manière aléatoire à partir de données bootstrapped et appliquons plusieurs méthodes différentes. Les méthodes que nous avons utilisées sont les suivantes :
- Régression au niveau de la livraison
- Régression régionale-temporelle au niveau de l'unité
- Niveau de prestation avec CRSE sur l'unité de temps régionale
- Niveau de livraison avec CRSE sur l'unité de temps régionale et marché ajouté comme effets fixes
Résultats de la simulation
Voici les résultats de la simulation utilisant les méthodes mentionnées ci-dessus. Nous utilisons WithinCI, le pourcentage qui calcule l'intervalle de confiance qui couvre la vraie moyenne, pour mesurer la validité de la méthode ; et Power, le pourcentage qui détecte réellement la différence avec une signification statistique quand il y en a une, pour évaluer et comparer les méthodes.
Le tableau montre que lorsque nous effectuons le test au niveau de la livraison sans CRSE, le WithinCI est beaucoup plus petit que 0,95, ce qui signifie qu'il sous-estime fortement la variance et l'intervalle de confiance et qu'il ne peut donc pas être utilisé. Le test au niveau de l'unité a une bonne validité si l'on en juge par le fait que le WithinCI est proche de 0,95. Cependant, la puissance est très faible et la taille de l'échantillon devient beaucoup plus petite après avoir pris la moyenne sur chaque unité. Plus important encore, l'établissement d'une moyenne pour chaque unité pèsera sur chacune d'entre elles de manière égale. Or, d'un point de vue commercial, nous souhaiterions accorder la même importance à chaque livraison plutôt qu'à chaque unité régionale. Après avoir utilisé CRSE sur l'unité région-temps au niveau de la livraison, les résultats de la simulation montrent que l'erreur type est correctement estimée, avec une amélioration de la puissance. Nous avons également expérimenté l'ajout d'un effet de fixation de la région ou la transformation de la métrique en plus de l'application CRSE, le résultat montre une amélioration importante de la puissance avec l'effet de fixation. Bien que le résultat ne soit pas montré ici, nous avons également simulé l'utilisation de MLM sur les mêmes données. CRSE prouve à nouveau qu'il s'agit d'une méthode plus robuste dans le cadre de nos expériences d'inversion.
Autres applications et mise en œuvre
Mises en garde concernant la mise en œuvre du CRSE
Une hypothèse importante de l'erreur type robuste aux grappes est que le nombre de grappes va jusqu'à l'infini. L'ajustement est courant dans les scénarios de grappes finies. Par exemple, dans Stata, au lieu d'utiliser ug, cug dans la formule (2) peut être utilisé au lieu de ugoù 
Il existe de nombreux logiciels et bibliothèques qui mettent en œuvre l'ESRC et ils peuvent être légèrement différents. Lorsque nous avons appliqué la CRSE, afin de vérifier si la mise en œuvre spécifique est appropriée, nous avons utilisé le bootstrap en grappes pour obtenir une "véritable" erreur standard robuste en grappes et la comparer à celle que nous avons mise en œuvre. Dans le bootstrap par grappes, le rééchantillonnage est effectué au niveau des grappes.
- Pour i dans le nombre d'échantillons bootstrap N :
- Generate m clusters {(X1, y1), (X2, y2), ...(Xm, ym)} by resampling with replacement m times from the original data
- Calculer l'estimateur bêta à partir des données générées i
- Collect {i, i=1,2,3...n} and compute the variance
Nous nous attendons à ce que notre implémentation de CRSE ait une valeur assez proche du résultat bootstrap en grappes. L'une des principales raisons pour lesquelles nous n'appliquons pas directement la variance bootstrap en grappes dans l'expérience est la vitesse. Générer CRSE par bootstrap suffisamment de fois sur un grand ensemble de données peut prendre beaucoup de temps.
Application de l'ESRC en Diff-in-Diff
Comme indiqué précédemment, le regroupement est un phénomène très courant dans les expériences de DoorDash, de sorte que l'erreur type robuste au regroupement peut être utilisée dans de nombreuses analyses d'expérimentation. En particulier, l'erreur type robuste aux grappes est utilisée dans les expériences Diff-in-Diff. Chez DoorDash, l'expérience Diff-in-Diff est généralement appliquée lorsque nous mesurons l'effet du traitement au niveau géographique agrégé. Par exemple, nous expérimentons l'effet d'une campagne de marketing en assignant la campagne de marketing à certains états de traitement et en utilisant certains états comme contrôle. 
Où i est l'individu, t est le temps, et s(i) est le marché dans lequel l'individu i se trouve. Les erreurs sont fortement corrélées entre elles au fil du temps au sein d'un même marché. Par conséquent, l'ESRC est nécessaire en diff-in-diff pour obtenir une estimation correcte de l'erreur type. Dans cet exemple, étant donné que l'erreur type est regroupée au niveau du marché, la CRSE doit être appliquée au niveau du marché.
Conclusion
Dans les expériences de commutation où les données sont regroupées en grappes, l'ESRC est un moyen robuste et simple d'obtenir une inférence statistique non biaisée. En nous attaquant à ce problème au sein de l'équipe de répartition, nous avons pu trouver des applications de CRSE dans de nombreuses autres expériences de consommateurs, dashers et marchands. Réussir à contrôler la corrélation des erreurs de grappes est un grand pas en avant dans l'itération de nos expériences sur les places de marché avec plus de confiance. Au fur et à mesure, nous continuerons à améliorer notre cadre d'expérimentation à rebours, notamment en ce qui concerne les effets d'interaction, les tests séquentiels et les tests conjoints.
Nous remercions tout particulièrement le professeur Navdeep S.Sahni, Sifeng Lin, Richard Hwang et toute l'équipe d'expédition de DoorDash pour leur aide dans la publication de ce billet.
Références
- A. Colin Cameron & Douglas L. Miller, (2015). A Practitioner's Guide to Cluster-Robust Inference. Journal of Human Resources, University of Wisconsin Press, vol. 50(2), 317-372.
- Freedman, D. A. (2008). On regression adjustments to experimental data. Progrès en mathématiques appliquées, 40(2), 180-193.
