机器学习中的样本量问题
Published:
在机器学习业务中经常需要评估模型的效果。例如在流量划分实验A/B Test中，我们需要确定需要多少流量可以得出统计结论是模型A好还是模型B好。一个显而易见的结论是流量越多越好，但是流量切分试验做得越久，也就意味着更多损失。所以我们需要确定样本量来对流量实验进行统计检验。
另一个相似的问题是，我们需要多少样本量才可以使样本均值足够逼近总体均值（也就是期望），例如我们通过100次用户行为（点击或曝光）来计算得出的ctr与当天的整体ctr会有多少偏差？根据大数定律，样本均值随着样本量增大逼近分布期望，那么我们需要多少样本才能使样本均值够足够逼近期望呢？
这两个问题的区别是：
- 统计检验样本量是通过样本来计算两个总体的差异是否有显著性。
- 采样所需样本量是计算样本和总体的偏差。
统计检验样本量预估
计算原理
问题描述：
假设有两个总体均值$\mu_0$和$\mu_1$，已知总体标准差$\sigma$，在给定显著水平$\alpha$和统计功效$1-\beta$ 时，每个实验组至少需要多少样本量$n$，才能够比较两个总体均值？
- $\alpha$：Type I Error的概率，即当零假设成立时拒绝零假设的概率。
- $\beta$：Type II Error的概率，即当零假设不成立时不拒绝零假设的概率。
- $1-\beta$：当零假设不成立时拒绝零假设的概率。
该问题的零假设与备择假设为：
\[H_0:\mu_0-\mu_1=0\\H_1:\mu_0-\mu_1=\delta\]通过计算可得，零假设$H_0$的临界值为
\[z_{1-\alpha/2}\sigma\sqrt{2/n}\]其中$\sigma\sqrt{2/n}$是均值的标准差，通过两个总体的方差相加和中心极限定理计算得出。备择假设$H_1$的临界值为
\[\delta - z_{1-\beta}\sigma\sqrt{2/n}\]临界值在0与$\beta$之间，代表在给定标准差时的不确定性。令两个临界值相等可得：
\[n = \frac{2(z_{1-\alpha/2} + z_{1-\beta})^2\sigma^2}{（\mu_0 - \mu_1)^2}\]即当$n$满足该式时，我们则可以在给定显著水平$\alpha$和统计功效$1-\beta$比较两个总体均值。通常当$\alpha=0.05$和$1-\beta=0.8$时，可以用近似值快速计算$n$：
\[n = \frac{16\sigma^2}{\delta^2}\]在实际计算中，我们需要预估备择假设中两个总体的均值差异$\delta$。
注：
- 如果该问题是单样本问题，则将计算$n$的公式里的分子中的2去掉。
- 如果该问题是单侧检验问题，则使用$z_{1-\alpha}$来替代$z_{1-\alpha/2}$。
- 如果两个样本的方差不同，则将(4)分子中的$\sigma^2$替换成$\sigma_0^2 + \sigma_1^2$。
计算流程
- 通过给定显著水平$\alpha$和统计功效$1-\beta$，查表得出相应的$z$值$z_{1-\alpha/2}$和$z_{1-\beta}$。
- 预估总体均值差异$\delta$和方差$\sigma^2$，如果无法预估，可以通过一小段时间的快速实验的样本均值差异$\bar{\delta}$和样本方差$\bar{\sigma}^2$来取值。
- 通过公式(4)计算得出$n$。
- 进行流量实验，对每个实验组取$n$个样本，并进行统计检验。
业务案例
现一推荐系统随机推荐ctr为0.5，准备上线模型推荐，预期ctr提升0.01。因为ctr服从伯努利分布，其方差为$\sigma=p(1-p)$。当$\alpha=0.05$和$1-\beta=0.8$时，根据方差不同版本的(4)计算可得：
\[n=\frac{16\times(0.5\times 0.5+ 0.51\times 0.49)}{0.01^2}\approx 79983\]通过流量实验对随机组和模型组分别取79983个样本，并使用双比例z检验计算z值和p值。
CASE 1 （显著结论）：随机ctr为0.498，模型ctr为0.504，计算得出$z_{1-\alpha/2}=2.39$。通过查表得出p值为0.0168。则结论为模型推荐比随机推荐有显著差异，并且两种推荐方式无差异时得出该结论的概率小于0.0168。
CASE 2（不显著结论）：随机ctr为0.498，模型ctr为0.501，计算得出$z_{1-\alpha/2}=1.19$。通过查表得出p值为0.234。则结论为模型推荐比随机推荐无显著差异，并且两种推荐方式差异为0.01的情况下得出该结论的概率小于0.0516（通过将$n$，$z_{1-\alpha/2}$代回(1)中计算得出$z_{1-\beta}$）。
参考资料
- Van Belle, Gerald. Statistical rules of thumb. Vol. 699. John Wiley & Sons, 2011.
采样所需样本量预估
计算原理
问题描述：
假设总体均值为$\mu$，需要在该总体中采样多少样本$n$，才能使样本均值$\bar{x}$与$\mu$的差异大于$\epsilon$的概率小于$\delta$？
该问题可以采用Hoeffding不等式：
\[P(\rvert \bar{x}\rvert - \mu\rvert \ge \epsilon) \le 2\exp(-2n\epsilon^2)\]该不等式说明了样本均值$\bar{x}$与总体均值$\mu$的差异大于$\epsilon$的概率的上界是$2\exp(-2n\epsilon^2)$。令$P(\rvert \bar{x} - \mu\rvert \ge \epsilon)=\delta$，得出：
\[n=\frac{-\log(\delta/2)}{2\epsilon^2}\]从该式可以看出，样本量跟概率$\delta$和差异$\epsilon$成反比，即要求$\epsilon$更小或概率$\delta$更小，则需要更大的样本量$n$。
同理，也可以固定$n$和$\delta$计算$\epsilon$：
\[\epsilon = \sqrt{\frac{-\log(\delta/2)}{2n}}\]公式(7)默认样本的取值范围为[0,1]，例如比率。如果样本取值范围不是0~1，则使用：
\[n=\frac{-\log(\delta/2)(b-a)^2}{2\epsilon^2}\]其中$a$和$b$是样本取值的上下界。
注：
- 如果只需要计算$\bar{x} - \mu>\epsilon$或者$\bar{x} - \mu<\epsilon$的概率，则(7)的右侧变为$\exp(-2n\epsilon^2)$。
计算流程
- 给定目标差异$\epsilon$和概率$\delta$。
- 根据样本取值范围通过等式(8)或(10)计算所需样本量$n$。
业务案例
1. 画像性别特征
已知一组画像数据中总体性别特征存在少许错误，则至少需要多少样本量n，才能够使样本性别准确率与总体性别准确率差异不超过0.01的概率不超过5%？
通过等式(8)计算可得：
\[n=\frac{-\log(5\%/2)}{2\times 0.01^2}\approx18444\]所以当样本量大于18444时，样本性别准确率与总体性别准确率差异不超过1%的概率不超过0.05。也就是说，采样18444个样本重复100次，样本均值和总体均值差异超过1%不会超过5次。
2. 新闻推荐CTR
在新闻推荐业务中，观测数据发现凌晨1点到2点的CTR高于全天CTR，想要分析产生该现象的原因是由于凌晨用户点击推荐新闻意愿更高，还是由于凌晨数据量少产生的采样偏差。1点到2点的曝光PV为3070，CTR为1.66%，全天曝光PV为954605，CTR为0.9%。由于全天曝光PV较大，可以将其CTR当做总体CTR，则我们需要计算CTR差值超过1.66%-0.9%=0.76%的概率最高是多少。由于我们只需要计算大于差值的概率，所以将等式(7)改为：
\[P(CTR - \overline{CTR} \ge \epsilon) \le \exp(-2n\epsilon^2)\]计算可得：
\[P(CTR - \overline{CTR} \ge 0.0076) \le 70.14\%\]可得出结论1点到2点的CTR比全天CTR高0.76%以上的概率上界为0.7014，说明有很大几率是由于样本量不足导致的偏差。
查询表格
列代表差异$\epsilon$，行代表概率$\delta$。
双侧偏差
| $\epsilon=0.0001$ | $\epsilon=0.001$ | $\epsilon=0.01$ | $\epsilon=0.05$ | $\epsilon=0.1$ | $\epsilon=0.2$ | |
|---|---|---|---|---|---|---|
| $\delta=0.001\%$ | 610,303,632 | 6,103,036 | 61,030 | 2,441 | 610 | 153 |
| $\delta=0.01\%$ | 495,174,378 | 4,951,744 | 49,517 | 1,981 | 495 | 124 |
| $\delta=0.1\%$ | 380,045,123 | 3,800,451 | 38,005 | 1,520 | 380 | 95 |
| $\delta=0.5\%$ | 299,573,227 | 2,995,732 | 29,957 | 1,198 | 300 | 75 |
| $\delta=1.0\%$ | 264,915,868 | 2,649,159 | 26,492 | 1,060 | 265 | 66 |
| $\delta=5.0\%$ | 184,443,973 | 1,844,440 | 18,444 | 738 | 184 | 46 |
| $\delta=10.0\%$ | 149,786,614 | 1,497,866 | 14,979 | 599 | 150 | 37 |
| $\delta=20.0\%$ | 115,129,255 | 1,151,293 | 11,513 | 461 | 115 | 29 |
| $\delta=30.0\%$ | 94,855,999 | 948,560 | 9,486 | 379 | 95 | 24 |
| $\delta=40.0\%$ | 80,471,896 | 804,719 | 8,047 | 322 | 80 | 20 |
| $\delta=50.0\%$ | 69,314,718 | 693,147 | 6,931 | 277 | 69 | 17 |
单侧偏差
| $\epsilon=0.0001$ | $\epsilon=0.001$ | $\epsilon=0.01$ | $\epsilon=0.05$ | $\epsilon=0.1$ | $\epsilon=0.2$ | |
|---|---|---|---|---|---|---|
| $\delta=0.001\%$ | 575,646,273 | 5,756,463 | 57,565 | 2,303 | 576 | 144 |
| $\delta=0.01\%$ | 460,517,019 | 4,605,170 | 46,052 | 1,842 | 461 | 115 |
| $\delta=0.1\%$ | 345,387,764 | 3,453,878 | 34,539 | 1,382 | 345 | 86 |
| $\delta=0.5\%$ | 264,915,868 | 2,649,159 | 26,492 | 1,060 | 265 | 66 |
| $\delta=1.0\%$ | 230,258,509 | 2,302,585 | 23,026 | 921 | 230 | 58 |
| $\delta=5.0\%$ | 149,786,614 | 1,497,866 | 14,979 | 599 | 150 | 37 |
| $\delta=10.0\%$ | 115,129,255 | 1,151,293 | 11,513 | 461 | 115 | 29 |
| $\delta=20.0\%$ | 80,471,896 | 804,719 | 8,047 | 322 | 80 | 20 |
| $\delta=30.0\%$ | 60,198,640 | 601,986 | 6,020 | 241 | 60 | 15 |
| $\delta=40.0\%$ | 45,814,537 | 458,145 | 4,581 | 183 | 46 | 11 |
| $\delta=50.0\%$ | 34,657,359 | 346,574 | 3,466 | 139 | 35 | 9 |
参考资料
- https://en.wikipedia.org/wiki/Hoeffding%27s_inequality
感谢腾讯高级研究员陈亮对本文的指点与修改。