并行随机数生成

实施了四种主要策略,可用于在多个进程(本地或分布式)中生成可重复的伪随机数.

SeedSequence 派生

NumPy 允许您通过它们的 spawn() 方法来派生新的(具有非常高的概率)独立的 BitGenerator 和 Generator 实例.此派生由用于初始化位生成器随机流的 SeedSequence 实现.

SeedSequence implements an algorithm 来处理用户提供的种子(通常是某种大小的整数),并将其转换为 BitGenerator 的初始状态.它使用哈希技术来确保低质量的种子被转化为高质量的初始状态(至少,概率非常高).

例如, MT19937 的状态由 624 个 uint32 整数组成.采用 32 位整数种子的一种幼稚方法是只将状态的最后一个元素设置为 32 位种子,其余的保持为 0.这是 MT19937 的有效状态,但不是一个好的状态.如果 0 太多,Mersenne Twister 算法会 suffers if there are too many 0s .类似地,两个相邻的 32 位整数种子(即 12345 和 12346 )会产生非常相似的流.

SeedSequence 通过使用具有良好 avalanche properties 的连续整数哈希来避免这些问题,以确保翻转输入中的任何一位大约有 50% 的机会翻转输出中的任何一位.彼此非常接近的两个输入种子将产生彼此相差很远的初始状态(概率非常高).它的构造方式也使得您可以提供任意大小的整数或整数列表. SeedSequence 将获取您提供的所有位并将它们混合在一起,以生成 BitGenerator 初始化自身所需的位数.

这些属性共同意味着我们可以安全地将通常由用户提供的种子与简单的递增计数器混合在一起,以获得(以非常高的概率)彼此独立的 BitGenerator 状态.我们可以将其包装到一个易于使用且难以误用的 API 中.请注意,虽然 SeedSequence 试图解决与用户提供的小种子相关的许多问题,但我们仍然 recommend 使用 secrets.randbits 生成具有 128 位熵的种子,以避免人类选择的种子引入的剩余偏差.

from numpy.random import SeedSequence, default_rng

ss = SeedSequence(12345)

# Spawn off 10 child SeedSequences to pass to child processes.
child_seeds = ss.spawn(10)
streams = [default_rng(s) for s in child_seeds]

为方便起见,不需要直接使用 SeedSequence .上面的 streams 可以通过 spawn 直接从父生成器派生派生:

parent_rng = default_rng(12345)
streams = parent_rng.spawn(10)

子对象也可以派生来生成孙子对象,依此类推.每个子对象都有一个 SeedSequence ,其中它在派生的子对象树中的位置与用户提供的种子混合在一起,以生成独立的(具有非常高的概率)流.

grandchildren = streams[0].spawn(4)

此功能使您可以做出关于何时以及如何分割流的本地决策,而无需进程之间的协调.您不必预先分配空间以避免重叠或从公共全局服务请求流.这种通用的"树哈希"方案 not unique to numpy 但尚未得到广泛应用.Python 具有越来越灵活的并行化机制,此方案非常适合这种用法.

使用此方案,如果知道派生的流的数量,则可以估计碰撞概率的上限. SeedSequence 默认将其输入(包括种子和生成树路径)哈希到 128 位池中. 悲观估计 ( [1] ),该池发生冲突的概率约为 \(n^2*2^{-128}\) ,其中 ** n ** 是生成的流的数量. 如果一个程序使用了激进的一百万个流,约为 \(2^{20}\) ,那么至少有一对流相同的概率约为 \(2^{-88}\) ,这在很大程度上可以忽略不计 ( [2] ).

[1]

该算法经过精心设计,以消除许多可能发生冲突的方式. 例如,如果只进行一级生成,则可以保证所有状态都是唯一的. 但在餐巾纸上估计朴素的上限更容易,并且可以知道概率实际上更低而感到欣慰.

[2]

在此计算中,我们基本上可以忽略从每个流中提取的数字量. 有关 PCG64 的技术细节,请参见 使用 PCG64DXSM 升级 PCG64 . 我们提供的其他 PRNG 都内置了一些额外的保护措施,如果 SeedSequence 池略有不同,则可以避免重叠. PCG64DXSM 除了每个周期的 \(2^{127}\) 长度之外,还有 \(2^{128}\) 个由种子确定的单独周期,因此必须既要进入或靠近同一周期,又要播种周期中附近的位置. Philox 具有完全独立的,由种子确定的周期. SFC64 包含一个 64 位计数器,因此每个唯一的种子都至少与其他任何种子相距 \(2^{64}\) 次迭代. 最后, MT19937 具有难以想象的巨大周期. 观察到失败的方式是 SeedSequence 内部发生冲突.

整数种子序列

如上一节所述, SeedSequence 不仅可以接受整数种子,还可以接受任意长度的(非负)整数序列. 如果稍加注意,可以使用此功能来设计临时方案,以获得具有与生成相似安全保证的安全并行 PRNG 流.

