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

Riepilogo Tecnico: Accelerazione dell'Inferenza Filogenetica Bayesiana tramite Accettazione Ritardata con Monte Carlo Sequenziale e Surrogati a Foreste Casuali

Enunciato del Problema
Nella filogenetica bayesiana, l'obiettivo principale è stimare la distribuzione a posteriori sugli alberi filogenetici (topologia e lunghezze dei rami) e sui parametri evolutivi. Ciò comporta il calcolo di una distribuzione a posteriori che richiede la somma su un numero intrattabile di topologie di alberi e l'integrazione su lunghezze dei rami ad alta dimensionalità. Sebbene i metodi Markov Chain Monte Carlo (MCMC) e Sequential Monte Carlo (SMC) siano lo standard per l'approssimazione di tali distribuzioni, essi incontrano un collo di bottiglia critico con dati di sequenza su larga scala: la valutazione ripetuta della funzione di verosimiglianza è computazionalmente proibitiva. Gli approcci esistenti, come mosse MCMC adattive o approssimazioni variazionali, hanno tentato di mitigare questo problema, ma il costo computazionale dei calcoli esatti della verosimiglianza rimane un fattore dominante nel tempo di inferenza.

Metodologia
Gli autori propongono un nuovo framework che integra meccanismi di Accettazione Ritardata (DA) con Monte Carlo Sequenziale (SMC), utilizzando surrogati a Foreste Casuali (RF) per accelerare la ricerca nello spazio degli alberi.

1. Nucleo MCMC ad Accettazione Ritardata:
   L'innovazione centrale è una procedura di accettazione in due stadi (effettivamente in tre passaggi) progettata per evitare il calcolo della vera verosimiglianza per proposte che hanno alta probabilità di essere rifiutate.

   • Passo 1 (Controllo del Surrogato): Al momento di proporre un nuovo stato $x^*$, l'algoritmo valuta prima una variazione surrogata nel log-verosimiglianza, $\Delta x^*$, prevista da un modello di apprendimento automatico. Se $\Delta x^* < \kappa$ (dove $\kappa$ è una soglia negativa specificata dall'utente), la proposta viene rifiutata immediatamente senza calcolare la vera verosimiglianza, le prior o i rapporti di proposta.
   • Passo 2 (Pseudo-Accettazione): Se la proposta supera il primo controllo, l'algoritmo calcola il rapporto tra le prior e le proposte combinato con la verosimiglianza surrogata $f(x^*)$. Viene calcolata una seconda probabilità di accettazione $\tilde{\alpha}$.
   • Passo 3 (Vera Verosimiglianza): Solo se la proposta supera i primi due stadi viene calcolata la vera verosimiglianza $p(D|x^*)$ per determinare la probabilità finale di accettazione $\bar{\alpha}$.
   • Parametro di Aggiustamento ($\delta$): Un parametro di sintonizzazione $\delta$ viene aggiunto alla variazione surrogata del log-verosimiglianza per controllare il compromesso tra velocità computazionale e accuratezza della posterior. Un $\delta$ più grande riduce i falsi rifiuti (errori di Tipo II) ma aumenta il numero di valutazioni della vera verosimiglianza.

2. Modellazione del Surrogato a Foresta Casuale:
   Poiché le topologie degli alberi filogenetici esistono in uno spazio degli stati discreto, l'apprendimento automatico standard non può modellare direttamente la verosimiglianza. Invece, gli autori modellano la variazione nel log-verosimiglianza causata dalle mosse dell'albero.

   • Estrazione delle Caratteristiche: Il metodo estrae 35 caratteristiche continue che rappresentano le proposte di alberi (specificamente mosse eSPR, stNNI, Multiplier e global Multiplier). Queste caratteristiche includono statistiche globali dell'albero, informazioni parziali sui sottorami, dettagli del percorso di riarrangiamento e indicatori euristici (ad esempio, "Rischio di attrazione dei rami lunghi").
   • Addestramento del Modello: Un regressore a Foresta Casuale viene addestrato per prevedere la variazione del log-verosimiglianza ($\Delta \log L$) basandosi su queste caratteristiche. I dati di addestramento vengono raccolti tramite una corsa preliminare di un algoritmo SMC annnealed, garantendo la copertura sia delle regioni ad alta che di quelle a bassa posterior.

3. SMC ad Accettazione Ritardata (DA-SMC):
   Il nucleo DA-MCMC è incorporato in un framework SMC. L'algoritmo mantiene una popolazione di particelle che evolvono attraverso una serie di distribuzioni target intermedie $\pi_r(x) \propto p(x)[1(\Delta x > \kappa) \min\{p(D|x), f(x)\}]^{\phi_r}$.

   • Propagazione: Le particelle vengono propagate utilizzando il nucleo DA-MCMC.
   • Ripesatura: I pesi vengono aggiornati in base al rapporto tra i target intermedi, utilizzando la verosimiglianza surrogata laddove la vera verosimiglianza non viene calcolata.
   • Campionamento: Le particelle vengono ricampionate quando la dimensione effettiva del campione relativa (rESS) scende sotto una soglia.
   • Verosimiglianza Marginale: Il framework fornisce uno stimatore non distorto per la verosimiglianza marginale della posterior arricchita dal surrogato, che può essere utilizzata per la selezione del modello.

