Learning Causal Structure of Time Series using Best Order Score Search

Cet article présente TS-BOSS, une méthode évolutive de découverte causale pour les séries temporelles multivariées qui étend l'algorithme BOSS aux réseaux bayésiens dynamiques en garantissant théoriquement sa validité et en démontrant une supériorité empirique, notamment dans les régimes à forte autocorrélation.

L'essentiel

🕵️‍♂️ Le Détective du Temps : Comment TS-BOSS déchiffre les causes cachées

Imaginez que vous regardez une vidéo de la météo d'une ville pendant un an. Vous voyez qu'il pleut souvent le matin, que les gens ouvrent leurs parapluies, et que les trottoirs sont mouillés. Mais la question est : qui fait quoi ? Est-ce que la pluie fait ouvrir les parapluies ? Ou est-ce que les parapluies ouverts font pleuvoir ? (Non, mais vous voyez l'idée !).

En science, on appelle cela l'apprentissage de la structure causale. Le but est de trouver la "recette" cachée qui explique comment les événements s'enchaînent dans le temps.

Le problème, c'est que le temps est un traître. Dans le monde réel, les choses ne sont pas indépendantes : ce qui se passe maintenant dépend de ce qui s'est passé il y a 5 minutes, 1 heure ou hier. C'est ce qu'on appelle la dépendance temporelle.

C'est là que cette équipe de chercheurs (Irene et Urmi) arrive avec une nouvelle méthode appelée TS-BOSS.

🧩 L'Analogie du Puzzle Géant

Pour comprendre leur méthode, imaginons que vous essayez de reconstruire un puzzle géant représentant une chaîne de causes et d'effets.

1. Les anciennes méthodes (les "Détectives de Contraintes") :
   Imaginez un détective qui vérifie chaque pièce du puzzle une par une en demandant : "Est-ce que cette pièce est liée à celle-ci ?". Il teste des milliers de combinaisons. C'est précis, mais c'est lent. Et si le puzzle a beaucoup de pièces qui bougent toutes ensemble (comme une forte autocorrélation, où tout est lié), le détective se perd et commence à faire des erreurs. C'est un peu comme essayer de deviner la recette d'un gâteau en goûtant chaque ingrédient séparément dans un brouillard épais.

2. La nouvelle méthode (TS-BOSS) :
   TS-BOSS est comme un chef cuisinier génial qui ne goûte pas chaque ingrédient séparément. Au lieu de ça, il essaie de trouver l'ordre parfait dans lequel les ingrédients doivent être ajoutés.

   • Il sait que vous ne pouvez pas mettre le glaçage avant le gâteau (le futur ne peut pas causer le passé).
   • Il essaie différentes séquences d'ajout d'ingrédients (c'est la "recherche par permutation").
   • Pour ne pas perdre de temps, il utilise une astuce de mémoire incroyable (les "arbres de croissance-réduction") pour se souvenir de ce qui a déjà été goûté, sans avoir à recommencer tout le travail.

⚡ Pourquoi TS-BOSS est spécial ?

Le papier montre deux choses principales :

1. La Vitesse et la Mémoire :
   Grâce à son astuce de mémoire (les arbres), TS-BOSS est beaucoup plus rapide que les méthodes classiques. Il ne perd pas de temps à recalculer les mêmes choses. C'est comme si le chef cuisinier avait une liste de courses intelligente qui lui dit exactement ce qu'il lui faut, sans qu'il ait à fouiller dans tous les placards.

2. Le Roi des "Brouillards" (Haute Autocorrélation) :
   C'est le point le plus important. Quand les données sont très liées entre elles (comme une tempête où tout bouge en même temps), les anciennes méthodes (comme PCMCI+) commencent à paniquer et à rater des liens importants. Elles disent "je ne vois rien" et oublient des connexions.
   TS-BOSS, lui, reste calme. Il continue de trouver les bons liens même dans le brouillard. Il est particulièrement doué pour retrouver les connexions manquantes (ce qu'on appelle le "rappel" ou recall) quand les choses sont très chaotiques.

🏗️ Comment ça marche techniquement (en version simplifiée) ?

• Le "Déroulement" (Unrolling) : Au lieu de regarder le temps comme un fleuve continu, TS-BOSS le découpe en tranches (comme des tranches de saucisson). Il prend une fenêtre de temps (par exemple, les 3 dernières heures) et regarde comment les variables interagissent dans cette fenêtre.
• L'Ordre Sacrée : Il respecte une règle stricte : le passé doit toujours être avant le futur. Il ne mélange jamais les cartes.
• La Recherche de l'Ordre Parfait : Il essaie de trouver l'ordre des variables qui donne le meilleur "score" (la meilleure explication des données). Une fois qu'il a trouvé le meilleur ordre, il dessine le graphique des causes.

🏆 Le Verdict

En résumé, TS-BOSS est comme un nouveau détective de police qui a remplacé son vieux carnet de notes par une tablette ultra-puissante.

• Il est plus rapide.
• Il est plus précis quand les données sont bruyantes et liées entre elles (ce qui est le cas le plus fréquent dans la vraie vie).
• Il permet de comprendre des systèmes complexes, comme l'économie, la météo ou le cerveau, beaucoup plus efficacement que les outils précédents.

Les chercheurs ont prouvé mathématiquement que leur méthode est solide (elle ne va pas vous raconter n'importe quoi) et l'ont testée sur des données simulées où elle a battu l'ancien champion (PCMCI+) dans les situations les plus difficiles.

En une phrase : TS-BOSS est un outil intelligent et rapide qui permet de démêler les causes et les effets dans des données temporelles complexes, là où les autres méthodes se perdent dans le chaos.

Résumé technique

Voici un résumé technique détaillé de l'article de prépublication "Learning Causal Structure of Time Series using Best Order Score Search" (TS-BOSS), rédigé en français.

1. Problématique et Contexte

L'apprentissage de la structure causale à partir de données observationnelles est fondamental dans de nombreux domaines scientifiques (économie, épidémiologie, neurosciences). Cependant, l'application de ces méthodes aux séries temporelles multivariées pose des défis spécifiques :

• Dépendance temporelle : La violation de l'hypothèse d'indépendance et d'identité de distribution (i.i.d.) limite les garanties théoriques des méthodes classiques.
• Limitations des approches existantes :
  • Les méthodes basées sur les contraintes (comme PCMCI+) reposent sur des tests d'indépendance conditionnelle (CI). Ces tests deviennent souvent mal calibrés en présence de fortes dépendances temporelles (autocorrélation élevée).
  • Les méthodes basées sur le score (comme GES) peinent à être mises à l'échelle (scalabilité) ou à s'adapter efficacement aux structures dynamiques sans perdre en précision.

L'objectif de cet article est de proposer une méthode basée sur le score capable de découvrir la structure causale de séries temporelles, en surmontant les problèmes de scalabilité et de performance dans les régimes à forte autocorrélation.

2. Méthodologie : TS-BOSS

Les auteurs proposent TS-BOSS (Time Series - Best Order Score Search), une extension temporelle de l'algorithme BOSS (Andrews et al., 2023). La méthode repose sur une recherche de permutation optimisée couplée à des structures de données efficaces.

A. Fondements Théoriques

• Modèle : Les données sont modélisées par un SCM de série temporelle (ts-SCM) menant à un graphe acyclique dirigé de série temporelle (ts-DAG).
• Hypothèses clés :
  • Propriété de Markov locale et de fidélité pour les séries temporelles.
  • Stationnarité : Les mécanismes causaux restent constants dans le temps.
  • Lag maximal connu ($\tau_{max}$) : La causalité ne s'étend pas au-delà d'un certain retard temporel.
• Représentation : Au lieu de travailler directement sur l'infini des ts-DAG, la méthode se concentre sur la découverte d'un graphe causal de fenêtre (Window Causal Graph, $G_W$) sur une fenêtre de temps $[t-\tau_{max}, t]$. Grâce à la stationnarité, la connaissance de ce graphe permet de reconstruire le graphe complet.

B. Algorithme TS-BOSS

L'algorithme fonctionne en deux phases, adaptées du cadre statique BOSS :

1. Phase 1 : Recherche de permutation et Grow-Shrink

   • Déroulement temporel (Unrolling) : Les données sont transformées en un ensemble de variables distinctes incluant les retards ($X_{t-\tau_{max}}, \dots, X_t$).
   • Contrainte d'ordre temporel : La recherche de permutation est contrainte. Les variables retardées doivent toujours précéder les variables contemporaines dans l'ordre de permutation ($\pi$). Seules les variables contemporaines sont permutées librement.
   • Arbres Grow-Shrink (GST) : Pour chaque permutation candidate, l'algorithme construit efficacement le graphe minimal correspondant en utilisant des arbres GST pour mettre en cache les calculs de score intermédiaires. Cela évite de recalculer le score complet à chaque modification locale.
   • Optimisation : L'algorithme recherche itérativement la permutation qui maximise le score (BIC - Bayesian Information Criterion).

2. Phase 2 : Recherche d'équivalence arrière (TS-BES)

   • Une fois le graphe optimal trouvé, une phase de suppression d'arêtes (Backward Equivalence Search) est appliquée pour garantir que le graphe résultant est le plus parcimonieux possible (subgraph minimal) tout en respectant les données, assurant ainsi la convergence vers la classe d'équivalence markovienne (MEC).

3. Contributions Clés

1. TS-BOSS : Introduction d'un algorithme scalable pour la découverte causale en séries temporelles, combinant la recherche de permutations et les arbres Grow-Shrink.
2. Garanties Théoriques :
   • Preuve de la correction asymptotique de TS-BOSS sous des hypothèses de stationnarité et d'accès à des données i.i.d. (fenêtres).
   • Extension du théorème de minimalité des sous-graphes (Verma & Pearl, 1990) au cadre dynamique (Théorème 5), établissant que les méthodes basées sur la permutation la plus parcimonieuse sont valides pour les réseaux bayésiens dynamiques.
3. Performance Empirique : Démonstration que l'approche par score surpasse les méthodes basées sur les contraintes (PCMCI+) dans des régimes spécifiques, notamment ceux caractérisés par une forte autocorrélation.

4. Résultats Expérimentaux

Les auteurs ont évalué TS-BOSS sur des données synthétiques générées à partir de modèles linéaires et l'ont comparé à PCMCI+ (méthode de référence basée sur les contraintes) et à une version i.i.d. de TS-BOSS.

• Régime à forte autocorrélation : C'est le résultat le plus significatif. TS-BOSS maintient un rappel (recall) d'adjacence élevé et stable lorsque l'autocorrélation augmente, tandis que le rappel de PCMCI+ chute drastiquement. Cela suggère que les tests d'indépendance conditionnelle de PCMCI+ échouent face à la dépendance temporelle forte, alors que l'approche par score de TS-BOSS reste robuste.
• Précision et Rappel : TS-BOSS offre généralement un meilleur rappel (détection de plus de vraies arêtes) à une précision comparable à celle de PCMCI+.
• Scalabilité :
  • TS-BOSS est nettement plus rapide que PCMCI+, surtout lorsque le nombre de variables ($N$) ou la densité du graphe augmente.
  • Le temps d'exécution de PCMCI+ croît de manière exponentielle avec la taille du graphe (due au nombre croissant de tests CI), tandis que TS-BOSS, grâce aux arbres GST, gère mieux cette complexité.
• Taille de l'échantillon : La performance de TS-BOSS s'améliore avec la taille de l'échantillon, confirmant sa consistance.

5. Signification et Perspectives

• Pont Théorique : L'article fournit un pont principiel pour étendre la théorie de l'apprentissage causal basée sur la parcimonie et les permutations (développée pour les données i.i.d.) aux environnements dynamiques.
• Alternative aux tests CI : Il démontre que dans les séries temporelles complexes (fortes dépendances), les méthodes basées sur le score peuvent être plus robustes que les méthodes basées sur les contraintes, contournant ainsi les problèmes de calibration des tests d'indépendance conditionnelle.
• Scalabilité : La méthode ouvre la voie à l'analyse de systèmes temporels de grande dimension (grand nombre de variables) là où les méthodes actuelles deviennent prohibitives en temps de calcul.

En conclusion, TS-BOSS représente une avancée majeure pour la découverte causale en séries temporelles, offrant un compromis optimal entre précision théorique, robustesse aux dépendances temporelles et efficacité computationnelle.