PaperlayerView exact revision on arXiv

Source-linked AI summary

PolyChord: next-generation nested sampling

W. J. Handley, M. P. Hobson, A. N. Lasenby

arXiv:1506.00171v1astro-ph.IM

TL;DR

PolyChord addresses the difficulty of Bayesian evidence computation in high-dimensional parameter spaces, where conventional methods and existing nested sampling can struggle. It uses slice sampling within hard likelihood constraints, supports semi-independent mode evolution and parameter-speed hierarchies, and is applied in cosmological codes. Its scope includes limitations from insufficient live-point resolution and uncertain performance on high-dimensional curving degeneracies.

  • Problem

    High-dimensional cosmological likelihoods challenge existing nested-sampling methods, while MultiNest cannot exploit hierarchies of parameter speeds.

  • Method

    PolyChord uses slice sampling at each nested-sampling iteration and evolves separate posterior modes semi-independently while exploiting parameter-speed hierarchies.

  • Results

    PolyChord correctly identifies tested clusters up to D = 100, recovers analytic global evidence, and divides local evidence among peaks according to their contributions.

  • Takeaways & Limitations

    PolyChord is used in CosmoChord and ModeChord, including a 37parameter cosmological reconstruction with slow, semi-slow, and fast parameters.

  • Takeaways & Limitations

    Insufficient live-point resolution can cause modes to die out or be missed, while Gaussian shells may not proxy high-dimensional curving degeneracies well.

Abstract

from arXiv · show

PolyChord is a novel nested sampling algorithm tailored for high-dimensional parameter spaces. This paper coincides with the release of PolyChord v1.3, and provides an extensive account of the algorithm. PolyChord utilises slice sampling at each iteration to sample within the hard likelihood constraint of nested sampling. It can identify and evolve separate modes of a posterior semi-independently, and is parallelised using openMPI. It is capable of exploiting a hierarchy of parameter speeds such as those present in CosmoMC and CAMB, and is now in use in the CosmoChord and ModeChord codes. PolyChord is available for download at: http://ccpforge.cse.rl.ac.uk/gf/project/polychord/

1 INTRODUCTION

Bayesian model comparison requires evidence calculations that conventional MCMC cannot perform efficiently, while growing parameter dimensionality and speed hierarchies challenge MultiNest. PolyChord is introduced to address these high-dimensional sampling issues and is already used in cosmological applications.

  • Evidence calculations are high-dimensional integrations required for Bayesian model comparison, but Metropolis–Hastings methods cannot compute them on a usable timescale.
  • MultiNest struggles with high-dimensional parameter spaces and cannot exploit separations in parameter speeds present in modern cosmological likelihoods.
  • PolyChord aims to sample high-dimensional spaces across a hierarchy of parameter speeds.
  • The paper provides an extensive overview of the algorithm, which is used in several cosmological applications.
  • PolyChord is available for download from the paper’s linked repository.

2 BAYESIAN INFERENCE

Bayesian inference combines likelihoods with prior beliefs to obtain posteriors and evidences, supporting both parameter estimation and model comparison. Evidence computation is central to these tasks but has historically been difficult numerically.

  • 2.1 Nomenclature: The likelihood gives the probability of observing data for chosen parameters, while the prior quantifies initial assumptions about parameter values.
  • 2.1 Nomenclature: Integrating the likelihood over the prior yields the evidence, or marginalised likelihood, giving the probability of the data conditioned on the model.
  • 2.2 Parameter estimation: Bayes’ theorem combines likelihood, prior, and evidence to produce the posterior, which updates prior knowledge in light of data.
  • 2.3 Model comparison: Model comparison relies primarily on model evidences; similar evidences require marginalising inferences over all considered models.
  • 2.3 Model comparison: The fully Bayesian approach has been historically underused because numerical evidence computation is difficult.

3 NESTED SAMPLING

Nested sampling contracts prior volume around high-likelihood regions while producing posterior samples and estimating evidence. It replaces constrained-prior draws through iterative live-point updates and prior-to-hypercube transformations.

  • 3.1 Nested sampling: Nested sampling maintains nlive live points and repeatedly removes the lowest-likelihood point, replacing it with a prior draw satisfying a higher likelihood constraint.
  • 3.1 Nested sampling: The live-point region contracts exponentially, with expected prior volume shrinking by a factor of nlive/(nlive + 1) per iteration.
  • 3.2 Evidence calculation: Evidence is estimated by transforming the prior integral into a one-dimensional integral over prior volume and applying quadrature to dead and live points.
  • 3.3 Parameter estimation: Dead and live points support posterior estimation when each point receives an importance weighting determined by its prior-volume shell.
  • 3.3 Parameter estimation: In high dimensions, the evidence is visualised by the area under the X log(X) curve, and sampling terminates when remaining live-point mass is negligible.
  • 3.4 Prior distributions: Nested sampling can operate in the unit D-dimensional hypercube, where prior generation uses uniform random variables and distances have common probability dimensionality.

4 SAMPLING WITHIN AN ISO-LIKELIHOOD CONTOUR

