Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

Riepilogo Tecnico: Scoperta Causale Iterativa con Certificati di Impossibilità per Arco

Enunciazione del Problema
Gli algoritmi attuali di scoperta causale restituiscono tipicamente un grafo aciclico diretto (DAG) completamente orientato, ma non riescono a distinguere tra le direzioni degli archi identificate dai dati e quelle imposte dall'algoritmo per soddisfare i vincoli di output. In condizioni standard di Markov e fedeltà, i dati osservazionali identificano solo una classe di equivalenza di Markov; le orientazioni degli archi non presenti nelle strutture-v sono indeterminati dalla distribuzione congiunta. I metodi esistenti o impongono orientamenti su archi non identificabili (ad es. NOTEARS, DAGMA) senza giustificazione diagnostica, o li lasciano non orientati (ad es. FCI) senza specificare le informazioni a priori necessarie per risolverli. Inoltre, è stato dimostrato che i metodi di ottimizzazione continua sfruttano artefatti dei dati (ad es. la varsortabilità) che mimano un'identificazione genuina. Manca un protocollo principiato che fornisca l'auditabilità per arco, separando esplicitamente l'identificabilità guidata dai dati dall'imposizione algoritmica, e identificando le specifiche domande da porre agli esperti per risolvere gli archi non identificabili.

Metodologia
Il documento propone un protocollo deterministico a tre stadi per la scoperta causale su dati osservazionali continui. Il protocollo emette un "certificato di impossibilità" discreto per ogni arco candidato in uno scheletro basato solo sui dati, classificando l'arco come risolto (identificato o mediato dai dati) o impossibile (dati insufficienti, richiede input esperto).

1. Stadio 1: Ricerca dello Scheletro e dei Mediatori:

   • Costruisce uno scheletro utilizzando test HSIC controllati per il FDR per scartare coppie marginalmente indipendenti.
   • Esegue una ricerca a più livelli dei mediatori per identificare e rimuovere gli archi mediati da variabili osservate.

