PaperlayerView exact revision on arXiv

Source-linked AI summary

Model selection and parameter inference in phylogenetics using Nested Sampling

Patricio Maturana, Brendon J. Brewer, Steffen Klaere, Remco Bouckaert

arXiv:1703.05471v3q-bio.QMstat.CO

TL;DR

Phylogenetic Bayesian inference needs computationally reliable estimates of marginal likelihoods and posterior distributions, but existing methods can be costly, tuning-dependent, or difficult to quantify uncertainty for. This paper introduces nested sampling for phylogenetics, finding that it supports both tasks within one framework and is competitive across the assessed scenarios.

  • Problem

    Phylogenetic marginal-likelihood estimation and posterior inference can require high computational effort, while existing marginal-likelihood methods depend on tuning parameters and often lack directly calculated uncertainty estimates.

  • Method

    The paper introduces nested sampling to phylogenetic inference, including variable tree topologies, and assesses it against established methods.

  • Results

    Nested sampling produced reliable marginal-likelihood estimates, consistent posterior clade probabilities in difficult tree spaces, and posterior summaries from the same run used for model selection.

  • Takeaways & Limitations

    Nested sampling provides marginal-likelihood estimation with uncertainty and posterior parameter inference without extra sampling cost from recycled points.

  • Takeaways & Limitations

    The number of MCMC steps must exceed the parameter-space dimension to avoid a downward-biased marginal-likelihood estimate, and more efficient transition kernels remain an open research area.

Abstract

from arXiv · show

Bayesian inference methods rely on numerical algorithms for both model selection and parameter inference. In general, these algorithms require a high computational effort to yield reliable estimates. One of the major challenges in phylogenetics is the estimation of the marginal likelihood. This quantity is commonly used for comparing different evolutionary models, but its calculation, even for simple models, incurs high computational cost. Another interesting challenge relates to the estimation of the posterior distribution. Often, long Markov chains are required to get sufficient samples to carry out parameter inference, especially for tree distributions. In general, these problems are addressed separately by using different procedures. Nested sampling (NS) is a Bayesian computation algorithm which provides the means to estimate marginal likelihoods together with their uncertainties, and to sample from the posterior distribution at no extra cost. The methods currently used in phylogenetics for marginal likelihood estimation lack in practicality due to their dependence on many tuning parameters and the inability of most implementations to provide a direct way to calculate the uncertainties associated with the estimates. To address these issues, we introduce NS to phylogenetics. Its performance is assessed under different scenarios and compared to established methods. We conclude that NS is a competitive and attractive algorithm for phylogenetic inference. An implementation is available as a package for BEAST 2 under the LGPL licence, accessible at https://github.com/BEAST2-Dev/nested-sampling.

1 Bayesian inference

Bayesian phylogenetic model selection uses marginal likelihoods, but established estimators trade accuracy against computational cost, tuning requirements, or applicability. Nested sampling addresses these issues by reducing the marginal-likelihood calculation to one dimension while requiring less problem-specific tuning.

  • Harmonic-mean estimation is unreliable, whereas path sampling and stepping-stone sampling are more accurate but computationally expensive.
  • Nested sampling inherits a model-selection advantage from estimating marginal likelihoods while also supporting direct posterior inference from the same framework.
  • Path sampling and stepping-stone sampling require annealing schedules and other problem-dependent specifications that may be impractical or unsuitable.
  • Path sampling and stepping-stone sampling can fail or become impractical for partly convex likelihood functions, while generalized stepping-stone sampling depends on an appropriate reference distribution.
  • Nested sampling measures the relationship between likelihood values and prior mass, reducing the multidimensional integral to one dimension and requiring less problem-specific tuning.

2 Nested Sampling

Nested sampling rewrites the evidence as a one-dimensional integral over cumulative prior mass. It then approximates that integral from likelihood values evaluated along decreasing prior-mass thresholds.

  • The evidence is the expected likelihood under the prior, and nested sampling transforms this multidimensional integral into a one-dimensional integral.
  • Nested sampling defines ξ(λ) as the prior-mass proportion with likelihood greater than λ and uses its inverse to express evidence as an integral over ξ.
  • The function L(ξ) decreases from its highest value at ξ = 0 to its lowest at ξ = 1, with posterior mass generally concentrated near ξ = 0.
  • Numerical quadrature estimates the evidence from a sequence of decreasing ξ-values and increasing likelihood values, with weights defined by successive ξ differences.

2.1 Sequence of L-values

Nested sampling generates likelihood values by iteratively replacing the active point with the lowest likelihood. The replacement is drawn from the prior subject to a likelihood constraint.

  • Nested sampling maintains N active points, discards the point with the lowest likelihood, and replaces it with a prior draw constrained by the current likelihood threshold.

2.2 Sequence of ξ-values