Sampling within an unknown hard likelihood contour is the central challenge distinguishing nested-sampling implementations. PolyChord uses slice sampling to generate constrained points, gaining polynomial dimensional scaling while supporting efficient contour exploration, though correlated or curved degeneracies remain difficult.

  • 4.2 Slice sampling: PolyChord introduces slice sampling at each iteration to generate new live points within the hard likelihood constraint.
  • 4.1 Historical implementations: The hardest nested-sampling step is drawing a new prior point satisfying the hard constraint L > Li when the likelihood contour is unknown.
  • 4.1 Historical implementations: MultiNest uses rejection sampling inside ellipsoids, but rejection sampling eventually has exponential scaling with dimensionality.
  • 4.1 Historical implementations: Markov-chain constrained sampling offers polynomial rather than exponential dimensional scaling, although traditional MH or Gibbs methods require substantial proposal tuning.
  • 4.2 Slice sampling: In higher dimensions, coordinate-wise slice sampling requires a number of likelihood calculations that scales linearly with dimensionality.
  • 4.2 Slice sampling: Slice sampling expands bounds around a point inside the contour, samples within them, and preserves uniformity through detailed balance.
  • 4.2 Slice sampling: The slice-sampling procedure works exceptionally well for non-degenerate parameters but becomes inefficient for correlated parameters or curving degeneracies.

5 THE PolyChord ALGORITHM

PolyChord combines slice sampling with contour whitening, clustering, and parallelisation to address correlated, high-dimensional, and multi-modal nested-sampling problems. Its adaptive sampling uses live and phantom points, while cluster evolution preserves global nested-sampling information and scales nearly linearly up to the number of live points.

  • Cluster evolution: PolyChord identifies clusters and evolves them semi-independently, using estimated cluster volumes to control spawning while retaining the global lowest-likelihood removal rule.The method also partitions evidence among clusters to estimate local evidences whose sum matches the total evidence within inference error.
  • Slice sampling: PolyChord uses slice sampling within the hard likelihood contour to generate decorrelated, uniformly sampled live points.A randomly chosen live point seeds repeated one-dimensional slices; intermediate points are retained as phantom points.
  • Contour whitening: The live and phantom points provide covariance information for whitening contours to size ∼O(1) in every direction and setting w = 1.The whitening transformation is constructed from the covariance matrix through its Cholesky decomposition.
  • Slice-chain length: For roughly convex contours, nrepeats∼O(ndims) is sufficient, with a constant of proportionality between 2 and 6.More complicated contour shapes may require substantially longer chains.
  • Multi-modal posteriors: Multi-modal sampling is constrained by live-point resolution and by covariance whitening that can misrepresent far-separated modes as strongly correlated.Modes with too few live points may die out or be missed, while increasing nlive can alleviate the resolution problem.
  • Parallelisation and tuning: PolyChord parallelises nearly linearly up to the number of live points, and its tuning-parameter count does not scale with dimensionality.The parallelisation is described as suitable for typical astronomical applications, while the tuning contrast is made with Metropolis–Hastings and Gibbs sampling.

Resolution nlive

nlive controls nested-sampling resolution: increasing it slows volume contraction, samples more thoroughly, and improves evidence inference, while too few live points can miss posterior modes.

  • Resolution nlive: nlive is the number of live points maintained throughout nested sampling and acts as a resolution parameter.Increasing nlive causes slower volume contraction and more thorough sampling; runtime scales ∼O(nlive).
  • Resolution nlive: If nlive is set too low, posterior modes may be missed; increasing it improves the accuracy of the evidence Z inference.

Reliability nrepeats

nrepeats controls the slice-sampling chain length and therefore the correlation among live points. Longer chains improve evidence reliability, with curving degeneracies requiring more than the typical setting.

  • Reliability nrepeats: nrepeats is the slice-sampling chain length used to generate a new live point, and increasing it decreases live-point correlation.Posterior estimates remain accurate even when nrepeats is low.
  • Reliability nrepeats: nrepeats∼O(3 × ndims) is typically sufficient, but curving degeneracies may require significantly longer chains for reliable evidence estimates.Setting nrepeats too low can correlate live points; runtime scales ∼O(nrepeats).

6 PolyChord IN ACTION

