Rejection sampling

Last updated

In numerical analysis and computational statistics, rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type of exact simulation method. The method works for any distribution in with a density.

Contents

Rejection sampling is based on the observation that to sample a random variable in one dimension, one can perform a uniformly random sampling of the two-dimensional Cartesian graph, and keep the samples in the region under the graph of its density function. [1] [2] [3] Note that this property can be extended to N-dimension functions.

Description

To visualize the motivation behind rejection sampling, imagine graphing the probability density function (PDF) of a random variable onto a large rectangular board and throwing darts at it. Assume that the darts are uniformly distributed around the board. Now remove all of the darts that are outside the area under the curve. The remaining darts will be distributed uniformly within the area under the curve, and the ‑positions of these darts will be distributed according to the random variable's density. This is because there is the most room for the darts to land where the curve is highest and thus the probability density is greatest.

The visualization just described is equivalent to a particular form of rejection sampling where the "proposal distribution" is uniform. Hence its graph is a rectangle. The general form of rejection sampling assumes that the board is not necessarily rectangular but is shaped according to the density of some proposal distribution (not necessarily normalized to ) that we know how to sample from (for example, using inversion sampling). Its shape must be at least as high at every point as the distribution we want to sample from, so that the former completely encloses the latter. Otherwise, there would be parts of the curved area we want to sample from that could never be reached.

Rejection sampling works as follows:

  1. Sample a point on the ‑axis from the proposal distribution.
  2. Draw a vertical line at this ‑position, up to the maximum y-value of the probability density function of the proposal distribution.
  3. Sample uniformly along this line from 0 to the maximum of the probability density function. If the sampled value is greater than the value of the desired distribution at this vertical line, reject the ‑value and return to step 1; else the ‑value is a sample from the desired distribution.

This algorithm can be used to sample from the area under any curve, regardless of whether the function integrates to 1. In fact, scaling a function by a constant has no effect on the sampled ‑positions. Thus, the algorithm can be used to sample from a distribution whose normalizing constant is unknown, which is common in computational statistics.

Theory

The rejection sampling method generates sampling values from a target distribution with an arbitrary probability density function by using a proposal distribution with probability density . The idea is that one can generate a sample value from by instead sampling from and accepting the sample from with probability , repeating the draws from until a value is accepted. here is a constant, finite bound on the likelihood ratio , satisfying over the support of ; in other words, M must satisfy for all values of . Note that this requires that the support of must include the support of —in other words, whenever .

The validation of this method is the envelope principle: when simulating the pair , one produces a uniform simulation over the subgraph of . Accepting only pairs such that then produces pairs uniformly distributed over the subgraph of and thus, marginally, a simulation from

This means that, with enough replicates, the algorithm generates a sample from the desired distribution . There are a number of extensions to this algorithm, such as the Metropolis algorithm.

This method relates to the general field of Monte Carlo techniques, including Markov chain Monte Carlo algorithms that also use a proxy distribution to achieve simulation from the target distribution . It forms the basis for algorithms such as the Metropolis algorithm.

The unconditional acceptance probability is the proportion of proposed samples which are accepted, which is where , and the value of each time is generated under the density function of the proposal distribution .

The number of samples required from to obtain an accepted value thus follows a geometric distribution with probability , which has mean . Intuitively, is the expected number of the iterations that are needed, as a measure of the computational complexity of the algorithm.

