AB实验中指标协方差及其应用

1 AB实验简介

1.1 随机对照实验(AB Testing)

AB实验是一种衡量新功能对用户影响的方法。如上图所示，一个典型的AB实验将随机采样两组用户，分别称为A组和B组，其中B组用户能看到新功能，而A组用户看不到新功能。经过一段时间后，实验者通过对比AB两组用户的实际表现，做出实验结论。

在对比AB两组用户的实际表现时，通常会采取一些严谨的统计学方法，比如假设检验。以对比AB两组的人均停留时长为例，如果我们观测到B组的人均停留时长比A组要长，这有可能是因为新功能带来的结果。但是因为采样具有随机性，这也有可能是采样的随机波动导致，如何区分这两者呢？我们可以先假设新功能不影响人均停留时长，那么AB两组的差异会服从一个均值为0的正态分布，如下图所示：

如果这个假设是正确的，那么我们应该有很大概率观测到AB组的人均停留时长差异在0附近。换句话说，如果我们观测到这个差异距离0比较远，比如在两倍标准差之外，这只有很小的概率（5%）发生，那么我们可以理所当然地认为，这个假设大概率是错误的。这时候，我们称之为我们拒绝了这个假设，而拒绝假设的这个概率阈值（5%），也叫做假设检验的显著性水平（alpha）。

1.2 随机实验的数学框架：潜在结果模型

