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

Resumo Técnico: Aceleração da Inferência Filogenética Bayesiana via Amostragem Sequencial de Monte Carlo com Aceitação Atrasada e Surrogatos de Floresta Aleatória

Declaração do Problema
Na filogenética bayesiana, o objetivo principal é estimar a distribuição posterior sobre árvores filogenéticas (topologia e comprimentos dos ramos) e parâmetros evolutivos. Isso envolve calcular uma distribuição posterior que exige somar sobre um número intratável de topologias de árvores e integrar sobre comprimentos de ramos de alta dimensão. Embora os métodos de Monte Carlo via Cadeias de Markov (MCMC) e de Monte Carlo Sequencial (SMC) sejam padrão para aproximar essas distribuições, eles enfrentam um gargalo crítico com dados de sequência em grande escala: a avaliação repetida da função de verossimilhança é computacionalmente proibitiva. Abordagens existentes, como movimentos de MCMC adaptativos ou aproximações variacionais, tentaram mitigar isso, mas o custo computacional dos cálculos exatos de verossimilhança permanece um fator dominante no tempo de inferência.

Metodologia
Os autores propõem um novo quadro integrando mecanismos de Aceitação Atrasada (AA) com Monte Carlo Sequencial (SMC), utilizando surrogatos de Floresta Aleatória (FA) para acelerar a busca no espaço de árvores.

1. Núcleo de MCMC com Aceitação Atrasada:
   A inovação central é um procedimento de aceitação em duas etapas (efetivamente três passos) projetado para evitar o cálculo da verossimilhança verdadeira para propostas que provavelmente serão rejeitadas.

   • Passo 1 (Verificação do Surrogato): Ao propor um novo estado $x^*$, o algoritmo avalia primeiro uma mudança surrogata no log-verossimilhança, $\Delta x^*$, prevista por um modelo de aprendizado de máquina. Se $\Delta x^* < \kappa$ (onde $\kappa$ é um limite negativo especificado pelo usuário), a proposta é rejeitada imediatamente sem calcular a verossimilhança verdadeira, os priores ou as razões de proposta.
   • Passo 2 (Aceitação Pseudo): Se a proposta passar na primeira verificação, o algoritmo calcula a razão de priores e propostas combinada com a verossimilhança surrogata $f(x^*)$. Uma segunda probabilidade de aceitação $\tilde{\alpha}$ é calculada.
   • Passo 3 (Verossimilhança Verdadeira): Apenas se a proposta passar nas duas primeiras etapas é que a verossimilhança exata $p(D|x^*)$ é calculada para determinar a probabilidade final de aceitação $\bar{\alpha}$.
   • Parâmetro de Ajuste ($\delta$): Um parâmetro de ajuste $\delta$ é adicionado à mudança de log-verossimilhança surrogata para controlar o compromisso entre velocidade computacional e precisão posterior. Um $\delta$ maior reduz rejeições falsas (erros do Tipo II), mas aumenta o número de avaliações de verossimilhança verdadeira.

2. Modelagem Surrogata com Floresta Aleatória:
   Como as topologias de árvores filogenéticas existem em um espaço de estados discreto, o aprendizado de máquina padrão não pode modelar diretamente a verossimilhança. Em vez disso, os autores modelam a mudança na log-verossimilhança causada por movimentos na árvore.

   • Extração de Características: O método extrai 35 características contínuas representando propostas de árvores (especificamente movimentos eSPR, stNNI, Multiplier e Multiplier global). Essas características incluem estatísticas globais da árvore, informações parciais de subárvores, detalhes do caminho de rearranjo e indicadores heurísticos (por exemplo, "Risco de atração de ramo longo").
   • Treinamento do Modelo: Um regressor de Floresta Aleatória é treinado para prever a mudança na log-verossimilhança ($\Delta \log L$) com base nessas características. Os dados de treinamento são coletados por meio de uma execução piloto de um algoritmo SMC annealed, garantindo a cobertura de regiões posteriores altas e baixas.

3. SMC com Aceitação Atrasada (AA-SMC):
   O núcleo de MCMC com AA é incorporado a um quadro de SMC. O algoritmo mantém uma população de partículas que evoluem através de uma série de distribuições alvo intermediárias $\pi_r(x) \propto p(x)[1(\Delta x > \kappa) \min\{p(D|x), f(x)\}]^{\phi_r}$.

   • Propagação: As partículas são propagadas usando o núcleo de MCMC com AA.
   • Reponderação: Os pesos são atualizados com base na razão dos alvos intermediários, utilizando a verossimilhança surrogata onde a verossimilhança verdadeira não é calculada.
   • Ressamplagem: As partículas são ressampeladas quando o tamanho efetivo de amostra relativo (rESS) cai abaixo de um limite.
   • Verossimilhança Marginal: O quadro fornece um estimador não tendencioso para a verossimilhança marginal da posterior aumentada pelo surrogato, que pode ser usada para seleção de modelos.

