标签回传有快有慢,哪些才能计入?预随机完整前缀与幂等审计账本
用五人乱序回传例子和可重放 Python 账本,守住置信序列的样本顺序,区分完整前缀、重复投递与标签修订,并解释结果相关延迟为何仍可安全等待。
上一篇六路审计证据的置信序列允许标签边补边看,达到预定门槛就停。上线后,报表工程师却遇到一个更早的问题:五位候选人都已送审,三份正标签当天回传,两份负标签几天后才到。现在的“3/3”能放进那个区间公式吗?
本篇讲透预随机完整前缀(Pre-randomized Complete Prefix)怎样把乱序事件转换成合法审计计数。三个环节是冻结顺序、按前缀释放、幂等接收与修订隔离。示例均为合成数据;封面是队列隐喻。这里冻结模型,执行的是审计推断前的数据处理,没有训练参数更新。
01 先定义“第一个样本”,再接收第一个标签#
设某条证据流的潜在二元结果依次为 ,每个 。沿用上一篇的独立同分布(Independent and Identically Distributed,IID)设定:每路目标来源固定,均值为 ,顺序由抽样设计决定,不能按尚未观察的结果重排。对敏感度流,“成功”指可信真阳性中参考判正;对特异度流,“成功”指可信真阴性中参考判负。名单来源与成功含义一起冻结。
清单(Manifest)记录候选键到位置的映射,形状
[M];它不包含标签。名单可以是从目标来源独立抽取的候选,再在不看结果的条件下定序。对一个固定有限总体直接随机不放回,则属于另一种抽样模型:可使用适用的不放回浓缩界,不能把“洗过牌”当作
IID 的证明。本文账本同时适用两种模型,区间定理须跟随真实抽样设计。
最小冻结单元为 (stream_id, protocol, manifest),其中 protocol 绑定模型、参考标签规则、目标来源与成功定义的不可变版本。可用 Python 官方 Random.shuffle ↗在独立于结果的键列表上原地打乱;固定种子便于重放,但仍需保存实际名单、代码与运行环境。伪随机生成器的可复现性不等同于来源具有代表性。
设日历时刻 已收到最终标签的案例集合为 。最长完整前缀长度定义为
空前缀约定 。后面的标签可先进入缓冲区,但只有前面缺口补齐后才释放到统计量。received 是已完成案例数,n 是已释放前缀人数,k 是前缀成功数;三者不是同一计数。输入键、标签各 [M],标签另有“未知”状态;输出给区间器的是 [k,n],六路合并为 [2,3,2]。
02 五个人,足以看见 100% 的幻觉#
固定教学顺序为 A、B、C、D、E,最终结果为 [1,0,1,1,0]。到达顺序为 A、C、D、B、E。下表记录每次接受新案例后的状态,比例均无量纲。
| 新到标签 | 已完成数 | 按已完成案例算的比例 | 完整前缀 | 交给推断器的 |
|---|---|---|---|---|
| A=1 | 1 | A | ||
| C=1 | 2 | A | ||
| D=1 | 3 | A | ||
| B=0 | 4 | A…D | ||
| E=0 | 5 | A…E |
第三行里,A、C、D 是“最快完成的三人”,它们没有组成原始抽样顺序的前三人。若成功者更容易完成核验,按已完成案例估计会系统性偏高。账本则把 C、D 保存为已到但未释放;B 补齐时一次释放 B、C、D。重复刷新第三行仍只有一个前缀样本,不会增加信息。
这个例子展示的是数据处理机制,不把五人的实现比例当作覆盖率模拟。对固定名单,最后结果就是 ;若要推断名单以外的目标均值,还须使用与抽样设计相符的统计保证。
晚到的恰好都是负标签,等完整前缀还有用吗?
有用。结果相关延迟会改变当前前缀长度,却没有删除或重排前缀内部的任何候选。它可能让进度停住;统计有效性与完成速度需要分别报告。
03 为什么结果相关的等待时间仍能被同时覆盖?#
上一篇给六路所有固定前缀同时构造区间。记事件
在 上,每个前缀都已覆盖。即使完成延迟依赖标签、当前长度 也因此依赖标签,当前区间仍只是从全部前缀中挑出一个:。这个逐路径(Pathwise)包含关系不需要再假设“延迟与结果独立”。 时使用 [0,1]。
这里真正需要守住的是:底层抽样流满足原定定理,前缀里的标签最终可信且固定,当前统计量确实等于原始顺序下该前缀的和。只统计所有已完成案例,相当于换成了另一个由延迟筛选的子集,失去这条包含关系。普通固定样本区间也没有覆盖所有 的事件,不能借用此论证来无限查看。
六路异步更新时,每路各自维护前缀。区间器用各自 算半径,再按前文错分方程投影。哪一路先补齐可以由资源安排决定;在一路内部替换掉“太难”的人,会改变抽样契约。
04 账本的数据流:接收成功,不等于统计量立即增加#
| 阶段 | 输入 | 核心操作 | 输出与不变量 |
|---|---|---|---|
| 冻结 | 候选键 [M]、协议版本 | 保存唯一顺序和来源 | 同一流位置始终指向同一案例 |
| 接收 | 事件键、案例键、0/1、协议 | 校验版本和键,检查重投与冲突 | 一个案例至多一个最终结果 |
| 缓冲 | 合法但乱序的标签 | 存入按案例索引的缓冲区 | 后方完成不会跨越前方未知 |
| 释放 | 当前位置之后连续已知段 | 每个位置只加一次 | |
| 快照 | 计数、名单身份、日志截点 | 保存并可重放 | 同一截点重算得到同一状态 |
幂等(Idempotency)
指同一有效事实重复投递,最终状态与投递一次相同。需要两层键:event_id 标识一次投递事实,case_id
标识抽样单位。同一案例换了事件键再次发送相同结果,也不能再加一个人。同一事件键换了载荷,或同一案例换了结果,都应显式拒绝。
加载冻结清单;恢复前缀指针、案例结果和事件索引
接到最终标签:先校验协议、身份、二元结果
同事件同载荷:返回原状态;同键异载荷:拒绝
同案例同结果:记录合法重投;同案例异结果:进入修订流程
保存新结果;只要下一个清单位置已知,就推进指针并加计数
原子保存事件与新快照,再让区间器读取快照text05 Python:一个能离线重放的最小前缀账本#
以下完整程序保存为 prefix.py,运行 python3 prefix.py,只依赖 Python 标准容器。accept 的输入是一条最终标签事件,返回新快照字典;snapshot 的输出包括已完成数、前缀计数、阻塞案例键和缓冲人数。演示名单用显式顺序方便手算,真实任务应先按设计生成并持久保存。
class PrefixLedger:
def __init__(self, manifest, protocol):
if type(protocol) is not str or not protocol:
raise ValueError("need a protocol version")
if not isinstance(manifest, (tuple, list)) or not manifest:
raise ValueError("need a nonempty ordered manifest")
if any(type(key) is not str or not key for key in manifest):
raise ValueError("case keys must be nonempty strings")
if len(set(manifest)) != len(manifest):
raise ValueError("duplicate case key in manifest")
self.order = tuple(manifest)
self.members = frozenset(manifest)
self.protocol = protocol
self.labels = {}
self.events = {}
self.n = self.k = 0
def snapshot(self):
return dict(k=self.k, n=self.n, received=len(self.labels),
buffered=len(self.labels) - self.n,
blocked=None if self.n == len(self.order) else self.order[self.n])
def accept(self, event_id, case_id, outcome, protocol):
if type(event_id) is not str or not event_id:
raise ValueError("need an event key")
if type(case_id) is not str or case_id not in self.members:
raise ValueError("unknown case")
if type(protocol) is not str or protocol != self.protocol:
raise ValueError("protocol mismatch")
if type(outcome) is not int or outcome not in (0, 1):
raise ValueError("final outcome must be integer 0 or 1")
payload = (case_id, outcome, protocol)
if event_id in self.events:
if self.events[event_id] != payload:
raise ValueError("event key reused with different payload")
return self.snapshot()
if case_id in self.labels and self.labels[case_id] != outcome:
raise ValueError("label revision requires separate analysis")
self.events[event_id] = payload
self.labels[case_id] = outcome
while self.n < len(self.order) and self.order[self.n] in self.labels:
self.k += self.labels[self.order[self.n]]
self.n += 1
return self.snapshot()
if __name__ == "__main__":
ledger = PrefixLedger(["A", "B", "C", "D", "E"], "audit-v1")
for key, y in [("A", 1), ("C", 1), ("D", 1), ("B", 0), ("E", 0)]:
state = ledger.accept("event-" + key, key, y, "audit-v1")
print(key, state["k"], state["n"], state["buffered"], state["blocked"])
old = ledger.snapshot()
assert ledger.accept("event-C", "C", 1, "audit-v1") == old
assert ledger.accept("retry-C", "C", 1, "audit-v1") == old
try:
ledger.accept("revision-B", "B", 1, "audit-v1")
except ValueError as error:
print(error)
assert ledger.snapshot() == oldpython输出的五行依次为 A 1 1 0 B、C 1 1 1 B、D 1 1 2 B、B 3 4 0 E、E 3 5 0 None;最后打印修订被拒绝的原因。完全相同的事件和新事件键的相同案例都不改变统计快照,冲突修订也不会先修改旧计数。
每个清单位置最多由 while 推进一次, 个位置的总推进代价为 ;单次 B 到达可以释放一长段,所以最坏单次代价是 ,平均摊销为每个释放位置 。案例与事件索引分别占 、, 是有效不同事件键数。示例是单进程内存模型;生产实现需用事务把事件唯一约束、案例最终结果、前缀快照一起落盘,并按流串行化或使用等效并发控制。
06 从“代码没报错”到“抽样契约真的成立”#
先检查来源:完整候选池是否包含难查人群?按模型不确定性只挑案例,是主动学习样本,不能直接替代目标随机审计流。若验证敏感度/特异度,入流所依据的可信类别及核验协议也需固定。再检查顺序与状态:离线重放全部事件,对每个截点从头扫描清单,核对第一个未知位置、 与缓冲区。
调试可枚举五人全部 种到达排列:中间快照不同,完整回放都应得到 (3,5);每个中间状态应等于该时刻已知清单的最长连续前缀。插入重复事件、用新事件键重投、模拟重启重放,计数应保持一致。未知案例、布尔值标签、事件键冲突、协议改变都应在修改状态前被拒绝。
| 情况或方法 | 它解决什么 | 处理方式 |
|---|---|---|
| 完整前缀 | 乱序回传下保持原样本顺序 | 代价是头部阻塞,报告等待年龄 |
| 成熟窗口 | 结果定义所需观察时长 | 先等结果成熟,再接受最终标签 |
| 到达时间水位线(Watermark) | 管道认为事件已基本到齐的时间界 | 须核对延迟假设,不能替代抽样证明 |
| 响应概率加权 | 在可识别假设下修正非响应 | 使用相应估计器与不确定性,不能直接套无权区间 |
| 旧标签被纠正 | 原有“最终标签”假设失效 | 保存冲突、停用受影响旧结论,建立明确的修订分析 |
| 永久失联案例 | 前缀可能永远不能推进 | 保留未决,或显式纳入未知结果的界限 |
新版本分析需要记录撤回原因、新目标及覆盖预算。若把重启当成“重新抽一次幸运区间”,仍需控制跨分析的总体错误率;改协议也可能改变参数含义。保留旧日志可以追溯过去为何作出决定,不能让已知错误标签继续支撑现行结论。
B 一直查不到,可否把 C 移到第二位,让进度继续?
这样会根据核验可见性重排已冻结的抽样流。可以继续把 C 的标签保存在缓冲区,并报告阻塞状态;若要利用后方完成标签,需要显式保留 B 的未知结果,计算能容纳它的保守范围。下一篇给出这个替代接口。
思考练习#
- 将 E=0 改为最先回传,逐步写出五次事件后的
received、buffered、k、n,解释哪些量允许领先于前缀。 - 枚举五人的到达排列,在每个截点独立扫描清单验证快照;再插入同案例新事件键的重投,检查不变量是否保持。
- 构造“所有负标签多等三天”的延迟机制。用同时覆盖事件解释完整前缀为何仍可用,再指出仅给每个固定 单独 95% 覆盖时,证明缺少了哪个量词。
相关工作#
- Howard, Ramdas, McAuliffe & Sekhon (2021), Time-Uniform, Nonparametric, Nonasymptotic Confidence Sequences ↗:同时覆盖全部前缀的推断基础;本文账本是数据接口示例。
- Serfling (1974), Probability Inequalities for the Sum in Sampling without Replacement ↗:固定有限总体随机不放回时,应选择适配设计的浓缩保证。
- Joulani, György & Szepesvári (2013), Online Learning under Delayed Feedback ↗:研究反馈延迟对在线学习的影响;其遗憾界与本篇审计覆盖目标不同。
下一篇预告#
完整前缀守住顺序,也可能被一个永久缺失案例卡住。下一篇保留全部已发出位置,把未回传标签逐一允许为 0 或 1,推导“缺失宽度 + 抽样半径”的区间,让后方已完成标签在明确代价下参与持续审计。