例如,一种常见的用例是,一个 worker 进程传递一个用于整个计算的根种子整数,以及一个整数 worker ID(或更精细的 ID,例如作业 ID,批处理 ID 或类似的东西). 如果这些 ID 是确定性且唯一创建的,那么可以通过在列表中组合 ID 和根种子整数来派生可重现的并行 PRNG 流.

# default_rng() and each of the BitGenerators use SeedSequence underneath, so
# they all accept sequences of integers as seeds the same way.
from numpy.random import default_rng

def worker(root_seed, worker_id):
    rng = default_rng([worker_id, root_seed])
    # Do work ...

root_seed = 0x8c3c010cb4754c905776bdac5ee7501
results = [worker(root_seed, worker_id) for worker_id in range(10)]

这可以用来替代过去使用过的许多不安全的策略,这些策略试图将根种子和 ID 组合回单个整数种子值. 例如,通常会看到用户将 worker ID 添加到根种子,尤其是在使用遗留的 RandomState 代码时.

# UNSAFE! Do not do this!
worker_seed = root_seed + worker_id
rng = np.random.RandomState(worker_seed)

确实,对于以这种方式构建的并行程序的任何一次运行,每个 worker 都将具有不同的流. 但是,使用不同种子多次调用该程序很可能会获得重叠的 worker 种子集. 在作者的亲身经历中,更改根种子仅仅通过一两个增量来执行这些重复运行并不少见. 如果 worker 种子也是通过 worker ID 的小增量派生的,那么 worker 的子集将返回相同的结果,从而导致整个结果集合中存在偏差.

将 worker ID 和根种子组合为整数列表可以消除这种风险. 惰性播种实践仍然相当安全.

此方案确实要求额外的 ID 是唯一且确定性创建的. 这可能需要 worker 进程之间的协调. 建议将变化的 ID 放在不变的根种子之前. spawn 在用户提供的种子之后附加整数,因此如果您可能混合使用这种临时机制和生成,或者将您的对象传递给可能正在生成的库代码,那么预先附加您的 worker ID 而不是附加它们可以稍微安全一些,以避免冲突.

# Good.
worker_seed = [worker_id, root_seed]

# Less good. It will *work*, but it's less flexible.
worker_seed = [root_seed, worker_id]

考虑到这些注意事项,防止冲突的安全保证与上一节中讨论的生成几乎相同. 算法机制是相同的.

独立流

Philox 是一个基于计数器的 RNG,它通过使用弱密码学原语加密递增计数器来生成值.种子决定了用于加密的密钥.唯一的密钥会创建唯一的,独立的流. Philox 允许您绕过种子算法来直接设置 128 位密钥.相似但不同的密钥仍然会创建独立的流.

import secrets
from numpy.random import Philox

# 128-bit number as a seed
root_seed = secrets.getrandbits(128)
streams = [Philox(key=root_seed + stream_id) for stream_id in range(10)]

此方案确实要求您避免重用流 ID.这可能需要并行进程之间的协调.

跳转 BitGenerator 状态

jumped 推进 BitGenerator 的状态,就像已经绘制了大量的随机数一样,并返回具有此状态的新实例.特定数量的绘制因 BitGenerator 而异,范围从 \(2^{64}\) 到 \(2^{128}\) .此外,as-if 绘制还取决于特定 BitGenerator 生成的默认随机数的大小.支持 jumped 的 BitGenerator,以及 BitGenerator 的周期,跳转大小和默认无符号随机数中的位数如下所示.

BitGenerator	周期	跳转大小	每次抽取的位数
MT19937	\(2^{19937}-1\)	\(2^{128}\)	32
PCG64	\(2^{128}\)	\(~2^{127}\) ( [3] )	64
PCG64DXSM	\(2^{128}\)	\(~2^{127}\) ( [3] )	64
Philox	\(2^{256}\)	\(2^{128}\)	64

[3] (1,2)

跳转大小为 \((\phi-1)*2^{128}\) ,其中 \(\phi\) 是黄金比例.由于跳转会环绕周期,因此相邻流之间的实际距离将缓慢地变得小于跳转大小,但是以这种方式使用黄金比例是构建低差异序列的经典方法,该序列以最佳方式将状态分散在周期周围.您将无法跳转足够多,以使这些距离小到足以在您的生命周期内重叠.

jumped 可用于产生足够长的长块,以避免重叠.

import secrets
from numpy.random import PCG64

seed = secrets.getrandbits(128)
blocked_rng = []
rng = PCG64(seed)
for i in range(10):
    blocked_rng.append(rng.jumped(i))

使用 jumped 时,必须注意不要跳转到已使用的流.在上面的示例中,以后不能使用 blocked_rng[0].jumped() ,因为它会与 blocked_rng[1] 重叠.与独立流一样,如果此处的主进程想要通过跳转来拆分 10 个以上的流,则它需要从 range(10, 20) 开始,否则它将重新创建相同的流.另一方面,如果您仔细构造流,那么您可以保证拥有不重叠的流.