使用 PCG64 升級 PCG64DXSM#

已證實在高度平行環境中使用 PCG64 BitGenerator 存在統計上的弱點，這在 numpy 1.17 的首次發行時並不明顯。大多數使用者永遠不會觀察到這個弱點，並且可以安全地繼續使用 PCG64。我們推出了一個新的 PCG64DXSM BitGenerator，它最終將成為未來版本中 default_rng 使用的新的預設 BitGenerator 實作。PCG64DXSM 解決了統計上的弱點，同時保留了 PCG64 的效能和功能。

這會影響我嗎？#

如果您

  1. 只使用單一 Generator 實例，

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

  3. 只使用 PCG64.jumped 方法來產生平行串流，

  4. 明確地使用 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 的輸出函數旨在通過對位元進行「恰到好處」的擾亂，來彌補其中一些已知的弱點，以輔助統計特性，而不會增加太多的計算成本。

其中一個已知的弱點是，以二的次方步數推進 LCG 的狀態 (bg.advance(2**N)) 會使較低的 N 位元與剛離開的狀態相同。對於從序列中提取的單一串流，這並不重要。剩餘的 \(128-N\) 位元提供了大量的偽隨機性，這些偽隨機性將混合到任何實際的 N 中，而 N 可以在單一串流中觀察到，這就是為什麼如果您僅在應用程式中使用單一串流，則無需擔心此問題的原因。同樣地，PCG64.jumped 方法使用精心選擇的步數，以避免產生這些碰撞。但是，一旦您開始建立「隨機初始化」的平行串流，無論是透過重複呼叫 default_rng 使用作業系統熵，還是使用 SeedSequence.spawn，那麼我們需要考慮有多少個較低的位元需要「碰撞」才能建立一對不良串流，然後評估產生這種碰撞的機率。根據經驗，已確定如果共享狀態的較低 58 位元並共享一個增量，則這對串流在交錯時，在提取幾個 GB 的資料後，會在合理的時間內未能通過 PractRand 測試。根據 58 位元碰撞的標準生日悖論計算，我們可以看到我們可以建立 \(2^{29}\) 個，或大約 5 億個串流，此時這種碰撞的機率變得很高。五億個串流非常多，並且每個串流需要提取的資料量，才能讓統計相關性甚至對嚴格的 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 池中碰撞的微不足道的機會還要小。PCG64DXSM 的 DXSM 輸出函數比 XSL-RR 需要更多的計算，但 LCG 中的一些優化措施在大多數機器上都彌補了效能損失，因此 PCG64DXSM 是一個良好且安全的升級。當然，可以考慮有無數個更強大的輸出函數，但大多數函數的計算成本都會更高，而 DXSM 輸出函數目前已通過 PractRand 進行了大量的 CPU 週期測試。