PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic nested sampling: an improved algorithm for parameter estimation and evidence calculation

Edward Higson, Will Handley, Mike Hobson, Anthony Lasenby

arXiv:1704.03459v4stat.COastro-ph.IMphysics.data-anstat.ME

TL;DR

Standard nested sampling uses a fixed live-point allocation that can spend many samples in regions with negligible posterior mass. The paper introduces dynamic nested sampling, which varies live points to allocate samples more efficiently, and finds improved accuracy across parameter estimation and evidence calculation, including simultaneous improvement of both.

  • Problem

    Standard nested sampling cannot adapt its sample allocation to whether Bayesian evidence calculation or posterior parameter estimation is the primary goal, often sampling regions with negligible posterior mass.

  • Method

    Dynamic nested sampling varies the number of live points to allocate posterior samples efficiently for a priori unknown likelihoods and priors.

  • Results

    Dynamic nested sampling produces significant efficiency gains for parameter estimation, improves evidence calculation accuracy, and can improve both calculations simultaneously.

  • Takeaways & Limitations

    Dynamic nested sampling can be incorporated into existing standard nested-sampling software, with dyPolyChord created for PolyChord-based use.

  • Takeaways & Limitations

    Parameter-estimation error can remain dominated by sampling regions with small posterior mass but extreme parameter values.

Abstract

from arXiv · show

We introduce dynamic nested sampling: a generalisation of the nested sampling algorithm in which the number of "live points" varies to allocate samples more efficiently. In empirical tests the new method significantly improves calculation accuracy compared to standard nested sampling with the same number of samples; this increase in accuracy is equivalent to speeding up the computation by factors of up to ~72 for parameter estimation and ~7 for evidence calculations. We also show that the accuracy of both parameter estimation and evidence calculations can be improved simultaneously. In addition, unlike in standard nested sampling, more accurate results can be obtained by continuing the calculation for longer. Popular standard nested sampling implementations can be easily adapted to perform dynamic nested sampling, and several dynamic nested sampling software packages are now publicly available.

1 Introduction

Nested sampling jointly produces posterior samples and Bayesian evidence estimates, but standard sampling allocates effort inefficiently. Dynamic nested sampling varies live points to target calculation accuracy and improves parameter estimation, evidence calculations, or both.

  • Nested sampling simultaneously provides posterior samples and Bayesian evidence estimates.
  • Standard nested sampling uses a fixed number of live points, often sampling prior regions remote from the posterior bulk.Its allocation cannot adapt to whether evidence calculation or posterior estimation is the primary goal.
  • Dynamic nested sampling varies the number of live points to maximise accuracy for a specified number of posterior samples under practical constraints.Standard nested sampling is the special case with a constant number of live points.
  • Dynamic nested sampling can improve parameter-estimation and evidence-calculation accuracy simultaneously.The method is particularly effective for parameter estimation because standard runs spend substantial effort iterating toward the posterior peak.
  • The paper evaluates dynamic nested sampling against standard nested sampling through empirical tests, including challenging posteriors and signal reconstruction.A detailed comparison with MCMC-based parameter estimation and thermodynamic integration is outside the paper’s scope.
  • Dynamic nested sampling differs from related nested-sampling variants and targets a priori unknown problems without requiring prior posterior knowledge.The paper situates it alongside diffusive, superposition-enhanced, and adaptive thermodynamic-integration approaches.

2 Background: the nested sampling algorithm

Nested sampling computes posterior samples and Bayesian evidence by progressively replacing the lowest-likelihood live point with a higher-likelihood draw. Standard nested sampling keeps the live-point count constant, producing stochastic prior-volume shrinkage.

  • For a likelihood L(θ) and prior π(θ), nested sampling simultaneously computes Bayesian evidence and posterior samples.
  • The algorithm begins with live points sampled from the prior and iteratively replaces the lowest-likelihood point with a draw satisfying L(θ) > L_i.The resulting dead points, together with any remaining live points, support subsequent calculations.
  • Evidence is represented as a one-dimensional integral over prior volume, with X(L) denoting the prior fraction having likelihood greater than L.
  • Prior volumes for dead points are modelled through shrinkage ratios X_i = t_iX_{i−1}, where each t_i follows the largest-of-n-uniforms distribution.The shrinkage ratios are unknown and therefore treated statistically.
  • In standard nested sampling, the number of live points n remains constant for every shrinkage ratio.This constant-n process is illustrated schematically in Figure 1.

