PaperlayerView exact revision on arXiv

Source-linked AI summary

Importance Nested Sampling and the MultiNest Algorithm

F. Feroz, M. P. Hobson, E. Cameron, A. N. Pettitt

arXiv:1306.2144v3astro-ph.IMphysics.data-anstat.CO

TL;DR

Multimodal posterior exploration and high-dimensional Bayesian evidence integration challenge conventional inference methods. The paper develops importance nested sampling, which reuses all MultiNest draws—including rejected points—to improve evidence estimation without changing parameter-space exploration. Across the paper’s scope, INS offers up to an order-of-magnitude higher evidence accuracy than vanilla nested sampling, while its reliability depends on coverage and high-dimensional volume approximations.

  • Problem

    Multimodal posteriors impede traditional MCMC, while Bayesian model selection requires difficult integration over the full parameter space to estimate evidence.

  • Method

    INS treats all points collected during MultiNest’s ellipsoidal rejection sampling, including constraint-rejected points, as a pseudo-importance sample for evidence summation.

  • Results

    INS can calculate Bayesian evidence at up to an order-of-magnitude higher accuracy than vanilla nested sampling without changing how MultiNest explores parameter space.

  • Takeaways & Limitations

    INS also provides reasonably accurate evidence estimates in MultiNest’s constant-efficiency mode, which explores spaces up to approximately 50 dimensions more efficiently than default mode.

  • Takeaways & Limitations

    INS uncertainty estimates require non-vanishing proposal probability wherever the posterior has non-vanishing probability, while ellipsoid-overlap volume approximations become less accurate in higher dimensions.

Abstract

from arXiv · show

