importance sampling

Importance sampling is a Monte Carlo method for evaluating properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest. Its introduction in statistics is generally attributed to a paper by Teun Kloek and Herman K. van Dijk in 1978, but its precursors can be found in statistical physics as early as 1949. Importance sampling is also related to umbrella sampling in computational physics. Depending on the application, the term may refer to the process of sampling from this alternative distribution, the process of inference, or both.

Importance sampling is a Monte Carlo method for evaluating properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest. Its introduction in statistics is generally attributed to a paper by Teun Kloek and Herman K. van Dijk in 1978, but its precursors can be found in statistical physics as early as 1949. Importance sampling is also related to umbrella sampling in computational physics. Depending on the application, the term may refer to the process of sampling from this alternative distribution, the process of inference, or both. \widehat{\mathbb{E}}_{\mathbb{P}}[X] = \frac{1}{n} \sum_{i=1}^n X_i \quad \mathrm{where}\; X_i \sim \mathbb{P}(X) and the precision of this estimate depends on the variance of X : \operatorname{var}_\mathbb{P}\big[\widehat{\mathbb{E}}_{\mathbb{P}}[X]\big] = \frac{\operatorname{var}_\mathbb{P}[X]} n. The basic idea of importance sampling is to sample from a different distribution to lower the variance of the estimation of \mathbb{E}_\mathbb{P}[X] , or when sampling directly from \mathbb{P} is difficult. This is accomplished by first choosing a random variable Y\geq 0 such that \mathbb{E}_\mathbb{P}[Y] = 1 and that \mathbb{P} -almost everywhere Y(\omega)\neq 0 . With the variable Y we define a probability \mathbb{Q} that satisfies \mathbb{E}_{\mathbb{P}}[X] = \mathbb{E}_{\mathbb{Q}}\left[\frac{X}{Y}\right]. The variable X/Y will thus be sampled under \mathbb{Q} to estimate \mathbb{E}_{\mathbb{P}}[X] as above and this estimation is improved when \operatorname{var}_{\mathbb{Q}}\left[\frac{X}{Y}\right] When X is of constant sign over \Omega , the best variable Y would clearly be Y^*=\frac{X}{\mathbb{E}_{\mathbb{P}}[X]}\geq 0 , so that X/Y^* is the searched constant \mathbb{E}_{\mathbb{P}}[X] and a single sample under \mathbb{Q}^* suffices to give its value. Unfortunately we cannot take that choice, because \mathbb{E}_{\mathbb{P}}[X] is precisely the value we are looking for! However this theoretical best case Y^* gives us an insight into what importance sampling does: for all x \in \mathbb{R} , the density of \mathbb{Q}^* at X=x can be written as \begin{align} \mathbb{Q}^*\big(X\in[x;x+dx]\big) &= \int_{\omega\in\{X\in[x;x+dx]\}} \frac{X(\omega)}{\mathbb{E}_{\mathbb{P}}[X]} \, d\mathbb{P}(\omega) \\[6pt] &= \frac{1}{\mathbb{E}_{\mathbb{P}}[X]}\; x\,\mathbb{P}(X\in[x;x+dx]). \end{align} To the right, x\,\mathbb{P}(X\in[x;x+dx]) is one of the infinitesimal elements that sum up to \mathbb{E}_{\mathbb{P}}[X] : \mathbb{E}_{\mathbb{P}}[X] = \int_{-\infty}^{+\infty} x\,\mathbb{P}(X\in[x;x+dx]) therefore, a good probability change \mathbb{Q} in importance sampling will redistribute the law of X so that its samples' frequencies are sorted directly according to their contributions in \mathbb{E}_{\mathbb{P}}[X] as opposed to \mathbb{E}_{\mathbb{P}}[1] . Hence the name "importance sampling." Importance sampling is often used as a Monte Carlo integrator. When \mathbb{P} is the uniform distribution over \Omega =\mathbb{R} , the expectation \mathbb{E}_{\mathbb{P}}[X] corresponds to the integral of the real function X\colon \mathbb{R}\to\mathbb{R} . g^* = \min_g \operatorname{var}_g \left( X \frac{f(X)}{g(X)} \right). It can be shown that the following distribution minimizes the above variance: g^*(X) = \frac{|X| f(X)}{ \int |x| f(x) \, dx}. Notice that when X\ge 0 , this variance becomes 0. Consider estimating by simulation the probability p_t\, of an event X \ge t , where X is a random variable with cumulative distribution function F(x) and probability density function f(x)= F'(x)\, , where prime denotes derivative. A K -length independent and identically distributed (i.i.d.) sequence X_i\, is generated from the distribution F , and the number k_t of random variables that lie above the threshold t are counted. The random variable k_t is characterized by the Binomial distribution P(k_t = k)={K\choose k}p_t^k(1-p_t)^{K-k},\,\quad \quad k=0,1,\dots,K. One can show that \mathbb{E} [k_t/K] = p_t , and \operatorname{var} [k_t/K] = p_t(1-p_t)/K , so in the limit K \to \infty we are able to obtain p_t . Note that the variance is low if p_t \approx 1 . Importance sampling is concerned with the determination and use of an alternate density function f_*\, (for X ), usually referred to as a biasing density, for the simulation experiment. This density allows the event { X \ge t\ } to occur more frequently, so the sequence lengths K gets smaller for a given estimator variance. Alternatively, for a given K , use of the biasing density results in a variance smaller than that of the conventional Monte Carlo estimate. From the definition of p_t\, , we can introduce f_*\, as below. \begin{align} p_t & = \mathbb{E} [1_{\{X \ge t\}}] \\[6pt] & = \int 1_{\{x \ge t\}} \frac{f(x)}{f_*(x)} f_*(x) \,dx \\[6pt] & = \mathbb{E}_* [1_{\{X \ge t\}} W(X)] \end{align} where W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)} is a likelihood ratio and is referred to as the weighting function. The last equality in the above equation motivates the estimator \hat p_t = \frac{1}{K}\,\sum_{i=1}^K 1_{\{X_i \ge t\}} W(X_i),\,\quad \quad X_i \sim f_* This is the importance sampling estimator of p_t\, and is unbiased. That is, the estimation procedure is to generate i.i.d. samples from f_*\, and for each sample which exceeds t\, , the estimate is incremented by the weight W\, evaluated at the sample value. The results are averaged over K\, trials. The variance of the importance sampling estimator is easily shown to be \begin{align} \operatorname{var}_*\widehat p_t & = \frac{1}{K}\operatorname{var}_* [1_{\{X_i \ge t\}}W(X)] \\[5pt] & = \frac{1}{K}\left\{\mathbb{E}_*[1_{\{X_i \ge t\}}^2 W^2(X)] - p_t^2\right\} \\[5pt] & = \frac{1}{K}\left\{\mathbb{E}[1_{\{X_i \ge t\}}W(X)] - p_t^2\right\} \end{align} Now, the importance sampling problem then focuses on finding a biasing density f_*\, such that the variance of the importance sampling estimator is less than the variance of the general Monte Carlo estimate. For some biasing density function, which minimizes the variance, and under certain conditions reduces it to zero, it is called an optimal biasing density function. f_*(x)=\frac{1}{a} f \bigg( \frac{x}{a} \bigg)\, and the weighting function is W(x)= a \frac{f(x)}{f(x/a)} \, While scaling shifts probability mass into the desired event region, it also pushes mass into the complementary region X which is undesirable. If X\, is a sum of n\, random variables, the spreading of mass takes place in an n\, dimensional space. The consequence of this is a decreasing importance sampling gain for increasing n\, , and is called the dimensionality effect. A modern version of importance sampling by scaling is e.g. so-called sigma-scaled sampling (SSS) which is running multiple Monte Carlo (MC) analysis with different scaling factors. In opposite to many other high yield estimation methods (like worst-case distances WCD) SSS does not suffer much from the dimensionality problem. Also addressing multiple MC outputs causes no degradation in efficiency. On the other hand, as WCD, SSS is only designed for Gaussian statistical variables, and in opposite to WCD, the SSS method is not designed to provide accurate statistical corners. Another SSS disadvantage is that the MC runs with large scale factors may become difficult, e. g. due to model and simulator convergence problems. In addition, in SSS we face a strong bias-variance trade-off: Using large scale factors, we obtain quite stable yield results, but the larger the scale factors, the larger the bias error. If the advantages of SSS does not matter much in the application of interest, then often other methods are more efficient. f_*(x)= f(x-c), \quad c>0 \, where c\, is the amount of shift and is to be chosen to minimize the variance of the importance sampling estimator. When different proposal distributions, g_i(x) , i=1,\ldots,n, are jointly used for drawing the samples x_1, \ldots, x_n, different proper weighting functions can be employed (e.g., see ). In an adaptive setting, the proposal distributions, g_{i,t}(x) , i=1,\ldots,n, and t=1,\ldots,T, are updated each iteration t of the adaptive importance sampling algorithm. Hence, since a population of proposal densities is used, several suitable combinations of sampling and weighting schemes can be employed.

External links

Sequential Monte Carlo Methods (Particle Filtering) homepage on University of Cambridge Introduction to importance sampling in rare-event simulations European journal of Physics. PDF document. Adaptive Monte Carlo methods for rare event simulations Winter Simulation Conference

Text derived from https://en.wikipedia.org/w/index.php?oldid=1340239574 under CC BY-SA 4.0; modifications have been made.