2. Stadio 2: Cascata di Identificabilità con Gate:

   • Una cascata a otto livelli valuta gli archi rimanenti. I livelli includono metodi classici (ANM Lineare $L_0$, ANM Non Lineare $L_1$, HOC LiNGAM $L_2$) e cinque nuovi livelli introdotti in questo lavoro: LSNM (Rumore Scala-Posizione), IGCI (Geometrico-Informazionale), Stein (Corrispondenza del Punteggio), MDL (Condizione di Markov Algoritmica) e PEIT (Test di Inversione dell'Entropia).
   • Meccanismo di Gate: Ogni livello è precondizionato da test statistici (ad es. Shapiro–Wilk per la non gaussianità, test di eteroscedasticità). Se il precondizionamento di un livello fallisce, questo si astiene invece di forzare un'orientazione.
   • Consenso Inter-Livello: Una "guardia di disaccordo" declassa gli impegni di $L_0$ se livelli a maggiore precisione (IGCI, Stein, MDL) contraddicono la direzione, rinominando l'arco come impossible_l0_disagrees_with_high_tier.
   • Gli archi non risolti da alcun livello ricevono un'etichetta impossible_*, che codifica la specifica modalità di fallimento (ad es. confondimento latente, non linearità debole) e la corrispondente domanda per un esperto di dominio.

3. Stadio 3: Query Mirate all'Oracolo:

   • Il protocollo interagisce con un esperto di dominio solo sugli archi etichettati impossible_*.
   • Primitive di Query:
     • Query per arco: Chiede la direzione (AVANTI/INDIETRO) o l'assenza.
     • Query meta-hub: Chiede i nodi top-$K$ per grado di uscita.
     • Query figli-nodo: Chiede i figli diretti di un nodo specifico, impegnando simultaneamente tutti gli archi in uscita.
   • Auto-Propagazione: Dopo ogni impegno dell'oracolo, il sistema esegue passaggi di auto-risoluzione a costo zero (controlli di aciclicità, regole di Meek, d-separazione transitiva) per risolvere archi aggiuntivi senza ulteriori query.

Contributi Chiave

1. Certificati per Arco: Il protocollo assegna un codice discreto a ogni arco. I codici risolto_* citano il teorema specifico (ad es. $L_{Stein}$) che giustifica la direzione, mentre i codici impossibile_* registrano la modalità di fallimento e la specifica domanda necessaria per risolverlo.
2. Astensione Consapevole dei Livelli: L'introduzione di cinque nuovi livelli con gate (LSNM, IGCI, Stein, MDL, PEIT) garantisce che le direzioni siano impegnate solo quando è soddisfatto un teorema di identificabilità specifico. Se un precondizionamento fallisce, il sistema si astiene invece di forzare un'orientazione potenzialmente spuria.
3. Limite di Interazione 1+K: Il documento stabilisce un limite superiore informativo-teorico di $1+K$ interazioni con l'esperto per recuperare qualsiasi DAG vero, dove $K$ è il numero di vertici non foglia. Ciò è ottenuto combinando una singola query meta-hub (per identificare i target) con $K$ query figli-nodo.
4. Elicitazione Mirata: A differenza dei metodi di apprendimento attivo che potrebbero richiedere ordini topologici completi o interventi ampi, questo protocollo isola solo gli archi non identificabili e richiede le specifiche informazioni necessarie per risolverli.

Risultati Sperimentali
Il protocollo è stato valutato su quattro benchmark standard (Asia, Sachs, Child, Alarm) e su dati sintetici progettati per stressare specifici livelli.

• Prestazioni con Oracolo Ideale: Assumendo un oracolo perfetto, il protocollo ha recuperato il DAG vero con Precisione = Recall = F1 = 1.000 su tutti e quattro i benchmark utilizzando esattamente $1+K$ interazioni.
  • Alarm (V=37): 46 archi recuperati in 27 interazioni.
  • Sachs (V=11): 17 archi recuperati in 8 interazioni.
• Efficacia della Cascata: Sul dataset Sachs, la cascata da sola ha risolto 5 dei 19 archi veri partendo solo dai dati. L'aggiunta dei nuovi livelli sicuri ha migliorato la precisione della direzione dal 61,5% (base L0-L2) al 66,7% quando la guardia di disaccordo era attiva.
• Specificità dei Livelli: I test di stress sintetici hanno confermato che ogni nuovo livello è positivo in termini di precisione nel suo regime nativo (ad es. LLSNM sul rumore scala-posizione, LIGCI sui dati quasi deterministici) e si astiene (attiva 0/40) sui dati fuori regime, prevenendo falsi positivi.
• Frontiera di Pareto: Su Sachs, il protocollo ha dimostrato un compromesso tra numero di query e punteggio F1. Un approccio "SOLO-SAFE" (cascata senza oracolo) ha raggiunto F1=0,571 con 5 query, mentre il protocollo completo ha raggiunto F1=1,000 con 13 query (utilizzando la cascata per ridurre il carico sull'oracolo).

Significato e Affermazioni
Il documento afferma di colmare un divario fondamentale nella scoperta causale: l'incapacità dei metodi attuali di distinguere tra direzioni identificate dai dati e quelle imposte algoritmicamente. Associando un "certificato" a ogni arco, il protocollo fornisce una traccia di audit trasparente.

• Contributo Teorico: Il limite $1+K$ rappresenta il corrispettivo sul lato dell'elicitazione dei limiti sul budget di intervento nella scoperta causale attiva, quantificando l'informazione minima richiesta per risolvere un DAG quando è disponibile la conoscenza esperta.
• Utilità Pratica: Il protocollo permette ai praticanti di concentrare lo sforzo esperto esclusivamente sugli archi non identificabili, riducendo il carico cognitivo presentando domande specifiche e consapevoli del regime invece di direzioni di archi grezze.
• Limitazioni: Gli autori notano esplicitamente che l'ambito attuale è limitato alle variabili continue; le reti bayesiane discrete sono trattate solo come controllo di robustezza per il livello dell'oracolo. Il protocollo assume un oracolo perfetto; la gestione di risposte esperte rumorose o probabilistiche è identificata come lavoro futuro. Inoltre, la fase di costruzione dello scheletro impone un limite di recall, poiché gli archi potati dal test HSIC iniziale non possono essere recuperati.

Il lavoro si posiziona non come sostituto dell'ottimizzazione continua scalabile o dei metodi basati su vincoli, ma come un approccio ortogonale che dà priorità all'auditabilità per arco e minimizza il costo dell'elicitazione esperta attraverso query mirate e guidate da certificati.