Rewrite the above equation, Note that , due to the above formula, where is a probability which can only take values in the interval . When is chosen closer to one, the unconditional acceptance probability is higher the less that ratio varies, since is the upper bound for the likelihood ratio . In practice, a value of closer to 1 is preferred as it implies fewer rejected samples, on average, and thus fewer iterations of the algorithm. In this sense, one prefers to have as small as possible (while still satisfying , which suggests that should generally resemble in some way. Note, however, that cannot be equal to 1: such would imply that , i.e. that the target and proposal distributions are actually the same distribution.

Rejection sampling is most often used in cases where the form of makes sampling difficult. A single iteration of the rejection algorithm requires sampling from the proposal distribution, drawing from a uniform distribution, and evaluating the expression. Rejection sampling is thus more efficient than some other method whenever M times the cost of these operations—which is the expected cost of obtaining a sample with rejection sampling—is lower than the cost of obtaining a sample using the other method.

Algorithm

The algorithm, which was used by John von Neumann [4] and dates back to Buffon and his needle, [5] obtains a sample from distribution with density using samples from distribution with density as follows:

The algorithm will take an average of iterations to obtain a sample. [6]

Advantages over sampling using naive methods

Rejection sampling can be far more efficient compared with the naive methods in some situations. For example, given a problem as sampling conditionally on given the set , i.e., , sometimes can be easily simulated, using the naive methods (e.g. by inverse transform sampling):

The problem is this sampling can be difficult and inefficient, if . The expected number of iterations would be , which could be close to infinity. Moreover, even when you apply the Rejection sampling method, it is always hard to optimize the bound for the likelihood ratio. More often than not, is large and the rejection rate is high, the algorithm can be very inefficient. The Natural Exponential Family (if it exists), also known as exponential tilting, provides a class of proposal distributions that can lower the computation complexity, the value of and speed up the computations (see examples: working with Natural Exponential Families).

Rejection sampling using exponential tilting

Given a random variable , is the target distribution. Assume for simplicity, the density function can be explicitly written as . Choose the proposal as

where and . Clearly, , is from a natural exponential family. Moreover, the likelihood ratio is

Note that implies that it is indeed a cumulant-generation function, that is,

.

It is easy to derive the cumulant-generation function of the proposal and therefore the proposal's cumulants.

As a simple example, suppose under , , with . The goal is to sample , where . The analysis goes as follows:

,
which further implies it is a normal distribution .
,
that is The proposal distribution is thus .

holds, accept the value of ; if not, continue sampling new and new until acceptance.

For the above example, as the measurement of the efficiency, the expected number of the iterations the natural exponential family based rejection sampling method is of order , that is , while under the naive method, the expected number of the iterations is , which is far more inefficient.

In general, exponential tilting a parametric class of proposal distribution, solves the optimization problems conveniently, with its useful properties that directly characterize the distribution of the proposal. For this type of problem, to simulate conditionally on , among the class of simple distributions, the trick is to use natural exponential family, which helps to gain some control over the complexity and considerably speed up the computation. Indeed, there are deep mathematical reasons for using natural exponential family.

Drawbacks

Rejection sampling requires knowing the target distribution (specifically, ability to evaluate target PDF at any point).

Rejection sampling can lead to a lot of unwanted samples being taken if the function being sampled is highly concentrated in a certain region, for example a function that has a spike at some location. For many distributions, this problem can be solved using an adaptive extension (see adaptive rejection sampling), or with an appropriate change of variables with the method of the ratio of uniforms. In addition, as the dimensions of the problem get larger, the ratio of the embedded volume to the "corners" of the embedding volume tends towards zero, thus a lot of rejections can take place before a useful sample is generated, thus making the algorithm inefficient and impractical. See curse of dimensionality. In high dimensions, it is necessary to use a different approach, typically a Markov chain Monte Carlo method such as Metropolis sampling or Gibbs sampling. (However, Gibbs sampling, which breaks down a multi-dimensional sampling problem into a series of low-dimensional samples, may use rejection sampling as one of its steps.)

Adaptive rejection sampling

For many distributions, finding a proposal distribution that includes the given distribution without a lot of wasted space is difficult. An extension of rejection sampling that can be used to overcome this difficulty and efficiently sample from a wide variety of distributions (provided that they have log-concave density functions, which is in fact the case for most of the common distributions—even those whose density functions are not concave themselves) is known as adaptive rejection sampling (ARS).

There are three basic ideas to this technique as ultimately introduced by Gilks in 1992: [7]

  1. If it helps, define your envelope distribution in log space (e.g. log-probability or log-density) instead. That is, work with instead of directly.
    • Often, distributions that have algebraically messy density functions have reasonably simpler log density functions (i.e. when is messy, may be easier to work with or, at least, closer to piecewise linear).
  2. Instead of a single uniform envelope density function, use a piecewise linear density function as your envelope instead.
    • Each time you have to reject a sample, you can use the value of that you evaluated, to improve the piecewise approximation . This therefore reduces the chance that your next attempt will be rejected. Asymptotically, the probability of needing to reject your sample should converge to zero, and in practice, often very rapidly.
    • As proposed, any time we choose a point that is rejected, we tighten the envelope with another line segment that is tangent to the curve at the point with the same x-coordinate as the chosen point.
    • A piecewise linear model of the proposal log distribution results in a set of piecewise exponential distributions (i.e. segments of one or more exponential distributions, attached end to end). Exponential distributions are well behaved and well understood. The logarithm of an exponential distribution is a straight line, and hence this method essentially involves enclosing the logarithm of the density in a series of line segments. This is the source of the log-concave restriction: if a distribution is log-concave, then its logarithm is concave (shaped like an upside-down U), meaning that a line segment tangent to the curve will always pass over the curve.
    • If not working in log space, a piecewise linear density function can also be sampled via triangle distributions [8]
  3. We can take even further advantage of the (log) concavity requirement, to potentially avoid the cost of evaluating when your sample is accepted.
    • Just like we can construct a piecewise linear upper bound (the "envelope" function) using the values of that we had to evaluate in the current chain of rejections, we can also construct a piecewise linear lower bound (the "squeezing" function) using these values as well.
    • Before evaluating (the potentially expensive) to see if your sample will be accepted, we may already know if it will be accepted by comparing against the (ideally cheaper) (or in this case) squeezing function that have available.
    • This squeezing step is optional, even when suggested by Gilks. At best it saves you from only one extra evaluation of your (messy and/or expensive) target density. However, presumably for particularly expensive density functions (and assuming the rapid convergence of the rejection rate toward zero) this can make a sizable difference in ultimate runtime.

The method essentially involves successively determining an envelope of straight-line segments that approximates the logarithm better and better while still remaining above the curve, starting with a fixed number of segments (possibly just a single tangent line). Sampling from a truncated exponential random variable is straightforward. Just take the log of a uniform random variable (with appropriate interval and corresponding truncation).

Unfortunately, ARS can only be applied for sampling from log-concave target densities. For this reason, several extensions of ARS have been proposed in literature for tackling non-log-concave target distributions. [9] [10] [11] Furthermore, different combinations of ARS and the Metropolis-Hastings method have been designed in order to obtain a universal sampler that builds a self-tuning proposal densities (i.e., a proposal automatically constructed and adapted to the target). This class of methods are often called as Adaptive Rejection Metropolis Sampling (ARMS) algorithms. [12] [13] The resulting adaptive techniques can be always applied but the generated samples are correlated in this case (although the correlation vanishes quickly to zero as the number of iterations grows).

See also

Related Research Articles

<span class="mw-page-title-main">Normal distribution</span> Probability distribution

In probability theory and statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is The parameter is the mean or expectation of the distribution, while the parameter is the variance. The standard deviation of the distribution is . A random variable with a Gaussian distribution is said to be normally distributed, and is called a normal deviate.

In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statistical model, the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called the maximum likelihood estimate. The logic of maximum likelihood is both intuitive and flexible, and as such the method has become a dominant means of statistical inference.

In statistics, sufficiency is a property of a statistic computed on a sample dataset in relation to a parametric model of the dataset. A sufficient statistic contains all of the information that the dataset provides about the model parameters. It is closely related to the concepts of an ancillary statistic which contains no information about the model parameters, and of a complete statistic which only contains information about the parameters and no ancillary information.

In mechanics and geometry, the 3D rotation group, often denoted SO(3), is the group of all rotations about the origin of three-dimensional Euclidean space under the operation of composition.

<span class="mw-page-title-main">Gamma distribution</span> Probability distribution

In probability theory and statistics, the gamma distribution is a versatile two-parameter family of continuous probability distributions. The exponential distribution, Erlang distribution, and chi-squared distribution are special cases of the gamma distribution. There are two equivalent parameterizations in common use:

  1. With a shape parameter k and a scale parameter θ
  2. With a shape parameter and an inverse scale parameter , called a rate parameter.

In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function of the base form

In probability theory and statistics, a Gaussian process is a stochastic process, such that every finite collection of those random variables has a multivariate normal distribution. The distribution of a Gaussian process is the joint distribution of all those random variables, and as such, it is a distribution over functions with a continuous domain, e.g. time or space.

In probability and statistics, an exponential family is a parametric set of probability distributions of a certain form, specified below. This special form is chosen for mathematical convenience, including the enabling of the user to calculate expectations, covariances using differentiation based on some useful algebraic properties, as well as for generality, as exponential families are in a sense very natural sets of distributions to consider. The term exponential class is sometimes used in place of "exponential family", or the older term Koopman–Darmois family. Sometimes loosely referred to as "the" exponential family, this class of distributions is distinct because they all possess a variety of desirable properties, most importantly the existence of a sufficient statistic.

In information geometry, the Fisher information metric is a particular Riemannian metric which can be defined on a smooth statistical manifold, i.e., a smooth manifold whose points are probability measures defined on a common probability space. It can be used to calculate the informational difference between measurements.

<span class="mw-page-title-main">Cramér–Rao bound</span> Lower bound on variance of an estimator

In estimation theory and statistics, the Cramér–Rao bound (CRB) relates to estimation of a deterministic parameter. The result is named in honor of Harald Cramér and C. R. Rao, but has also been derived independently by Maurice Fréchet, Georges Darmois, and by Alexander Aitken and Harold Silverstone. It is also known as Fréchet-Cramér–Rao or Fréchet-Darmois-Cramér-Rao lower bound. It states that the precision of any unbiased estimator is at most the Fisher information; or (equivalently) the reciprocal of the Fisher information is a lower bound on its variance.

<span class="mw-page-title-main">Rice distribution</span> Probability distribution

In probability theory, the Rice distribution or Rician distribution is the probability distribution of the magnitude of a circularly-symmetric bivariate normal random variable, possibly with non-zero mean (noncentral). It was named after Stephen O. Rice (1907–1986).

In statistics, M-estimators are a broad class of extremum estimators for which the objective function is a sample average. Both non-linear least squares and maximum likelihood estimation are special cases of M-estimators. The definition of M-estimators was motivated by robust statistics, which contributed new types of M-estimators. However, M-estimators are not inherently robust, as is clear from the fact that they include maximum likelihood estimators, which are in general not robust. The statistical procedure of evaluating an M-estimator on a data set is called M-estimation.

In directional statistics, the von Mises–Fisher distribution, is a probability distribution on the -sphere in . If the distribution reduces to the von Mises distribution on the circle.

In statistics, the multivariate t-distribution is a multivariate probability distribution. It is a generalization to random vectors of the Student's t-distribution, which is a distribution applicable to univariate random variables. While the case of a random matrix could be treated within this structure, the matrix t-distribution is distinct and makes particular use of the matrix structure.

Covariance matrix adaptation evolution strategy (CMA-ES) is a particular kind of strategy for numerical optimization. Evolution strategies (ES) are stochastic, derivative-free methods for numerical optimization of non-linear or non-convex continuous optimization problems. They belong to the class of evolutionary algorithms and evolutionary computation. An evolutionary algorithm is broadly based on the principle of biological evolution, namely the repeated interplay of variation and selection: in each generation (iteration) new individuals are generated by variation of the current parental individuals, usually in a stochastic way. Then, some individuals are selected to become the parents in the next generation based on their fitness or objective function value . Like this, individuals with better and better -values are generated over the generation sequence.

A ratio distribution is a probability distribution constructed as the distribution of the ratio of random variables having two other known distributions. Given two random variables X and Y, the distribution of the random variable Z that is formed as the ratio Z = X/Y is a ratio distribution.

<span class="mw-page-title-main">Half-normal distribution</span> Probability distribution

In probability theory and statistics, the half-normal distribution is a special case of the folded normal distribution.

In probability theory and statistics, the normal-exponential-gamma distribution is a three-parameter family of continuous probability distributions. It has a location parameter , scale parameter and a shape parameter .

Exponential Tilting (ET), Exponential Twisting, or Exponential Change of Measure (ECM) is a distribution shifting technique used in many parts of mathematics. The different exponential tiltings of a random variable is known as the natural exponential family of .

A Stein discrepancy is a statistical divergence between two probability measures that is rooted in Stein's method. It was first formulated as a tool to assess the quality of Markov chain Monte Carlo samplers, but has since been used in diverse settings in statistics, machine learning and computer science.

References

  1. Casella, George; Robert, Christian P.; Wells, Martin T. (2004). Generalized Accept-Reject sampling schemes. Institute of Mathematical Statistics. pp. 342–347. doi:10.1214/lnms/1196285403. ISBN   9780940600614.
  2. Neal, Radford M. (2003). "Slice Sampling". Annals of Statistics . 31 (3): 705–767. doi: 10.1214/aos/1056562461 . MR   1994729. Zbl   1051.65007.
  3. Bishop, Christopher (2006). "11.4: Slice sampling". Pattern Recognition and Machine Learning. Springer. ISBN   978-0-387-31073-2.
  4. Forsythe, George E. (1972). "Von Neumann's Comparison Method for Random Sampling from the Normal and Other Distributions". Mathematics of Computation. 26 (120): 817–826. doi:10.2307/2005864. ISSN   0025-5718. JSTOR   2005864.
  5. Legault, Geoffrey; Melbourne, Brett A. (2019-03-01). "Accounting for environmental change in continuous-time stochastic population models". Theoretical Ecology. 12 (1): 31–48. doi:10.1007/s12080-018-0386-z. ISSN   1874-1746.
  6. Thomopoulos, Nick T. (2012-12-19). Essentials of Monte Carlo Simulation: Statistical Methods for Building Simulation Models (2013th ed.). New York, NY Heidelberg: Springer. ISBN   978-1-4614-6021-3.
  7. Gilks, W. R.; Wild, P. (1992). "Adaptive Rejection Sampling for Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. doi:10.2307/2347565. JSTOR   2347565.
  8. Thomas, D. B.; Luk, W. (2007). "Non-uniform random number generation through piecewise linear approximations". IET Computers & Digital Techniques. 1 (4): 312–321. doi:10.1049/iet-cdt:20060188.
  9. Hörmann, Wolfgang (1995-06-01). "A Rejection Technique for Sampling from T-concave Distributions". ACM Trans. Math. Softw. 21 (2): 182–193. CiteSeerX   10.1.1.56.6055 . doi:10.1145/203082.203089. ISSN   0098-3500.
  10. Evans, M.; Swartz, T. (1998-12-01). "Random Variable Generation Using Concavity Properties of Transformed Densities". Journal of Computational and Graphical Statistics. 7 (4): 514–528. CiteSeerX   10.1.1.53.9001 . doi:10.2307/1390680. JSTOR   1390680.
  11. Görür, Dilan; Teh, Yee Whye (2011-01-01). "Concave-Convex Adaptive Rejection Sampling". Journal of Computational and Graphical Statistics. 20 (3): 670–691. doi:10.1198/jcgs.2011.09058. ISSN   1061-8600.
  12. Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1995-01-01). "Adaptive Rejection Metropolis Sampling within Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. doi:10.2307/2986138. JSTOR   2986138.
  13. Meyer, Renate; Cai, Bo; Perron, François (2008-03-15). "Adaptive rejection Metropolis sampling using Lagrange interpolation polynomials of degree 2". Computational Statistics & Data Analysis. 52 (7): 3408–3423. doi:10.1016/j.csda.2008.01.005.

Further reading