Nonlinear Causal Discovery through a Sequential Edge Orientation Approach

1. Il Problema

La scoperta causale mira a ricostruire la struttura di un Grafo Aciclico Diretto (DAG) che rappresenta le relazioni causali tra un insieme di variabili, partendo da dati osservativi.

• Limiti degli approcci esistenti: La maggior parte dei metodi attuali si basa su modelli lineari con rumore additivo gaussiano, che permettono di identificare solo una classe di equivalenza di Markov (rappresentata da un CPDAG - Completed Partially Directed Acyclic Graph), non il DAG vero e proprio.
• Sfide nei modelli non lineari: Sebbene i modelli a rumore additivo non lineare (ANM) offrano l'identificabilità del DAG vero, i metodi esistenti soffrono di:
  • Assunzioni di modello troppo restrittive.
  • Dipendenza eccessiva da test di indipendenza generali (es. basati su kernel) che sono computazionalmente costosi ($O(n^2)$) e difficili da calibrare.
  • Scarsa robustezza in caso di errata specificazione del modello (model misspecification).
  • Difficoltà nel gestire grandi grafi o dati con distribuzioni complesse.

L'obiettivo del paper è sviluppare un algoritmo efficiente, robusto e teoricamente garantito per orientare gli archi non diretti di un CPDAG e recuperare il DAG causale vero in scenari non lineari.

2. Metodologia: SNOE

Gli autori propongono SNOE (Sequential Nonlinear Orientation of Edges), un algoritmo basato su un approccio sequenziale per orientare gli archi. Il metodo si articola in tre fasi principali:

A. Impostazione e Assunzioni

Il metodo assume che i dati siano generati da un Modello a Rumore Additivo (ANM): $X_i = f_i(PA_i) + \epsilon_i$, dove $f_i$ è una funzione non lineare arbitraria e il rumore $\epsilon_i$ è indipendente dai genitori $PA_i$. Viene utilizzata una versione ristretta di ANM (funzioni tre volte differenziabili).

B. Il Criterio PANM (Pairwise Additive Noise Model)

Il cuore teorico dell'algoritmo è il PANM.

• Definizione: Una coppia di nodi $(X, Y)$ con archi non diretti in un PDAG soddisfa il PANM se, dati i loro insiemi di genitori identificati nel grafo parziale, la relazione causale può essere determinata verificando l'indipendenza tra il termine di errore e le variabili genitore.
• Identificabilità: Il paper dimostra che se una coppia soddisfa il PANM, la direzione causale è identificabile.
• Strategia Sequenziale: Invece di cercare un ordinamento topologico globale dei nodi, SNOE identifica iterativamente gli archi non diretti che soddisfano il PANM (basandosi sui genitori già noti), li orienta, e utilizza le regole di Meek per propagare le nuove direzioni. Questo processo garantisce che, a ogni iterazione, esista almeno un arco orientabile correttamente.

C. Componenti dell'Algoritmo

