观文听傑

返回

青色光沿玻璃队列的连续前缀前进,在琥珀色空槽处停下,后方已完成玻璃块等待的装饰性插画青色光沿玻璃队列的连续前缀前进,在琥珀色空槽处停下,后方已完成玻璃块等待的装饰性插画

上一篇六路审计证据的置信序列允许标签边补边看,达到预定门槛就停。上线后,报表工程师却遇到一个更早的问题:五位候选人都已送审,三份正标签当天回传,两份负标签几天后才到。现在的“3/3”能放进那个区间公式吗?

本篇讲透预随机完整前缀(Pre-randomized Complete Prefix)怎样把乱序事件转换成合法审计计数。三个环节是冻结顺序、按前缀释放、幂等接收与修订隔离。示例均为合成数据;封面是队列隐喻。这里冻结模型,执行的是审计推断前的数据处理,没有训练参数更新。

01 先定义“第一个样本”,再接收第一个标签#

设某条证据流的潜在二元结果依次为 X1,X2,…X_1,X_2,\ldots,每个 Xi∈{0,1}X_i\in\{0,1\}。沿用上一篇的独立同分布(Independent and Identically Distributed,IID)设定:每路目标来源固定,均值为 θ\theta,顺序由抽样设计决定,不能按尚未观察的结果重排。对敏感度流,“成功”指可信真阳性中参考判正;对特异度流,“成功”指可信真阴性中参考判负。名单来源与成功含义一起冻结。

清单(Manifest)记录候选键到位置的映射,形状 [M];它不包含标签。名单可以是从目标来源独立抽取的候选,再在不看结果的条件下定序。对一个固定有限总体直接随机不放回,则属于另一种抽样模型:可使用适用的不放回浓缩界,不能把“洗过牌”当作 IID 的证明。本文账本同时适用两种模型,区间定理须跟随真实抽样设计。

最小冻结单元为 (stream_id, protocol, manifest),其中 protocol 绑定模型、参考标签规则、目标来源与成功定义的不可变版本。可用 Python 官方 Random.shuffle ↗在独立于结果的键列表上原地打乱;固定种子便于重放,但仍需保存实际名单、代码与运行环境。伪随机生成器的可复现性不等同于来源具有代表性。

设日历时刻 tt 已收到最终标签的案例集合为 CtC_t。最长完整前缀长度定义为

N(t)=max⁡{n:{1,…,n}⊆Ct},K(t)=∑i=1N(t)Xi.N(t)=\max\{n:\{1,\ldots,n\}\subseteq C_t\},\qquad K(t)=\sum_{i=1}^{N(t)}X_i.

空前缀约定 N=K=0N=K=0。后面的标签可先进入缓冲区,但只有前面缺口补齐后才释放到统计量。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。下表记录每次接受新案例后的状态,比例均无量纲。

新到标签已完成数按已完成案例算的比例完整前缀交给推断器的 (K,N)(K,N)
A=111/11/1A(1,1)(1,1)
C=122/22/2A(1,1)(1,1)
D=133/33/3A(1,1)(1,1)
B=043/43/4A…D(3,4)(3,4)
E=053/53/5A…E(3,5)(3,5)

第三行里,A、C、D 是“最快完成的三人”,它们没有组成原始抽样顺序的前三人。若成功者更容易完成核验,按已完成案例估计会系统性偏高。账本则把 C、D 保存为已到但未释放;B 补齐时一次释放 B、C、D。重复刷新第三行仍只有一个前缀样本,不会增加信息。

这个例子展示的是数据处理机制,不把五人的实现比例当作覆盖率模拟。对固定名单,最后结果就是 3/53/5;若要推断名单以外的目标均值,还须使用与抽样设计相符的统计保证。

晚到的恰好都是负标签,等完整前缀还有用吗?

有用。结果相关延迟会改变当前前缀长度,却没有删除或重排前缀内部的任何候选。它可能让进度停住;统计有效性与完成速度需要分别报告。

03 为什么结果相关的等待时间仍能被同时覆盖?#

上一篇给六路所有固定前缀同时构造区间。记事件

E={∀j∈{1,…,6}, ∀n≥1:θj∈Ij,n},P(E)≥1−α.E=\{\forall j\in\{1,\ldots,6\},\ \forall n\ge1: \theta_j\in I_{j,n}\},\qquad P(E)\ge1-\alpha.

在 EE 上,每个前缀都已覆盖。即使完成延迟依赖标签、当前长度 Nj(t)N_j(t) 也因此依赖标签,当前区间仍只是从全部前缀中挑出一个:θj∈Ij,Nj(t)\theta_j\in I_{j,N_j(t)}。这个逐路径(Pathwise)包含关系不需要再假设“延迟与结果独立”。Nj(t)=0N_j(t)=0 时使用 [0,1]。

这里真正需要守住的是:底层抽样流满足原定定理,前缀里的标签最终可信且固定,当前统计量确实等于原始顺序下该前缀的和。只统计所有已完成案例,相当于换成了另一个由延迟筛选的子集,失去这条包含关系。普通固定样本区间也没有覆盖所有 nn 的事件,不能借用此论证来无限查看。

六路异步更新时,每路各自维护前缀。区间器用各自 NjN_j 算半径,再按前文错分方程投影。哪一路先补齐可以由资源安排决定;在一路内部替换掉“太难”的人,会改变抽样契约。

04 账本的数据流:接收成功,不等于统计量立即增加#

