并行随机数生成

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

SeedSequence 衍生

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

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

例如, MT19937 的状态由 624 个 uint32 整数组成.采用 32 位整数种子的一个简单方法是将状态的最后一个元素设置为 32 位种子,其余元素保留为 0.对于 MT19937 来说,这是一个有效的状态,但不是一个好状态.如果 0 太多,梅森旋转算法会 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 池略有不同时发生重叠. 除了每个周期中 \(2^{127}\) 个长周期的位置之外, PCG64DXSM 还具有由种子确定的 \(2^{128}\) 个单独的周期,因此,必须同时进入或靠近同一周期,并在周期中播种附近的位置. Philox 具有完全独立的由种子确定的周期. SFC64 包含一个64位计数器,因此每个唯一的种子至少与任何其他种子相距 \(2^{64}\) 次迭代. 最后, MT19937 具有难以想象的巨大周期. 观察到失败的方式是 SeedSequence 内部发生冲突.

整数种子序列

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

例如,一种常见的用例是将一个根种子整数传递给工作进程以进行整个计算,并将整数worker 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) 开始,否则它将重新创建相同的流.另一方面,如果您仔细构造流,那么您可以保证拥有不重叠的流.