Contributi Chiave

• Framework Algoritmico: L'integrazione di un meccanismo di accettazione ritardata con SMC per la filogenetica bayesiana, specificamente adattato per ridurre la frequenza delle costose valutazioni della verosimiglianza.
• Ingegneria delle Caratteristiche: Lo sviluppo di un set completo di 35 caratteristiche topologiche e di lunghezze dei rami per caratterizzare le mosse dell'albero (eSPR, stNNI, ecc.) per la previsione tramite apprendimento automatico.
• Modellazione del Surrogato: L'applicazione delle Foreste Casuali per prevedere le variazioni di verosimiglianza, dimostrando robustezza rispetto a caratteristiche ad alta dimensionalità e relazioni non lineari senza pre-selezione.
• Strategia di Selezione dei Parametri: Una procedura guidata dai dati per selezionare il parametro di sintonizzazione $\delta$ controllando il tasso di falso rifiuto (errore di Tipo II) durante la fase di addestramento.
• Implementazione Software: Sviluppo di un pacchetto Python (DAphyloSMC) che implementa il metodo proposto.

Risultati
Gli autori validano il metodo su dataset sia simulati che reali:

• Studi di Simulazione:
  • Selezione del Modello: DA-SMC ha correttamente identificato il vero modello generatore dei dati (K2P) tra i candidati (JC69, K2P, GTR) stimando le verosimiglianze marginali, penalizzando efficacemente sia il sottodimensionamento che la sovrapparametrizzazione.
  • Sensibilità dei Parametri: È stato riscontrato che aumentare il numero di iterazioni ($R$) è più critico per la convergenza rispetto all'aumento del numero di particelle ($K$) sotto un budget totale fisso.
  • Efficienza: DA-SMC ha raggiunto notevoli risparmi di tempo rispetto all'SMC Annealed (ASMC) standard, con un aumento di velocità che diventa più pronunciato all'aumentare del numero di taxa. La parallelizzazione del passo di valutazione della verosimiglianza ha ulteriormente accelerato le prestazioni.
  • Accuratezza: Il metodo ha mantenuto una stima robusta delle topologie degli alberi (misurata tramite le metriche Robinson-Foulds e Partition Metrics) riducendo significativamente il numero di valutazioni della verosimiglianza.
• Analisi su Dati Reali:
  • Applicato a tre dataset (Primati, M336, M1809) e confrontato con MrBayes sotto budget computazionali identici.
  • DA-SMC ha costantemente superato MrBayes in termini di metriche di distanza degli alberi (RF e PM) e ha raggiunto stime di log-verosimiglianza e verosimiglianza marginale più elevate.
  • Per il dataset M1809, il metodo ha bypassato i calcoli esatti della verosimiglianza per il 46,64% delle proposte mantenendo un tasso di falsi negativi controllato, dimostrando un'efficienza computazionale significativa senza sacrificare l'accuratezza.

Significato e Affermazioni
Il documento afferma che l'approccio DA-SMC proposto offre una soluzione pratica al collo di bottiglia computazionale nell'inferenza filogenetica bayesiana su larga scala. Sfruttando l'apprendimento automatico per filtrare le proposte scadenti nelle fasi iniziali del processo, il metodo riduce significativamente il carico computazionale associato alle valutazioni della verosimiglianza. Gli autori affermano che il loro approccio:

1. Accelera la Ricerca: Riduce sostanzialmente il numero di valutazioni della verosimiglianza necessarie per esplorare lo spazio degli alberi.
2. Mantiene l'Accuratezza: Preserva la qualità dell'inferenza a posteriori e delle capacità di selezione del modello, spesso superando l'MCMC standard (MrBayes) entro lo stesso budget computazionale.
3. Fornisce Garanzie Teoriche: Sotto condizioni specifiche (surrogato perfetto), il metodo recupera la posterior esatta. Gli autori forniscono dimostrazioni teoriche per la consistenza e la normalità asintotica dello stimatore SMC e per la non distorsione dello stimatore della verosimiglianza marginale per la distribuzione arricchita dal surrogato.
4. Offre Flessibilità: Il framework è modulare, consentendo la potenziale integrazione di altri modelli di apprendimento automatico o architetture di deep learning in futuro, e supporta la parallelizzazione intrinseca all'SMC.

Gli autori rimangono modesti riguardo alle limitazioni, riconoscendo che le imprecisioni nel modello surrogato possono portare a falsi accetti (errori di Tipo I) o falsi rifiuti (errori di Tipo II), che sono gestiti attraverso il parametro di sintonizzazione $\delta$. Osservano che, sebbene l'implementazione attuale si basi su caratteristiche create manualmente, un lavoro futuro potrebbe esplorare rappresentazioni più sofisticate dello spazio degli alberi.