FACTOID # 17: Though Rhode Island is the smallest state in total area, it has the longest official name: The State of Rhode Island and Providence Plantations.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Importance sampling

Importance sampling is a general technique for estimating the properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest. Depending on the application, the term may refer to the process of sampling from this alternative distribution, the process of inference, or both.

Contents

Basic theory

More formally, let X be a random variable in S. Let p be a probability measure on S, and f some function on S. Then the expectation of f under p can be written as



If we have random samples x_1, ldots, x_n, generated according to p, then an empirical estimate of p is

In that case, we can easily obtain the Monte-Carlo empirical estimate of



Unfortunately, when the samples are generated from a different distribution than the one that we are interested in, we can no longer use this straightforward estimate. However, we may use the importance sampling technique, which consists of placing different importance on each sample, depending on how likely it was for it to have been generated by the distribution that we're interested in, p, rather than the actual sampling distribution, q.


More formally, let another probability measure q, with the same support as p. From the definition of the expectation given above, we have



where , is known as the importance weight and the distribution q is frequently referred to as the sampling or proposal distribution. Then, if we have random samples x_1, ldots, x_n, generated according to q, a Monte Carlo estimate of follows from the above equation by viewing the problem as that of estimating the expectations and .



where v_i=frac{w(x_i)}{sum_{j=1}^n w(x_j)} are the normalised importance weights.


The technique is completely general and the above analysis can be repeated essentially exactly also for other choices of p, for example when it represents a conditional distribution. Note that when p is the uniform distribution, we are just estimating the (scaled) integral of f over S, so the method can also be used for estimating simple integrals.


There are two main applications of importance sampling methods, which naturally, are interrelated. While the aim of both applications is to estimate statistics of random variables, the field of probabilistic inference focuses more on the estimation of p or related statistics, while the field of simulation focuses more on the the choice of the distribution q. Nevertheless, the basic theory and tools are identical.


Application to probabilistic inference

Such methods are frequently used to estimate posterior densities or expectations in state and/or parameter estimation problems in probabilistic models that are too hard to treat analytically.


Application to simulation

Importance sampling (IS) is a variance reduction technique that can be used in the Monte Carlo method. The idea behind IS is that certain values of the input random variables in a simulation have more impact on the parameter being estimated than others. If these "important" values are emphasized by sampling more frequently, then the estimator variance can be reduced. Hence, the basic methodology in IS is to choose a distribution which "encourages" the important values. This use of "biased" distributions will result in a biased estimator if it is applied directly in the simulation. However, the simulation outputs are weighted to correct for the use of the biased distribution, and this ensures that the new IS estimator is unbiased. The weight is given by the likelihood ratio, that is, the Radon-Nikodym derivative of the true underlying distribution with respect to the biased simulation distribution. In probability theory and statistics, the variance of a random variable (or somewhat more precisely, of a probability distribution) is a measure of its statistical dispersion, indicating how its possible values are spread around the expected value. ... Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations. ... A random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. ... Look up simulation in Wiktionary, the free dictionary. ... In statistics, an estimator is a function of the observable sample data that is used to estimate an unknown population parameter; an estimate is the result from the actual application of the function to a particular set of data. ... A likelihood-ratio test is a statistical test relying on a test statistic computed by taking the ratio of the maximum value of the likelihood function under the constraint of the null hypothesis to the maximum with that constraint relaxed. ... In mathematics, the Radon-Nikodym theorem is a result in functional analysis that states that if a measure Q is absolutely continuous with respect to another sigma-finite measure P then there is a measurable function f, taking values in [0,∞], on the underlying space such that for any...


The fundamental issue in implementing IS simulation is the choice of the biased distribution which encourages the important regions of the input variables. Choosing or designing a good biased distribution is the "art" of IS. The rewards for a good distribution can be huge run-time savings; the penalty for a bad distribution can be longer run times than for a general Monte Carlo simulation without importance sampling.


Mathematical Approach

