interleaving实验: 快速找到最优解;
多臂老虎机: 降低实验成本;
背景
经典统计分析的样本: 农业统计中样本是同时产生的。
在线服务中的样本: 序列样本,在线服务中样本是依次到达的;
利用这个特性,可以有比传统统计分析方法成本更小、更灵活的实验方法。
序列样本环境下的假设检验,在相同显著性和检验力下,经典t检验结束更早,需要样本更少。
Interleaving实验
交错实验
优先确定哪个方案更好,而不是统计出具体效果好多少.
参考: https://zhuanlan.zhihu.com/p/31770319优点: 更少的样本达到与Abtest相同的偏向结果；缺点： 无法知道究竟有多好的效果；（比如A组究竟能提高多少阅读时长）
解决方案
用Interleaving+ABtest两阶段完成整个评估。
要点：抛硬币交错，保证公平。灵敏度： 高于AB；准确度： 与AB有很强的相关性；场景： 排名算法
案例: Netflix的方法
第一阶段: 快速筛选,从众多算法中挑选出最有前途的排名算法;
第二阶段，进行传统的A/B测试,以测量长期效应;
使用条件
- 指标对排序算法的质量非常敏感;
- 对第二阶段进行准确预测：第一阶段衡量的指标与A/B 评估的指标正相关；
指标示例
传统AB指标: 留存、观看时长；
交错测试指标: 观看时长比例；
MAB: 多臂老虎机
What: 什么是多臂老虎机
一种在线实验的方法，特点是兼顾实验结果和实验成本，不会让差劲的方案暴露给用户太久。
在线上进行大规模实验的时候，可能会影响用户体验，从而影响用户留存等关键业务指标。因此我们希望在实验过程中，尽可能降低差方案曝光的频率。为了达到这个目的,大致有两种思路:
思路1: 动态结束;一旦A方案胜出,立即停止实验,采用A方案;
思路2: 非均衡分组;在优势方案下多分配用户.(多臂老虎机)
使用场景: 序列样本/在线服务
背景
Bandit: 老虎机
多臂老虎机问题:
老虎机有N个摇杆,每个得到奖励的概率为p1~pN;
假设可以拉很多次摇杆，使用什么策略可以使总收益最大化?
一种可能的思路
先抽样统计收益较好的摇杆,然后利用统计解决快速调整策略。
也就是分两个阶段:
- 探索规律;
- 利用规律;
汤普森抽样
在每个周期计算”摇杆i是最优摇杆”的后验概率,作为下一个周期随机分配摇杆的依据。
优点: 灵活性、扩展性、保证实验过程坑用户比例最小;
缺点: 没有人公开发表过简单靠谱的停止条件。
PVR: 停止条件的解决方案
google analytics: PVR(潜在剩余价值)。
定义分界线为a,分界概率为b:
P(潜在最优收益>(1+a%)*目前最优收益) < b
google analytics的参数设置是a=0.01,b=0.05,即潜在最优收益比目前最优收益大1%的概率不到5%。
PVR方案的缺点
即使A/B方案没有任何区别,PVR也会导致相当一部分实验在有限时间内终止。
第一类错误的概率随时间延长增加。
scott: 线上实验不需要考虑第一类错误，因为代价极小；而第二类错误是致命的。
案例
谷歌analytics/yahoo/bing: 汤普森抽样的贝叶斯解法
论文: http://quinonero.net/Publications/AdPredictorICML2010-final.pdf
数学要求: 超精深
相关图灵书: 《Bandit Algorithms for Website Optimization》
