BUILD with Precision: Bottom-Up Inference of Linear DAGs

Résumé technique : BUILD (Inférence ascendante de DAG linéaires)

Énoncé du problème
L'article aborde le problème fondamental de l'apprentissage de la structure des graphes acycliques dirigés (DAG) à partir de données observationnelles. Plus précisément, il se concentre sur le cadre des modèles d'équations structurelles (SEM) linéaires où les variables observées suivent une distribution gaussienne conjointe avec des variances de bruit connues et égales. Dans ce régime spécifique, le DAG sous-jacent est théoriquement identifiable à partir des seules données observationnelles. Le défi réside dans le développement de méthodes de calcul capables de retrouver la structure du DAG (matrice d'adjacence $A$) de manière efficace et robuste, en particulier lorsqu'il s'agit de tailles d'échantillons finis et du conditionnement potentiellement défavorable de la matrice de covariance des données.

Méthodologie
Les auteurs proposent BUILD (Inférence ascendante de DAG linéaires), un algorithme déterministe et itératif qui reconstruit le DAG en identifiant et en élaguant itérativement les nœuds feuilles. La méthodologie repose sur les propriétés structurelles de la matrice de précision de l'ensemble ($\Theta = \Sigma^{-1}$) des observations.

1. Fondement théorique :

   • Pour un SEM gaussien linéaire $x = Ax + z$ avec une variance de bruit égale $\sigma^2$, la matrice de précision est donnée par $\Theta = \sigma^{-2}(I - A - A^\top + A^\top A)$.
   • Identification des feuilles : Les auteurs établissent qu'un nœud $i$ est une feuille (n'a pas d'enfants) si et seulement si l'entrée diagonale correspondante de la matrice de précision satisfait $\Theta_{ii} = \sigma^{-2}$. Les nœuds non-feuilles satisfont strictement $\Theta_{jj} > \sigma^{-2}$.
   • Récupération des parents : Une fois un nœud feuille $i$ identifié, ses parents et les poids d'arête associés peuvent être récupérés directement à partir des entrées hors-diagonale de la $i$-ème ligne de $\Theta$. Plus précisément, $A_{ij} = -\sigma^2 \Theta_{ij}$ pour $j < i$ (en supposant un ordre topologique), et $A_{ij} = 0$ sinon.

2. Processus algorithmique :

   • Initialisation : L'algorithme commence par estimer la matrice de précision $\hat{\Theta}$ à partir de la matrice de données $X$. En raison du risque de mauvais conditionnement dans les SEM linéaires de grande dimension (où le bruit s'accumule le long des chaînes de dépendance), les auteurs utilisent GreedyPrune pour cette estimation initiale, car il fonctionne mieux que les méthodes standard comme le Graphical Lasso dans ces contextes.
   • Élagage itératif : L'algorithme maintient un ensemble de nœuds actifs. À chaque étape, il identifie le nœud ayant la plus petite entrée diagonale dans la matrice de précision courante (au-dessus d'une tolérance $\epsilon$) comme une feuille. Il récupère les arêtes reliant cette feuille à ses parents, les ajoute à la matrice d'adjacence, puis « élague » la feuille.
   • Mise à jour de la matrice : L'élagage est effectué en mettant à jour la matrice de précision des nœuds restants en utilisant une identité d'inversion de matrice par blocs (complément de Schur), éliminant ainsi efficacement l'influence de la feuille identifiée.

3. Stratégie de mitigation des erreurs :

   • Un défi critique dans la pratique est que les erreurs d'estimation dues à un échantillon fini dans $\hat{\Theta}$ peuvent s'accumuler à mesure que l'algorithme progresse, conduisant à un « effet boule de neige » de détections d'arêtes incorrectes.
   • Pour atténuer cela, BUILD intègre un système de rafraîchissement. À intervalles fixes (définis par un taux de rafraîchissement $\rho$), l'algorithme ré-estime la matrice de précision en utilisant uniquement les nœuds actuellement actifs (non élagués) et les données originales. Cela réinitialise les erreurs accumulées et recalibre le modèle, échangeant le temps d'exécution contre une robustesse accrue.

