Peeking at A/B test——Optimizely解

2020-08-28 本文已影响0人老姚记事本

Optimizely通过mSPRT理论的扩展，提供了时时有效的P值与置信区间，解决了ab实验中的偷看问题。

1. 定义

单样本：
$\theta_{0}$ 已知， $X = (X_{iid,n})_{n=1}^{\infty} \sim F_{\theta }$ 。
$H_{0}: \theta = \theta_{0}$
$H_{1}: \theta \neq \theta_{0}$

双样本：
X、Y独立同分布。
$H_{0}: \theta = \mu ^{B} - \mu ^{A} = 0$
$H_{1}: \theta \neq 0$

判决条件：
$(T, \delta )$ ， $T$ 为结束时间(样本量)，允许为 $\infty$ ， $\delta=1$ 代表拒绝原假设。

2. 始终有效推断

为了解决偷看，需要始终有效。

2.1 始终有效的P

任意时间T，满足：
$\forall s\ \epsilon\ [0,1],\ \mathbb{P}_{\theta _{0}}(p_T \leq s) \leq s$

2.2 始终有效的贯序检测

依靠样本数据决策样本量。

判决条件：
$(T(\alpha), \delta(\alpha) )$

$\mathbb{P}_{\theta _{0}}( \delta(\alpha) = 1) \leq \alpha$
$T(\alpha),\delta(\alpha)$ 不会影响 $\alpha$ 水平

2.3 置信区间

对 $\theta = \widetilde{\theta}$ 来说，如果 $p_{n}^{\widetilde{\theta}}$ 始终有效， $I_{n} = \{\theta: p_{n}^{\theta} > \alpha\}$ 就是始终有效的 $1-\alpha$ 水平置信区间。

3. 构造始终有效的P

Optimizely通过混合贯序检验(mSPRT)构造始终有效的P值。

3.1 混合贯序检验(mSPRT)

H为 $\Theta$ 上的混合分布，概率密度函数为h。计算H的似然比除以 $\theta_{0}$ 的似然比：
$\Lambda _{n}^{H,\theta _{0}} = \int _{\Theta }\prod_{m=1}^{n}\frac{f_{\theta}(X_{m})}{f_{\theta_{0}}(X_{m})}h(\theta)d\theta$

mSPRT判断流程：
选择 $\alpha$ ，则拒绝原假设条件为 $\Lambda_{T}^{H,\theta_{0}} \ge \alpha^{-1}$ ，此时 $T = T^{\alpha}$ 。
详细原理参照文末。

3.2 mSPRT的P值与置信区间

$p_0 = 1;\ p_n=min\{p_{n-1},1/\Lambda _{n}^{H,\theta _{0}}\}$
$I_0 = \Theta,I_n = I_{n-1}\cap \{\tilde{\theta}: \Lambda _{n}^{H,\tilde{\theta}}\ge \alpha^{-1}\}$

如果数据自正态分布 $N(\theta, \sigma^2)$ ，且混合分布 $H = N(\theta_0, \tau^2)$ ，则

$\Lambda _{n}^{H,\theta _{0}} = \frac{\sigma}{\sqrt{\sigma^2 + n\tau^2 }} exp\{\frac{n^2\tau^2(\bar{X}_{n} - \theta_0)^2}{2\sigma^2(\sigma^2 + n\tau^2)}\}$

3.3 mSPRT扩展到A/B

定义 $Z_n = Y_n - X_n \sim N(\theta, 2\sigma^2)$ ，并对其做mSPRT检测，则：

$\Lambda _{n}^{H,\theta _{0}} = \sqrt{\frac{2\sigma^2}{2\sigma^2 + n\tau^2 }} exp\{\frac{n^2\tau^2(\bar{Y}_n - \bar{X}_{n} - \theta_0)^2}{4\sigma^2(2\sigma^2 + n\tau^2)}\}$

对于0/1型数据， $\bar{Y}_n - \bar{X}_n$ 近似于正态分布 $N(\theta, V_n/n)$ ， $V_n = \bar{X}_n(1-\bar{X}_n) + \bar{Y}_n(1- \bar{Y}_n)$ ，则：

