使用 PCG64DXSM 升级 PCG64#
在高度并行环境中使用 PCG64 BitGenerator 已被证明存在在 numpy 1.17 首次发布时未显现的统计弱点.大多数用户永远不会观察到这一弱点,因此可以继续安全地使用 PCG64.我们引入了一个新的 PCG64DXSM BitGenerator,它最终将成为未来版本中 default_rng 使用的新默认 BitGenerator 实现.`PCG64DXSM` 解决了统计弱点,同时保留了 PCG64 的性能和特性.
这会影响我吗?#
如果你
只使用一个
Generator实例仅使用
RandomState或numpy.random中的函数仅使用
PCG64.jumped方法生成并行流,显式使用一个
BitGenerator而不是PCG64
那么这个弱点对你完全没有影响.继续.
如果你使用由 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` 的输出函数旨在通过进行”恰到好处”的位搅动来弥补一些已知的弱点,以协助统计特性,而不会增加太多的计算成本.
这些已知弱点之一是,通过一个二的幂次步数（bg.advance(2**N)）推进LCG的状态将使较低的``N``位与刚刚离开的状态相同.对于从顺序抽取的单个流,这几乎没有影响.剩余的 \(128-N\) 位提供了足够的伪随机性,将在任何实际的``N``中混合,这就是为什么如果你只在应用程序中使用单个流,就不需要担心这一点.同样,`PCG64.jumped` 方法使用精心选择的步数来避免创建这些碰撞.然而,一旦你开始创建”随机初始化”的并行流,无论是通过调用 default_rng 重复使用操作系统熵,还是使用 SeedSequence.spawn,那么我们需要考虑多少低位需要”碰撞”才能创建一对坏流,然后评估创建这种碰撞的概率.`经验上 <numpy/numpy#16313>`_,已经确定,如果共享状态的低58位并共享一个增量,那么当交错时,这对流将在合理的时间内失败 PractRand,在抽取几吉字节的数据后.根据标准的生日悖论计算58位的碰撞,我们可以看到我们可以创建 \(2^{29}\),或大约5亿个流,这时这种碰撞的概率变得很高.5亿个流相当高,每个流在统计相关性甚至在严格的``PractRand``测试中变得明显之前需要抽取的数据量在吉字节级别.但对于像分布式强化学习这样的非常大的应用程序,这是可以预见的.有理由期望即使在这样应用程序中,碰撞可能也不会在总结果中产生实际影响,因为统计问题仅限于碰撞的一对流.
现在,让我们考虑增量不受相同约束的情况.我们对 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 周期测试.