阶段输入核心操作输出与不变量
冻结候选键 [M]、协议版本保存唯一顺序和来源同一流位置始终指向同一案例
接收事件键、案例键、0/1、协议校验版本和键,检查重投与冲突一个案例至多一个最终结果
缓冲合法但乱序的标签存入按案例索引的缓冲区后方完成不会跨越前方未知
释放当前位置之后连续已知段每个位置只加一次 K,NK,N0≤K≤N≤M0\le K\le N\le M
快照计数、名单身份、日志截点保存并可重放同一截点重算得到同一状态

幂等(Idempotency) 指同一有效事实重复投递,最终状态与投递一次相同。需要两层键:event_id 标识一次投递事实,case_id 标识抽样单位。同一案例换了事件键再次发送相同结果,也不能再加一个人。同一事件键换了载荷,或同一案例换了结果,都应显式拒绝。

加载冻结清单;恢复前缀指针、案例结果和事件索引
接到最终标签:先校验协议、身份、二元结果
同事件同载荷:返回原状态;同键异载荷:拒绝
同案例同结果:记录合法重投;同案例异结果:进入修订流程
保存新结果;只要下一个清单位置已知,就推进指针并加计数
原子保存事件与新快照,再让区间器读取快照
text

05 Python:一个能离线重放的最小前缀账本#

以下完整程序保存为 prefix.py,运行 python3 prefix.py,只依赖 Python 标准容器。accept 的输入是一条最终标签事件,返回新快照字典;snapshot 的输出包括已完成数、前缀计数、阻塞案例键和缓冲人数。演示名单用显式顺序方便手算,真实任务应先按设计生成并持久保存。

输出的五行依次为 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 推进一次,MM 个位置的总推进代价为 O(M)O(M);单次 B 到达可以释放一长段,所以最坏单次代价是 O(M)O(M),平均摊销为每个释放位置 O(1)O(1)。案例与事件索引分别占 O(M)O(M)、O(E)O(E),EE 是有效不同事件键数。示例是单进程内存模型;生产实现需用事务把事件唯一约束、案例最终结果、前缀快照一起落盘,并按流串行化或使用等效并发控制。

06 从“代码没报错”到“抽样契约真的成立”#

先检查来源:完整候选池是否包含难查人群?按模型不确定性只挑案例,是主动学习样本,不能直接替代目标随机审计流。若验证敏感度/特异度,入流所依据的可信类别及核验协议也需固定。再检查顺序与状态:离线重放全部事件,对每个截点从头扫描清单,核对第一个未知位置、K,NK,N 与缓冲区。

调试可枚举五人全部 5!5! 种到达排列:中间快照不同,完整回放都应得到 (3,5);每个中间状态应等于该时刻已知清单的最长连续前缀。插入重复事件、用新事件键重投、模拟重启重放,计数应保持一致。未知案例、布尔值标签、事件键冲突、协议改变都应在修改状态前被拒绝。

情况或方法它解决什么处理方式
完整前缀乱序回传下保持原样本顺序代价是头部阻塞,报告等待年龄
成熟窗口结果定义所需观察时长先等结果成熟,再接受最终标签
到达时间水位线(Watermark)管道认为事件已基本到齐的时间界须核对延迟假设,不能替代抽样证明
响应概率加权在可识别假设下修正非响应使用相应估计器与不确定性,不能直接套无权区间
旧标签被纠正原有“最终标签”假设失效保存冲突、停用受影响旧结论,建立明确的修订分析
永久失联案例前缀可能永远不能推进保留未决,或显式纳入未知结果的界限

新版本分析需要记录撤回原因、新目标及覆盖预算。若把重启当成“重新抽一次幸运区间”,仍需控制跨分析的总体错误率;改协议也可能改变参数含义。保留旧日志可以追溯过去为何作出决定,不能让已知错误标签继续支撑现行结论。

B 一直查不到,可否把 C 移到第二位,让进度继续?

这样会根据核验可见性重排已冻结的抽样流。可以继续把 C 的标签保存在缓冲区,并报告阻塞状态;若要利用后方完成标签,需要显式保留 B 的未知结果,计算能容纳它的保守范围。下一篇给出这个替代接口。

思考练习#

  1. 将 E=0 改为最先回传,逐步写出五次事件后的 received、buffered、k、n,解释哪些量允许领先于前缀。
  2. 枚举五人的到达排列,在每个截点独立扫描清单验证快照;再插入同案例新事件键的重投,检查不变量是否保持。
  3. 构造“所有负标签多等三天”的延迟机制。用同时覆盖事件解释完整前缀为何仍可用,再指出仅给每个固定 nn 单独 95% 覆盖时,证明缺少了哪个量词。

相关工作#

  1. Howard, Ramdas, McAuliffe & Sekhon (2021), Time-Uniform, Nonparametric, Nonasymptotic Confidence Sequences ↗:同时覆盖全部前缀的推断基础;本文账本是数据接口示例。
  2. Serfling (1974), Probability Inequalities for the Sum in Sampling without Replacement ↗:固定有限总体随机不放回时,应选择适配设计的浓缩保证。
  3. Joulani, György & Szepesvári (2013), Online Learning under Delayed Feedback ↗:研究反馈延迟对在线学习的影响;其遗憾界与本篇审计覆盖目标不同。

下一篇预告#

完整前缀守住顺序,也可能被一个永久缺失案例卡住。下一篇保留全部已发出位置,把未回传标签逐一允许为 0 或 1,推导“缺失宽度 + 抽样半径”的区间,让后方已完成标签在明确代价下参与持续审计。

标签回传有快有慢,哪些才能计入?预随机完整前缀与幂等审计账本
https://zwjcode.cn/blog/audit-randomized-prefix-event-ledger
作者 傑
发布于 2026年11月10日
版权协议 CC BY-NC-SA 4.0
评论加载似乎遇到了问题,请尝试刷新页面。