Nested sampling algorithm

Nested sampling algorithm

The nested sampling algorithm is a computational approach to the problem of comparing models in Bayesian statistics, developed in 2004 by physicist John Skilling.[1]

Contents

Background

Bayes' theorem can be applied to a pair of competing models M1 and M2 for data D, one of which may be true (though which one is not known) but which both cannot simultaneously be true, as follows:


\begin{align}
 P(M1|D) & {} = \frac{P(D|M1) P(M1)}{P(D)} \\
  & {} = \frac{P(D|M1) P(M1)}{P(D|M1) P(M1) + P(D|M2) P(M2)}  \\
  & {} = \frac{1}{1 + \frac{P(D|M2)}{P(D|M1)} \frac{P(M2)}{P(M1)} }
\end{align}

Given no a priori information in favor of M1 or M2, it is reasonable to assign prior probabilities P(M1) = P(M2) = 1 / 2, so that P(M2) / P(M1) = 1. The remaining ratio P(D | M2) / P(D | M1) is not so easy to evaluate since in general it requires marginalization of nuisance parameters. Generally, M1 has a collection of parameters that can be lumped together and called θ, and M2 has its own vector of parameters that may be of different dimensionality but is still referred to as θ. The marginalization for M1 is

P(D|M1) = \int d \theta P(D|\theta,M1) P(\theta|M1)

and likewise for M2. This integral is often analytically intractable, and in these cases it is necessary to employ a numerical algorithm to find an approximation. The nested sampling algorithm was developed by John Skilling specifically to approximate these marginalization integrals, and it has the added benefit of generating samples from the posterior distribution P(θ | D,M1).[2] It is an alternative to methods from the Bayesian literature[3] such as bridge sampling and defensive importance sampling.

Here is a simple version of the nested sampling algorithm, followed by a description of how it computes the marginal probability density Z = P(D | M) where M is M1 or M2:

  Start with N points θ1,...,θN sampled from prior.
  for i = 1 to j do        % The number of iterations j is chosen by guesswork.
      Li: = min(current likelihood values of the points);
      Xi: = exp( − i / N);
      wi: = Xi − 1Xi
      Z: = Z + Li * wi;
      Save the point with least likelihood as a sample point with weight wi.
      Update the point with least likelihood with some Markov Chain
      Monte Carlo steps according to the prior, accepting only steps that
      keep the likelihood above Li.
  end
  return Z;

At each iteration, Xi is an estimate of the amount of prior mass covered by the hypervolume in parameter space of all points with likelihood greater than θi. The weight factor wi is an estimate of the amount of prior mass that lies between two nested hypersurfaces {θ | P(D | θ,M) = P(D | θi − 1,M)} and {θ | P(D | θ,M) = P(D | θi,M)}. The update step Z: = Z + Li * wi computes the sum over i of Li * wi to numerically approximate the integral


 \begin{array}{lcl}
  P(D|M) &=& \int P(D|\theta,M) P(\theta|M) d \theta \\
         &=& \int P(D|\theta,M) dP(\theta|M)\\
 \end{array}

The idea is to chop up the range of f(θ) = P(D | θ,M) and estimate, for each interval [fi − 1),fi)], how likely it is a priori that a randomly chosen θ would map to this interval. This can be thought of as a Bayesian's way to numerically implement Lebesgue integration.

Simple example code written in C, R, or Python demonstrating this algorithm can be downloaded from John Skilling's website. There is also a Haskell port on Hackage.

Applications

Since nested sampling was proposed in 2004, it has been used in multiple settings within the field of astronomy. One paper suggested using nested sampling for cosmological model selection and object detection, as it "uniquely combines accuracy, general applicability and computational feasibility."[4] A refinement of the nested sampling algorithm to handle multimodal posteriors has also been suggested as a means of detecting astronomical objects in existing datasets.[5]

See also

References

  1. ^ Skilling, John (2004). "Nested Sampling". AIP Conference Proceedings 735: 395–405. doi:10.1063/1.1835238. 
  2. ^ Skilling, John (2006). "Nested Sampling for General Bayesian Computation". Bayesian Analysis 1 (4): 833–860. doi:10.1214/06-BA127. 
  3. ^ Chen, Ming-Hui, Shao, Qi-Man, and Ibrahim, Joseph George (2000). Monte Carlo methods in Bayesian computation. Springer. ISBN 9780387989358. http://books.google.com/?id=R3GeFfshc7wC. 
  4. ^ Mukherjee, P., Parkinson, D., and Liddle, A.R. (2006). "A Nested Sampling Algorithm for Cosmological Model Selection". Astrophysical Journal 638 (2): 51–54. Bibcode 2005astro.ph..8461M. doi:10.1086/501068. 
  5. ^ Feroz, F., Hobson, M.P. (2008). "Multimodal nested sampling: an efficient and robust alternative to Markov Chain Monte Carlo methods for astronomical data analyses". MNRAS 384 (2): 449–463. Bibcode 2008MNRAS.384..449F. doi:10.1111/j.1365-2966.2007.12353.x. http://adsabs.harvard.edu/cgi-bin/bib_query?arXiv:0704.3704. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia

  • List of mathematics articles (N) — NOTOC N N body problem N category N category number N connected space N dimensional sequential move puzzles N dimensional space N huge cardinal N jet N Mahlo cardinal N monoid N player game N set N skeleton N sphere N! conjecture Nabla symbol… …   Wikipedia

  • Nesting — may refer to: building or having a nest Nesting instinct Nesting, Shetland Nesting (computing) Nesting (voting districts), the process of combining or splitting of voting districts Nesting (process), a process of efficiently manufacturing parts… …   Wikipedia

  • Nesting (disambiguation) — Nesting could refer to* building or having a nest * Nesting, Shetland * Nesting (computing) * Nesting, a manufacturing process * Nested sampling algorithm, a method in Bayesian statistics * Nested variation or nested data , described at… …   Wikipedia

  • Bayesian model comparison — A common problem in statistical inference is to use data to decide between two or more competing models. Frequentist statistics uses hypothesis tests for this purpose. There are several Bayesian approaches. One approach is through Bayes… …   Wikipedia

  • Nucleic acid structure prediction — This article is about the computational prediction of nucleic acid structure. For experimental methods, see Nucleic acid structure determination. Nucleic acid structure prediction is a computational method to determine nucleic acid secondary and… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… …   Wikipedia

  • Monte Carlo method — Not to be confused with Monte Carlo algorithm. Computational physics …   Wikipedia

  • Quicksort — Infobox Algorithm class=Sorting algorithm Quicksort in action on a list of numbers. The horizontal lines are pivot values. data=Varies time=O(nlog n) on average space=Varies by implementation optimal=Sometimes Stability= [Sorting… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”