Bayesian inference involves two main computational challenges. First, in estimating the parameters of some model for the data, the posterior distribution may well be highly multi-modal: a regime in which the convergence to stationarity of traditional Markov Chain Monte Carlo (MCMC) techniques becomes incredibly slow. Second, in selecting between a set of competing models the necessary estimation of the Bayesian evidence for each is, by definition, a (possibly high-dimensional) integration over the entire parameter space; again this can be a daunting computational task, although new Monte Carlo (MC) integration algorithms offer solutions of ever increasing efficiency. Nested sampling (NS) is one such contemporary MC strategy targeted at calculation of the Bayesian evidence, but which also enables posterior inference as a by-product, thereby allowing simultaneous parameter estimation and model selection. The widely-used MultiNest algorithm presents a particularly efficient implementation of the NS technique for multi-modal posteriors. In this paper we discuss importance nested sampling (INS), an alternative summation of the MultiNest draws, which can calculate the Bayesian evidence at up to an order of magnitude higher accuracy than `vanilla' NS with no change in the way MultiNest explores the parameter space. This is accomplished by treating as a (pseudo-)importance sample the totality of points collected by MultiNest, including those previously discarded under the constrained likelihood sampling of the NS algorithm. We apply this technique to several challenging test problems and compare the accuracy of Bayesian evidences obtained with INS against those from vanilla NS.

1. INTRODUCTION

Bayesian inference separates parameter estimation from model selection, but multimodal posteriors challenge MCMC and evidence calculation requires difficult integration. Nested sampling addresses both tasks, and this paper introduces INS as a more accurate evidence summation using MultiNest draws.

  • 1. INTRODUCTION: Parameter estimation and model selection are distinct Bayesian inference tasks with different computational demands.Parameter estimation concerns model parameters, whereas model selection requires comparing competing models through their evidence.
  • 1. INTRODUCTION: MCMC methods can be highly inefficient when posterior distributions are multi-modal or degenerate.
  • 1. INTRODUCTION: Nested sampling calculates Bayesian evidence while also enabling posterior inference as a by-product.
  • 1. INTRODUCTION: MultiNest implements nested sampling efficiently for posteriors containing multiple modes and/or degeneracies.
  • 1. INTRODUCTION: INS is an alternative summation of MultiNest draws with potential to improve evidence-computation efficiency by up to an order of magnitude.The paper describes INS as an addition to the vanilla nested-sampling scheme without changing the paper’s overall MultiNest exploration framework.

2. BAYESIAN INFERENCE

Bayesian inference uses the posterior to update parameter beliefs from data, while the evidence normalizes that posterior and supports model comparison. The evidence also averages likelihood over the prior, favoring models that assign substantial prior volume to likely parameter regions.

  • 2. BAYESIAN INFERENCE: Bayes’ theorem defines the posterior probability of model parameters given data and a model hypothesis.
  • 2. BAYESIAN INFERENCE: The Bayesian evidence is the factor that normalizes the posterior over the parameter domain.
  • 2. BAYESIAN INFERENCE: Because the evidence is independent of parameters, it can be ignored when parameter inference uses samples from the unnormalized posterior.
  • 2. BAYESIAN INFERENCE: The evidence is central to Bayesian model selection between competing hypotheses.
  • 2. BAYESIAN INFERENCE: Evidence averages likelihood over the prior, penalizing models with large low-likelihood regions and implementing an automatic Occam’s Razor.

3. NESTED SAMPLING AND THE MULTINEST ALGORITHM

Nested sampling transforms evidence calculation into a one-dimensional integral over likelihood as a function of prior volume, using constrained-prior draws. MultiNest uses adaptive ellipsoidal rejection sampling to explore complex posteriors and supports posterior inference from discarded points.

  • 3. NESTED SAMPLING AND THE MULTINEST ALGORITHM: Nested sampling transforms the multidimensional evidence integral into a one-dimensional integral over the likelihood’s inverse survival function with respect to prior mass.
  • 3. NESTED SAMPLING AND THE MULTINEST ALGORITHM: Nested sampling repeatedly removes the lowest-likelihood live point and replaces it with a prior draw constrained to have higher likelihood.The prior volume is modeled as Xi = tiXi−1, with the expected shrinkage commonly approximated by Xi ≈ exp(−i/Nlive).
  • 3.2. Stopping criterion: The algorithm terminates when the expected evidence contribution from the remaining live points falls below a user-defined tolerance.A cautious estimate is ΔZi = LmaxXi.
  • 3.3. Posterior inferences: Discarded nested-sampling points and final live points can provide importance-weighted posterior summaries such as means, standard deviations, and covariances.
  • 3.5. MULTINEST algorithm: MultiNest encloses live points in possibly overlapping ellipsoids and samples replacement points from their union under the likelihood constraint.Its expectation-minimisation decomposition minimizes ellipsoid volume while requiring coverage of at least Xi/f.
  • 3.5. MULTINEST algorithm: MultiNest’s ellipsoidal decomposition adapts to elongated, curving degeneracies and distinguishes complex posterior geometries using multiple smaller ellipsoids.
  • 3.5. MULTINEST algorithm: High-dimensional ellipsoidal overshoot can sharply reduce rejection-sampling efficiency, motivating MultiNest’s constant-efficiency mode.Constant-efficiency mode targets a user-defined efficiency while keeping every live point enclosed, but can miss constrained-likelihood regions and bias vanilla evidence estimates.

4. IMPORTANCE NESTED SAMPLING

Importance nested sampling (INS) reuses all points generated during MultiNest exploration, including points rejected by constrained likelihood sampling, to improve evidence computation. It constructs a posteriori pseudo-importance weights and can also assign posterior-density estimators, while uncertainty estimation remains dependent on MultiNest’s sampling mode and draw dependence.

  • MultiNest discards likelihood-evaluated points failing L > L_i; INS incorporates these points rather than wasting their computational cost.The method addresses inefficiency in MultiNest’s ellipsoidal rejection sampling by reusing the rejected pool.
  • INS defines a pseudo-importance density from MultiNest’s ellipsoidal decompositions, iteration point counts, and union volumes.The density is constructed after sampling, so later draws are dependent to some extent on earlier draws and decompositions.
  • Union volumes for overlapping ellipsoids are estimated by Monte Carlo sampling, counting how many ellipsoids contain each sampled point.This volume procedure requires no likelihood evaluations and is therefore not computationally demanding.
  • INS estimates Bayesian evidence by weighting MultiNest points under the pseudo-importance density and can assign each collected point a posterior probability-density estimator.The evidence summation uses the union volume at each iteration, while posterior-density estimates are available for all N_tot collected points.
  • INS can produce accurate evidence estimates and posterior summaries in MultiNest’s constant-efficiency mode without requiring ellipsoids to enclose every constrained-likelihood region.The usefulness of this feature is often limited by difficulties estimating uncertainty for constant-efficiency evidence estimates.
  • INS uncertainty estimates are not strictly applicable because its a posteriori draws are dependent, although default MultiNest operation makes them increasingly near-independent.For constant-efficiency mode, the authors recommend repeat simulations to check evidence stability under reasonable changes in N_live and/or f.

5. APPLICATIONS

The applications test MULTINEST with importance nested sampling (INS) on challenging likelihoods and posterior distributions, comparing evidence estimates with and without INS. Across these problems, INS improves evidence accuracy in several settings but does not eliminate biases in the most difficult heavy-tailed case.

  • Test problem 1: For the two-ring problem, INS remains consistent with the true log(Z) in default mode and is off by at most ∼0.2 in constant-efficiency mode.This holds for a 50D problem using 500 live points, although the constant-efficiency uncertainty estimate may be unreliable.
  • Test problem 2: For the egg-box problem, INS gives log(Ẑ) = 235.837 ± 0.008 versus 235.848 ± 0.078 without INS, compared with the true log Z = 235.856.Both estimates compare favorably with the true value, while the INS result has a smaller reported uncertainty.
  • Test problem 3: For the 16D Gaussian mixture, INS returns log(Ẑ) = −0.03 ± 0.01 in default mode and 0.21 ± 0.01 in constant-efficiency mode, against true log(Z) = 0.Without INS, the corresponding estimates are 0.39 ± 0.27 and 0.25 ± 0.27.
  • Test problem 4: For the 20D Gaussian-LogGamma mixture, INS recovers all four posterior modes but the evidence estimate remains substantially biased, at ∼8σ from the true value.Default-mode INS gives log(Ẑ) = −81.958 ± 0.008 versus true log(Z) = −81.887; constant-efficiency mode is poorer and also biased.

6. SUMMARY AND DISCUSSION

The paper develops INS as a further development of MULTINEST, improving evidence accuracy without changing parameter-space exploration. It also discusses settings and tuning choices that affect accuracy, dimensionality, memory, and computational cost.

  • 6. SUMMARY AND DISCUSSION: INS can calculate Bayesian evidence at up to an order-of-magnitude higher accuracy than vanilla nested sampling without changing MULTINEST’s exploration.INS also provides reasonably accurate evidence estimates in MULTINEST’s constant efficiency mode.
  • 6. SUMMARY AND DISCUSSION: Constant efficiency mode enables MULTINEST to explore higher-dimensional spaces up to approximately 50D more efficiently than its default mode.The paper links this mode to the practical value of obtaining higher-accuracy evidence estimates with INS.
  • 6. SUMMARY AND DISCUSSION: Higher evidence accuracy could allow fewer live points or higher target efficiency while maintaining vanilla nested sampling’s accuracy, potentially speeding analysis by several factors.The authors recommend checking posterior stability under reasonable variations of Nlive and f.
  • 6. SUMMARY AND DISCUSSION: INS has increased memory requirements as a slight drawback.This cost accompanies retaining and using the broader set of MULTINEST samples for evidence estimation.
  • 6. SUMMARY AND DISCUSSION: Larger Nlive and lower f generally improve posterior and evidence accuracy but increase computational cost.For multi-modal problems, Nlive determines effective sampling resolution and is particularly important when modes must be resolved.

A. RELATION OF INS TO EXISTING MONTE CARLO SCHEMES

INS is situated within pseudo-importance sampling, nested sampling, and adaptive Monte Carlo methods. Its distinctive proposal mixture is built through the nested-sampling pathway rather than iteratively selected from a pre-specified proposal family.

  • A. RELATION OF INS TO EXISTING MONTE CARLO SCHEMES: INS is reviewed as part of pseudo-importance sampling, nested sampling, and adaptive Monte Carlo methods whose convergence proofs remain limited.The paper gives particular attention to variance reduction and consistency questions within this methodological heritage.
  • A. RELATION OF INS TO EXISTING MONTE CARLO SCHEMES: INS arose from recursive marginal likelihood estimators such as Reverse Logistic Regression and Density of States methods, which pool draws from largely unnormalised densities.These schemes estimate marginal likelihood by losing the labels attached to draws from different densities.
  • A. RELATION OF INS TO EXISTING MONTE CARLO SCHEMES: Deterministic Multiple Mixture Sampling applies a related pooling strategy to strictly normalised importance-sampling proposals to reduce estimator variance.Its motivation is variance reduction relative to allocating the same number of draws to each proposal separately.
  • A. RELATION OF INS TO EXISTING MONTE CARLO SCHEMES: INS differs from AMIS because it builds an efficient mixture proposal through the nested-sampling pathway, whereas AMIS iterates within a pre-specified proposal family.INS’s proposal densities are designed to share near-equal importance in the final mixture, unlike AMIS’s increasingly refined later proposals.
  • A. RELATION OF INS TO EXISTING MONTE CARLO SCHEMES: General consistency for AMIS is difficult to demonstrate because pseudo-importance-weighted terms have an inherent dependence structure.The paper notes that existing solutions rely on modifications and assumptions incompatible with INS or restrictive for target and proposal families.
  • A. RELATION OF INS TO EXISTING MONTE CARLO SCHEMES: Vanilla MULTINEST estimates evidence through nested sampling with constrained-likelihood rejection sampling inside successive ellipsoidal decompositions.This provides the baseline heritage from which INS’s alternative summation is developed.

B. CONVERGENCE BEHAVIOUR OF INS

The convergence analysis studies the INS estimator as the live-point sample size increases, focusing on the ellipsoidal decompositions used in MULTINEST and the assumptions required for the analysis.

  • B. CONVERGENCE BEHAVIOUR OF INS: The appendix studies asymptotic convergence of the INS marginal-likelihood estimator toward the true marginal likelihood as Nlive approaches infinity.It also examines pseudo-importance sampling as a source of variance reduction and bias-related analytical difficulty.
  • B. CONVERGENCE BEHAVIOUR OF INS: The analysis investigates ellipsoidal decompositions almost exactly as implemented in MULTINEST.This connects the appendix’s convergence discussion directly to the algorithm described in the main text.
  • B. CONVERGENCE BEHAVIOUR OF INS: At each decomposition, points are sampled uniformly until a point exceeds the current likelihood threshold and replaces the corresponding live point.The decomposition’s volume and the number of sampled points enter the analysis of the evolving sequence.
  • B. CONVERGENCE BEHAVIOUR OF INS: Pooling draws from each ellipsoidal decomposition into g(·) permits the labels identifying their originating decompositions to be discarded.The first decomposition is fixed to the prior support so the target’s support is contained within g(Θ).
  • B. CONVERGENCE BEHAVIOUR OF INS: The analysis neglects uncertainty in ellipsoidal volumes because their precision can be improved by simulation without likelihood evaluations and at negligible considered cost.This is an explicit assumption of the convergence treatment.

B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture

The paper motivates losing proposal labels in INS by comparing labelled and unlabelled estimators in a simplified normalised mixture setting. The analysis shows that pooling draws can reduce asymptotic variance under stated simplifications.

  • B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture: The ‘losing the labels’ strategy pools draws from proposal components into a pseudo-importance mixture instead of retaining component labels.The simplified analysis uses one independent draw from each of n labelled densities with matching supports.
  • B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture: The simplified convergence argument assumes independent draws, matching proposal supports, and one point per labelled density, unlike full MULTINEST sampling.The paper explicitly identifies these as three key simplifications.
  • B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture: Under finite-variance and Lindeberg conditions, the labelled estimator is analyzed through a central-limit-theorem argument for a triangular array.The target normalizing constant is Z.
  • B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture: For iid samples from the mixture density g(·), the unlabelled estimator is expected to converge in distribution to a Normal with mean Z.Its asymptotic variance is described separately from the labelled estimator’s variance.
  • B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture: Pseudo-importance sampling with explicit samples from each mixture component has smaller asymptotic variance than ordinary importance sampling from the mixture.The reduction follows from replacing multinomial component sampling with fixed sampling in expected proportions.
  • B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture: The unlabelled estimator’s asymptotic variance is always smaller than the labelled estimator’s in the analyzed setting.This strict ordering motivates using pseudo-importance sampling to combine MULTINEST’s ellipsoidal draws.
  • B.1. Motivation for ‘losing the labels’ on a normalised pseudo-importance sampling mixture: The variance reduction appears paradoxical because discarding sampling-process information can improve estimation of the target normalizing constant.The paper interprets this as using information extracted from the target more efficiently rather than literally gaining information.

B.2. Consistency of INS

The paper gives a heuristic consistency argument for INS under strong assumptions about the limiting ellipsoidal decompositions and their continuity. Under these assumptions, the INS empirical distribution converges to the limiting form and the evidence estimator becomes consistent.

  • Assumptions: INS consistency is argued heuristically by assuming each constrained-likelihood contour has a unique limiting ellipsoidal decomposition as Nlive increases.The decompositions are assumed to converge almost surely for the relevant prior-volume sequence.
  • Assumptions: A continuity condition on the limiting decompositions is imposed to ensure that a limiting distribution exists and sampling variation becomes asymptotically irrelevant.This parallels the requirement for an optimal proposal in the equivalent AMIS analysis.
  • Limitations: Formulating sufficient convergence conditions is difficult because the ellipsoidal decompositions have an intractable dependence structure.The required coverage conditions may resemble assumptions already needed for rejection nested sampling.
  • Sampling qualification: The argument acknowledges that the negative-binomial draws within each ellipsoid are not strictly uniform draws, despite being treated as such in the INS summation.The single likelihood-constrained replacement point creates a sampling bias that must vanish asymptotically.
  • Consistency argument: The INS sample empirical distribution converges in distribution to the asymptotic form by the Strong Law of Large Numbers.The convergence-determining classes are hyper-cubes in the compact parameter domain.
  • Consistency argument: The resulting evidence estimator is consistent, with Var[Ẑ_INS] tending to zero under the stated assumptions.The argument treats the pool of biased draws from nearby ellipsoids as asymptotically approximating an unbiased sample.

B.3. Variance breakdown of INS

The INS variance is decomposed into contributions from live-point geometry, negative-binomial sampling, and ordinary importance sampling. Because some variance may be underestimated, the paper recommends larger live-point sets, validation by repeated simulation, and the default MultiNest mode.

  • Variance components: INS variance has three sources: randomness in the live-point decompositions, negative-binomial sampling of ni, and importance-sampling variance of f(Θk)/g(Θk).The paper applies the Law of Total Variance to separate these contributions.
  • Variance components: The decomposition-sequence contribution may be negligible when posterior exploration is sufficiently thorough and all significant modes have been reached.This condition concerns the evolution of the Nlive live-point set and its ellipsoidal geometry.
  • Practical safeguards: INS variance can be underestimated because unaccounted contributions arise from ellipsoidal-sequence randomness and negative-binomial sampling.The paper therefore treats variance-reduction and validation strategies as necessary safeguards.
  • Practical safeguards: The paper advises maximizing Nlive where feasible and comparing estimated variance with repeat-simulation variability before an expensive run.The feasible range of Nlive is often constrained by computational resources.
  • Practical safeguards: Using MultiNest’s default mode rather than constant-efficiency mode reduces one unaccounted variance contribution by limiting ellipsoid shrinkage rates.This recommendation is tied to controlling randomness in the ellipsoidal decomposition sequence.

C. SOME MEASURE-THEORETIC CONSIDERATIONS

The appendix formalizes nested sampling through prior and posterior measures and the transformation from parameter space to prior volume. It clarifies the conditions under which the one-dimensional evidence integral and posterior expectations are valid.

  • Measure-theoretic setup: The measure-theoretic setup assumes well-defined prior and posterior probability spaces on the same parameter sample space.Both measures are characterized through Radon–Nikodym derivatives relative to a common σ-finite baseline measure.
  • Measure-theoretic setup: Nested sampling induces a measure on prior volume X by transforming parameters according to the prior mass above a likelihood threshold.The transformation is valid when it is measurable.
  • Evidence calculation: For the vanilla nested-sampling Riemann integral to be valid, the induced prior-volume measure must be absolutely continuous with respect to Lebesgue measure.Connected support of L(Θ) is given as an additional condition.
  • Evidence calculation: When the inverse likelihood function L(X) exists, the multidimensional evidence can be obtained from the one-dimensional integral over prior volume.This requires L(Θ) to be continuous with connected support.
  • Posterior expectations: The nested-sampling posterior estimator weights sampled functions by likelihood and prior-volume weights, producing an approximation to posterior expectations.The relevant function of prior volume is interpreted as a conditional expectation over likelihood level sets.
  • Posterior expectations: The appendix argues that the equality underlying this posterior-expectation relation follows from the change-of-variables theorem without requiring absolute continuity of the conditional function.A discontinuous indicator-function example is given as a case where both sides exist and agree.
Loading 1306.2144v3…