ExDAG : Apprentissage exact des DAG

Un intérêt croissant pour l'apprentissage causal s'est manifesté ces dernières années. Les représentations couramment utilisées des structures causales, y compris les réseaux bayésiens et les modèles d'équations structurelles (SEM), prennent la forme de graphes acycliques orientés (DAG). Nous proposons une nouvelle formulation de programmation quadratique mixte entière et un algorithme associé qui identifie des DAGs contenant jusqu'à 50 sommets, là où ceux-ci sont identifiables. Nous appelons cette méthode ExDAG, qui signifie Apprentissage exact des DAG. Bien qu’il existe un nombre superexponentiel de contraintes qui empêchent la formation de cycles, l'algorithme ajoute des contraintes violées par les solutions trouvées, plutôt que d'imposer toutes les contraintes dans chaque relaxation à valeurs continues. Nos résultats empiriques montrent qu'ExDAG surpasse les solveurs locaux à la pointe de la technologie en termes de précision et surpasse les solveurs globaux à la pointe de la technologie en ce qui concerne l'échelle, en tenant compte du bruit gaussien. Nous fournissons également une validation par rapport à d'autres distributions de bruit.