Consider estimating by simulation the probability p_t, of an event { X ge t }, where X is a random variable with distribution F 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 kt of random variables that lie above the threshold t are counted. The random variable kt is characterized by the Binomial distribution In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ... In mathematics, a probability density function (pdf) is a function that represents a probability distribution in terms of integrals. ... For a non-technical overview of the subject, see Calculus. ... In probability theory, a sequence or other collection of random variables is independent and identically distributed (i. ... In probability theory and statistics, the binomial distribution is the discrete probability distribution of the number of successes in a sequence of n independent yes/no experiments, each of which yields success with probability p. ...

P(k_t = k)={Kchoose k}p_t^k(1-p_t)^{K-k},,quad quad k=0,1,dots,K.

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. In statistics, an estimator is a function of the observable sample data that is used to estimate an unknown population parameter; an estimate is the result from the actual application of the function to a particular set of data. ...

p_t = {E} [X ge t]
= int (x ge t) frac{f(x)}{f_*(x)} f_*(x) ,dx

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 (X_i ge t) W(X_i),,quad quad X_i sim f_*

This is the IS 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 IS estimator is easily shown to be

var_*hat p_t = frac{1}{K} var_* [(X ge t)W(X)]
= frac{1}{K}Big[{E}[(X ge t)^2 W(X)] - p_t^2 Big]

Now, the IS problem then focuses on finding a biasing density f_*, such that the variance of the IS 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.


Conventional biasing methods

Although there are many kinds of biasing methods, the following two methods are most widely used in the applications of IS.


Scaling

Shifting probability mass into the event region { X ge t } by positive scaling of the random variable X, with a number greater than unity has the effect of increasing the variance (mean also) of the density function. This results in a heavier tail of the density, leading to an increase in the event probability. Scaling is probably one of the earliest biasing methods known and has been extensively used in practice. It is simple to implement and usually provides conservative simulation gains as compared to other methods.


In IS by scaling, the simulation density is chosen as the density function of the scaled random variable aX,, where usually a > 1 for tail probability estimation. By transformation,

 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<t, 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 IS gain for increasing n,, and is called the dimensionality effect.


Translation

Another simple and effective biasing technique employs translation of the density function (and hence random variable) to place much of its probability mass in the rare event region. Translation does not suffer from a dimensionality effect and has been successfully used in several applications relating to simulation of digital communication systems. It often provides better simulation gains than scaling. In biasing by translation, the simulation density is given by Digital communication, as opposed to analogue communication refers to all emerging communications and technologies via a digital platform usually combining text, graphics, sound, and video, utilising computer or mobile technology. ...

 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 IS estimator.


Effects of System Complexity

The fundamental problem with IS is that designing good biased distributions becomes more complicated as the system complexity increases. Complex systems are the systems with long memory since complex processing of a few inputs is much easier to handle. This dimensionality or memory can cause problems in three ways:

In principle, the IS ideas remain the same in these situations, but the design becomes much harder. A successful approach to combat this problem is essentially breaking down a simulation into several smaller, more sharply defined subproblems. Then IS strategies are used to target each of the simpler subproblems. Examples of techniques to break the simulation down are conditioning and error-event simulation (EES) and regenerative simulation. In telecommunication, the term intersymbol interference has the following meanings: 1. ... A viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using Forward error correction based on a Convolutional code. ...


Evaluation of IS

In order to identify successful IS techniques, it is useful to be able to quantify the run-time savings due to the use of the IS approach. The performance measure commonly used is sigma^2_{MC} / sigma^2_{IS} ,, and this can be interpreted as the speed-up factor by which the IS estimator achieves the same precision as the MC estimator. This has to be computed empirically since the estimator variances are not likely to be analytically possible when their mean is intractable. Other useful concepts in quantifying an IS estimator are the variance bounds and the notion of asymptotic efficiency.


Variance Cost Function

Variance is not the only possible cost function for a simulation, and other cost functions, such as the mean absolute deviation, are used in various statistical applications. Nevertheless, the variance is the primary cost function addressed in the literature, probably due to the use of variances in confidence intervals and in the performance measure sigma^2_{MC} / sigma^2_{IS} ,. Optimization is a branch of mathematics which is concerned with finding maxima and minima of real-valued functions. ... In this diagram, the bars represent observation means and the red lines represent the confidence intervals surrounding them. ...


An associated issue is the fact that the ratio sigma^2_{MC} / sigma^2_{IS} , overestimates the run-time savings due to IS since it does not include the extra computing time required to compute the weight function. Hence, some people evaluate the net run-time improvement by various means. Perhaps a more serious overhead to IS is the time taken to devise and program the technique and analytically derive the desired weight function.


References

  • P. J.Smith, M.Shafi, and H. Gao, "Quick simulation: A review of importance sampling techniques in communication systems," IEEE J.Select.Areas Commun., vol. 15, pp. 597-613, May 1997.
  • M. Ferrari, S. Bellini, "Importance Sampling simulation of turbo product codes," ICC2001, The IEEE International Conference on Communications, vol. 9, pp. 2773-2777, June 2001.
  • Tommy Oberg, Modulation, Detection, and Coding, John Wiley & Sons, Inc., New York, 2001.
  • R. Srinivasan., Importance Sampling. New York: Springer, 2002.
  • Arouna. Adaptative Monte Carlo Method, A Variance Reduction Technique. Monte Carlo Methods and Their Applications. 2004

See also

Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations. ... In statistics, stratified sampling is a method of sampling from a population. ... Result of particle filtering (red line) based on observed data generated from the blue line ( Much larger image) Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation. ...

External links

  • Monte Carlo Methods and Importance Sampling, Eric C. Anderson, Lecture notes for Stat 587C
  • 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 simulation: adaptive monte carlo methods for rare event simulations Winter Simulation Conference

References

  • Stochastic Simulation, B. D. Ripley, 1987, Wiley & Sons
  • Sequential Monte Carlo Methods in Practice, by A Doucet, N de Freitas and N Gordon. Springer, 2001. ISBN 978-0387951461
  • Introduction to rare event simulation, James Antonio Bucklew, Springer-Verlag, New York, 2004.
  • Importance sampling - Applications in communications and detection, Rajan Srinivasan, Springer-Verlag, Berlin, 2002.

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m