The nested sampling algorithm is a
computation
A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms.
Mechanical or electronic devices (or, hist ...
al approach to the
Bayesian statistics
Bayesian statistics ( or ) is a theory in the field of statistics based on the Bayesian interpretation of probability, where probability expresses a ''degree of belief'' in an event. The degree of belief may be based on prior knowledge about ...
problems of comparing models and generating samples from posterior distributions. It was developed in 2004 by
physicist
A physicist is a scientist who specializes in the field of physics, which encompasses the interactions of matter and energy at all length and time scales in the physical universe. Physicists generally are interested in the root or ultimate cau ...
John Skilling.
Background
Bayes' theorem
Bayes' theorem (alternatively Bayes' law or Bayes' rule, after Thomas Bayes) gives a mathematical rule for inverting Conditional probability, conditional probabilities, allowing one to find the probability of a cause given its effect. For exampl ...
can be applied to a pair of competing models
and
for data
, one of which may be true (though which one is unknown) but which both cannot be true simultaneously. The posterior probability for
may be calculated as:
:
The prior probabilities
and
are already known, as they are chosen by the researcher ahead of time. However, the remaining
Bayes factor
The Bayes factor is a ratio of two competing statistical models represented by their evidence, and is used to quantify the support for one model over the other. The models in question can have a common set of parameters, such as a null hypothesis ...
is not so easy to evaluate, since in general it requires marginalizing nuisance parameters. Generally,
has a set of parameters that can be grouped together and called
, and
has its own vector of parameters that may be of different dimensionality, but is still termed
. The marginalization for
is
:
and likewise for
. 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
.
It is an alternative to methods from the Bayesian literature
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
where
is
or
:
Start with
points
sampled from prior.
for
to
do % The number of iterations j is chosen by guesswork.
current likelihood values of the points
;
Save the point with least likelihood as a sample point with weight
.
Update the point with least likelihood with some
Markov chain Monte Carlo
In statistics, Markov chain Monte Carlo (MCMC) is a class of algorithms used to draw samples from a probability distribution. Given a probability distribution, one can construct a Markov chain whose elements' distribution approximates it – that ...
steps according to the prior, accepting only steps that
keep the likelihood above
.
end
return
;
At each iteration,
is an estimate of the amount of prior mass covered by the hypervolume in parameter space of all points with likelihood greater than
. The weight factor
is an estimate of the amount of prior mass that lies between two nested hypersurfaces
and
. The update step
computes the sum over
of
to numerically approximate the integral
:
In the limit
, this estimator has a positive bias of order
which can be removed by using
instead of the
in the above algorithm.
The idea is to subdivide the range of
and estimate, for each interval
Lebesgue integration
In mathematics, the integral of a non-negative function of a single variable can be regarded, in the simplest case, as the area between the graph of that function and the axis. The Lebesgue integral, named after French mathematician Henri L ...
.
Choice of MCMC algorithm
The original procedure outlined by Skilling (given above in pseudocode) does not specify what specific Markov chain Monte Carlo algorithm should be used to choose new points with better likelihood.
Skilling's own code examples (such as one in Sivia and Skilling (2006)
available on Skilling's website chooses a random existing point and selects a nearby point chosen by a random distance from the existing point; if the likelihood is better, then the point is accepted, else it is rejected and the process repeated. Mukherjee et al. (2006)
found higher acceptance rates by selecting points randomly within an ellipsoid drawn around the existing points; this idea was refined into the MultiNest algorithm
which handles multimodal posteriors better by grouping points into likelihood contours and drawing an ellipsoid for each contour.
Implementations
Example implementations demonstrating the nested sampling algorithm are publicly available for download, written in several
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s.
* Simple examples in
C,
R, or
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (prog ...
are o
John Skilling's website
* A
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
port o
the above simple codes is on Hackage
* An example in
R originally designed for
fitting spectra is described o
Bojan Nikolic's websiteand i
available on GitHub
* A NestedSampler is part of the
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (prog ...
toolbox BayesicFitting
for generic model fitting and evidence calculation. It i
available on GitHub
* An implementation in
C++
C++ (, pronounced "C plus plus" and sometimes abbreviated as CPP or CXX) is a high-level, general-purpose programming language created by Danish computer scientist Bjarne Stroustrup. First released in 1985 as an extension of the C programmin ...
, named DIAMONDS
is on GitHub
* A highly modular
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (prog ...
parallel example for
statistical physics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. Sometimes called statistical physics or statistical thermodynamics, its applicati ...
and
condensed matter physics
Condensed matter physics is the field of physics that deals with the macroscopic and microscopic physical properties of matter, especially the solid and liquid State of matter, phases, that arise from electromagnetic forces between atoms and elec ...
uses i
on GitHub
* pymatnest is a package designed for exploring the
energy landscape
Energy () is the quantitative property that is transferred to a body or to a physical system, recognizable in the performance of work and in the form of heat and light. Energy is a conserved quantity—the law of conservation of energy ...
of different materials, calculating thermodynamic variables at arbitrary temperatures and locating
phase transitions
In physics, chemistry, and other related fields like biology, a phase transition (or phase change) is the physical process of transition between one state of a medium and another. Commonly the term is used to refer to changes among the basic Sta ...
i
on GitHub* The MultiNest software package is capable of performing nested sampling on multi-modal posterior distributions.
It has interfaces for C++, Fortran and Python inputs, and i
available on GitHub
* PolyChord is another nested sampling software packag
available on GitHub
PolyChord's computational efficiency scales better with an increase in the number of parameters than MultiNest, meaning PolyChord can be more efficient for high dimensional problems. It has interfaces to likelihood functions written in Python, Fortran, C, or C++.
* NestedSamplers.jl, a Julia
Julia may refer to:
People
*Julia (given name), including a list of people with the name
*Julia (surname), including a list of people with the name
*Julia gens, a patrician family of Ancient Rome
*Julia (clairvoyant) (fl. 1689), lady's maid of Qu ...
package for implementing single- and multi-ellipsoidal nested sampling algorithms i
on GitHub
Korali
is a high-performance framework for uncertainty quantification, optimization, and deep reinforcement learning, which also implements nested sampling.
Applications
Since nested sampling was proposed in 2004, it has been used in many aspects of the field of astronomy
Astronomy is a natural science that studies celestial objects and the phenomena that occur in the cosmos. It uses mathematics, physics, and chemistry in order to explain their origin and their overall evolution. Objects of interest includ ...
. One paper suggested using nested sampling for cosmological
Cosmology () is a branch of physics and metaphysics dealing with the nature of the universe, the cosmos. The term ''cosmology'' was first used in English in 1656 in Thomas Blount's ''Glossographia'', with the meaning of "a speaking of the wo ...
model selection
Model selection is the task of selecting a model from among various candidates on the basis of performance criterion to choose the best one.
In the context of machine learning and more generally statistical analysis, this may be the selection of ...
and object detection, as it "uniquely combines accuracy, general applicability and computational feasibility."[ A refinement of the algorithm to handle multimodal posteriors has been suggested as a means to detect astronomical objects in extant datasets.][ Other applications of nested sampling are in the field of finite element updating where the algorithm is used to choose an optimal ]finite element
Finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat tran ...
model, and this was applied to structural dynamics
Structural dynamics is a type of structural analysis which covers the behavior of a structure subjected to dynamic (actions having high acceleration) loading. Dynamic loads include people, wind, waves, traffic, earthquakes, and blasts. Any structu ...
. This sampling method has also been used in the field of materials modeling. It can be used to learn the partition function from statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. Sometimes called statistical physics or statistical thermodynamics, its applicati ...
and derive thermodynamic
Thermodynamics is a branch of physics that deals with heat, work, and temperature, and their relation to energy, entropy, and the physical properties of matter and radiation. The behavior of these quantities is governed by the four laws of th ...
properties.
Dynamic nested sampling
Dynamic nested sampling is a generalisation of the nested sampling algorithm in which the number of samples taken in different regions of the parameter space is dynamically adjusted to maximise calculation accuracy. This can lead to large improvements in accuracy and computational efficiency when compared to the original nested sampling algorithm, in which the allocation of samples cannot be changed and often many samples are taken in regions which have little effect on calculation accuracy.
Publicly available dynamic nested sampling software packages include:
* – a Python implementation of dynamic nested sampling which can b
downloaded from GitHub
* dyPolyChord: a software package which can be used with Python, C++ and Fortran likelihood and prior distributions. dyPolyChord i
available on GitHub
Dynamic nested sampling has been applied to a variety of scientific problems, including analysis of gravitational waves, mapping distances in space and exoplanet detection.
See also
* Bayesian model comparison
*List of algorithms
An algorithm is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems.
Broadly, algorithms define process(es), sets of rules, or methodologies that are to be f ...
References
{{Reflist
Bayesian statistics
Model selection
Randomized algorithms