Evidence estimation

Nested sampling estimates evidence by quadrature over dead points, using weights determined by stochastic prior-volume shrinkage. The dominant perfect-sampling error comes from variation in the unknown prior-shell volumes.

  • Nested sampling calculates evidence as a quadrature sum over dead points.
  • The quadrature uses unknown shrinkage ratios t and appropriately chosen weights, with the trapezium rule used in this paper.Remaining live points can also be included at termination if required.
  • The dominant perfect-nested-sampling evidence error is statistical variation in the unknown volumes of the prior shells.Expected evidence values and errors are calculated because the shrinkage ratios are unknown a priori.

Parameter estimation

Nested sampling parameter estimation uses weighted dead points, with weights proportional to posterior-mass contributions. Errors arise from estimating weights and from representing entire iso-likelihood contours with single points.

  • Parameter estimation uses dead points, and optionally remaining live points, to construct weighted posterior samples.Each sample’s weight is proportional to its share of posterior mass.
  • Sampling errors include approximating stochastic point weights with their expectations.
  • Sampling errors also arise when a function’s mean over an iso-likelihood contour is approximated by its value at one point.

Combining and dividing nested sampling runs

Nested sampling runs can be combined by merging and ordering their dead points, while individual runs can also be decomposed into valid single-live-point threads.

  • Runs with constant live-point counts can be combined by merging dead points and sorting them by likelihood.The combined sequence is equivalent to one run with live points equal to the sum across constituent runs.
  • A run with n live points can be decomposed into n valid runs, each containing one live point.These single-live-point runs, called threads, are the smallest units used to construct valid nested-sampling runs.

3 Variable numbers of live points

Variable-live-point nested sampling remains valid when shrinkage ratios are independently distributed and supports combining, dividing, and incorporating runs with changing live-point counts. Local live-point allocation affects evidence and parameter-estimation accuracy differently, with posterior weights usually approximating parameter influence but not universally.

  • Variable-live-point runs are valid when successive shrinkage ratios are independently distributed, with live-point counts represented as n_i for each interval.The count must remain constant across the shrinkage ratios between successive dead points.
  • Variable-live-point runs can be combined by requiring the combined live-point count at each likelihood to equal the sum across constituent runs.They can also be divided into constituent threads, although threads may start and finish partway through the run.
  • Additional samples reduce evidence errors in proportion to 1/n_i and approximately in proportion to the evidence contained in point i and all subsequent points.Shrinkage-ratio errors affect the weights of every later point, so local sampling choices have downstream effects.
  • Increasing live points where samples have the highest normalized posterior weights generally improves parameter-estimation accuracy.More equal sample weights also increase information content for a fixed number of samples.
  • For some problems, posterior weights poorly represent parameter influence because errors arise in low-mass regions containing extreme parameter values.Dynamic allocation can instead estimate point importance for a specific parameter or function of parameters.

4 The dynamic nested sampling algorithm

The dynamic nested sampling algorithm first explores with a small fixed live-point run, then adds threads in likelihood regions estimated to matter most for evidence or parameter estimation. It supports user-controlled resource allocation and can improve with longer continuation.

  • Dynamic nested sampling optimizes sample allocation by dynamically varying the number of live points.Its goal is to optimize calculations with a specified number of posterior samples, while standard nested sampling is the constant-live-point special case.
  • The algorithm first performs a small standard run to approximate the unknown posterior-mass distribution across likelihood.It then repeatedly identifies important likelihood ranges and generates additional threads there.
  • The user-controlled goal G allocates resources between evidence calculation and parameter estimation by weighting their normalized importance measures.G = 0 targets evidence calculation, whereas G = 1 targets parameter estimation.
  • Additional threads are generated across points whose importance exceeds a fraction f of the maximum, using f = 0.9 in the paper.The selected range is extended slightly beyond its endpoints to capture steep or discontinuous likelihood changes.
  • Dynamic nested sampling can produce more accurate results by continuing the calculation longer and stopping under a user-specified termination condition.Stopping may depend on a fixed sample count or a desired accuracy level.
  • Standard nested-sampling implementations can be adapted because dynamic nested sampling only requires prior sampling within a hard likelihood constraint.The paper demonstrates this with dyPolyChord and notes dynamic implementations including dynesty and forthcoming PolyChord 2 support.

5 Numerical tests with perfect nested sampling

