跳至內容

別名方法

維基百科,自由的百科全書

在計算機科學的計算中,別名方法(英語:Alias Method),又稱別名採樣法別名表法別名表採樣法,是一個由A. J. 沃克(英語:A. J. Walker)提出的用於從一個離散的概率分佈中取樣的高效算法[1][2] 該算法可在任意的概率分佈 pi 下返回整數值 1 ≤ in。此類算法通常需要 O(n log n)O(n) 的預處理時間,之後可 O(1) 時間複雜度內進行隨機取樣。[3]

算法

算法在內部構造兩張表:概率 Ui別名表 Ki (1 ≤ in)。隨機取樣時,首先由一個均勻的骰子確定表內索引。而後,根據概率表索引位置存儲的概率,進行一次有偏硬幣英語Biased_coin拋投實驗,從而確定最終結果是 i 還是 Ki[4]

具體來說,算法進行如下操作:

  1. 輸出一個均勻的隨機變量 0 ≤ x < 1
  2. i = ⌊nx⌋ + 1y = nx + 1 − i。(此時 i 均勻分佈於 {1, 2, …, n},y 均勻分佈於 [0, 1)。)
  3. 如果 y < Ui,則返回 i。這是有偏硬幣拋投實驗。
  4. 否則,返回 Ki

Marsaglia等人曾提出名為「平方直方圖」的概率表的替代方案。[5]該方案在上述第3步使用 x < Vi(其中 Vi = (Ui + i − 1)/n)作為判斷條件,從而無需計算 y

表的生成

可以在原概率分佈上,增加若干 pi = 0 的情形,以將 n 增加到某些便於計算的值,例如2的冪。

生成表的第一步是執行 Ui = npi,由此將表中的元素為三類:

  • 「溢滿」組:Ui > 1
  • 「不滿」組:Ui < 1Ki 尚未初始化,
  • 「恰好」組:Ui = 1Ki 已被初始化。

Ui = 1,則相應的別名表值 Ki 永遠不會被用到,因而其取值是無關緊要的。但令 Ki = i 會更加自然。

只要不是所有的元素是在「恰好」組,就重複執行以下步驟:

  1. 任意從「溢滿」組和「不滿」組各選擇一個元素 Ui > 1Uj < 1。(若其中一個存在,則另一個也必然存在。)
  2. 別名表中索引為 j 的空間尚未被設置,將其設置為 iKj = i
  3. 更新概率表中索引為 i 的空間: Ui = Ui − (1 − Uj) = Ui + Uj − 1
  4. 元素 j 現在應歸為「恰好」組。
  5. 對於元素 i,根據更新後的 Ui,將其分在恰當的組中。

每輪迭代至少使一個元素進入「恰好」組。因此,至多經過 n−1 輪迭代後,該過程必然終止。每輪迭代可在 O(1) 時間內完成,從而生成表的過程可在 O(n) 時間內完成。

Vose<ref name="Vose">:974指出,浮點數四捨五入帶來的誤差可能導致第1步中提到的斷言不成立。若其中一個組別已無剩餘元素,則可將另一個組內剩餘的其他元素的 Ui 以課忽略的誤差設置為1。

別名表的構造不唯一。

由於當 y < Ui 時,查表過程會稍微快一些(因為無需訪問 Ki);生成表時,人們會期望最大化所有 Ui 的和。然而,這是一個NP困難問題<ref name="marsaglia">:6,但以貪心算法可以合理地接近這一目標:從最富有者拆解給最貧窮者。也就是說,在每次迭代中,選取最大的 Ui 和最小的 Uj。在這個過程中,我們要對 Ui 進行排序,於是需要 O(n log n) 的時間複雜度。

效率

儘管在產生均勻隨機變量非常快時,Alias方法非常高效;但在某些情況下,就隨機比特的使用而言,還有很大優化空間。這是因為,哪怕其實只需少量隨機比特,Alias方法每回也都使用隨機變量 x 的所有隨機比特。

舉個例子,當概率特別平衡時,會有很多 Ui = 1 的情形;此時 Ki 是不必要的。因此,產生 y 就是浪費時間了。例如,如果 p1 = p2 = 12,然後一個3 位的隨機變量 x 可以用來做32次隨機取樣,但Alias方法只能用一次。

再舉一個例子,當概率特別不平衡時,會有很多 Ui ≈ 0 的情形。例如,如果 p1 = 0.999p2 = 0.001;那麼多數時候,只需少量隨機比特即可決定結果為1。在這種情況下,Marsaglia 提出的表方法<ref name="marsaglia">:1–4更為有效。若在相同概率分佈下進行大量重複取樣,平均而言,我們只需遠少於1個隨機比特即可。利用算術編碼技術,在給定二元熵函數英語Binary_entropy_function時,我們可以達到這一下限。

文獻

實現

參考文獻

  1. ^ Walker, A. J. New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters. April 1974, 10 (8): 127. doi:10.1049/el:19740097. 
  2. ^ Walker, A. J. An Efficient Method for Generating Discrete Random Variables with General Distributions. ACM Transactions on Mathematical Software. September 1977, 3 (3): 253–256. doi:10.1145/355744.355749. 
  3. ^ Vose, Michael D. A linear algorithm for generating random numbers with a given distribution (PDF). IEEE Transactions on Software Engineering. September 1991, 17 (9): 972–975 [2019-12-02]. Bibcode:10.1.1.398.3339 請檢查|bibcode=值 (幫助). doi:10.1109/32.92917. (原始內容存檔 (PDF)於2013-10-29). 
  4. ^ Darts, Dice, and Coins: Sampling from a Discrete Distribution. KeithSchwarz.com. 29 December 2011 [2011-12-27]. (原始內容存檔於2012-01-04). 
  5. ^ Marsaglia, George; Tsang, Wai Wan; Wang, Jingbo, Fast Generation of Discrete Random Variables, Journal of Statistical Software, 2004-07-12, 11 (3): 1–11, doi:10.18637/jss.v011.i03