重要性抽樣

重要性抽樣（英文：importance sampling），或者喊做優惠抽樣（法文：échantillonnage préférentiel），係一種方法攞來減少方差嘅，用喺Monte-Carlo方法裏頭。重要性抽樣嘅基本思想係，喺要揾到嘅估計器上高，一場模擬當中啲值憑隨機變量抽出嘅有噻啲嘅影響係大過其他值。如果啲值啲大尐嘅出現得頻繁多尐，就可以降低隻估計器嘅方差。

所以，重要性抽樣嘅做法就係揀一隻分佈鼓勵啲重要嘅值。如果直接應用佢做模擬，有偏分佈會導致隻估計都有偏。之不過加權畀嘸同嘅模擬之後種偏差就得到找平，所以重要性抽樣估計係無偏嘅。啲權重攞来派畀每個模擬嘅係似然比，係真實分佈相對於有偏分佈嘅Radon-Nikodym 密度。

基本點畀攞重要性抽樣來實現模擬係揀返有偏分佈。重要性抽樣嘅關鍵係揀或者作一個好嘅有偏分佈。噉子嘅優勢係慳得計算時間好多，而一隻勩嘅分佈會有缺點係計算時間仲長過簡單嘅Monte-Carlo模擬。

理論

蒙地卡羅

計便要估計一個量G ，個量攞積分形式表示：

${\displaystyle G=\int _{a}^{b}g(x)\,{\mbox{d}}x}$

本例考慮積分喺一維，不過都推廣得，到任何維度。 蒙地卡羅基本原理係，捉上高隻積分睇成

${\displaystyle G=(b-a)\int _{a}^{b}g(x)f_{X}(x)\,{\mbox{d}}x=(b-a)\,\mathbb {E} (g(X))}$

其中X係隨機變量，均勻分佈喺 [ a;b ] 上嘅，而且${\displaystyle f_{X}(\cdot )={\frac {1}{b-a}}}$係佢隻密度。 如果有樣本${\displaystyle (x_{1},x_{2},\cdots ,x_{N})}$, 獨立同分佈 (iid) ，根據${\displaystyle {\mathcal {U}}([a;b])}$ ，憑下式就估計得到G：

${\displaystyle {\hat {g}}_{N}={\frac {(b-a)}{N}}\sum _{i=1}^{N}g(x_{i})}$

隻係隻估計量畀G，係無偏（即， ${\displaystyle \mathbb {E} ({\hat {g}}_{N})=G}$ ) 又一致（根據大數定律 ）嘅。佢方差係：

${\displaystyle \sigma _{{\hat {g}}_{N}}^{2}={\frac {(b-a)^{2}\sigma _{g}^{2}}{N}}}$

其中${\displaystyle \sigma _{g}^{2}}$係方差畀隨機變量${\displaystyle g(X)}$

${\displaystyle \sigma _{g}^{2}={\frac {1}{(b-a)}}\int _{a}^{b}g^{2}(x)\,{\mbox{d}}x-\left({\frac {1}{b-a}}\int _{a}^{b}g(x)\,{\mbox{d}}x\right)^{2}}$

優惠抽樣原理

優惠抽樣嘅主要思想係喺模擬入便換走喺${\displaystyle [a;b]}$上嘅均勻密度，變成一隻替代密度（或者講係biaisée密度），隻表示成${\displaystyle f^{\ast }\,}$、嘗試去模仿隻函數g嘅。噉樣就取代得隻均勻抽樣冇偏向到任何埞方嘅，成為「可信」多尐嘅抽樣。因此，抽樣係根據函數g嘅重要性来：喺g嘸顯著嘅區柵抽樣冇乜意義，相反要專注喺啲高重要性嘅區柵。噉樣做來希望到減少得到隻方差${\displaystyle \sigma _{g}^{2}}$。即係如果畀有誤差水平係固定嘅，相較經典嘅蒙特卡羅方法，理論上來講優惠抽樣減少得模擬次數 N。

改寫隻要估計嘅積分，改成：

${\displaystyle G=\int _{a}^{b}{\frac {g(x)}{f^{\ast }(x)}}f^{\ast }(x)\,{\mbox{d}}x}$

相當於：

${\displaystyle G=\mathbb {E} ^{\ast }[w(X)]}$

其中${\displaystyle w(x)=g(x)/f^{\ast }(x)}$ （喊做似然比），其中X係模擬跟密度${\displaystyle f^{\ast }}$來。好容易推廣上高結果：估計量G係