The numerical tests evaluate dynamic nested sampling under idealized, perfectly sampled conditions across posterior-mass distributions and parameter-estimation targets. Dynamic allocation improves accuracy and efficiency relative to standard nested sampling, with gains depending on posterior concentration, prior scale, and the allocation objective.

  • Test setup: The tests use spherically symmetric likelihoods and priors where uncorrelated samples within iso-likelihood contours can be generated exactly.This isolates allocation effects from implementation-specific sampling uncertainties.
  • Test setup: Dynamic nested sampling estimates posterior means and credible intervals for parameter components, alongside evidence and radial-coordinate summaries.The first parameter component is representative because of spherical symmetry.
  • Live-point allocation: Dynamic nested sampling accurately and consistently allocates live points across logX for the 10-dimensional Gaussian example, relative to posterior mass and mass remaining.The allocation remains accurate in additional exponential-power likelihood tests.
  • Accuracy and efficiency: Dynamic nested sampling with G = 0 and G = 1 produces more accurate evidence and parameter-estimation results than standard nested sampling with similar sample counts.G = 0 targets evidence accuracy, whereas G = 1 targets parameter estimation.
  • Accuracy and efficiency: A balanced choice, G = 0.25, improves evidence calculation and parameter estimation simultaneously.This result is reported for the tested Gaussian and exponential-power cases.
  • Accuracy and efficiency: 72 ± 5 is the largest reported parameter-estimation efficiency gain for a 1,000-dimensional exponential-power likelihood with b = 2.The largest improvement occurs for estimating the posterior median of |θ|.
  • Accuracy and efficiency: Approximately 7 is the evidence-calculation efficiency gain when σπ = 0.1 for all three tested likelihoods.The gain reflects dynamic allocation placing fewer samples after most posterior mass has been reached.

6 Dynamic nested sampling with challenging posteriors

Dynamic nested sampling improves accuracy and efficiency on challenging multimodal and signal-reconstruction problems by reallocating live points, while its gains depend on posterior structure and sampling coverage.

  • 6.1 Numerical tests with a multimodal posterior: Dynamic nested sampling may under-sample a mode discovered late because that mode is absent from threads calculated before its discovery.For highly multimodal posteriors, the initial live-point count must be large enough to avoid losing significant modes.
  • 6.1 Numerical tests with a multimodal posterior: Dynamic nested sampling allocates live points in ways that track posterior mass or remaining posterior mass, even for the multimodal likelihood.The allocation was less precise because dyPolyChord used only the initial exploratory run to estimate point importances.
  • 6.1 Numerical tests with a multimodal posterior: 1.3 ± 0.1 evidence and up to 4.0 ± 0.4 parameter-estimation efficiency gains were measured for the 10-dimensional Gaussian mixture.These tests used dyPolyChord and compared repeated dynamic nested sampling calculations with standard nested sampling using similar sample counts.
  • 6.1 Numerical tests with a multimodal posterior: Dynamic nested sampling reduces implementation-specific effects in parameter-estimation calculations for a challenging 10-dimensional Gaussian mixture.For evidence calculation with G = 0, the difference was not statistically significant because implementation-specific effects formed a smaller fraction of total error.
  • 6.1 Numerical tests with a multimodal posterior: Its efficiency gains can be lower than in comparable unimodal tests because a higher initial live-point count is used and stochastic sampling errors are not reduced as strongly.This comparison concerns the challenging multimodal tests and their corresponding unimodal Gaussian benchmark.
  • 6.2 Numerical tests with signal reconstruction from noisy data: 9.0 ± 4.1 maximum efficiency gain was obtained for estimating the mean fitted signal in noisy-data reconstruction.Dynamic nested sampling also reduced implementation-specific effects in this practical signal-reconstruction calculation.

7 Conclusion

The paper introduces dynamic nested sampling, which varies live points to allocate posterior samples efficiently. Tests report substantial efficiency gains, reduced implementation-specific effects, and an ability to improve accuracy further by running longer.

  • 7 Conclusion: Dynamic nested sampling varies the number of live points to allocate posterior samples efficiently for previously unknown likelihoods and priors.Standard nested sampling is the special case with a constant number of live points.
  • 7 Conclusion: 72 ± 5 maximum computational-efficiency gain was obtained for parameter estimation in numerical tests.The method can also be optimized for evidence calculation or configured to improve evidence and parameter estimation simultaneously.
  • 7 Conclusion: Empirical tests found significant efficiency gains across the likelihoods, priors, dimensions, and estimators considered.The conclusion also reports reduced implementation-specific effects in challenging posterior tests.
  • 7 Conclusion: Continuing a dynamic nested-sampling run can produce more accurate results, unlike standard nested sampling.This provides a practical way to improve accuracy by extending computation.
  • 7 Conclusion: Popular standard nested-sampling implementations can be adapted because dynamic nested sampling requires the same type of constrained prior sampling.Public packages include dyPolyChord, dynesty, and perfectns.

