使用 PCG64DXSM 升级 PCG64#
PCG64 BitGenerator 在大规模并行上下文中的使用已被证明存在统计弱点,这在 numpy 1.17 的首次发布时并不明显. 大多数用户永远不会观察到这种弱点,并且可以安全地继续使用 PCG64 . 我们引入了一个新的 PCG64DXSM BitGenerator ,它最终将成为未来版本中 default_rng 使用的新默认 BitGenerator 实现. PCG64DXSM 解决了统计弱点,同时保留了 PCG64 的性能和特性.
这会影响我吗?#
如果
仅使用单个
Generator实例,仅使用
RandomState或numpy.random中的函数,仅使用
PCG64.jumped方法生成并行流,显式使用
PCG64之外的BitGenerator,
那么这种弱点根本不会影响到您.继续吧.
如果您使用 default_rng 或 SeedSequence.spawn 创建的适度数量的并行流(数千个),那么观察到这种弱点的机会微乎其微.您可以继续舒适地使用 PCG64 .
如果您使用非常大量的并行流(数百万个),并从每个流中抽取大量数字,那么如果仍然很小,观察到这种弱点的机会可能会变得不可忽略. 这种用例的一个例子是一个非常大的分布式强化学习问题,其中数百万个长的蒙特卡罗模拟,每个模拟生成数十亿个随机数抽取. 这种用例应考虑显式使用 PCG64DXSM 或其他现代 Birthday Paradox ,如 SFC64 或 Philox ` ,但您可能已经计算出的任何旧结果都不太可能无效. 无论如何,这种弱点是一种"生日悖论 碰撞". 也就是说,数百万个并行流中的一对,放在一起考虑,可能会在严格的随机性统计测试集中失败. 剩下的数百万个流都将完全正常,并且在大多数应用中,坏对在整个计算中的影响很可能被剩余流淹没.
技术细节#
与许多 PRNG 算法一样, PCG64 由一个转换函数(用于推进一个 128 位状态)和一个输出函数(用于将 128 位状态混合成一个 64 位整数以便输出)构成.PCG 系列 PRNG 的指导设计原则之一是在转换函数和输出函数之间平衡计算成本(以及伪随机强度).转换函数是一个 128 位线性同余发生器 (LCG),它包括将 128 位状态与一个固定的乘法常数相乘,然后在 128 位模算术中加上一个用户选择的增量.LCG 是经过充分分析的 PRNG,具有已知的弱点,尽管 128 位 LCG 足够大,可以通过对其自身进行严格的统计测试,只使用简单的输出函数. PCG64 的输出函数旨在通过对位进行"恰到好处"的加扰来弥补其中一些已知的弱点,以协助统计特性,而不会增加太多的计算成本.
其中一个已知的弱点是,将 LCG 的状态以 2 的幂次 ( bg.advance(2N) ) 的步数推进将使较低的 N 位与刚刚离开的状态相同.对于从顺序中提取的单个流,这几乎没有影响.剩余的 \(128-N\) 位提供了大量的伪随机性,这些伪随机性将被混合到任何可以在单个流中观察到的实际 N 中,这就是为什么如果您仅在应用程序中使用单个流,则无需担心这一点.类似地, PCG64.jumped 方法使用精心选择的步数来避免创建这些冲突.但是,一旦您开始创建"随机初始化"的并行流,无论是通过调用 default_rng 重复使用 OS 熵,还是使用 SeedSequence.spawn ,那么我们需要考虑有多少较低的位需要"冲突"才能创建一对坏流,然后评估创建这种冲突的概率. Empirically ,已经确定,如果共享状态的较低 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 author’s credit 赞扬的是,她在新的 BitGenerator 系统漫长的诞生过程中,针对相关讨论开发了一个更强大的输出函数.我们 NumPy 开发者选择"保守",使用当时经过更长时间测试的 XSL-RR 变体.DXSM 输出函数采用了一种在强整数哈希中使用的 "xorshift-multiply" 结构,它比 XSL-RR 输出函数具有更好的雪崩效应.虽然存在诱导 "坏" 加性常数的 "病态" 增量对,这些加性常数关联两个流,但绝大多数对会诱导 "好" 加性常数,使 LCG 状态的仅仅不同的流变成实际上独立的输出流.事实上,现在我们曾经对 PCG64 所做的声明实际上适用于 PCG64DXSM :碰撞是可能的,但两个流必须同时在 128 位状态空间中"接近"并且在 127 位增量空间中"接近",因此这比在 128 位内部 SeedSequence 池中碰撞的可以忽略不计的机会更小.DXSM 输出函数比 XSL-RR 在计算上更密集,但 LCG 中的一些优化弥补了大多数机器上的性能损失,因此 PCG64DXSM 是一个好的,安全的升级.当然,可以考虑无数个更强大的输出函数,但大多数函数会产生更大的计算成本,并且 DXSM 输出函数现在已经通过 PractRand 接受了多次 CPU 周期测试.