[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.