Accelerating Bayesian Phylogenetic Inference via Delayed Acceptance Sequential Monte Carlo with Random Forest Surrogates

Technical Summary: Accelerating Bayesian Phylogenetic Inference via Delayed Acceptance Sequential Monte Carlo with Random Forest Surrogates

Problem Statement
In Bayesian phylogenetics, the primary objective is to estimate the posterior distribution over phylogenetic trees (topology and branch lengths) and evolutionary parameters. This involves computing a posterior distribution that requires summing over an intractable number of tree topologies and integrating over high-dimensional branch lengths. While Markov chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC) methods are standard for approximating these distributions, they face a critical bottleneck with large-scale sequence data: the repeated evaluation of the likelihood function is computationally prohibitive. Existing approaches, such as adaptive MCMC moves or variational approximations, have attempted to mitigate this, but the computational cost of exact likelihood calculations remains a dominant factor in inference time.

Methodology
The authors propose a novel framework integrating Delayed Acceptance (DA) mechanisms with Sequential Monte Carlo (SMC), utilizing Random Forest (RF) surrogates to accelerate the search of tree space.

1. Delayed Acceptance MCMC Kernel:
   The core innovation is a two-stage (effectively three-step) acceptance procedure designed to avoid calculating the true likelihood for proposals that are likely to be rejected.

   • Step 1 (Surrogate Check): Upon proposing a new state $x^*$, the algorithm first evaluates a surrogate change in the log-likelihood, $\Delta x^*$, predicted by a machine learning model. If $\Delta x^* < \kappa$ (where $\kappa$ is a user-specified negative threshold), the proposal is rejected immediately without computing the true likelihood, priors, or proposal ratios.
   • Step 2 (Pseudo-Acceptance): If the proposal passes the first check, the algorithm computes the ratio of priors and proposals combined with the surrogate likelihood $f(x^*)$. A second acceptance probability $\tilde{\alpha}$ is calculated.
   • Step 3 (True Likelihood): Only if the proposal passes the first two stages is the exact likelihood $p(D|x^*)$ computed to determine the final acceptance probability $\bar{\alpha}$.
   • Adjustment Parameter ($\delta$): A tuning parameter $\delta$ is added to the surrogate log-likelihood change to control the trade-off between computational speed and posterior accuracy. A larger $\delta$ reduces false rejections (Type II errors) but increases the number of true likelihood evaluations.

2. Random Forest Surrogate Modeling:
   Since phylogenetic tree topologies exist in a discrete state space, standard machine learning cannot directly model the likelihood. Instead, the authors model the change in log-likelihood caused by tree moves.

   • Feature Extraction: The method extracts 35 continuous features representing tree proposals (specifically eSPR, stNNI, Multiplier, and global Multiplier moves). These features include global tree statistics, partial subtree information, rearrangement path details, and heuristic indicators (e.g., "Long branch attraction risk").
   • Model Training: A Random Forest regressor is trained to predict the log-likelihood change ($\Delta \log L$) based on these features. The training data is collected via a pilot run of an annealed SMC algorithm, ensuring coverage of both high and low posterior regions.

3. Delayed Acceptance SMC (DA-SMC):
   The DA-MCMC kernel is embedded into an SMC framework. The algorithm maintains a population of particles that evolve through a series of intermediate target distributions $\pi_r(x) \propto p(x)[1(\Delta x > \kappa) \min\{p(D|x), f(x)\}]^{\phi_r}$.

   • Propagation: Particles are propagated using the DA-MCMC kernel.
   • Re-weighting: Weights are updated based on the ratio of the intermediate targets, utilizing the surrogate likelihood where the true likelihood is not computed.
   • Resampling: Particles are resampled when the relative effective sample size (rESS) drops below a threshold.
   • Marginal Likelihood: The framework provides an unbiased estimator for the marginal likelihood of the surrogate-augmented posterior, which can be used for model selection.

Key Contributions

• Algorithmic Framework: The integration of a delayed acceptance mechanism with SMC for Bayesian phylogenetics, specifically tailored to reduce the frequency of expensive likelihood evaluations.
• Feature Engineering: The development of a comprehensive set of 35 topological and branch-length features to characterize tree moves (eSPR, stNNI, etc.) for machine learning prediction.
• Surrogate Modeling: The application of Random Forests to predict likelihood changes, demonstrating robustness to high-dimensional features and non-linear relationships without pre-selection.
• Parameter Selection Strategy: A data-driven procedure to select the tuning parameter $\delta$ by controlling the false rejection rate (Type II error) during the training phase.
• Software Implementation: Development of a Python package (DAphyloSMC) implementing the proposed method.

Results
The authors validate the method on both simulated and real-world datasets:

• Simulation Studies:
  • Model Selection: DA-SMC correctly identified the true data-generating model (K2P) among candidates (JC69, K2P, GTR) by estimating marginal likelihoods, effectively penalizing both underfitting and over-parameterization.
  • Parameter Sensitivity: Increasing the number of iterations ($R$) was found to be more critical for convergence than increasing the number of particles ($K$) under a fixed total budget.
  • Efficiency: The DA-SMC achieved substantial time savings compared to standard Annealed SMC (ASMC), with the speedup becoming more pronounced as the number of taxa increased. Parallelization of the likelihood evaluation step further accelerated performance.
  • Accuracy: The method maintained robust estimation of tree topologies (measured by Robinson-Foulds and Partition Metrics) while significantly reducing the number of likelihood evaluations.
• Real Data Analysis:
  • Applied to three datasets (Primates, M336, M1809) and compared against MrBayes under identical computational budgets.
  • DA-SMC consistently outperformed MrBayes in terms of tree distance metrics (RF and PM) and achieved higher log-likelihood and marginal likelihood estimates.
  • For the M1809 dataset, the method bypassed exact likelihood calculations for 46.64% of proposals while maintaining a controlled false-negative rate, demonstrating significant computational efficiency without sacrificing accuracy.

Significance and Claims
The paper claims that the proposed DA-SMC approach offers a practical solution to the computational bottleneck in large-scale Bayesian phylogenetic inference. By leveraging machine learning to filter out poor proposals early in the process, the method significantly reduces the computational burden associated with likelihood evaluations. The authors assert that their approach:

1. Accelerates Search: Substantially reduces the number of likelihood evaluations required to explore tree space.
2. Maintains Accuracy: Preserves the quality of posterior inference and model selection capabilities, often outperforming standard MCMC (MrBayes) within the same computational budget.
3. Provides Theoretical Guarantees: Under specific conditions (perfect surrogate), the method recovers the exact posterior. The authors provide theoretical proofs for the consistency and asymptotic normality of the SMC estimator and the unbiasedness of the marginal likelihood estimator for the surrogate-augmented distribution.
4. Offers Flexibility: The framework is modular, allowing for the potential integration of other machine learning models or deep learning architectures in the future, and supports parallelization inherent to SMC.

The authors remain modest regarding the limitations, acknowledging that inaccuracies in the surrogate model can lead to false acceptances (Type I errors) or false rejections (Type II errors), which are managed through the tuning parameter $\delta$. They note that while the current implementation relies on hand-crafted features, future work could explore more sophisticated representations of tree space.