重要性抽樣 (英文 :importance sampling ),或者喊做優惠抽樣 (法文 :échantillonnage préférentiel ),係一種方法攞來減少方差 嘅,用喺Monte-Carlo方法 裏頭。重要性抽樣嘅基本思想係,喺要揾到嘅估計器上高,一場模擬 當中啲值憑隨機變量 抽出嘅有噻啲嘅影響係大過其他值。如果啲值啲大尐嘅出現得頻繁多尐,就可以降低隻估計器嘅方差。
所以,重要性抽樣嘅做法就係揀一隻分佈鼓勵啲重要嘅值。如果直接應用佢做模擬,有偏分佈會導致隻估計都有偏。之不過加權畀嘸同嘅模擬之後種偏差就得到找平,所以重要性抽樣估計係無偏嘅。啲權重攞来派畀每個模擬嘅係似然比,係真實分佈相對於有偏分佈嘅Radon-Nikodym 密度 。
基本點畀攞重要性抽樣來實現模擬係揀返有偏分佈。重要性抽樣嘅關鍵係揀或者作一個好嘅有偏分佈。噉子嘅優勢係慳得計算時間好多,而一隻勩嘅分佈會有缺點係計算時間仲長過簡單嘅Monte-Carlo模擬。
蒙地卡羅
編輯
計便要估計一個量G ,個量攞積分形式表示:
G = ∫ a b g ( x ) d x {\displaystyle G=\int _{a}^{b}g(x)\,{\mbox{d}}x} 本例考慮積分喺一維,不過都推廣得,到任何維度。
蒙地卡羅基本原理係,捉上高隻積分睇成
G = ( b − a ) ∫ a b g ( x ) f X ( x ) d x = ( b − a ) E ( g ( 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 ] 上嘅,而且f X ( ⋅ ) = 1 b − a {\displaystyle f_{X}(\cdot )={\frac {1}{b-a}}} 係佢隻密度。
如果有樣本( x 1 , x 2 , ⋯ , x N ) {\displaystyle (x_{1},x_{2},\cdots ,x_{N})} , 獨立同分佈 (iid) ,根據U ( [ a ; b ] ) {\displaystyle {\mathcal {U}}([a;b])} ,憑下式就估計得到G:
g ^ N = ( b − a ) N ∑ i = 1 N g ( x i ) {\displaystyle {\hat {g}}_{N}={\frac {(b-a)}{N}}\sum _{i=1}^{N}g(x_{i})} 隻係隻估計量畀G ,係無偏(即, E ( g ^ N ) = G {\displaystyle \mathbb {E} ({\hat {g}}_{N})=G} ) 又一致(根據大數定律 )嘅。佢方差係:
σ g ^ N 2 = ( b − a ) 2 σ g 2 N {\displaystyle \sigma _{{\hat {g}}_{N}}^{2}={\frac {(b-a)^{2}\sigma _{g}^{2}}{N}}} 其中σ g 2 {\displaystyle \sigma _{g}^{2}} 係方差畀隨機變量g ( X ) {\displaystyle g(X)}
σ g 2 = 1 ( b − a ) ∫ a b g 2 ( x ) d x − ( 1 b − a ∫ a b g ( x ) d x ) 2 {\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}}
優惠抽樣原理
編輯
優惠抽樣嘅主要思想係喺模擬入便換走喺[ a ; b ] {\displaystyle [a;b]} 上嘅均勻密度,變成一隻替代密度(或者講係biaisée密度 ),隻表示成f ∗ {\displaystyle f^{\ast }\,} 、嘗試去模仿隻函數g 嘅。噉樣就取代得隻均勻抽樣冇偏向到任何埞方嘅,成為「可信」多尐嘅抽樣。因此,抽樣係根據函數g 嘅重要性来:喺g 嘸顯著嘅區柵抽樣冇乜意義,相反要專注喺啲高重要性嘅區柵。噉樣做來希望到減少得到隻方差σ g 2 {\displaystyle \sigma _{g}^{2}} 。即係如果畀有誤差水平係固定嘅,相較經典嘅蒙特卡羅方法,理論上來講優惠抽樣減少得模擬次數 N。
改寫隻要估計嘅積分,改成:
G = ∫ a b g ( x ) f ∗ ( x ) f ∗ ( x ) d x {\displaystyle G=\int _{a}^{b}{\frac {g(x)}{f^{\ast }(x)}}f^{\ast }(x)\,{\mbox{d}}x} 相當於:
G = E ∗ [ w ( X ) ] {\displaystyle G=\mathbb {E} ^{\ast }[w(X)]} 其中w ( x ) = g ( x ) / f ∗ ( x ) {\displaystyle w(x)=g(x)/f^{\ast }(x)} (喊做似然比 ),其中X 係模擬跟密度f ∗ {\displaystyle f^{\ast }} 來。好容易推廣上高結果:估計量G 係
g ~ N = 1 N ∑ i = 1 N w ( x i ) {\displaystyle {\tilde {g}}_{N}={\frac {1}{N}}\sum _{i=1}^{N}w(x_{i})} 其中( x 1 , x 2 , ⋯ , x N ) {\displaystyle (x_{1},x_{2},\cdots ,x_{N})} 係一串獨立同分佈嘅樣本,根據密度f ∗ {\displaystyle f^{\ast }} 來嘅。方差畀隻估計量係攞下式得出:
Var ∗ ( g ~ N ) = Var ∗ [ w ( X ) ] N {\displaystyle {\mbox{Var}}^{\ast }({\tilde {g}}_{N})={\frac {{\mbox{Var}}^{\ast }[w(X)]}{N}}} 最後有:
Var ∗ [ w ( X ) ] = Var ∗ [ g ( X ) f ∗ ( X ) ] = ∫ a b [ g ( x ) f ∗ ( x ) ] 2 f ∗ ( x ) d x − G 2 {\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}} 因此,問題係專注喺攞到一隻有偏密度f ∗ {\displaystyle f^{\ast }\,} 等隻方差畀 EP 估計量要細過隻方差畀經典嘅蒙特卡洛方法。隻密度、最細化到隻方差嘅(噻啲條件下最細化到零),喊做最啱嘅偏置密度 ,後者等於:
f ∗ ( x ) = | g ( x ) | ∫ a b | g ( x ) | d x {\displaystyle f^{\ast }(x)={\frac {|g(x)|}{\displaystyle \int _{a}^{b}|g(x)|\,{\mbox{d}}x}}} 之不過種揀選係冇效用嘅,因為我哋揾緊嘅係分母。但係,可以期待透過揀選密度f ∗ {\displaystyle f^{\ast }} 來減少方差,再現隻函數g 。
Quasi蒙地卡羅
編輯
要估計積分G = ∫ a b g ( x ) d x {\displaystyle G=\int _{a}^{b}g(x)\,{\mbox{d}}x} ,都可以慳丟前面所有啲概率形式。嘸使隨機變量,我哋可以使啲序列係低差異 嘅(譬如 Sobol 序列)。考慮維度 1,最簡單嘅方法係:
G = ∫ a b g ( x ) d x ≃ b − a N ∑ i = 1 N g ( a + ( b − a ) i N ) {\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 都好重要;為達成個目標,使用優惠抽樣就要似下式噉:
G = ∫ a b g ( x ) d x = ∫ a b g ( x ) f ∗ ( x ) f ∗ ( x ) d x = ∫ F ( a ) F ( b ) g ( F − 1 ( y ) ) f ∗ ( F − 1 ( y ) ) d y {\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 ) ,藉由F ′ ( x ) = f ∗ ( x ) > 0 {\displaystyle F\,'(x)=f^{*}(x)>0} 。好明顯,如果f ∗ ≃ g {\displaystyle f^{*}\simeq g} ,噉隻函數喺右便等待積分嘅就接近常數1(並因此方差低)。
為了建立聯繫畀上節啲概率解釋,我哋留意到f ∗ {\displaystyle f^{*}} 係着定義成一隻因子K ,隻會消失喺隻商附近嘅。 因此,可以強行定∫ a b f ∗ ( x ) d x = 1 {\displaystyle \int _{a}^{b}f^{*}(x)\,{\mbox{d}}x=1} ,等佢成為 [a , b ] 上嘅概率密度。然之後變量嘅變化就得自然解釋成為概率嘅變化,因此有簡化 :
∫ F ( a ) F ( b ) g ( F − 1 ( y ) ) f ∗ ( F − 1 ( y ) ) d y = ∫ 0 1 g ( F − 1 ( y ) ) f ∗ ( F − 1 ( y ) ) d y {\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 .