1. Apprendimento Iniziale (CPDAG): Utilizza una versione modificata dell'algoritmo PC per apprendere lo scheletro del grafo e le strutture v (v-structures), producendo un CPDAG iniziale. Viene mantenuto un set di archi candidati per evitare di perdere connessioni reali a causa di soglie di significatività troppo rigide.
2. Classificazione degli Archi (Ranking): Prima di orientare, gli archi non diretti vengono classificati in base alla loro adesione al PANM.
   • Viene calcolato una misura di dipendenza (basata sull'informazione reciproca normalizzata) tra i residui della regressione e le variabili parenti.
   • Gli archi che soddisfano il PANM (dove la dipendenza è zero o minima) vengono valutati per primi.
3. Test di Orientamento (Likelihood Ratio Test): Per ogni arco candidato, viene eseguito un test del rapporto di verosimiglianza (Likelihood Ratio Test - LRT) per confrontare le due direzioni possibili ($X \to Y$ vs $Y \to X$).
   • Il test confronta la verosimiglianza congiunta condizionata dei due modelli.
   • Utilizza una strategia di splitting del campione (training/test) per garantire la distribuzione asintotica normale della statistica del test e prevenire l'overfitting.
   • Il test fornisce una decisione definitiva sulla direzione causale o lascia l'arco non orientato se i modelli sono indistinguibili.
4. Pulizia e Raffinamento: Vengono rimossi gli archi spurie tramite test di significatività sui coefficienti di regressione (GAM) e, se necessario, il PDAG viene esteso a un DAG completo.

3. Contributi Chiave

1. Criterio PANM: Una nuova condizione basata su un modello di rumore additivo a coppie per determinare l'identificabilità e l'orientamento corretto degli archi in un grafo parziale.
2. Algoritmo Sequenziale Garantito: Un algoritmo che, a livello di popolazione, recupera il DAG vero dal suo CPDAG orientando gli archi in sequenza secondo il criterio PANM.
3. Consistenza Strutturale: Prove teoriche che dimostrano la consistenza dell'algoritmo nel limite di grandi campioni (large-sample limit).
4. Efficienza Computazionale: A differenza dei metodi basati su kernel (che scalano quadraticamente), SNOE è computazionalmente efficiente perché valuta solo sottografi locali (nodi e genitori) e non l'intero grafo in ogni passo.
5. Robustezza: Il metodo è dimostrato robusto rispetto a violazioni delle assunzioni del modello (es. rumore non gaussiano) e a errori di specificazione.

4. Risultati Sperimentali

Gli autori hanno valutato SNOE su dati sintetici e reali confrontandolo con metodi di riferimento come CAM, NOTEARS, DAGMA e SCORE.

• Dati Sintetici:
  • Accuratezza: SNOE ha ottenuto punteggi F1 superiori in modo coerente rispetto ai metodi concorrenti su diverse funzioni generatrici (lineari, invertibili, non invertibili) e distribuzioni di rumore (Gaussiana e non Gaussiana).
  • Velocità: SNOE è significativamente più veloce (fino a 7.7 volte più veloce per grafi grandi) rispetto agli approcci basati su ottimizzazione continua o deep learning.
  • Robustezza: Le prestazioni rimangono elevate anche quando il rumore non è gaussiano o quando le funzioni non sono puramente additive (es. MLP).
• Dati Reali:
  • Flow Cytometry (Sachs Network): SNOE ha prodotto il grafo più vicino alla verità, con un punteggio F1 superiore del 30% rispetto agli altri metodi, minimizzando i falsi positivi.
  • Coppie Causa-Effetto (Tübingen): Su 98 coppie, la variante con cross-validazione (SNOE-CV) ha raggiunto un'accuratezza globale del 66.3%, superando la maggior parte dei metodi basati su entropia esistenti.

5. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nella scoperta causale non lineare per diversi motivi:

• Colma il divario teorico-pratico: Fornisce un metodo che non solo è teoricamente garantito per recuperare il DAG vero, ma è anche pratico ed efficiente da implementare.
• Supera i limiti dei test di indipendenza: Sostituisce i costosi test di indipendenza condizionale con un test di verosimiglianza locale e un criterio di ordinamento intelligente, riducendo drasticamente il costo computazionale.
• Flessibilità: Non richiede che l'intero grafo sia identificabile in una sola volta; lavora localmente, rendendolo scalabile e robusto agli errori iniziali nella struttura del grafo.
• Versatilità: Dimostra che l'approccio sequenziale basato su criteri locali è superiore alle strategie globali di ottimizzazione o ai metodi puramente basati su kernel per l'apprendimento di DAG non lineari.

In sintesi, SNOE offre una soluzione robusta, veloce e teoricamente fondata per la scoperta di relazioni causali in scenari complessi e non lineari, superando molte delle limitazioni degli stati dell'arte attuali.