[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

[Reading Notes] Overlapping Experiment Infrastructure

Overlapping Experiment Infrastructure: More, Better, Faster Experimentation
KDD 2010
[Google] Tang, Agarwal, O'Brien, Meyer

Conventional experiment infrastructure:
Single layer of experiments: every query is in at most one experiment.
Pros: easy to use, flexible
Cons: insufficiently scalable
Multi-factorial experiment design: each parameter can be experimented on independently.
However, some parameters can not be independent, especially when the number of parameters is large. E.g. blue text cannot be combined with blue background.

Overlapping experiment infrastructure
Advantages: easy to use, speed, scalability, flexibility, robustness, enable gradual ramping-up of launches
Parameter partition: 
parameters from different binaries can be in different subsets, which solves the starvation and bias issues.
all parameters for a given binary do not need to be in a single subset, that can be further partitioned.


Key concepts:
domain: a segmentation of traffic
layer: corresponds to a subset of the system parameters.
experiment: a segmentation of traffic where zero or more system parameters can be given algternate values
Relations: domain contain layers, layers contain experiments and can also contain domains. domains and layers can be nested.
Launch layers are always contained within the default domain (i.e. they run over all traffic).
A parameter can be in at most one launch layer and at most one normal layer (within a domain) simultaneously.
Alternative default values of parameters can be specified in launch layer.
Order of adopting parameter values (if specified in higher order, lower order values will be ignored):
Normal experiment layer parameter > Launch layer default value > system default value
Usage of the Launch layer: 1, gradually roll out changes to all users and to delete that layer when the feature is fully rolled out. 2, experiments in launch layers are generally larger, they can be used to test for interactions between features.

Traffic diversion types:
cookie-mods
random traffic
user-id mods
cookie-day mods: combine the mod of the cookie with the day, the set of cookies in an experiment changes from day to day.
Divert order: user id, cookie, cookie-day, random traffic

After diverting traffic, conditions provide better utilization of this traffic by only assigning specific events to an experiment or domain.
Google supports conditions based on country language, browser, etc.
Usage: 1, for particular population, e.g. Japan users; 2, canary new code, test new code on a small amount of traffic.

Biased / Unbiased traffic
If we take all traffic corresponding to a particular cookie mod, it is unbiased.
If after condition, take the rest of the traffic for subsequent diversion types, it is biased traffic. This should be avoided. Tagging the unassigned traffic with a biased id.

Other topics covered by this paper:
Procedure of evaluating and launching a typical feature (end of section 4)
sample size 5.2.1
triggering, logging, counter-factuals 5.2.2
pre-, post-periods (A/A test) 5.2.3


"Each binary has an associated binary push and data push."
Question: What is binary? Is that a program block? The output seems not a binary one.

[Reading Notes] Practical Guide to Controlled Experiments on the Web

This post is a summarizing notes on the following paper:

Practical Guide to Controlled Experiments on the Web: Listen to Your Customers not to the HiPPO

KDD 2007
[Microsoft] Kohavi, Henne, Sommerfield


Controlled experiments, are also called randomized experiments (single-factor or factorial designs), A/B tests (and their generalizations), split tests, Control/Treatment, and parallel flights.
Controlled experiments can be used for testing causal relationships.

Terminology
Overall Evaluation Criterion (OEC): A quantitative measure of the experiment's objective. A good OEC should not be short-term focused; it should include factors that predict long-term goals, such as predicted lifetime value and repeat visits.
Factor (or Variables): A controllable experimental variable that is thought to influence the OEC.
Variant: A user experience being tested by assigning levels to the factors; it is either the control or one of the treatments.
Experimentation Unit: On the web, the user is the most common experimentation unit.
Null Hypothesis: H0: the OECs for the variants are not different.
Confidence Level: The probability of failing to reject (i.e., retaining) the null hypothesis when it is true. Commonly 95%.
Power: Pr(rejecting H0 | H0 false). Commonly desired to be around 80%-95%.
A/A Test. Purpose: (1) collect data and assess its variability for power calculations; (2) test the experimentation system (H0 should be rejected about 5% of the time if CL=95%).

Standard Error Reduction 
1, Increasing sample size.
2, Use OEC components that have inherently lower variability. Eg, rate vs count.
3,Lower the variability of the OEC by filtering out users who were not exposed to the variants, yet were still included in the OEC.

Sample Size
5 Affecting factors:
Confidence level, desired power, standard error, the effect, number of variants,
Formula: E.g. CL=95%, Desired Power = 90%, then
n=(4r sigma / delta)^2
where n: sample size; r: number of variants (assumed to be approximately equal in size); sigma: std-dev of the OEC; delta: minimum difference between the OECs.
Note: for large n, the factor of 4 may over estimate by 25%.

Adjustment for familywise type I error
Fisher's least-significant difference
Bonferroni adjustment
Duncan's test
Scheffe's test
Tukey' test
Dunnett's test

Extensions for Online Settings
Treatment Ramp-up
A/B test, may start with 99.9%/0.1% split, then ramp up the treatment from 0.1% to 0.5% to 2.5% to 10% to 50%. For each step, it could run for a couple of hours that allow the data analysis tell whether there is egregious problems.

Automation
Run experiments to optimize certain areas amenable to automated search. For example, if the cost of mistakes is low, decisions can be made quickly with lower confidence levels.
algorithm: Multi-armed bandit algorithm, Hoeffding Races

Software Migrations
The goal here is to retain the Null Hypothesis to make sure two versions are consistent.

Limitations
1. Quantitative Metrics, but no explanations.
2. Short term vs. Long term effects
3. Primacy and Newness effects. Primacy effect: experienced users may be less efficient until they get used to new version (e.g. navigation). Newness effects: When new design or feature is introduced, some users will investigate it and click everywhere. Both primacy and newness concerns imply that some experiments need to be run for multiple weeks. One analysis that can be done is to compute the OEC only for new users on the different variants, since they are not affected by either factor.
4.Features must be implemented.
5.Consistency. Same users say the same version.
6.Parallel experiments. (for experiments containing possible interactions.) Authors' experience is that strong interactions are rare in practice. Pairwise statistical tests can also be done to flag such interactions automatically.
7.Launch events and Media announcements. Then all users need to see it.

Implementation Architecture
Randomization Algorithm
A good randomization algorithm should have 4 properties:
1, Users must be equally likely to see each variant of an experiment.
2,Repeat assignments of a single  user must be consistent.
3,When multiple experiments are run concurrently, there must be no correlation between experiments.
4,The algorithm should support monotonic ramp-up.

Pseudorandom with caching
Good pseudorandom number generator satisfies 1,3.
Cashing satisfies 2.
4 is particularly difficult to implement using this method. The authors have not seen a system using pseudorandom-based assignment that supports ramp-up.

Hash and partition
Hash functions may not satisfy 1,3 if not good enough
Any hash function will satisfy 2, but satisfying 1,3 is more difficult.
Hash functions: MD5 no correlations, SHA256 came close, .NET string failed to pass even a two-way interaction test.

Question: 
Now, is there a good pseudorandom with caching method supporting 4 (monotonic ramp-up)?
How does hash and partition support this feature?

Assignment Method
Traffic splitting
Implementing each variant on a different fleet of servers.
Server-side selection
API calls embedded into the servers invoke the randomization algorithm.
Client-side selection
JavaScript calls embedded into each web page. Easier to implement. But this method severely limits the features that may be subject to experimentation, e.g. dynamic content or backend features.


Analysis
Mine the Data
Rich data is typically collected that can be analyzed using machine learning and data mining techniques.
Speed Matters
Test one factor at a time (or not)

Trust and Execution
Run Continuous A/A Tests
Automate Ramp-up and Abort
Determine the minimum sample size
Assign 50% of users to treatment. C/T: (1-p)/p compared with 50%/50%, 1/(4p(1-p)) running time. e.g. 99%/1%, run about 25 times longer than if it ran at 50%/50%.
Beware of Day of Week effects

Culture and Business 
Agree on the OEC upfront
Beware of launching features that "do not hurt" users
Weigh the feature maintenance costs
Change to a data-driven culture.