Contributions clés

• Approche ascendante déterministe : Contrairement aux méthodes d'optimisation continue (par exemple, NOTEARS, DAGMA) qui résolvent des problèmes non convexes ou aux méthodes basées sur l'ordre qui négligent les poids d'arête, BUILD offre une reconstruction déterministe et itérative du DAG et de ses poids d'arête.
• Caractérisation de la matrice de précision : L'article fournit une caractérisation spécifique des entrées de la matrice de précision pour les SEM gaussiens linéaires à variances égales, révélant une structure distincte permettant une identification exacte des feuilles et une récupération des parents.
• Robustesse par ré-estimation : L'introduction du mécanisme de ré-estimation périodique aborde le problème de la propagation des erreurs dans les problèmes mal conditionnés, offrant un compromis réglable entre coût computationnel et précision.
• Complexité : Dans le cadre idéalisé avec la vraie matrice de précision, l'algorithme s'exécute en $O(N^2)$.

Résultats
Les auteurs évaluent BUILD sur des benchmarks synthétiques impliquant des DAG d'Erdős–Rényi avec $N=200$ nœuds et $M=1\,000$ échantillons.

• Comparaison avec les méthodes d'optimisation : Les variantes de BUILD (avec différents taux de rafraîchissement) surpassent généralement les méthodes d'optimisation continue de l'état de l'art (CoLiDE, DAGMA) en termes de distance de Hamming structurelle (SHD) et de taux de vrais positifs (TPR). Par exemple, une variante avec un rafraîchissement fréquent (BUILD-0,005) atteint un SHD et un taux de fausses découvertes (FDR) nettement inférieurs à ceux de CoLiDE et DAGMA, bien qu'avec un temps d'exécution plus élevé.
• Comparaison avec les méthodes basées sur l'ordre : Comparé aux méthodes basées sur l'ordre (Gao et al., Daskalakis et al.), BUILD correspond à la précision de la méthode basée sur l'ordre la plus précise (Gao et al.) tout en maintenant une meilleure évolutivité. Contrairement à Daskalakis et al., qui peine avec des poids d'arête généraux, BUILD gère efficacement toute la gamme des poids.
• Estimation des poids d'arête : BUILD démontre des performances supérieures dans l'estimation des poids d'arête (mesurée par l'erreur quadratique moyenne normalisée) par rapport aux références, en particulier à mesure que la taille de l'échantillon augmente.
• Compromis : Les résultats mettent en évidence un compromis clair : des taux de rafraîchissement plus élevés entraînent des taux d'erreur plus faibles (meilleur SHD et FDR) mais augmentent le temps de calcul.

Signification et affirmations
L'article affirme que BUILD offre une alternative viable aux algorithmes existants d'apprentissage de DAG en exploitant les propriétés d'identifiabilité spécifiques des SEM gaussiens linéaires à variances de bruit égales. Sa signification réside dans :

1. Contrôle explicite de la complexité : Il fournit un contrôle explicite de la complexité via le paramètre de taux de rafraîchissement, permettant aux utilisateurs de équilibrer précision et temps d'exécution.
2. Gestion du mauvais conditionnement : En intégrant un estimateur robuste de la matrice de précision (GreedyPrune) et une stratégie de ré-estimation, il aborde l'instabilité numérique souvent rencontrée dans l'apprentissage de DAG avec de longues chaînes de dépendance.
3. Reproductibilité : Les auteurs soulignent le caractère déterministe de l'algorithme et la disponibilité de leur implémentation, les contrastant avec des méthodes qui peuvent faire face à des problèmes de convergence d'optimisation.

Les auteurs reconnaissent modestement les limites, notant que la performance de l'algorithme est sensible à la précision de l'estimation initiale de la matrice de précision et que le mécanisme de rafraîchissement, bien que robuste, introduit une inefficacité en jetant les entrées de matrice précédemment calculées. Ils suggèrent un travail futur sur l'ordonnancement adaptatif du rafraîchissement et l'extension de l'approche à des contextes non gaussiens ou non linéaires.