Appendices

The appendices examine evidence and sampling-error behavior in dynamic nested sampling, including how live-point allocation affects accuracy and how bootstrap estimates perform. They show that additional samples are most valuable where subsequent dead points contain substantial evidence, while identifying a limitation for evidence-error bootstrapping when ninit is small.

  • Sampling-error validation: Bootstrap error estimates match sampling errors observed across repeated dynamic nested sampling calculations.The tests used G = 1, where most threads covered only part of the explored logX range.
  • Sampling-error validation: When ninit is low and G = 1, bootstrap replications may contain too few threads that begin by sampling the whole prior.Separate resampling of initial exploratory threads can ensure each replication contains ninit such threads.
  • Sampling-error validation: When ninit is close to 1, this bootstrap approach produces imprecise estimates of logZ uncertainties.The simulated weights method may perform better in this regime.
  • Evidence accuracy: Increasing the local live-point count reduces evidence uncertainty because shrinkage-ratio errors affect the current and all subsequent points.The analysis treats shrinkage ratios as independent random variables and examines the effect of increasing n_i over an interval.
  • Evidence accuracy: Additional sampling gains are approximately proportional to the evidence contained in subsequent dead points.The expected computational work for increasing live points over an interval is proportional to its log prior shrinkage.

D Tuning for a specific parameter estimation problem

This section tunes dynamic nested sampling for parameter-specific estimation and tests it across heavy-tailed and exponential-power likelihoods. The results show that importance-aware allocation can target influential regions, but tuning may trade accuracy among quantities while broader tests improve evidence and parameter-estimation efficiency.

  • D Tuning for a specific parameter estimation problem: Dynamic nested sampling can allocate more samples to logX regions with significant posterior mass and fewer samples to regions with little posterior mass.For parameter-specific estimation, importance functions can instead emphasize regions containing extreme or highly variable parameter values.
  • D Tuning for a specific parameter estimation problem: Cauchy likelihoods provide a demanding test because their heavy tails leave significant posterior mass across much of the explored logX range.The section therefore expects relatively low efficiency gains for untuned dynamic parameter estimation.
  • D Tuning for a specific parameter estimation problem: Tuned dynamic nested sampling allocates live points consistently with the tuned importance function.Figure 14 shows that the tuned live-point counts as a function of logX agree with the corresponding analytical expectation.
  • D Tuning for a specific parameter estimation problem: For the Cauchy example, G = 1 slightly worsens estimates of the global mean, while tuning improves the gain for that quantity but reduces accuracy for its 84% credible interval.The tuned importance function significantly improves estimates of the second moment in this case.
  • Additional likelihood tests: In the b = 2 exponential-power case, dynamic sampling improves efficiency by 1.25 ± 0.04 for evidence calculation and up to 6.8 ± 0.2 for parameter estimation.Figures 15 and 16 also show accurate and consistent live-point allocation for the tested likelihoods.
  • Additional likelihood tests: Dynamic nested sampling results for the Gaussian mixture likelihood are close to analytical values, indicating no significant sampling bias.The near equality of root-mean-squared errors and standard deviations supports reliable efficiency-gain estimates.

G Signal reconstruction priors and data

This section specifies the priors and true-signal parameters used for a basis-function fitting example. It also describes resuming the exploratory run when later likelihood regions require additional live points.

  • G Signal reconstruction priors and data: Table 11 lists the priors on the basis-function parameters used in the fitting example.Sorted priors enforce an ordering constraint.
  • G Signal reconstruction priors and data: Table 12 gives the parameters of the four generalised Gaussian basis functions used as the true signal.The data were sampled from this constructed signal.
  • G Signal reconstruction priors and data: The exploratory run is resumed at later likelihood values when the target live-point count becomes non-zero again.This allows additional sampling in regions where the allocation n(L) requires it.
Loading 1704.03459v4…