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

Résumé technique : Découverte causale itérative avec certificats d'impossibilité par arête

Énoncé du problème
Les algorithmes actuels de découverte causale renvoient généralement un graphe acyclique dirigé (DAG) entièrement orienté, mais échouent à distinguer entre les directions d'arêtes identifiées par les données et celles imposées par l'algorithme pour satisfaire les contraintes de sortie. Dans des conditions standard de Markov et de fidélité, les données observationnelles n'identifient qu'une classe d'équivalence de Markov ; les orientations d'arêtes non situées sur des structures en V sont indéterminées par la distribution conjointe. Les méthodes existantes imposent soit des orientations sur des arêtes non identifiables (par exemple, NOTEARS, DAGMA) sans justification diagnostique, soit les laissent non orientées (par exemple, FCI) sans spécifier les informations a priori spécifiques requises pour les résoudre. De plus, il a été démontré que les méthodes d'optimisation continue exploitent des artefacts de données (par exemple, la varsortabilité) qui imitent une identification authentique. Il manque un protocole fondé sur des principes offrant une auditabilité par arête, séparant explicitement l'identifiabilité pilotée par les données de l'imposition algorithmique, et identifiant les questions d'expert spécifiques nécessaires pour résoudre les arêtes non identifiables.

Méthodologie
L'article propose un protocole déterministe en trois étapes pour la découverte causale sur données continues à partir d'observations. Le protocole émet un « certificat d'impossibilité » discret pour chaque arête candidate dans un squelette basé uniquement sur les données, catégorisant l'arête soit comme résolue (identifiée par les données ou médiatisée), soit comme impossible (données insuffisantes, nécessitant une intervention d'expert).

1. Étape 1 : Recherche de squelette et de médiateurs :

   • Construction d'un squelette à l'aide de tests HSIC contrôlés par le FDR pour éliminer les paires marginalement indépendantes.
   • Réalisation d'une recherche de médiateurs multi-niveaux pour identifier et supprimer les arêtes médiatisées par des variables observées.

2. Étape 2 : Cascade d'identifiabilité à portes :

   • Une cascade à huit niveaux évalue les arêtes restantes. Les niveaux incluent des méthodes classiques (ANM linéaire $L_0$, ANM non linéaire $L_1$, HOC LiNGAM $L_2$) et cinq nouveaux niveaux introduits dans ce travail : LSNM (Bruit à échelle et localisation), IGCI (Géométrie de l'information), Stein (Appariement de scores), MDL (Condition de Markov algorithmique) et PEIT (Test d'inversion d'entropie).
   • Mécanisme de porte : Chaque niveau est conditionné par des tests statistiques (par exemple, Shapiro–Wilk pour la non-gaussianité, tests d'hétéroscédasticité). Si la condition préalable d'un niveau échoue, il s'abstient plutôt que de forcer une orientation.
   • Consensus inter-niveaux : Une « garde de désaccord » dégrade les engagements $L_0$ si des niveaux de plus haute précision (IGCI, Stein, MDL) contredisent la direction, renommant l'arête en impossible_l0_disagrees_with_high_tier.
   • Les arêtes non résolues par aucun niveau reçoivent une étiquette impossible_*, qui encode le mode d'échec spécifique (par exemple, confusion latente, non-linéarité faible) et la question correspondante pour un expert du domaine.

3. Étape 3 : Requêtes ciblées à l'oracle :

   • Le protocole interagit avec un expert du domaine uniquement sur les arêtes étiquetées impossible_*.
   • Primitives de requête :
     • Requête par arête : Demande la direction (AVANT/ARRIÈRE) ou l'absence.
     • Requête de meta-hub : Demande les $K$ premiers nœuds par degré de sortie.
     • Requête nœud-enfants : Demande les enfants directs d'un nœud spécifique, engageant simultanément toutes les arêtes sortantes.
   • Auto-propagation : Après chaque engagement de l'oracle, le système exécute des passes de résolution automatique à coût nul (vérifications d'acyclicité, règles de Meek, d-séparation transitive) pour résoudre des arêtes supplémentaires sans requêtes supplémentaires.

Contributions clés

1. Certificats par arête : Le protocole attribue un code discret à chaque arête. Les codes resolved_* citent le théorème spécifique (par exemple, $L_{Stein}$) justifiant la direction, tandis que les codes impossible_* enregistrent le mode d'échec et la question spécifique requise pour la résoudre.
2. Abstention consciente des niveaux : L'introduction de cinq nouveaux niveaux à portes (LSNM, IGCI, Stein, MDL, PEIT) garantit que les directions ne sont engagées que lorsqu'un théorème d'identifiabilité spécifique est satisfait. Si une condition préalable échoue, le système s'abstient plutôt que de forcer une orientation potentiellement erronée.
3. Limite d'interaction 1+K : L'article établit une borne supérieure informationnelle de $1+K$ interactions d'expert pour récupérer n'importe quel DAG de vérité terrain, où $K$ est le nombre de sommets non feuilles. Cela est réalisé en combinant une seule requête de meta-hub (pour identifier les cibles) avec $K$ requêtes nœud-enfants.
4. Élicitation ciblée : Contrairement aux méthodes d'apprentissage actif qui peuvent demander des ordres topologiques complets ou des interventions larges, ce protocole isole uniquement les arêtes non identifiables et demande les informations spécifiques nécessaires pour les résoudre.

Résultats expérimentaux
Le protocole a été évalué sur quatre benchmarks standards (Asia, Sachs, Child, Alarm) et des données synthétiques conçues pour tester spécifiquement certains niveaux.

• Performance oracle idéale : Sous l'hypothèse d'un oracle parfait, le protocole a récupéré le DAG de vérité terrain avec Précision = Rappel = F1 = 1,000 sur les quatre benchmarks en utilisant exactement $1+K$ interactions.
  • Alarm (V=37) : 46 arêtes récupérées en 27 interactions.
  • Sachs (V=11) : 17 arêtes récupérées en 8 interactions.
• Efficacité de la cascade : Sur le jeu de données Sachs, la cascade seule a résolu 5 des 19 arêtes réelles à partir des données seules. L'ajout des nouveaux niveaux sûrs a amélioré la précision de la direction de 61,5 % (base L0-L2) à 66,7 % lorsque la garde de désaccord était active.
• Spécificité des niveaux : Les tests de stress synthétiques ont confirmé que chaque nouveau niveau est positif en précision sur son régime natif (par exemple, LLSNM sur le bruit à échelle et localisation, LIGCI sur des données quasi-déterministes) et s'abstient (déclenche 0/40) sur des données hors régime, empêchant les faux positifs.
• Frontière de Pareto : Sur Sachs, le protocole a démontré un compromis entre le nombre de requêtes et le score F1. Une approche « SAFE-only » (cascade sans oracle) a atteint F1=0,571 avec 5 requêtes, tandis que le protocole complet a atteint F1=1,000 avec 13 requêtes (en utilisant la cascade pour réduire la charge de l'oracle).

Signification et affirmations
L'article prétend combler un écart fondamental dans la découverte causale : l'incapacité des méthodes actuelles à distinguer entre les directions identifiées par les données et celles imposées algorithmiquement. En attachant un « certificat » à chaque arête, le protocole fournit une piste d'audit transparente.

• Contribution théorique : La borne $1+K$ représente le pendant du côté élicitation des limites de budget d'intervention dans la découverte causale active, quantifiant l'information minimale requise pour résoudre un DAG lorsque la connaissance experte est disponible.
• Utilité pratique : Le protocole permet aux praticiens de concentrer l'effort d'expert exclusivement sur les arêtes non identifiables, réduisant la charge cognitive en présentant des questions spécifiques et conscientes du régime plutôt que des directions d'arêtes brutes.
• Limites : Les auteurs notent explicitement que le champ actuel est restreint aux variables continues ; les réseaux bayésiens discrets ne sont traités que comme un test de robustesse pour la couche oracle. Le protocole suppose un oracle parfait ; la gestion de réponses d'experts bruitées ou probabilistes est identifiée comme un travail futur. De plus, la phase de construction du squelette impose une limite de rappel, car les arêtes élaguées par le test HSIC initial ne peuvent pas être récupérées.

Le travail se positionne non pas comme un remplacement des méthodes d'optimisation continue évolutives ou basées sur des contraintes, mais comme une approche orthogonale qui privilégie l'auditabilité par arête et minimise le coût de l'élicitation d'expert grâce à des requêtes ciblées et pilotées par des certificats.