變異數縮減(variance reduction)
蒙地卡羅的誤差棒是 s / sqrt(N):你可以靠提高 N(多取樣本,但因為有平方根而又慢又貴)來縮小它,或靠縮小 s(你所平均之物的變異性)來縮小它。變異數縮減就是一族巧妙的技巧,它們攻擊的是 s 而非 N——重寫估計量,使每個樣本攜帶更多資訊,讓你用少得多的樣本得到相同精度,或用相同預算得到好得多的精度。
關鍵洞見是:同一個量通常有「許多」無偏估計量——不同的隨機配方都平均到正確答案——而它們的變異數天差地別。變異數縮減就挑出或設計一個低變異數的。主要技巧各自利用某種你事先知道的結構:「重要性取樣」在被積函數大的地方多取樣,再重新加權以維持無偏;「控制變數」減去一個你知道其精確平均、與之相關的量,抵消大半雜訊;「對偶變數」把每個樣本與一個鏡像樣本配對(用 u 與 1 - u),使它們的誤差部分抵消;「分層取樣」把定義域切成若干層、各自分別取樣,防止隨機結塊與空隙。每一種都能把變異數削減一個大因子,偶爾達數量級。
為何重要:因為誤差只以 1/sqrt(N) 下降,把變異數縮減 100 倍就等同於多取 100 倍樣本——而且便宜得多。因此變異數縮減是「一夜跑完」與「要跑一年」的蒙地卡羅計算之間的分野。誠實的告誡:這些方法需要對問題有所了解(好的提議密度、相關的控制量、合理的分層),選得差會適得其反、「增加」變異數,而且必須小心保持估計量「無偏」——一個悄悄移動了期望值的巧妙加權,是拿隨機誤差換系統誤差,那更糟。
估計 e^x 在 [0, 1] 上的積分(真值 e - 1 = 1.718)。N 個樣本的單純蒙地卡羅有某個變異數。對偶版本把每個 u 與 1 - u 配對,平均 (e^u + e^(1-u))/2;因為 e^x 單調,配對的誤差負相關,變異數無償下降超過一半——一半的功就得到相同精度。
攻擊變異數,而非樣本數——遠比蠻力便宜。
變異數縮減仰賴事先知道結構;草率的選擇反而可能「升高」變異數。最高原則是保持估計量無偏——一個移動了期望值的把戲,是拿會縮小的隨機誤差換一個永久的系統誤差。