Nested sampling estimates prior-mass compression through successive shrinkage factors. These factors can be generated stochastically or deterministically, and their uncertainty contributes to uncertainty in the evidence estimate.

  • The discarded points provide an increasing sequence of likelihoods, while the corresponding ξ-values are inferred from the nested-sampling procedure.
  • Nested sampling estimates the evidence as the gray area relating cumulative prior mass to the likelihood function, typically concentrated near ξ ≈ 0.
  • Uncertainty in the nested-sampling estimate mainly arises from approximating the ξ-values.
  • Nested sampling explores prior mass geometrically through cumulative products of shrinkage factors, beginning with ξ0 = 1.
  • Each shrinkage factor ti follows a Beta(N, 1) distribution because it is the maximum of N uniform draws within the current prior mass.
  • Nested sampling offers stochastic and deterministic schemes for estimating shrinkage factors, using random Beta draws or their expectations.
  • Using the geometric mean for shrinkage is recommended in the described examples, whereas the arithmetic mean connects nested sampling to rare-event simulation and unbiased estimates of Z.

2.3 Sampling

Nested sampling must adapt its proposal mechanism to a target distribution that changes as the prior is compressed. Information and entropy quantify how much posterior mass remains and help guide termination.

  • 2.3 Sampling: NS proposals face a variable target distribution because prior compression progressively constrains the sampled region.Tree proposals must explore broadly early, then operate under increasingly restrictive likelihood conditions.
  • 2.3 Sampling: Bold moves support early exploration, whereas conservative moves retain higher acceptance as the target becomes constrained.An ideal proposal mechanism would adapt to this changing sampling behavior over time.
  • 2.3 Sampling: Entropy measures information gained from data by comparing the posterior distribution with the prior distribution.It is defined as the posterior expectation of log(P(θ)/π(θ)).
  • 2.3 Sampling: The quantity e^-H represents the typical prior-to-posterior mass ratio and approximates the bulk of posterior mass occupying the prior.This interpretation supports an information-based termination condition for nested sampling.
  • 2.3 Sampling: A prior consistent with the likelihood has lower information than one whose mass is concentrated in different regions.Greater change from prior belief to posterior belief corresponds to more information gained from the data.

2.5 Uncertainty

Nested-sampling uncertainty mainly reflects stochastic approximation of prior volume, while quadrature error is usually smaller. Uncertainty can also be estimated by replicating prior-volume sequences without regenerating the likelihood sequence.

  • 2.5 Uncertainty: Nested-sampling uncertainty arises from approximating prior volumes and from numerical integration, with the former usually dominating.Quadrature error is at most O(N^-1) for standard quadrature and O(N^-2) for the trapezoidal rule.
  • 2.5 Uncertainty: The uncertainty in log Z depends directly on uncertainty in the cumulative sum of log prior-volume estimates.The prior-volume shrinkage terms determine the stochastic component of the evidence estimate.
  • 2.5 Uncertainty: NS requires approximately N × H steps to reach the posterior, linking the number of live points and information to uncertainty estimation.Here H is the information measure and N is the number of active points.
  • 2.5 Uncertainty: The asymptotic variance of the NS approximation grows linearly with parameter dimension, and its distribution is asymptotically Gaussian.This result characterizes how dimensionality affects the estimator's uncertainty.
  • 2.5 Uncertainty: Replicating NS estimates with different prior-volume sequences yields a distribution for log Z at marginal computational cost.The same stochastic strategy can also be applied to parameter inference because likelihood-sequence generation dominates computation.

2.6 Algorithm

The NS algorithm maintains live prior-constrained points, repeatedly removes the lowest-likelihood point, updates its prior-volume weight, and replaces it with a higher-likelihood draw. Iteration continues until a stopping condition is met, although no rigorous condition guarantees complete evidence coverage.

  • 2.6 Algorithm: NS begins by sampling N points from the prior distribution.These points form the initial active or live set.
  • 2.6 Algorithm: At each iteration, the active point with the lowest likelihood is selected and discarded.The discarded point contributes to the evidence estimate before replacement.
  • 2.6 Algorithm: The algorithm assigns prior-volume weight w_i = ξ_i−1 − ξ_i, using a trapezoidal alternative when specified.The weight represents the prior-volume interval associated with the iteration.
  • 2.6 Algorithm: The discarded point is replaced by a draw from the prior constrained to have greater likelihood than the discarded point.This maintains the nested sequence of likelihood-constrained active points.
  • 2.6 Algorithm: NS repeats the routine until a stopping criterion is satisfied, but no rigorous criterion guarantees that most of the evidence has been found.Proposed criteria include monitoring the potential maximum contribution and the information-based progression of iterations.
  • 2.6 Algorithm: The authors use relative error as the termination criterion because proposed conditions can fail if future likelihood values increase faster than expected.Such future values could overwhelm points that currently have high weights.

2.7 Posterior samples

