Reservoir Sampling

一个客服模型在一条接一条到来的消息上学习。你想留下其中几条供以后回放，但记忆里只有四个位置。你也不知道还会来多少条消息：二十条，还是两百万条。

留下最先的四条？那样记忆只认识开头。永远保留最后四条？那样它只认识结尾。公平地“从全体中抽四条”，则需要把所有消息都存下来，或者事先知道消息的数量。问题是：在位置数量固定、数据流长度未知的情况下，怎样让每条消息都有同样的机会？

Reservoir Sampling 是一种在对数据的一次遍历中维持固定大小随机样本的方法，而数据的数量事先并不知道。每来一条消息之后，这里称为蓄水池的记忆里装的，都是到目前为止全部来过的消息的一份公平的随机样本。最简单的版本 Algorithm R，由 Vitter, Random Sampling with a Reservoir, §2 描述，他把它归于 Alan Waterman。

两步的做法

1. 最先的四条消息不经抽签，直接进入记忆。
2. 第 $t$ 条消息（第五条、第六条以及之后的每一条）以 $4/t$ 的机会进入记忆。如果它进去了，就替换掉已保存的四条中随机选出的一条。

所以第五条消息以 4/5 的机会进入，第一百条以 4/100 的机会进入。新消息进入的机会越来越小，但旧消息已经多次面临被挤出去的风险，这两种效应恰好相互抵消。我们在第五条消息之后验证一下。它以 4/5 的机会进入。第一条消息只有在第五条进入了（4/5）并且恰好落在它的位置上（1/4）时才会被挤出，也就是 1/5 的机会。它留下来的机会是 4/5：与第五条的相同。经过 $t$ 条消息之后，其中每一条留在记忆里的机会都是 $4/t$。

机会均等并不是保证

在实验中，数据流有 20 条消息。十八条与配送有关，而第九条和第十五条这两条与退货有关。每次运行都把这样的数据流跑 2000 遍，并统计每个位置最终留在记忆里的频率。抽签是真实的，所以每次的结果都会相差零点几个百分点。

采用 Reservoir Sampling 时，每根柱子都在 20% 左右，也就是 4/20。与此同时，在大多数轮次中，两条退货消息没有一条留在记忆里。精确值是 3060/4845，约 63%：在从 20 条消息中选出的所有四条组合里，完全由那十八条配送消息组成的就占这么多。这种方法对单条消息是公平的，但并不保证每个类别都有代表。

这在哪里要紧

在带回放的学习中，Reservoir Sampling 常被用作写入缓冲区的方式：既不需要知道数据流的长度，也不需要知道任务之间的边界。Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, 算法 2 正是这样用它的。在他们针对图像任务的实验中，它表现良好，只有记忆非常小时例外，那时较早的类别会从缓冲区里消失；这种情况下，注重各类别均等代表的策略表现更好（§4.4）。这是图像分类上的结果，而不是 LLM 上的。

算法本身与机器学习无关。Vitter 1985 年的论文描述的是从长度未知的磁带上随机抽取记录，并提出了更快的变体：它们不在每条记录上都抽签，而是算出要跳过多少条记录。客户消息和 20 个位置的数据流是自拟的例子。

• Experience Replay 需要一个装有旧样本的缓冲区；Reservoir Sampling 是决定哪些样本进入其中的方法之一。
• Continual Learning 设想的是在记忆有限的条件下从数据流中学习，也就是无法把一切都保留下来的情形。
• Catastrophic Forgetting [Polski] 在某个旧类别的样本全部从小记忆中被挤出时可能加剧。

文字和插图在 AI 的协助下完成。消息流和演示是自拟的简化教学示例；插图是比喻，而不是算法的示意图。