PolyChord is evaluated as a high-dimensional evidence calculator and multimodal posterior sampler, including difficult clustering and curving-degeneracy problems. It also exploits fast-slow parameter hierarchies in cosmological applications through CosmoChord.

  • 6.1 High-dimensional evidences: PolyChord produces evidence estimates with errors around 0.4 log units for Gaussian likelihoods across dimensionalities.With nlive = 25D, the evidence error remains constant with D; MultiNest estimates using importance nested sampling achieve similar accuracy.
  • 6.1 High-dimensional evidences: PolyChord requires polynomial-scaling likelihood evaluations, whereas MultiNest develops exponential scaling at higher dimensions.The comparison uses convergence when the posterior mass in live points is 10^-2 of the calculated evidence.
  • 6.2.1 Twin peaks: PolyChord identifies twin-peak clusters in arbitrary tested dimensions up to D = 100 and computes global and locally apportioned evidences.This requires nlive and nrepeats to scale in proportion to D.
  • 6.2.1 Twin peaks: For the two-dimensional Rastrigin likelihood, PolyChord accurately computes evidence and posterior samples while isolating the inner 21 modes.Increasing nlive increases the number of modes identified; additional outer modes are found as combinations of lower modes because of their low posterior fraction.
  • 6.3 Rosenbrock function: PolyChord finds both local and global maxima for the four-dimensional Rosenbrock function and produces correct evidence estimates.In higher dimensions it reliably finds both maxima, but the absence of an analytic Rosenbrock evidence prevents verification of the evidence calculation.
  • 6.4 Gaussian shells: For Gaussian shells, PolyChord computes local and global posteriors and evidences up to D = 100 and reliably identifies two modes.The comparison with MultiNest shows a similar runtime pattern to Figure 7, although MultiNest parameters require tuning for correct evidences above 30 dimensions.
  • 6.5 CosmoChord: CosmoChord exploits fast-slow parameter hierarchies and vastly outperforms MultiNest on modern Planck likelihoods.CosmoChord produces parameter estimates consistent with CosmoMC and has been applied to a 37-parameter reconstruction problem.
  • 6.5 CosmoChord: With a well-tuned CosmoMC proposal, PolyChord is 2–4 times slower, but without proposal matrices CosmoChord is significantly faster than native CosmoMC.PolyChord requires only two tuning parameters, compared with approximately O(D) for the native sampler.

7 CONCLUSIONS

PolyChord is introduced as a nested sampling algorithm for high-dimensional parameter spaces, combining slice sampling with fast-slow parameter handling. It can evolve separate posterior modes semi-independently and uses openMPI parallelisation.

  • PolyChord is tailored for high-dimensional parameter spaces and exploits hierarchies of parameter speeds found in CosmoMC and CAMB.
  • Slice sampling operates at each iteration within nested sampling’s hard likelihood constraint.
  • PolyChord identifies and evolves separate posterior modes semi-independently.
  • PolyChord is parallelised using openMPI.

DOWNLOAD LINK

This appendix describes transformations between the unit hypercube and physical parameter space for separable and dependent priors. It gives inverse-transform procedures for uniform, Gaussian, and forced-identifiability priors.

  • The appendix demonstrates transformations from the unit hypercube to physical parameter space for simple separable and more complicated dependent priors.
  • For separable priors, each conditional distribution depends only on its corresponding parameter, reducing the transformation to one-dimensional inverse-transform sampling.
  • A rectangular uniform prior is transformed by inverting its cumulative distribution between θmin and θmax.
  • A Gaussian prior transformation is expressed using its mean µ, standard deviation σ, and the conventional inverse error function erfinv.
  • A forced identifiability prior uniformly distributes ordered parameters within θmin < θ1 < · · · < θn < θmax, supporting applications with ordered spline knots.
  • For the forced identifiability prior, parameters are calculated sequentially from unit-hypercube variables and interpreted as successive uniform order statistics.

APPENDIX B: EVIDENCE ESTIMATES AND ERRORS

Appendix B develops recursive estimates of nested-sampling evidence and its uncertainty. The approach avoids storing prohibitively large dead-point chains and tracks correlated evidence-volume quantities in log form.

  • Monte-Carlo evidence-error estimation requires storing the entire dead-point chain, which is prohibitively large for high-dimensional problems.
  • The evidence is treated as a probability distribution because prior volumes Xi are unknown, with its mean and variance estimated in practice.
  • Nested-sampling volume evolution follows a recursion in which Xi is the largest of nlive uniform volume samples within Xi−1.
  • Because evidence is approximately log-normally distributed, the appendix recommends reporting the mean and variance of log Z.
  • Recursive updates replace the full general formula for clustered high-dimensional calculations, which would require prohibitively large data storage.
  • The unclustered calculation tracks Z, Z2, ZX, X, and X2, initializing them at {0, 0, 0, 1, 1} and storing their logarithms to avoid machine-precision errors.

APPENDIX C: EVIDENCE ESTIMATES AND ERRORS IN CLUSTERS

Appendix C extends evidence and error estimation to multiple evolving clusters. It recursively tracks global and local evidence, cluster volumes, errors, and their correlations, including principled initialization when clusters split.

  • Cluster tracking: For m identified clusters, the algorithm tracks each cluster’s volume and local evidence alongside global evidence and its error.
  • Cluster tracking: Updating {Z, Zp, Xp} with the cluster recursion relations yields consistent local and global evidence-error estimates.
  • Error propagation: Clustered error propagation requires tracking cross-correlations such as ZXp, ZpXp, X2p, and XpXq in addition to evidence variances.
  • Cluster splitting: At cluster splitting, live points are partitioned among new clusters and their volumes are inferred from the observed cluster counts.
  • Cluster splitting: The conditional posterior for split cluster volumes is a Dirichlet distribution with parameters given by the live-point counts.
  • Cluster splitting: The inferred volume means split proportionally to live-point fractions, while the volumes remain correlated at the split.
  • Initialization: Local evidences, errors, volumes, and cross-correlations are initialized consistently when clusters are created or split.
Loading 1506.00171v1…