Nested sampling also provides posterior samples from its discarded points by assigning them weights proportional to prior multiplied by likelihood. Thus, posterior sampling requires no extra cost beyond the NS run.

  • 2.7 Posterior samples: Discarded NS points can be reused as posterior samples by assigning weights proportional to prior multiplied by likelihood.The discarded sequence already contributes to marginal-likelihood estimation, so posterior sampling adds no extra cost.

3 Application

Across small, partitioned, and tree-island datasets, nested sampling (NS) was evaluated for marginal-likelihood estimation, model selection, and parameter inference. NS agreed with established estimates in simpler cases and produced consistent posterior results where MCMC or stepping-stone sampling had difficulty.

  • Small test case: NS estimated the four-taxa marginal likelihood as -2349.70 (SD 0.38), agreeing with the ILP estimate of -2349.97.The average of four stepping-stone estimates was -2349.55.
  • Model selection: The relaxed-clock model had a substantially higher marginal likelihood than the strict-clock model, yielding strong Bayes-factor evidence in its favour.This comparison was based on stepping-stone estimates, with NS providing consistent estimates and uncertainty intervals.
  • Model selection: For the Euphorbia dataset, NS 95% confidence intervals contained stepping-stone estimates for both strict-clock and relaxed-clock models.The non-overlapping intervals supported model selection, and overlapping intervals would require more active points.
  • Parameter inference: For Euphorbia parameter inference, every NS 95% confidence interval contained the corresponding MCMC mean and standard-deviation estimate.NS posterior sample sizes ranged from 9 to 47 points, with a mean of around 15 and standard deviation of 7.3.
  • Tetrapod: On the Tetrapod dataset, independent MCMC chains converged to different posterior distributions, whereas NS produced consistent clade probabilities across replicated analyses.Some clades had 100% support in one MCMC sample and 0% in the other; NS posterior sample sizes were around 2,300.
  • Tetrapod: Stepping-stone estimates for Tetrapod were more than 2 SDs below NS estimates, suggesting difficulty sampling near the posterior distribution.The authors state that this sampling problem could lead to marginal-likelihood underestimation and affect GSS as well.
  • Tetrapod: For another Tetrapod analysis, NS posterior clade probabilities were quite similar to MCMC values whose effective sampling sizes were at least 400.The values clustered around the straight line, indicating agreement between the posterior tree samples.

4 Conclusion

The paper finds nested sampling competitive for phylogenetic model selection and parameter inference across several challenging settings. NS combines marginal-likelihood estimation, uncertainty assessment, and posterior sampling, while requiring fewer tuning choices than established methods.

  • 4 Conclusion: NS was assessed across small, partitioned, tree-island, and flat-tree phylogenetic settings, including comparisons with established methods.The evaluations covered marginal likelihood estimation, parameter inference, and posterior clade probabilities.
  • 4 Conclusion: NS requires fewer user-specified tuning parameters than path sampling, stepping-stone sampling, and generalized stepping-stone sampling.Its main settings are the number of active points and MCMC steps used to generate replacement points.
  • 4 Conclusion: NS provides marginal-likelihood estimates and their uncertainty in a single run, whereas GSS requires replications to estimate uncertainty.Increasing the number of active points reduces NS uncertainty approximately in proportion to its inverse square root.
  • 4 Conclusion: NS also performs parameter inference without extra cost by recycling points used for marginal-likelihood estimation.The paper reports posterior confidence intervals and clade probabilities, including in complex tree-island spaces.
  • 4 Conclusion: The authors conclude that NS is competitive with established phylogenetic methods across the evaluated contexts.They describe its practical use as more user-friendly than the other methods presented.
  • 4 Conclusion: The NS algorithm is implemented as a parallel-capable package for BEAST 2 and supports phylogenetic inference with variable tree topology.The implementation is available under the LGPL licence.

Statistical example

The statistical example tests marginal-likelihood estimation when the likelihood contains regions with different scales. NS remains near the true value and produces accurate posterior samples, whereas MCMC-based reference distributions can cause GSS estimates to fail.

  • Statistical example: The true log marginal likelihood is log(2) = 0.693, and estimates are replicated 1,000 times for comparison.NS is evaluated with 1 and 99 active points, while GSS uses chains started at zero or at random uniform values.
  • Statistical example: GSS started at zero underestimates the true value, while its random-start variant has mean 17.56 and standard deviation 1.18.The zero-start reference distribution excludes substantial probability mass, and the random-start reference distribution fails to weight the parameter-space regions correctly.
  • Statistical example: NS estimates remain around the true value even with a single active point.The standard deviations are 5.85 with 1 active point and 0.57 with 99 active points.
  • Statistical example: NS produces accurate posterior samples that conventional MCMC methods cannot obtain in this example.The comparison includes Metropolis-Hastings and slice sampling.
  • Statistical example: MCMC reference-distribution quality depends on the starting point because chains can remain trapped in the narrow spike region.This dependence directly affects marginal-likelihood estimation when important regions of parameter space are excluded.
Loading 1703.05471v3…