Principais Contribuições

• Quadro Algorítmico: A integração de um mecanismo de aceitação atrasada com SMC para filogenética bayesiana, especificamente adaptado para reduzir a frequência de avaliações de verossimilhança caras.
• Engenharia de Características: O desenvolvimento de um conjunto abrangente de 35 características topológicas e de comprimento de ramo para caracterizar movimentos de árvores (eSPR, stNNI, etc.) para previsão por aprendizado de máquina.
• Modelagem Surrogata: A aplicação de Florestas Aleatórias para prever mudanças na verossimilhança, demonstrando robustez a características de alta dimensão e relações não lineares sem pré-seleção.
• Estratégia de Seleção de Parâmetros: Um procedimento orientado por dados para selecionar o parâmetro de ajuste $\delta$ controlando a taxa de rejeição falsa (erro do Tipo II) durante a fase de treinamento.
• Implementação de Software: Desenvolvimento de um pacote Python (DAphyloSMC) implementando o método proposto.

Resultados
Os autores validam o método em conjuntos de dados simulados e do mundo real:

• Estudos de Simulação:
  • Seleção de Modelo: O AA-SMC identificou corretamente o modelo gerador de dados verdadeiro (K2P) entre candidatos (JC69, K2P, GTR) estimando verossimilhanças marginais, penalizando efetivamente tanto o subajuste quanto a superparametrização.
  • Sensibilidade de Parâmetros: Verificou-se que aumentar o número de iterações ($R$) era mais crítico para a convergência do que aumentar o número de partículas ($K$) sob um orçamento total fixo.
  • Eficiência: O AA-SMC alcançou economias de tempo substanciais em comparação com o SMC Annealed padrão (ASMC), com o ganho de velocidade tornando-se mais pronunciado à medida que o número de táxons aumentava. A paralelização da etapa de avaliação da verossimilhança acelerou ainda mais o desempenho.
  • Precisão: O método manteve uma estimativa robusta de topologias de árvores (medida por Métricas de Robinson-Foulds e de Partição) enquanto reduzia significativamente o número de avaliações de verossimilhança.
• Análise de Dados Reais:
  • Aplicado a três conjuntos de dados (Primates, M336, M1809) e comparado ao MrBayes sob orçamentos computacionais idênticos.
  • O AA-SMC superou consistentemente o MrBayes em termos de métricas de distância de árvores (RF e PM) e alcançou estimativas de log-verossimilhança e verossimilhança marginal mais altas.
  • Para o conjunto de dados M1809, o método contornou cálculos exatos de verossimilhança para 46,64% das propostas enquanto mantinha uma taxa de falso-negativo controlada, demonstrando eficiência computacional significativa sem sacrificar a precisão.

Significado e Alegações
O artigo afirma que a abordagem AA-SMC proposta oferece uma solução prática para o gargalo computacional na inferência filogenética bayesiana em grande escala. Ao aproveitar o aprendizado de máquina para filtrar propostas ruins cedo no processo, o método reduz significativamente o ônus computacional associado às avaliações de verossimilhança. Os autores afirmam que sua abordagem:

1. Acelera a Busca: Reduz substancialmente o número de avaliações de verossimilhança necessárias para explorar o espaço de árvores.
2. Mantém a Precisão: Preserva a qualidade da inferência posterior e as capacidades de seleção de modelos, muitas vezes superando o MCMC padrão (MrBayes) dentro do mesmo orçamento computacional.
3. Oferece Garantias Teóricas: Sob condições específicas (surrogato perfeito), o método recupera a posterior exata. Os autores fornecem provas teóricas para a consistência e normalidade assintótica do estimador SMC e para a não tendenciosidade do estimador de verossimilhança marginal para a distribuição aumentada pelo surrogato.
4. Oferece Flexibilidade: O quadro é modular, permitindo a integração potencial de outros modelos de aprendizado de máquina ou arquiteturas de aprendizado profundo no futuro, e suporta a paralelização inerente ao SMC.

Os autores permanecem modestos quanto às limitações, reconhecendo que imprecisões no modelo surrogato podem levar a aceitações falsas (erros do Tipo I) ou rejeições falsas (erros do Tipo II), que são gerenciadas através do parâmetro de ajuste $\delta$. Eles observam que, embora a implementação atual dependa de características criadas manualmente, trabalhos futuros poderiam explorar representações mais sofisticadas do espaço de árvores.