重要性採樣

重要性採樣（英語：importance sampling）是統計學中估計某一分布性質時使用的一種方法。該方法從與原分布不同的另一個分布中採樣，而對原先分布的性質進行估計。重要性採樣與計算物理學中的傘形採樣（英語：Umbrella sampling）相關。

原理[編輯]

假設 $X:\Omega \to \mathbb {R}$ 為概率空間 $(\Omega ,{\mathcal {F}},P)$ 上的一個隨機變量。我們想要估計X的期望值，記作E[X;P]。如果根據P隨機抽取樣本 $x_{1},\ldots ,x_{n}$ ，估計的期望值即

{\widehat {\mathbf {E} }}_{n}[X;P]={\frac {1}{n}}\sum _{i=1}^{n}x_{i}

這一估計的精確度取決於X的方差，

\operatorname {var} [{\widehat {\mathbf {E} }}_{n};P]=\operatorname {var} [X;P]/n

而重要性採樣的基本思想則是從另一個分布中抽取樣本，用以降低E[X;P]估計的方差。進行重要性採樣時，首先選擇一個隨機變量 $L\geq 0$ ，使得E[L;P]=1，並滿足P上幾乎處處 $L(\omega )\neq 0$ 。由此，可以定義新的概率

\mathbf {E} [X;P]=\mathbf {E} \left[{\frac {X}{L}};P^{(L)}\right].

於是，我們可以從P^(L)上抽樣，通過變量X/L估計E[X;P]。如果 $\operatorname {var} \left[{\frac {X}{L}};P^{(L)}\right]<\operatorname {var} [X;P]$ 成立，此時的估計便優於直接在原分布上採樣得到的估計。

當X在Ω上不變號時，最優的L為 $L^{*}={\frac {X}{\mathbf {E} [X;P]}}\geq 0$ 。此時X/L*即為要估計的E[X;P]，只需一個樣本便可得到該值。然而由於L*與要估計的E[X;P]有關，在實際操作中我們無法取到理論上最優的L*。不過，我們仍可以採用如下方式逼近該理論值：

{\begin{aligned}\forall a\in \mathbb {R} ,\;P^{(L^{*})}(X\in [a;a+da])&=\int _{\omega \in \{X\in [a;a+da]\}}{\frac {X(\omega )}{E[X;P]}}dP(\omega )\\&={\frac {1}{E[X;P]}}\;a\,P(X\in [a;a+da])\end{aligned}}

於是，要估計的期望值可改寫為：

E[X;P]=\int _{a=-\infty }^{+\infty }a\,P(X\in [a;a+da])

注意到，更優（即讓估計值方差更小）的P^(L)會使得樣本分布的頻率與其在E[X;P]計算中的權重更加相關。這也是該方法得名「重要性採樣」的原因。

重要性採樣常用於蒙特卡洛積分。當 $P$ 為均勻分布、 $\Omega =\mathbb {R}$ 時，E[X;P]即為實函數 $X:\mathbb {R} \to \mathbb {R}$ 的積分。

參考文獻[編輯]

Arouna, Bouhari. Adaptative Monte Carlo Method, A Variance Reduction Technique. Monte Carlo Methods and Their Applications. 2004, 10 (1): 1–24. doi:10.1515/156939604323091180.
Bucklew, James Antonio. Introduction to Rare Event Simulation. New York: Springer-Verlag. 2004.
Doucet, A.; de Freitas, N.; Gordon, N. Sequential Monte Carlo Methods in Practice. Springer. 2001. ISBN 978-0-387-95146-1.
Ferrari, M.; Bellini, S. Importance Sampling simulation of turbo product codes. The IEEE International Conference on Communications. 2001, 9: 2773–2777. doi:10.1109/ICC.2001.936655.
Mazonka, Oleg. Easy as Pi: The Importance Sampling Method (PDF). Journal of Reference. 2016, 16 [2017-09-18]. （原始內容存檔 (PDF)於2021-04-14）.
Oberg, Tommy. Modulation, Detection, and Coding. New York: John Wiley & Sons. 2001.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP. Section 7.9.1 Importance Sampling. Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007 [2017-09-18]. ISBN 978-0-521-88068-8. （原始內容存檔於2011-08-11）.
Ripley, B. D. Stochastic Simulation. Wiley & Sons. 1987.
Smith, P. J.; Shafi, M.; Gao, H. Quick simulation: A review of importance sampling techniques in communication systems. IEEE J. Select. Areas Commun. 1997, 15 (4): 597–613. doi:10.1109/49.585771.
Srinivasan, R. Importance sampling – Applications in communications and detection. Berlin: Springer-Verlag. 2002.