重抽用户和日期时,一条请求会被算几次?配对失败率差的鸽巢 Bootstrap
分别抽取用户与日期,用两个抽中次数的乘积加权配对请求,逐轮重算失败率差并诊断空交叉样本。
一个检索系统回放了新版和基线版。某个故障日流量翻倍,许多用户的请求同时变难。用整用户自助法反复换用户名单,每个抽到的用户仍携带原来那几天的记录。这能观察固定日期下换一批用户的波动,却看不到故障日被重复抽到或完全略过时会发生什么。
上一篇把同一用户和同一天的相关性放进一个标准误。鸽巢自助法(Pigeonhole Bootstrap)沿两条轴分别有放回抽样。每次抽样都组成一个新的用户—日期网格,并重算全网格的失败率差。这样可以直接观察请求总量变化时,重抽样得到的比率分布。
01 一格的乘数来自两份名单#
沿用上一篇的配对回放。用户 在日期 的交叉格包含 条成熟、对齐的请求。当前版和基线版分别失败 、 次,净失败数 可正可负。观测差值 等于全量净失败数除以全量请求数。它按请求加权,正数表示当前版失败更多,乘 100 即百分点。
共有 位观测用户、 个观测日期和 个非空格。输入用 的稀疏长表(Sparse Long Table)保存,五列依次是用户、日期、当前版失败数、基线版失败数、请求数。公式可用两张 的矩阵理解,分别存净失败数和请求数。空格表示没有请求,对 和 的和都贡献零。缺失日志或未成熟标签要在上游处理,它们对应的是待核验请求。
在同一轮中,从 位用户均匀有放回抽 次,从 个日期独立地均匀有放回抽 次。记 为用户 的抽中次数、 为日期 的抽中次数。向量 长 且和为 ,向量 长 且和为 。两份名单做笛卡尔积(Cartesian Product)。若某人出现两次、某天出现三次,这个交点就会出现六次。所有共享一个用户的格共用同一个 ,所有共享一天的格共用同一个 。
是 的无量纲乘数矩阵。 和 都以次数计, 是比例差。同一个乘数应用于两版结果及其共享分母,保留原来逐请求的配对。分子变化时,分母也随抽到的流量组成变化。用全量请求数当每轮分母,会把高流量日期的复制误读成失败率变化。
为何不能为同一天的每位用户独立抽一个日期乘数?
故障日一旦被抽中两次,当天所有用户的记录都应获得同一个日期乘数 2。按人各抽各的乘数会让这个故障日对部分用户消失、对另一部分用户重复,破坏想保留的共同冲击(Common Shock)。
02 两人两天,分子一样也能得出不同差值#
下面三格都是合成数据。格内依次写净失败数 和请求数 ,总计 、,观测差值为 。B 在第二天没有请求。
| 用户 | 第一天 | 第二天 | 全窗口 |
|---|---|---|---|
| A | |||
| B |
抽到用户 [A, B]、日期 [第一天, 第一天],第一列的两格都乘 2。新分子为 ,新分母为 ,差值为 。若用户改抽 [B, B],日期仍抽 [第一天, 第一天],唯一留下的格乘 4,分子为 8,分母为 8,差值为 1。若两位用户和两个日期各出现一次,则回到 。
再比较两轮分子相同的情形。抽 [B, B] 与 [第一天, 第二天] 时,、。抽 [A, B] 与 [第一天, 第一天] 时,同样是 ,但 。后者里第一天 A 的请求两版都成功,给分母加了两次,差值因此从 1 变为 。
哪种抽法会让分母变成零?概率是多少?
两次都抽到 B 且两次都抽到第二天,只会访问右下角的空格。两条轴各自以 的概率抽到这份名单,两者独立,联合概率为 。此轮比率未定义,统计时应记录零分母。不断重抽直至非空,得到的是以存在请求为条件的分布。
03 Python 只扫描实际发生过请求的格#
固定版本、配对键、观察窗和标签成熟规则后,模型推理只需回放一次。后续抽样操作的是计数。下面的伪代码展示两份抽中次数如何汇入同一个稀疏格。
配对回放 → 用户×日期的非空格 → 观测比率
│
每轮抽用户 → W ├─ 对每个非空格取 W[i] × V[t]
每轮抽日期 → V │ 分别累加加权净失败数和请求数
└─ 请求数为正 → 本轮比率
请求数为零 → 记录未定义textdefault_rng(seed) 建立 NumPy 随机数生成器。Generator.multinomial(n, pvals) 一次返回各类别被抽中的次数。传入 次和长度为 的均匀概率向量,就得到一个 ,对日期同样操作得到 。代码把抽中次数转为 Python 整数再乘,避免让定宽 NumPy 整数承担累加。每轮返回一个浮点差值或 None,并保留整数分母。两份输出列表各长 reps,同一下标对应同一轮。示例要求每条轴至少有两个观测类别。
import numpy as np
def pigeonhole_ratio(rows, reps=10_000, seed=2026):
"""Resample a sparse crossed table of paired failure counts."""
if type(reps) is not int or reps < 1:
raise ValueError("reps must be a positive Python integer")
counts = {}
for user, day, current, baseline, requests in rows:
if any(not isinstance(key, str) or not key.strip()
for key in (user, day)):
raise ValueError("user and day must be nonempty strings")
if any(type(n) is not int for n in (current, baseline, requests)):
raise ValueError("counts must be Python integers")
if requests < 1 or not (
0 <= current <= requests and 0 <= baseline <= requests
):
raise ValueError("invalid paired counts")
key = (user, day)
if key in counts:
raise ValueError("aggregate each user-day cell exactly once")
counts[key] = (current - baseline, requests)
users = sorted({user for user, _ in counts})
days = sorted({day for _, day in counts})
n, g = len(users), len(days)
if min(n, g) < 2:
raise ValueError("at least two observed levels per axis are required")
user_id = {user: i for i, user in enumerate(users)}
day_id = {day: t for t, day in enumerate(days)}
cells = [
(user_id[user], day_id[day], diff, requests)
for (user, day), (diff, requests) in counts.items()
]
total_diff = sum(diff for _, _, diff, _ in cells)
total_requests = sum(requests for _, _, _, requests in cells)
observed = total_diff / total_requests
rng = np.random.default_rng(seed)
user_p = np.full(n, 1 / n)
day_p = np.full(g, 1 / g)
ratios, denominators = [], []
for _ in range(reps):
user_weights = rng.multinomial(n, user_p).tolist()
day_weights = rng.multinomial(g, day_p).tolist()
diff_sum = request_sum = 0
for i, t, diff, requests in cells:
copies = user_weights[i] * day_weights[t]
diff_sum += copies * diff
request_sum += copies * requests
denominators.append(request_sum)
ratios.append(diff_sum / request_sum if request_sum else None)
return observed, ratios, denominators
rows = [
("A", "day1", 0, 0, 1),
("A", "day2", 0, 1, 1),
("B", "day1", 2, 0, 2),
]
estimate, draws, totals = pigeonhole_ratio(rows)
print(estimate, min(totals), max(totals)) # 0.25 0 8
print(totals.count(0) / len(totals)) # 接近 0.0625python示例每轮遍历 个非空格,另需生成长度分别为 和 的乘数向量,避免构造完整网格或复制原始请求。大规模回放可按轮分批,预先编码索引。若用定宽数组向量化,先以最大可能乘数与全量请求数的乘积给累加量做上界检查。调试时固定数据快照、轴顺序、随机种子和 NumPy 版本。交换两版后,每个有效差值应反号,分母应逐轮相等。把每格的三项计数同时乘 2,分母应逐轮翻倍,有效差值应逐轮相同。NumPy 多项抽样文档 ↗
04 区分日期波动、稀疏性和真正缺少的证据#
- 日期是否应该随机。 若问题是本次已固定日期内换用户会怎样,固定所有日期权重为 1,沿用户轴重抽即可。要外推到类似的新日期,才需要日期轴上的重复抽样。分别重抽要求用户和日期在各自目标机制内可交换(Exchangeable),并要求两轴都不同的格可以视作独立。若同一故障跨日延续,或者工作日与节假日来自不同流量机制,逐日均匀重抽会打散依赖或改变要估计的流量组成。
- 零分母和主导格。 一旦出现空轮,保留其占比和正分母的分布,回查哪些用户与日期几乎没有交集。有效轮的分位数只描述非空轮。少数格占据大部分请求、独立日期很少时,增加抽样次数只会使模拟分布更稳定,证据仍来自原来的格和日期。
- 与双向聚类方差对照。 上一篇用线性化残差和容斥公式估计局部波动,这里观察非线性比率在重新加权后的整组结果。两者的方差在有限样本下可以不同。某格内独有的噪声会被两条轴同时重抽,在以格内噪声为主的场景可使乘积权重法高估波动。要把重采样分位数用作发布门槛,需先核验目标、两轴的有效样本量、依赖结构和覆盖率。原论文给出的均值结果有各自的模型条件,本文的三格例子用于复核计数机制。
思考练习#
- 固定抽到日期
[第二天,第二天],分别抽用户[A,A]与[A,B]。算出两轮的 、、,再把两轮都错除以观测分母 4,比较误差。 - B 在第二天新增一条两版均成功的请求。重算观测差值和空轮概率,并解释为什么净失败数保持不变。
- 若一次故障连续影响周二、周三和周四,指出两个不同用户在不同日也会相关的具体格对。说出逐日重抽时可能把这三天拆成哪几种样本。
相关工作#
- Owen(2007)提出行列分别有放回重采样,研究交叉且不平衡的数据中均值方差的估计。The Pigeonhole Bootstrap ↗
- Owen 与 Eckles(2012)用独立因子权重的乘积扩展到任意阶数组,并分析方差估计的偏差。Bootstrapping Data Arrays of Arbitrary Order ↗
- Davezies、D’Haultfœuille 与 Guyonvarch(2021)研究可交换数组的经验过程与自助法收敛,为多向聚类下的推断给出条件。Empirical Process Results for Exchangeable Arrays ↗
下一篇预告#
如果一次事故跨越三天,逐日抽样可能把同一次冲击拆开。下一篇保留日期的先后顺序,讨论怎样用连续时间块重采样,以及块长度怎样影响审计结论。