潜在结果模型(Rubin causal model)从数学上定义了因果效应。可以用来解释随机实验的基本原理。在这个模型下，被实验的对象在不同的实验策略下有不同的潜在结果(Potential outcomes)。比如，每个用户在A组(control)和B组(treatment)下，有对应的停留时长Y，用如下的表格表示：[以下相关表格引用自Wikipedia](https://en.wikipedia.org/wiki/Rubin_causal_model#Potential_outcomes)

这里，模型假设任何一个人的Potential outcomes不受其他人是否接受处理(Treatment)的影响，也就是说，不管其他用户被分配到A组还是B组，当前用户的Potential outcomes都是不变的，这个假设被称为STUVA：Stable unit treatment value assumption。

当实验运行一段时间后，我们可以观测到每个用户的部分Potential outcome，比如，对于被分配在B组的用户，我们观测到了他们的Yt，A组用户则相反。最终我们观测到的数据会如下表所示：

其中问号部分是没有观测到的Potential outcomes。可以发现，对于任何一个用户来说，我们只能观测到他在A组或者B组的结果，无法知道策略对他的影响具体是多少。因此，在随机实验中，我们推断的是总体的平均因果效应(或者叫平均处理效应，Average treatment effect, ATE)，而不是每个用户各自的效果。

为什么ATE是可以推断的呢？这里有一个前提条件：参与随机实验的用户是否被分到B组，需要和用户的Potential outcomes独立（作为一个反例，我们可以思考一下，如果我们选取AB组用户时不遵循这个独立原则，而是特意挑选在实验策略下outcome大的用户进入B组，同时特意挑选在对照策略下outcome小的用户进入A组，此时AB组的差异会明显被拉大，这样的对比是不公平的）。这往往通过随机采样的过程来实现，比如对于每个用户，我们通过投掷一枚均匀的硬币来决定是否将当前用户分到B组，此时，AB组的均值差是对ATE的一个无偏差的估计。

2 指标和指标协方差

2.1 简单指标

沿用上一节中的例子，在一次随机实验中，我们将每个用户分到了AB两个组，用I(u)表示对用户分组的结果，1表示B组(Treatment=1)。用Y(u)表示用户u的观测结果。我们可以对B组定义一种求和形式的指标，比如B组用户的总停留时长：

这样形式的指标，我们称之为简单指标。在随机采样条件下，对于所有的u，I(u)变量是独立同分布的，因此可以应用中心极限定理[Lindeberg CLT](https://en.wikipedia.org/wiki/Central_limit_theorem)。从而得到结论：在总体用户数量足够大时，任意的简单指标都近似服从一个如下的正态分布：

2.2 从简单指标到复杂指标

现实场景中，往往我们关心的除了简单指标，还有更复杂的指标形式，比如人均停留时长，就无法写成简单指标的形式。好在大多数时候，复杂指标都可以用简单指标表达出来，例如人均停留时长，就可以写成两个简单指标的比值，其中分母部分是B组命中的总用户数。

这样的复杂指标，由简单指标组合而成。而且，我们可以看到，这样的复杂指标可以近似写成简单指标的线性组合。得益于简单指标的良好性质（正态分布），复杂指标也满足这样的正态性质。推导过程可以参考下图：

2.3 指标的协方差

协方差是对随机变量相关性的一种度量。从上面的分析可以看到，实验的某个组的指标实际上也是一个随机变量，它的随机性来自于该组随机选取用户的过程。而指标的协方差，衡量了指标之间的相关程度，比如，曝光量这个指标，和点击量是明显有相关性的，因为曝光之后才可能发生点击行为。而这两个指标的协方差，给出了它们之间的相关性的一个定量的描述。协方差在很多统计方法中有着重要的应用，这些应用将会在下一节进行描述。

接下来，我们给指标协方差给一个具体的定义。对于实验某个组的任意两个指标m1和m2（可以是简单指标或是复杂指标，它们都可以写成多个简单指标的线性组合）：

我们想要估计它们之间的协方差，而协方差具有如下的线性性质：

将Cov[m1, m2]用上面的性质展开后，实际上我们只需要估计简单指标之间的协方差（Cov[Si, Sj]）就可以了。这会简化我们要解决的问题。

3 指标协方差的应用场景

3.1 假设检验中的方差估计

在假设检验的场景中，为了判断我们观测到的AB组差异是否在2倍标准差之外，我们需要对指标的标准差（也就是方差的平方根）进行估计。而指标的方差，就是指标自己和自己的协方差。这是一个特殊的协方差估计的问题。

3.2 方差消减

CUPED[1]是一种普适性很广，效果优越的方差消减方案，其原理为：

1. 对于任意指标M，使用实验开始前的历史数据进行回溯得到回溯指标P

2. 构造新的统计量Y=M+βP， β是一个待定的常数

3. 原指标M的AB两组的差异为：delta_m=MB-MA

4. 新统计量X的AB两组的差异为：delta_x= XB-XA=MB-MA+ β(PB-PA)

5. E(delta_x)=E(delta_m)，因此新统计量的差异和原指标的差异在期望上是相等的，我们可以通过比较新统计量来推断原指标在AB组的差异

6. 对于任意一个组，Var(X)=Var(M)+β2Var(P)-2βCov(M,P)，在β=Cov(M,P)/Var(P)时取到最小值

为了使得新统计量的方差达到最小值，我们需要估计指标M和P之间的协方差Cov(M,P)

3.3 持续观测

持续观测是这样一种场景：随着实验的进行，我们不断地观测到指标数据点，记为M1,M2,…,Mn（比如Mi表示第i天的指标结果），在观测新数据的同时进行统计推断（得到结论并停止 or 继续观测）

一个典型的模型：Bayes Factor[2]，在该模型中，我们需要计算在给定假设H0和假设H1下，数据的似然：

似然的计算：

对于指标M，假设每天观测一次，每次观测得到当天的指标数据，记为M1,M2,M3…

由于大多数场景下按照用户分流，观测到的数据点会有相关性。

(M1,M2,M3…)渐进意义上是一个多维正态分布。

利用多维正态分布进行似然计算，需要估计(M1,M2,M3…)的协方差矩阵。

3.4 贝叶斯优化

贝叶斯优化[3]（上图引用自[Ax.dev](https://ax.dev/docs/bayesopt.html)）：

1. 给定一个目标指标obj(x)，对参数x进行优化，使得obj(x)尽可能最优

2. 模型(Gauss Process)会给出参数空间每个x下，目标指标的预测结果

3. 不断迭代，每次迭代会选择下一个需要探索的点

4. 对被探索的点收集数据，更新模型的预测结果

5. 现实场景中，被优化的指标可能是一个由多个指标复合组成的复杂指标obj(x)=a*f(x)+b*g(x)，估计目标指标的方差时需要考虑指标之间的协方差：Var(obj)=a^2*Var(f(x))+b^2*Var(g(x))+2ab*Cov[f(x),g(x)]

3.5 FDR control under dependence

1. 单个指标的检验，犯第一类错误的概率为5%

2. 针对多个指标的多次检验，存在至少一个第一类错误的概率膨胀，可能远大于5%

3. FDR control用于控制多次检验下的False Discovery Rate，常用的有BH方法[4]

4. 近年有方法[5]考虑了同时检验的多个指标之间的相关性，可以相比BH方法提高power，该方法需要对多个指标的协方差矩阵进行估计

4 指标协方差的估计

4.1 朴素方法

以估计人均指标的协方差为例，X和Y是两个人均指标，比如人均停留时长和人均曝光内容数。红色是采样到实验某个组的用户。(注：本章节中停留时长和曝光feed数等数据都是虚构的用户数据)

对于实验某个组而言，进组的人是从总体人群中随机无放回地抽取的。在进组流量较小的情况下，我们可以近似认为这是有放回地抽取（流量较小时，每次抽取后，对总体的影响都很小）。这样一来，进组的样本近似是独立同分布(i.i.d.)的。

对于独立同分布的样本，我们可以用朴素的样本协方差估计量来估计X和Y的协方差，从而得到对应人均指标的协方差：

4.2 数据增广[6]

某些情况下，朴素方法无法处理如下的data missing问题：

在上面的场景中，我们想要估计停留时长和昨天的停留时长之间的协方差。但是有些用户不一定两天都来过，从而导致了部分数据的丢失。此时朴素方法由于丢失的数据而无法进行样本协方差的估计。如果只选取两天都来的用户进行朴素估计，那么可以想象得到，这部分用户明显是更活跃的用户，这样计算出来的协方差可能是不准确的。

为了解决这个问题，数据增广方法给没来的用户补了一个0值：

同时引入两个指示变量Ix和Iy表示用户在对应指标下有没有数据，I=1表示用户在对应指标下是有数据的。那么需要估计的目标为：

问题转换为估计两个复合指标的协方差，而这两个复合指标都可以写成两个人均指标的比值。比如sum(x)/sum(Ix)，可以写成avg(x)/avg(Ix)。类似我们在前面处理复杂指标的方法，应用Delta method[7]，我们可以把问题进一步转换为没有数据丢失的人均指标的协方差估计问题，然后用上一节中的朴素估计方法进行处理。

4.3 基于分桶的高效估计方法

上面的方法有一个共同的特点：计算是在用户粒度进行的，依赖用户级别的指标数据拼接。

现实情况下，实验组数量多，平均命中的用户量大；同时，指标数量多，口径复杂，来源于大量不同的数据源；以上方法的性能开销比较大。

为了解决性能开销的问题，我们引入了一个对用户进行随机分桶的过程：

分桶之后，我们可以基于分桶结果计算桶粒度的样本协方差：

我们可以证明[8]任意两个简单指标之间的协方差可以通过如下的式子进行估计：

在前面的章节中提到过，一旦解决了简单指标的协方差估计问题，复杂指标的协方差估计问题也就解决了。同时，基于分桶结果的计算开销取决的分桶的个数，这是一个可以灵活调整的数量。当我们需要更好的性能时，可以使用更少的分桶数，当然，这也牺牲了准确性。具体的测试结果我们在后面进行描述。

4.4 一个实际例子：Clickhouse指标性能优化

在真实的业务系统中，我们将指标明细数据按天存储在clickhouse中：

在进行指标的分析时，我们需要计算多天累计数据的一些结果，来进行假设检验，用sql来描述的话如下图：

分桶方案去掉了上面sql中按uid进行的group by操作，转而用桶号进行group by，性能更好[9]：

5 一些测试数据

5.1 协方差估计的性能和准确性测试

表一展示了不同协方差估计算法的效果，可以看到随着分桶个数B的增大，估计的准确性（SD列，表示多次估计的标准差，越小越好）增加了。而朴素方法在有数据丢失的情况下，直接使用没有丢失数据的用户样本进行估计，得到了错误的结果（Avg列，表示多次估计结果的均值，越接近Ground Truth越好）

表二展示了实验抽样比例对数据增广方法的影响，从表一中可以发现，数据增广方法的结果和Ground Truth存在一定的差异，这个差异是因为我们在小流量下将样本看成是近似独立同分布的，但是在流量变大后，这个近似变得不那么好，从而影响估计的结果。在下表中，随着实验流量（Ratio）的增大，数据增广方法的结果偏差越来越大，而分桶方法没有做这个近似，不存在这个问题

5.2 方差消减

表三展示了在不同的相关性下(相关系数取0.3到0.8的不同数值)，不同分桶数目下，方差消减方法所估计出的最优系数β的相对误差。可以看到分桶数越多，相关性越强，β的估计越准

5.3 持续观测

通过多元高斯分布生成non-iid的数据，对数据用Bayes Factor模型进行持续观测，统计FDR结果。

表四展示了用不同方法进行持续观测时，FDR的膨胀情况，FDR列的数值小于0.1为好，同时Power列的数值越大越好。

1. 不考虑相关性，FDR膨胀79%，从0.1增大到0.179

2. 用真实的协方差矩阵计算似然，FDR得到控制（0.079）

3. 用分桶方法估计协方差矩阵，FDR基本得到控制，在0.1附近，没有膨胀太多

5.4 贝叶斯优化

1. 两个指标f和g，对obj(x)=a*f(x)+b*g(x)进行贝叶斯优化

2. 分别模拟f和g具有正相关性和负相关性两种场景

蓝色曲线表示考虑指标协方差之后的优化过程，相比不考虑指标相关性的红色曲线，蓝色曲线更快更好地逼近了最优结果（位于-10位置的浅蓝色水平线）

6 总结

以上所有测试的代码均可在如下仓库找到并复现

https://github.com/xt2357/covariancesimulation

1. 指标协方差是指标相关性的度量，能够广泛应用于各种场景

2. 基于用户粒度计算的协方差性能开销较大

3. 分桶协方差估计方法可以在性能开销和精度之间进行权衡：

    3.1 每个指标可以灵活地独立计算分桶数据备用

    3.2 需要评估相关性时，取出分桶数据，基于桶进行协方差估计

    3.3 桶数越大，精度越高，性能越差

    3.4 针对不同的场景，选择一个合适的桶数，达到性能开销和精度之间的平衡

7 引用

[1] A. Deng, Y. Xu, R. Kohavi, and T. Walker, “Improving the sensitivity of online controlled experiments by utilizing pre-experiment data,” in Proceedings of the sixth ACM international conference on Web search and data mining, 2013, pp. 123–132.

[2] Deng A, Lu J, Chen S. Continuous monitoring of A/B tests without pain: Optional stopping in Bayesian testing[C]//2016 IEEE international conference on data science and advanced analytics (DSAA). IEEE, 2016: 243-252.

[3] Letham, B., Karrer, B., Ottoni, G., & Bakshy, E. (2019). Constrained Bayesian optimization with noisy experiments.

[4] https://en.wikipedia.org/wiki/False_discovery_rate#Benjamini%E2%80%93Hochberg_procedure

[5] Fithian, W., & Lei, L. (2022). Conditional calibration for false discovery rate control under dependence. The Annals of Statistics, 50(6), 3091-3118.

[6] Deng A, Knoblich U, Lu J. Applying the Delta method in metric analytics: A practical guide with novel ideas[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 233-242.

[7] https://en.wikipedia.org/wiki/Delta_method

[8] https://arxiv.org/pdf/2108.02668.pdf

[9] https://clickhouse.com/docs/en/sql-reference/statements/select/group-by/#group-by-optimization-depending-on-table-sorting-key