${\displaystyle {\tilde {g}}_{N}={\frac {1}{N}}\sum _{i=1}^{N}w(x_{i})}$

其中${\displaystyle (x_{1},x_{2},\cdots ,x_{N})}$係一串獨立同分佈嘅樣本，根據密度${\displaystyle f^{\ast }}$來嘅。方差畀隻估計量係攞下式得出：

${\displaystyle {\mbox{Var}}^{\ast }({\tilde {g}}_{N})={\frac {{\mbox{Var}}^{\ast }[w(X)]}{N}}}$

最後有：

${\displaystyle {\mbox{Var}}^{\ast }[w(X)]={\mbox{Var}}^{\ast }\left[{\frac {g(X)}{f^{\ast }(X)}}\right]=\int _{a}^{b}\left[{\frac {g(x)}{f^{\ast }(x)}}\right]^{2}f^{\ast }(x)\,{\mbox{d}}x-G^{2}}$

因此，問題係專注喺攞到一隻有偏密度${\displaystyle f^{\ast }\,}$等隻方差畀 EP 估計量要細過隻方差畀經典嘅蒙特卡洛方法。隻密度、最細化到隻方差嘅（噻啲條件下最細化到零），喊做最啱嘅偏置密度，後者等於：

${\displaystyle f^{\ast }(x)={\frac {|g(x)|}{\displaystyle \int _{a}^{b}|g(x)|\,{\mbox{d}}x}}}$

之不過種揀選係冇效用嘅，因為我哋揾緊嘅係分母。但係，可以期待透過揀選密度${\displaystyle f^{\ast }}$來減少方差，再現隻函數g 。

Quasi蒙地卡羅

要估計積分${\displaystyle G=\int _{a}^{b}g(x)\,{\mbox{d}}x}$，都可以慳丟前面所有啲概率形式。嘸使隨機變量，我哋可以使啲序列係低差異（英文：Low-discrepancy sequence）嘅（譬如 Sobol 序列）。考慮維度 1，最簡單嘅方法係：

${\displaystyle G=\int _{a}^{b}g(x)\,{\mbox{d}}x\quad \simeq \quad {\frac {b-a}{N}}\sum _{i=1}^{N}g\left(a+(b-a){\frac {i}{N}}\right)}$

同通常嘅蒙特卡洛一樣，函數g接近常數嘅話，種近似畀積分就收斂得快多尐。如果g係嚴格嘅常數，係噉定 N = 1 就攞得到精確嘅積分。因此，減少方差畀g都好重要；為達成個目標，使用優惠抽樣就要似下式噉：

${\displaystyle G=\int _{a}^{b}g(x)\,{\mbox{d}}x=\int _{a}^{b}{\frac {g(x)}{f^{*}(x)}}f^{*}(x)\,{\mbox{d}}x\quad =\quad \int _{F(a)}^{F(b)}{\frac {g(F^{-1}(y))}{f^{*}(F^{-1}(y))}}\,{\mbox{d}}y}$

其中更改到變量y = F ( x ) ，藉由${\displaystyle F\,'(x)=f^{*}(x)>0}$ 。好明顯，如果${\displaystyle f^{*}\simeq g}$，噉隻函數喺右便等待積分嘅就接近常數1（並因此方差低）。 為了建立聯繫畀上節啲概率解釋，我哋留意到${\displaystyle f^{*}}$係着定義成一隻因子K，隻會消失喺隻商附近嘅。因此，可以強行定${\displaystyle \int _{a}^{b}f^{*}(x)\,{\mbox{d}}x=1}$ ，等佢成為 [a, b] 上嘅概率密度。然之後變量嘅變化就得自然解釋成為概率嘅變化，因此有簡化 ：

${\displaystyle \int _{F(a)}^{F(b)}{\frac {g(F^{-1}(y))}{f^{*}(F^{-1}(y))}}\,{\mbox{d}}y\quad =\quad \int _{0}^{1}{\frac {g(F^{-1}(y))}{f^{*}(F^{-1}(y))}}\,{\mbox{d}}y}$

種技巧都立即推廣得，到任何維度。

引書

Morio, J.; Balesdent, M. (2015). Estimation of Rare Event Probabilities in Complex Aerospace and Other Systems (英文). Cambridge: Elsevier Science. p. 216. ISBN 978-0-08-100091-5.