[Reading Notes] Variance Reduction - Utilizing Pre-Experiment Data

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.

[Reading Notes] How long should experiments run for? - Dynamic p-value threshold

Experiments at Airbnb
http://nerds.airbnb.com/experiments-at-airbnb/

How long should experiments run for? 
1, Power calculation. Here is a resource that helps with that computation. 
2, See the trend of delta or p-value overtime, and determine whether it converts, rather than to consider the single result of an effect with a p-value. Then make conclusion.
3, When the results are extremely good/bad, may terminate early. 
Be skeptical of early results
4, Dynamic p-value threshold. 

"We solved the problem of how to figure out the p-value threshold at which to stop an experiment by running simulations and deriving a curve that gives us a dynamic (in time) p-value threshold to determine whether or not an early result is worth investigating. We wrote code to simulate our ecosystem with various parameters and used this to run many simulations with varying values for parameters like the real effect size, variance and different levels of certainty. This gives us an indication of how likely it is to see false positives or false negatives, and also how far off the estimated effect size is in case of a true positive. In Figure 6 we show an example decision boundary."

[Reading Notes] 5 Online Experiment Puzzling Cases

Trustworthy Online Controlled Experiments: Five Puzzling Outcomes Explained.
KDD 2012
Kohavi, Deng, Frasca, Longbotham, Walker, Xu

Rate of Success
1/3: One third of ideas tested at Microsoft improved the metric(s) they were designed to improve.
10%: Google ran approximately 12,000 randomized experiments in 2009, with only about 10 percent of these leading to business changes.
10%: Netflix considers 90% of what they try to be wrong.
33% guess to be true: Regis Hadiaris: I've been doing this for 5 years, and I can only "guess" the outcome of a test about 33% of the time.

Puzzling case 1 The OEC (Overall Evaluation Criterion) for Search Engine
Puzzling outcome: Poor searching results lead to two metrics improved significantly: Distinct queries per user, Revenue per user.
Why? Inappropriate OEC.
Explaination:
Revenue per user: When poor search results show, the relative relevance of ads increases, so users click more on ads. Revenue per user should not be used as an OEC for search and ad experiments without other constraints. We want this OEC increase without negatively impacting engagements metrics like sessions/user.
Distinct queries per user = Distinct queries per session * Sessions per user: Distinct queries per task should be minimized, but it is hard to measure. Distinct queries per session is subtle. Increasing it may indicate more queries are needed to complete a task, and decreasing it may indicate abandonment. This should be minimized subject to the task being successfully completed. Sessions per user is the key metric to optimize the experiments, as satisfied users will come more. (Tasks per user is preferrable but it is hard to measure.)
Solution:
Using Sessions per user as OEC.
In addition, we can do: minimizing distinct queries per user conditional on task completed, maximizing revenue per user conditional on no negative impact on long-term user value.
Lesson: Short term metrics can be inconsistent with long term goal.

Puzzling case 2 Click Tracking
Puzzling outcome: An additional code was added that slowed down the user experience slightly, but the experiment showed that users were clicking more.
Why? No real difference, but rather an instrumentation difference. Click-beacons have more chance to be sending back for additional time.
Explanation: Most sites use web beacons to track user actions, but returning the clicks and submits slows the next action. Chrome, Firefox, and Safari are aggressive about terminating requests, when navigating away from the current page. A non-negligible percentage of click-beacons never make it to the server. Adding a small delay gives the beacon more time, and more click request beacons reach the server. That is why the experiment showed users were clicking more.
Solution: IE continues to execute image/beacon requests even after navigation, that makes click tracking more reliable.
Lesson: Browsers can cause difference due to instrumentation issues or differences in HTML/JavaScript parsing.

Puzzling case 3 Initial Effects Appear to Trend

Puzzling outcome: The first few days' effect seems like a trend, like the figure above. Can we expect the next outcome to be positive? NO. (It is actually an A/A test.)
Why? This is not a trend, but rather caused by shrinking of the variance (and confidence interval), and cumulative effect.
Explanation: The effects in the initial days usually seem overly positive or negative, due to relatively small sample size, even if there is no real difference. During the first few days, the cumulative results seem to trend. It is rare that the Primacy effects reverse the initial effects (Effect is initially negative, when the user gets used to it, becomes positive).
Solution: High variance means that we need to collect enough data to get better estimates; early results are often misleading.
Lesson: Initial effects don't mean trend. Collect enough data to make inference.

Puzzling case 4 Experiment Length and Statistical Power
Puzzling outcome: For some of the key metrics, including Sessions/user (or the percent change of this metric), running the experiment longer does not provide additional power.
Why? Due to change of s.d. and mean over time for these metrics.
Explanation: Given the sample size and population variance are the same for treatment and control group, the width of the confidence interval for percentage change is roughly proportional to
  CV/sqrt(sample size)
CV = S.D. / Mean
If CV is constant over time, then CI shrinks over time. If CV changes over time, e.g. for sessions/user (both S.D. and mean increase),  CI may not shrink and power may not increase.
Solution: When looking at these metrics, we must run the experiments with more users per day. (Running experiment with more users per day is different from running longer.) Even running the experiment longer does not increase power, we should still run the experiment more than a week, for day-of-week effects, and primacy and novelty effects (through rare).
Lesson: For metrics, we need investigate whether the S.D. and mean will change over time. And if so, it means running the experiment longer will not necessarily provide additional power. Including more users per day is suggested.
Question: So, does the CV change over time for percentage change of Sessions/user?

