为什么要区分抽样机制
均匀蓄水池使每笔记录出现的机会相同;但记录也可能有已知的正权重,例如一笔记录代表另一笔三倍的流量。我们希望权重较大时较容易入选,同时限制样本容量,并让不同工作节点合并结果。“加权不放回抽样”有不止一种定义;以下先精确定义一种,再推导它的性质,而不是把每笔的入选概率直接当作与权重成正比。
定义 18.1.1
(容量为 的指数竞赛样本)
固定有限数据流中的互相区别的记录 ,其确定权重为 。内容相同的两笔仍算不同记录。给定整数容量 ,令 。独立抽取速率为 的指数时钟 ,即
样本由时钟最小的 笔组成,按时钟由小到大记为 。
理想连续抽样下,时钟相同的概率为零。此数学模型以固定数据及权重为条件,抽样随机性与之独立;若后续输入或停止时间取决于已观察的随机结果,固定数据流结论未必适用。此处不包括零权重,负权重亦不合法。
有序样本的概率
定理 18.1.2
(指数竞赛按剩余权重选择)
对固定有限数据流和正权重,将最小的 个独立时钟依次标记为 。对互异的 ,
时空乘积为一。因此每一步在尚未入选者中按其权重比例选择。
证明
(首次到达,然后无记忆性)
设 。第一个时钟属于 ,表示 而所有其他时钟大于 。利用独立密度和尾概率积分:
指数分布的无记忆性给出 。由独立性,条件于 及首次到达时间 时,其余时钟的剩余时间仍互相独立,并分别服从原来速率的指数分布。同样积分便得到下一笔在剩余权重中的比例;重复即证乘积公式。此处以确切连续时间为条件是相应条件密度的简写,而结果不依赖 。
证明透视
为什么每次到达后竞赛会重新开始
证明用到一个计算和一个结构性事实。计算是首次到达的积分:独立指数变量的最小值服从速率 的指数分布,胜出者为 的概率是 。结构性事实是:在首次到达时刻,仍在运行的时钟再次是原来速率的独立指数变量。这里同时需要独立性与无记忆性:无记忆性消去已过的时间 ;独立性保证得知哪个时钟先响、何时响,并不透露其他时钟的任何信息。于是归纳在较小的记录集合上以同一规则重新开始,这正是每个因子的分母为剩余权重的原因。若时钟不是指数分布,例如 在 上均匀,比例规则一开始就失效:权重为 和 时,第二个时钟先响的概率是 ,而非 。
定理描述的是有序样本。凡是只问哪些记录出现、不管次序的问题,都要把各个次序相加。
常见错误
(有序概率不是集合概率)
一个无序集合的概率,要把产生该集合的所有次序概率相加。定理并不表示大小为 的集合概率与其权重乘积成正比,也不表示入选概率是 。 时两者没有区别; 时通常有区别,见以下例子。
例题 18.1.3
(三笔不同权重的记录)
权重为 ,容量为二。记录 1 入选的互斥情况是它首先出现,或者在 2 或 3 之后第二个出现:
可是 ;因此把单次抽中概率乘以容量会出错。无序集合 的概率为 。若所有权重相等,每个有序列表的概率均为 ,每个集合有 个次序,所以无序样本均匀。
例题 18.1.4
(容量为二时的全部入选概率)
保留权重 及 。上例已得 。对记录 2,把它首先出现的情形,以及它第二个出现的两种情形相加:
同理 。验算:,正是样本大小。朴素的 分别为 、 和 :权重大的记录并非必然入选。在权重 、 的边缘情形,重记录的朴素值是 ,不可能是概率;指数竞赛给出 。
一次扫描与精确合并
每笔记录到达时只产生一次时钟。用最多 个 组成的大顶堆保留目前最小时钟:未满时插入;满后只有新时钟较堆顶小才替换堆顶。 时不存储。当 ,一次堆更新需 ,样本占 个项目;权重、标识符和时钟表示方式都影响实际字节数。这是理想实数运算的描述,并非有限精度随机数保证。
归纳可知每读完一笔,堆中都是目前前缀最小的 个时钟:新时钟若不比堆顶小,保留集合不变;否则恰好移除旧堆顶。在只插入的流程中,被舍弃的记录不会重新入选,因为已有至少 个较小时钟。
例题 18.1.5
(追踪容量为二的堆)
设 ,时钟依次为 。前两个填满堆:,堆顶 。 小于 ,所以 离开:。 不小于堆顶 ,堆不变;这是边界情形:新记录产生时钟、比较一次便被舍弃。最后 取代 ,剩下 ,确是五个时钟中最小的两个。被舍弃的 、 和 在离开或被拒时,前面都已有两个更小的时钟。
定理 18.1.6
(各分区最小的 个优先值可精确合并)
把固定记录集合分成互不重叠的分区。每笔产生一次符合其速率的独立时钟;各工作节点返回本区最小的 个时钟与记录。从所有返回结果中取最小的 个,在任何没有并列的结果上,都与直接取全局最小时钟完全相同。
证明
(本地落选者不可能全局入选)
一笔被其工作节点舍弃的记录,在该分区已有至少 笔时钟比它小,因此它不可能属于全局最小的 笔。所有全局入选者都在返回集合内,排序便可完全还原。这是逐次随机结果均成立的结论;再由有序样本定理得到抽样分布。空分区和 也适用。
这个逐结果的证明需要本地与全局比较的是同一组时钟;下例说明不遵守这一点会怎样。
反例模式
合并必须保留原始优先值
设 ,节点 A 有两笔、B 有一笔,权重均为一。原始时钟使三笔等概率胜出,故 A 胜出的概率为 。如果协调者丢弃时钟,然后在两个节点保留的记录中均匀选一笔,A 胜出的概率却是 。为本地胜出者重新抽时钟也会改变分布。必须保留原始优先值、互不重复的记录标识符,以及实际有限精度表示的统一并列规则。
理想独立均匀变量 可产生 。实际伪随机生成器只有有限状态,端点、舍入、下溢、重复优先值、种子独立性和溢出都需要具体实现策略。以标识符决定并列可重现结果,但不会精确还原理想连续分布。只要全体使用同一对偶值全序,上述合并证明仍逐结果成立,即使次序的分布不同。重试时不要重新产生优先值:应按记录去重并重用原值,否则同一记录会得到额外机会。
概念视角算法
最小时钟即最大幂次键
由于 严格递减, 个最小时钟就是 的 个最大值。取 时,这些值就是键 ,且当 时 。因此同一个样本也就是 个最大的键 ,可以用同一个堆、把比较方向反过来保存。在实数运算中两种形式完全一致。在浮点运算中,大权重会把 推向 ,而比较 则保留了幂次形式丢失的分辨率。
估计需要入选概率
按比例抽样本身并不是总量估计。令 为固定数值,。如果知道这些概率,Horvitz–Thompson 总量估计量
是无偏的:将它写为 ,逐项取期望便得 。这个期望计算不需要各入选指示变量独立,但方差通常需要联合概率。 时 ,入选值贡献 。 时,计算入选概率可能需要求和许多有序样本的概率;使用 一般有误,甚至可能大于一。若 而数据非空,便没有这种正入选概率。若缺少所需权重和入选信息,单靠样本不能确定这个无偏总量估计。
练习与解答
快速检查
(权重 且 ,求各入选概率。)
解答 · 答案
由首个时钟的分布,概率分别为 和 。
快速检查
(权重 且 ,求无序集合 的概率。)
解答 · 答案
两个次序的概率和为 。连同 的 及 的 ,三个集合的概率总和为 。
快速检查
(容量二,节点一的时钟为 ,节点二为 。怎样发送和合并?)
解答 · 答案
前者发送 ,后者发送 ;合并后为 。被舍弃的 在本区已有两个更小值,不可能全局入选。
快速检查
(抽一笔,权重 ,数值 。求两种可能的无偏总量估计及其期望。)
解答 · 答案
入选概率为 和 ,估计值为 和 ;期望 ,正是总量 。
快速检查
( 时,较大权重能保证入选吗?)
解答 · 答案
不能。所有有限正权重下,任意 个互异记录组成的有序列表都有正概率,包括不含指定记录的列表。权重改变概率,并不保证入选。
这里只处理固定正权重和有限的只插入数据流。不等概率删除、权重变动、自适应输入、有限比特的分布误差、高效计算入选概率及容错分布式实现均须另行分析。