Improving the Sensitivity of Online Controlled Experiments by Utilizing Pre-Experiment Data
Deng, Xu, Kohavi, and Walker
WSDM' 13
Highlight:
" The results on Bing's experimentation system are very successful: we can reduce variance by about 50%, effectively achieving the same statistical power with only half of the users, or half the duration. "
Review Variance Reduction Techniques:
Kohavi et al (2009) Using different metric, or through filtering out users who are not impacted by the change.
Deng et al. (2011) Use page level randomization at the design stage to reduce variance of page level metrics.
This paper: Controlled-experiment Using Pre-Experiment Data: CUPED
Stratification Approach
Basics:
1, Divide the sampling region into K strata with w_k the probability that Y falls into kth stratum.
2, The sample size for kth stratum is n_k = n * w_k.
3, Stratified average: Y_strat = sum(w_k * Y_bar_k), with Y_bar_k as the average within the kth stratum.
Benefits: Achieving variance reduction, as between-strata variance is removed through stratification.
For online experiment, using Post-stratification: utilize pre-experiment variables to construct strata after all the data are collected.
e.g. using browser type to form strata.
Note that the stratification variable (browser in eg) should not be affected by the treatment (the variable should be independent of the randomization assignment) to guarantee unbiased effect delta.
Control Variate Approach
Basics:
Y_hat_cv = mean(Y) - theta * mean(X) + theta * EX
where mean(Y), mean(X) denotes sample mean.
With optimal theta = cov(Y, X) / var(X), which is the regression coefficient of Y~X, we have
var(Y_hat_cv) = var(mean(Y))(1-rho^2),
where rho = corr(Y,X).
For online experiment, KEY notes:
1, Assume E(X_t) = E(X_c), then delta_cv = Y_hat_cv^t - Y_hat_cv^c is unbiased estimator of E[delta].
var(delta_cv) = var(delta)(1-rho^2).
2, A natural choice of X will be using the same variable during pre-experiment observation window as the control variable.
3, Estimating theta: estimate it from the pooled population of control and treatment. (Regress Y on X.)
4, Time period:
(1)Given the same pre-experiment period, extending the length of the experiment does not necessarily improve the variance reduction rate. A longer pre-period tends to give a higher reduction for the same experiment period.
(2)As the experiment duration increases, the coverage (percentage of users in the experiment that also appeared in the pre-experiment period) may decrease. Frequent users are seen early in the experiment, and users seen later are often new or "churned" users. Coverage decreases, the rate of variance reduction goes down.
5. Missing Pre-experiment Data: Some users are in the experiment but not in the pre-experiment period, we can define another covariate that indicates whether or not a user appeared in the pre-experiment period.
6. Other covariate: Day-of-week, information established before a user actually triggers the experiment. Note: the covariate should satisfy E(X_t) = E(X_c) and is not affected by the treatment, otherwise some delta part may be explained away by covariate, and result is biased.
7. Non-User Metrics: User as Randomization Unit, Page level metric as the analysis unit, and user level pre-experiment covariate (or page level pre-experiment covariate). Combine delta method and variance reduction together. See Appendix B in the paper.
8,Metric: Variance reduction rate depends on the correlation of the same metric between the experiment and the pre-experiment.
(1) queries-per-user, reduction 45%. Similar for clicks-per-user and visits-per-user.
(2)Revenue-per-user, less than 5% due to low correlation.
(3)Click-Through-Rate (page level) 40% ~50%.
9. Empirical recommendation:
(1)Variance reduction works well for metrics where the distribution varies large across users.
(2)A pre-experiment period of 1-2 weeks works well for variance reduction.
Relation between Stratification and Control Variables: When the covariate X is categorical, the two approaches produce identical estimates.
Meeting Notes:
Investigate the Multicolinearity effect on this approach if we use multiple covariates.
Deng, Xu, Kohavi, and Walker
WSDM' 13
Highlight:
" The results on Bing's experimentation system are very successful: we can reduce variance by about 50%, effectively achieving the same statistical power with only half of the users, or half the duration. "
Review Variance Reduction Techniques:
Kohavi et al (2009) Using different metric, or through filtering out users who are not impacted by the change.
Deng et al. (2011) Use page level randomization at the design stage to reduce variance of page level metrics.
This paper: Controlled-experiment Using Pre-Experiment Data: CUPED
Stratification Approach
Basics:
1, Divide the sampling region into K strata with w_k the probability that Y falls into kth stratum.
2, The sample size for kth stratum is n_k = n * w_k.
3, Stratified average: Y_strat = sum(w_k * Y_bar_k), with Y_bar_k as the average within the kth stratum.
Benefits: Achieving variance reduction, as between-strata variance is removed through stratification.
For online experiment, using Post-stratification: utilize pre-experiment variables to construct strata after all the data are collected.
e.g. using browser type to form strata.
Note that the stratification variable (browser in eg) should not be affected by the treatment (the variable should be independent of the randomization assignment) to guarantee unbiased effect delta.
Control Variate Approach
Basics:
Y_hat_cv = mean(Y) - theta * mean(X) + theta * EX
where mean(Y), mean(X) denotes sample mean.
With optimal theta = cov(Y, X) / var(X), which is the regression coefficient of Y~X, we have
var(Y_hat_cv) = var(mean(Y))(1-rho^2),
where rho = corr(Y,X).
For online experiment, KEY notes:
1, Assume E(X_t) = E(X_c), then delta_cv = Y_hat_cv^t - Y_hat_cv^c is unbiased estimator of E[delta].
var(delta_cv) = var(delta)(1-rho^2).
2, A natural choice of X will be using the same variable during pre-experiment observation window as the control variable.
3, Estimating theta: estimate it from the pooled population of control and treatment. (Regress Y on X.)
4, Time period:
(1)Given the same pre-experiment period, extending the length of the experiment does not necessarily improve the variance reduction rate. A longer pre-period tends to give a higher reduction for the same experiment period.
(2)As the experiment duration increases, the coverage (percentage of users in the experiment that also appeared in the pre-experiment period) may decrease. Frequent users are seen early in the experiment, and users seen later are often new or "churned" users. Coverage decreases, the rate of variance reduction goes down.
5. Missing Pre-experiment Data: Some users are in the experiment but not in the pre-experiment period, we can define another covariate that indicates whether or not a user appeared in the pre-experiment period.
6. Other covariate: Day-of-week, information established before a user actually triggers the experiment. Note: the covariate should satisfy E(X_t) = E(X_c) and is not affected by the treatment, otherwise some delta part may be explained away by covariate, and result is biased.
7. Non-User Metrics: User as Randomization Unit, Page level metric as the analysis unit, and user level pre-experiment covariate (or page level pre-experiment covariate). Combine delta method and variance reduction together. See Appendix B in the paper.
8,Metric: Variance reduction rate depends on the correlation of the same metric between the experiment and the pre-experiment.
(1) queries-per-user, reduction 45%. Similar for clicks-per-user and visits-per-user.
(2)Revenue-per-user, less than 5% due to low correlation.
(3)Click-Through-Rate (page level) 40% ~50%.
9. Empirical recommendation:
(1)Variance reduction works well for metrics where the distribution varies large across users.
(2)A pre-experiment period of 1-2 weeks works well for variance reduction.
Relation between Stratification and Control Variables: When the covariate X is categorical, the two approaches produce identical estimates.
Meeting Notes:
Investigate the Multicolinearity effect on this approach if we use multiple covariates.
No comments:
Post a Comment