使用 PCG64DXSM 升级 PCG64#

在 NumPy 1.17 发布后，发现在大规模并行环境中使用的 PCG64 BitGenerator 存在统计学上的弱点，这些弱点在首次发布时并不明显。大多数用户永远不会遇到这种弱点，继续使用 PCG64 是安全的。我们引入了一个新的 PCG64DXSM BitGenerator，它将最终成为未来版本中 default_rng 使用的新默认 BitGenerator 实现。PCG64DXSM 解决了统计学上的弱点，同时保留了 PCG64 的性能和特性。

这会影响我吗？#

如果您

  1. 只使用一个 Generator 实例，

  2. 只使用 RandomState 或 numpy.random 中的函数，

  3. 仅使用 PCG64.jumped 方法生成并行流，

  4. 显式使用 PCG64 以外的 BitGenerator，

那么这种弱点完全不会影响您。请继续。

如果您使用中等数量的并行流（数千个），这些流是通过 default_rng 或 SeedSequence.spawn 创建的，那么遇到此弱点的几率可以忽略不计。您可以继续舒适地使用 PCG64。

如果您使用非常大量的并行流（数百万个），并且从每个流中抽取大量数据，那么遇到此弱点的几率可能会变得不可忽略，即使仍然很小。一个这样的用例可能是一个非常大的分布式强化学习问题，其中有数百万次长期的蒙特卡洛回放，每次回放都会生成数十亿个随机数。此类用例应考虑显式使用 PCG64DXSM 或其他现代 BitGenerator，如 SFC64 或 Philox，但您可能计算过的旧结果不太可能无效。无论如何，这种弱点是一种 生日问题 碰撞。也就是说，数百万个并行流中的一对并行流，当一起考虑时，可能会在一段时间内未能通过严格的随机性统计测试。其余数百万个流都将是完美的，并且在大多数应用程序中，坏配对对整个计算的影响很可能被其余流所淹没。

技术细节#

像许多 PRNG 算法一样，PCG64 由一个转换函数和一个输出函数构成，转换函数使 128 位状态前进，输出函数将 128 位状态混合成一个 64 位整数进行输出。PCG 系列 PRNG 的设计原则之一是在转换函数和输出函数之间平衡计算成本（和伪随机性强度）。转换函数是一个 128 位线性同余生成器 (LCG)，它由 128 位状态乘以一个固定的乘法常数，然后在 128 位模运算中加上一个用户选择的增量组成。LCG 是经过良好分析的 PRNG，具有已知的弱点，尽管 128 位 LCG 本身足够大，可以通过严格的统计测试，只需一个微不足道的输出函数。PCG64 的输出函数旨在通过进行“恰到好处”的位混淆来弥补一些已知的弱点，以增强统计特性，而不会增加过多的计算成本。

这些已知的弱点之一是，将 LCG 的状态向前推进二的幂次方步（bg.advance(2**N)）将导致低 N 位与刚刚留下的状态相同。对于从单个流中顺序抽取，这影响很小。剩余的 \(128-N\) 位在任何实际可观察的 N 值下都提供了足够的伪随机性，这就是为什么当您的应用程序只使用单个流时，您不必担心这一点。同样，PCG64.jumped 方法使用精心选择的步数来避免创建这些冲突。但是，一旦您开始创建“随机初始化的”并行流，无论是通过反复调用 default_rng（使用操作系统熵）还是使用 SeedSequence.spawn，那么我们需要考虑创建一对不良流需要多少低位“碰撞”，然后评估创建此类碰撞的概率。经验表明，如果我们共享状态的低 58 位和增量，那么当交错这对流时，在抽取几 GB 数据后，它们将会在合理的时间内未能通过 PractRand 测试。根据标准的生日问题计算，对于 58 位碰撞，我们可以创建 \(2^{29}\) 个流，约合五亿个流，此时发生此类碰撞的概率就会很高。五亿个流已经很多了，而且每个流在统计相关性变得明显（即使对最严格的 PractRand 测试也是如此）之前需要抽取的数据量是 GB 级别。但这对于像分布式强化学习这样的大型应用程序来说已经迫在眉睫了。有理由预期，即使在这些应用程序中，碰撞可能也不会对总体结果产生实际影响，因为统计问题仅限于发生碰撞的那一对。

现在，让我们考虑增量不受约束相同的情况。我们对 PCG64 的实现同时播种状态和增量；也就是说，两次调用 default_rng（几乎可以肯定）具有不同的状态和增量。在我们首次发布时，我们认为拥有播种的增量会提供一定程度的额外保护，需要同时“接近”状态空间和增量空间才能观察到流对之间的相关性（PractRand 故障）。如果真是这样，那么“瓶颈”将是 SeedSequence 内部的 128 位熵池大小（128 位碰撞属于“极其不可能”的类别）。不幸的是，事实并非如此。

LCG 的一个已知特性是，不同的增量会创建 *不同的* 流，但存在已知关系。每个 LCG 都有一个遍历所有 \(2^{128}\) 个不同 128 位状态的轨道。具有不同增量的两个 LCG 是相关的，因为可以通过“旋转”第一个 LCG 的轨道（前进一定步数，这些步数可以从两个增量计算得出）使得这两个 LCG 始终具有相同的状态，最多相差一个加性常数，并且可能存在位反转。如果您以同步方式迭代两个流，那么状态将 *始终* 以该相同的加性常数（以及是否存在反转）保持相关。请记住，PCG64 由转换函数（LCG）和输出函数组成。人们曾期望输出函数的混淆效果足够强，可以使不同的流基本独立（即，“通过 PractRand 测试”），除非两个增量以病态方式相关（例如，1 和 3）。我们最初在 PCG64 中实现的当时标准的 PCG 算法的 XSL-RR 输出函数，被证明太弱，无法弥补我们上面描述的底层 LCG 的 58 位碰撞。对于任何给定的增量对，状态的“碰撞”空间的大小是相同的，因此对于这种弱点，增量提供的额外差异性并没有转化为 PractRand 可以检测到的统计相关性的额外保护。

幸运的是，增强输出函数可以纠正这种弱点，并且 *确实* 将增量差异提供的额外差异性转化为对这些低位碰撞的额外保护。值得称赞的是，PCG 的作者 在围绕新的 BitGenerator 系统漫长的诞生过程中，针对相关讨论开发了一个更强的输出函数。我们 NumPy 开发人员选择“保守”并使用了当时经过更长时间测试的 XSL-RR 变体。DXSM 输出函数采用了用于强整数哈希的“xorshift-multiply”结构，该结构比 XSL-RR 输出函数具有更好的雪崩效应。虽然存在会引起“坏”加性常数（将两个流关联起来）的“病态”增量对，但绝大多数增量对会引起“好”的加性常数，从而使 LCG 状态的仅仅是不同的流变成实际独立的输出流。确实，我们曾经关于 PCG64 的说法现在对 PCG64DXSM 也是成立的：碰撞是可能的，但两个流必须同时在 128 位状态空间中“接近” *并且* 在 127 位增量空间中“接近”，因此比在 128 位内部 SeedSequence 池中碰撞的微乎其微的机会要低。DXSM 输出函数比 XSL-RR 计算更密集，但在大多数机器上，LCG 中的一些优化弥补了性能损失，因此 PCG64DXSM 是一个良好、安全的升级。当然，有无数种更强的输出函数可以考虑，但大多数都会有更高的计算成本，而 DXSM 输出函数现在已经通过 PractRand 进行了大量 CPU 循环的测试。