$\Lambda _{n}^{H,\theta _{0}} = \sqrt{\frac{V_n}{V_n + n\tau^2 }} exp\{\frac{n^2\tau^2(\bar{Y}_n - \bar{X}_{n} - \theta_0)^2}{2V_{n}(V_n + n\tau^2)}\}$

3.4 实现细节

对于一些连续性指标，比如“付费”（严重右斜）使用正态分布是不合适的，需要其它更适应这种偏斜的分布。
由于为了保证单调性，可能导致后期 $\bar{Y}_n - \bar{X}_n$ 跑出置信区间，此时Optimizely会重置显著性。这样的做法只会让p值更大、置信区间更宽，不会增加假阳性错误，但是可能增大假阴性错误。

4.回归测试

假阳性错误已知被控制了，但是假阴性怎么样？Optimizely进行了一些优化和测试。

4.1 优化

实验者不会永远等待，因此有最大等待样本量M。
经过Optimizely验证，带M截断的mSPRT比一般的假设检验平均花费更少的样本量。

4.2 混合分布的选择

之前选择了混合分布为 $H = N(\theta_0, \tau^2)$ 。对于混合分布如何选择，没有现存的理论指导。
Optimizely选择的先验为 $G = N(0, \tau_0^2)$ ，并且通过数据仿真得到 $\tau_0^2$ 。

5.多重比较问题

Optimizely通过Benjamini-Hochberg方法对多重比较进行校正。

附: Statistical Methods Related to the Law of The Iterated Logarithm

若对随机变量 $x_1,...,x_n$ ，有联合概率密度函数 $g_{n}(x1,...,xn)$ ， $g_{n}'(x1,...,xn)$ 为任意其他概率密度函数，且 $Zn= g_{n}'(x1,...,xn)/g_{n}(x1,...,xn)$ ，则：

对任意 $\xi > 1$ ，存在这样的n的概率小于 $1/\xi$ ，即
$P(Zn \ge \xi\ for\ some\ n\ge1) \le 1/\xi$

以下仅简述x为正态分布下、混合函数为标准正态分布的场景

如果 $x.iid \sim N(\theta, 1)$ ,则:
$\varphi (x) = (2\pi )^{-\frac{1}{2}}exp(-x^{2}/2),\ \Phi (x) = \int _{-\infty }^{x} \varphi (t)dt,\ S_n = x_{1} + ... + x_{n}$
$x_1,...,x_n$ 的联合概率密度函数为:
$g_{\theta,n}(x_1...x_n) = \prod_1^n \varphi (x_i - \theta)$ ,
$g_{\theta,n}(x_1...x_n)' = \int _{-\infty }^{\infty} \prod_1^n \varphi (x_i - \theta)dF(\theta)$
$Zn = g_n'/g_{0,n} = \int _{-\infty }^{\infty}exp(\theta S_n - 1/2n\theta^2 )dF(\theta)$
定义 $f(x,y) = \int _{-\infty }^{\infty}exp(xy - 1/2ny^2 )dF(y)$ ，如果将 $F(\theta)$ 替换为 $F(\theta m^{1/2})$ :
$Zn = \int _{-\infty }^{\infty}exp(\theta S_n - 1/2n\theta^2 )dF(\theta m^{1/2}) = f(S_n/m^{1/2},n/m)\ \ \ \ (m>0)$

$P(f(S_n/m^{1/2},n/m) \ge \xi\ for\ some \ n\ge1) \le 1/\xi\ \ \ \ (m>0,\xi>1)$

若 $F=\Phi,x.iid\sim N(0,1)$

$双尾：P(|S_n| \ge [(n + m)(a^2 + log(n/m + 1))]^{\frac{1}{2}}\ for\ some\ n\ge1)\le e^{-\frac{1}{2}a^2}$
$单尾: P(|S_n| \ge [(n + m)(a^2 + log(n/m + 1))]^{\frac{1}{2}}\ for\ some\ n\ge1)\le e^{-\frac{1}{2}a^2}/\Phi(a)$