Puzzling case 5 Carryover Effects
Puzzling outcome: For bucket experiment, some unrelated metrics may be significant, but rerunning the experiment will find these effects disappeared.
Why? These effects are carried over from the previous experiment done in the bucket.
Explanation: Carryover effect is one big drawback of the bucket system: the same users who were impacted by the first experiment are being used for the follow-on experiment.
Solution: A/A test can be used to check for carryover effects.
One way to solve the issue is by local randomization.
(1) Re-randomizing users by changing the hashing function. But we need to stop all running experiments in that bucket line to change the hashing function.
(2) Two-level bucket system. Only re-randomizing on a subset of buckets by changing the hash function seed at second level. Drawback: can't use a shared control, each experiment needs its own control. Benefit: Retrospective A/A experiment. By changing the hashing function, the experiment running previously can be evaluated as an A/A experiment for the later A/B experiment. If A/A experiment shows an effect for key metrics, then change the hashing key and retry.
Lesson: Beware of the carryover effect by bucket system. Two-level bucket system is suggested for solving the issue.

Two themes
1. Instrumentation is not as precise as we would like it to be. Click tracking.
2. Offline experiments don't always map well online. Carryover effects, confidence intervals don't shrink by extending the duration and number of users.

[Reading Notes] Randomization Unit and Analysis Unit

Choice of the Randomization Unit in Online Controlled Experiment
Deng, Longbotham, Walker, Xu

Summary
This paper discusses pros and cons of choosing User / Page view as Randomization unit / Analysis unit. Choosing user as randomization unit can deliver consistent experience for users. Choosing page view as randomization unit reduces the variance and achieves better power for analysis, but it loses availability of many user level metrics, such as sessions per unique user, page loading time per unique users, etc.
This paper derives the asymptotic variance for different scenarios with User / Page view as Randomization unit / Analysis unit.

Key Concept:
Randomization Unit: In a randomized experiment, we call the unit on which randomization is performed the randomization unit.
Analysis Unit: In analysis phase, a metric will be naturally associated with an unit, which we call it analysis unit.

User and Page view are mostly used Randomization Unit and Analysis Unit.

Variance Analysis:
Suppose X_ij is the per-page measurement on user i's jth pageview.
i = 1,...,n; j=1,...K_i
X_ij ~ (u_i, sigma^2_i)
Consider the t-test statistic:
(mean(X_T) - mean(X_C))  /  sqrt(Var(mean(X_T) - mean(X_C)))

Randomization Unit: User + Analysis Unit: User
Simulation model: Draw (u_i, sigma^2_i) for each user, and draw X_i ~ (u_i, sigma^2_i).
mean(X_T) = mean(X_i for i in Treatment group)
The test is Regular t-test
mean(X_T) and mean(X_C) are independent
Var(mean(X_T) - mean(X_C)) = Var(mean(X_T)) - Var(mean(X_C))
Var(mean(X_T)), Var(mean(X_C)) can be estimated by sample variance.

Randomization Unit: User + Analysis Unit: Pageview
Simulation model: Draw (u_i, sigma^2_i) for each user, and draw X_ij ~ (u_i, sigma^2_i) i.i.d.
mean(X_T) = mean(X_ij for i in Treatment group, j=1,...,K_i)
Note that X_ij are independent conditioned on (u_i, sigma^2_i).
mean(X_T) and mean(X_C) are independent.
Var(mean(X_T)), Var(mean(X_C)) can be estimated by direct method (asymptotically biased) or Delta method (asymptotically unbiased).
Theorem 1
n * Var (mean(X)) -> C Var(u_i) + E(sigma^2_i) / E(K_i)
where C = E(K_i^2)/(EK_i)^2.
C Var(u_i): user effect, between user variance.
E(sigma^2_i) / E(K_i): Variance not explained by user effect, within user variance.
When EK_i large, between user variance will dominate.

Randomization Unit: Pageview + Analysis Unit: User
Not applicable. All page views are randomly divided into different groups. Since the data for the same user will be split into both treatment group and control group. It is not designed to make inference on user level.

Randomization Unit: Pageview + Analysis Unit: Pageview
Simulation model 1 (no user effect):
All page views from all possible users are randomly divided into different groups. Treat page view level measurement as i.i.d., since the page views are drawn from all users and no user selection variance is induced in this randomization scheme.
Given the i.i.d. page view level measurements, analysis is straightforward. - Regular t-test.

Simulation model 2 (user effect as random effect):
Two Layer Randomization Framework
First draw n users (like random effect); Then generate page view level measurements and divided into different groups.
User variance will show up for both within-group variance and between-group variance.
mean(X_T) = mean(X_ij for (i,j) in Treatment group)
mean(X_T) and mean(X_C) are NOT independent, since they come from common users.
Within each group, the variance can be estimated by the same way (taking the same form) as User + Pageview by direct method or Delta method.
Theorem 5
n * Var (mean(X_1) - mean(X_2)) -> (1/EK_i(1) + 1/EK_i(2)) (Var(u_i) + E(sigma^2_i))
Asymptotically unbiased estimator: direct_estimator(Var (mean(X_1)))  + direct_estimator(Var (mean(X_2)))

Interesting observation:
For variance estimator, 
Under Randomization Unit: User + Analysis Unit: Pageview, 
Delta  is asymptotically unbiased
Direct method is asymptotically biased
Under Randomization Unit: Pageview + Analysis Unit: Pageview, with two layer model
Delta  is asymptotically biased
Direct method is asymptotically unbiased