Learning Causal Structure of Time Series using Best Order Score Search

Dit paper introduceert TS-BOSS, een schaalbaar en theoretisch onderbouwd algoritme voor het leren van causale structuren in multivariate tijdreeksen dat, door een permutatiegebaseerde zoektocht te combineren met grow-shrink trees, superieure prestaties boekt in regimes met hoge auto-correlatie vergeleken met bestaande methoden.

De kern

Stel je voor dat je een enorme, complexe machine probeert te begrijpen door alleen naar de bewegingen van de onderdelen te kijken. Je ziet dat als het ene wiel draait, het andere een seconde later ook gaat draaien. Maar wat is de oorzaak? Draait het eerste wiel omdat het tweede dat doet, of draait het tweede omdat het eerste dat doet? Of bewegen ze allebei door een verborgen motor die je niet ziet?

In de wetenschap noemen we dit causale structuur leren. Het is het vinden van de "waarom"-verbanden in data.

Deze paper introduceert een nieuwe manier om dit te doen voor tijdreeksen (data die zich over tijd ontwikkelt, zoals weerdata, beurskoersen of hartslagmetingen). De auteurs noemen hun nieuwe methode TS-BOSS.

Hier is een uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Tijdsdilemma"

Stel je voor dat je een film bekijkt, maar je kunt alleen naar één frame per seconde kijken. Als je ziet dat een bal op de grond ligt en daarna een gat in de muur, weet je dat de bal waarschijnlijk de muur heeft geraakt. Maar in complexe systemen (zoals de economie of het weer) is het veel lastiger.

• Het oude probleem: Veel bestaande methoden gaan ervan uit dat elke meting onafhankelijk is van de vorige (alsof je een dobbelsteen gooit). Maar in de echte wereld hangt het weer van vandaag wel degelijk af van het weer van gisteren. Deze "afhankelijkheid" maakt het moeilijk om de juiste oorzaak te vinden.
• De uitdaging: Hoe vind je de juiste volgorde van oorzaak en gevolg als alles door elkaar loopt en afhankelijk is van het verleden?

2. De Oplossing: TS-BOSS (De Slimme Regisseur)

De auteurs hebben een nieuwe methode bedacht, gebaseerd op een bestaande techniek genaamd BOSS (Best Order Score Search).

Stel je voor dat je een regisseur bent die een film moet draaien met 10 acteurs. Je weet niet wie wie aanstuurt. Je moet een volgorde bedenken (een "permutatie") waarin de acteurs hun rollen spelen.

• De oude manier (Constraint-based): Kijkt naar elke mogelijke relatie apart. "Is A afhankelijk van B?" "Is B afhankelijk van C?" Dit is als proberen een puzzel op te lossen door elke stukje één voor één te testen. Het werkt, maar het is traag en kan vastlopen als de puzzel heel groot is.
• De nieuwe manier (TS-BOSS): Kijkt naar de hele volgorde van acteurs. De regisseur probeert verschillende scenario's: "Wat als A eerst komt, dan B, dan C?"
  • Ze gebruiken een slimme truc genaamd "Grow-Shrink Trees" (Groei- en Krimp-bomen). Stel je voor dat je een boomplantje hebt. Je probeert takken toe te voegen (groei) om te zien of de boom mooier wordt. Als een tak niet helpt, knip je hem er direct weer af (krimp). Je slaat de resultaten van deze proefjes op, zodat je niet elke keer opnieuw hoeft te rekenen. Dit maakt het proces razendsnel.

3. De Nieuwe Twist: De Tijden

De echte uitvinding in deze paper is dat ze deze techniek hebben aangepast voor tijd.
In een normale film mag een acteur later in de film verschijnen dan een andere. Maar in een tijdreeks is tijd heilig: Oud moet altijd voor Nieuw komen.

• TS-BOSS zorgt ervoor dat in hun "regisseursscenario's", de variabelen uit het verleden (gisteren, eergisteren) altijd voor de variabelen van vandaag worden geplaatst.
• Ze kijken naar een "raam" (window) in de tijd. Stel je kijkt naar de afgelopen 3 dagen. Ze proberen de beste volgorde te vinden voor wie wat beïnvloedt binnen die 3 dagen, en bouwen daarop voort.

4. Waarom is dit geweldig? (De Resultaten)

De auteurs hebben hun methode getest tegen de huidige "standaard" (een methode genaamd PCMCI+).

• Het scenario: Stel je hebt een systeem waar alles heel sterk met elkaar verbonden is (hoge "autocorrelatie"). Alsof je in een drukke stad loopt waar iedereen elkaar aanraakt en beïnvloedt.
• Het resultaat: De oude methoden (PCMCI+) raken hier de draad kwijt. Ze zien te veel valse verbanden of missen echte verbanden.
• TS-BOSS: Deze methode blijft kalm en vindt de juiste verbanden, zelfs in die chaotische, sterk verbonden systemen. Ze vinden meer van de echte connecties (hoge "recall") zonder dat ze te veel fouten maken.

Samenvattend in één zin:

TS-BOSS is als een slimme detective die, in plaats van elke verdachte één voor één te ondervragen, een complete scenario schrijft waarin de volgorde van gebeurtenissen logisch is, en die scenario's snel test en verbetert om de waarheid te vinden, zelfs als de getuigen (de data) erg met elkaar verweven zijn.

Waarom is dit belangrijk?
Of je nu de oorzaak wilt vinden van een ziekte-uitbraak, een crash op de beurs, of veranderingen in het klimaat: deze methode helpt ons om sneller en nauwkeuriger te begrijpen wat er echt gebeurt, zonder in de war te raken door de complexiteit van de tijd.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Learning Causal Structure of Time Series using Best Order Score Search" in het Nederlands.

Titel: Learning Causal Structure of Time Series using Best Order Score Search (TS-BOSS)

Auteurs: Irene Gema Castillo Mansilla en Urmi Ninad (Universiteit van Potsdam)

---

1. Het Probleem

Het leren van causale structuren uit observationele data is essentieel in vele domeinen, van economie tot neurowetenschappen. Hoewel er veel methoden bestaan voor statische data, vormt de tijdreekscontext (time series) een specifieke uitdaging.

• Temporele afhankelijkheid: Observaties op een tijdstip $t$ zijn afhankelijk van eerdere waarden, wat de standaard i.i.d. (independent and identically distributed) aanname schendt. Dit beperkt de theoretische garanties van bestaande causale discovery-methoden.
• Huidige benaderingen: Bestaande methoden voor tijdreeksen zijn vaak constraint-based (gebaseerd op conditionele onafhankelijkheidstests, zoals PCMCI+). Deze methoden kunnen echter gevoelig zijn voor slecht gekalibreerde tests bij sterke autocorrelatie.
• Score-based methoden: Hoewel score-based methoden (die een DAG optimaliseren op basis van een score zoals BIC) succesvol zijn voor statische data, zijn er weinig schaalbare en theoretisch onderbouwde oplossingen voor multivariate tijdreeksen.

Het doel van dit paper is om een schaalbare, score-based methode te ontwikkelen die specifiek is ontworpen voor multivariate tijdreeksen en die de prestaties van bestaande methoden overtreft, vooral in regimes met hoge autocorrelatie.

---

2. Methodologie: TS-BOSS

De auteurs stellen TS-BOSS (Time Series - Best Order Score Search) voor, een extensie van de recente BOSS-algoritme (Andrews et al., 2023) voor statische data.

Kernconcepten:

1. Permutatie-gebaseerde zoektocht: In plaats van te zoeken in de ruimte van alle mogelijke DAG's, zoekt TS-BOSS naar de optimale volgorde (permutatie) van variabelen. Voor elke permutatie kan een unieke, subgraaf-minimale DAG worden geconstrueerd.
2. Grow-Shrink Trees (GST): Om de berekening van scores efficiënt te houden, gebruikt het algoritme een datastructuur genaamd "grow-shrink trees" om tussentijdse berekeningen te cacheën. Dit zorgt voor schaalbaarheid.
3. Tijdreeks-aanpassingen:
   • Time-window unrolling: De tijdreeks wordt "uitgerold" tot een venster van variabelen $\{X_{t-\tau_{max}}, \dots, X_t\}$, waarbij $\tau_{max}$ de maximale tijdsvertraging is.
   • Temporele orde-beperking: In de permutatie moeten vertraagde variabelen (lagged variables) altijd vóór de gelijktijdige variabelen (contemporaneous variables) komen. De zoekruimte beperkt zich tot het permuteren van de gelijktijdige variabelen, terwijl de vertraagde variabelen als potentiële ouders worden beschouwd.
   • Stationariteit: Het algoritme veronderstelt dat de causale structuur stationair is (verandert niet in de tijd), waardoor het voldoende is om de "window causal graph" te leren om de volledige tijdreeksstructuur te reconstrueren.

Het Algoritme (TS-BOSS):

• Fase 1 (Permutatie Search): Het algoritme voert een zoektocht uit over permutaties van de gelijktijdige variabelen. Het gebruikt een "grow-shrink" procedure om de beste ouder-set voor elke variabele te vinden binnen de beperkte permutatie.
• Fase 2 (TS-BES - Backward Equivalence Search): Na het vinden van de beste permutatie, wordt een backward search uitgevoerd om randen te verwijderen die de score niet verbeteren. Dit garandeert asymptotische correctheid en vindt de Markov-equivalentieklasse (MEC).

---

3. Belangrijkste Bijdragen

1. TS-BOSS Algoritme: De introductie van een schaalbare, score-based methode voor causale discovery in multivariate tijdreeksen, die de efficiëntie van BOSS combineert met tijdreeks-specifieke beperkingen.
2. Theoretische Garanties:
   • De auteurs bewijzen de soundness (geldigheid) van TS-BOSS onder geschikte aannames (zoals lokale Markov-eigenschap en trouwheid).
   • Ze leveren een nieuw theoretisch resultaat (Theorem 5) dat de minimaliteit van subgrafen voor permutatie-gebaseerde methoden uitbreidt naar de dynamische (tijdreeks) setting. Dit toont aan dat de "sparsest permutation" aanpak ook werkt voor tijdreeksen onder stationariteitsaannames.
3. Empirische Prestaties: Uitgebreide experimenten tonen aan dat TS-BOSS superieur presteert aan de state-of-the-art constraint-based methode PCMCI+, vooral in scenario's met hoge autocorrelatie.
4. Schalbaarheid: Door het gebruik van grow-shrink trees en beperkte permutatiezoekruimtes, blijft het algoritme schaalbaar naar een groot aantal variabelen, terwijl constraint-based methoden vaak trager worden door het aantal benodigde conditionele onafhankelijkheidstests.

---

4. Resultaten

De auteurs hebben synthetische data gegenereerd op basis van lineaire structurele causale modellen (SCM) en TS-BOSS vergeleken met:

• TS-BOSS (i.i.d.): Een variant waarbij onafhankelijke steekproeven worden genomen (om het effect van tijdsafhankelijkheid te isoleren).
• PCMCI+: Een gevestigde constraint-based methode voor tijdreeksen.

Kernbevindingen:

• Hoge Autocorrelatie: In regimes met sterke autocorrelatie (waarbij $a \approx 0.3$ of hoger) presteert PCMCI+ slechter in termen van recall (het vinden van echte relaties), terwijl TS-BOSS stabiel blijft en een hogere recall behaalt. PCMCI+ lijdt onder de schending van de i.i.d.-aannames bij conditionele tests.
• Precisie vs. Recall: PCMCI+ behaalt vaak een iets hogere precisie (minder valse positieven), maar TS-BOSS behaalt een aanzienlijk hogere recall bij vergelijkbare precisie. Dit betekent dat TS-BOSS meer van de ware causale relaties vindt zonder veel ruis toe te voegen.
• Schaalbaarheid: TS-BOSS is aanzienlijk sneller dan PCMCI+, vooral naarmate het aantal variabelen ($N$) en de dichtheid van het graf toenemen. De runtime van PCMCI+ explodeert door het aantal noodzakelijke tests, terwijl TS-BOSS lineairer schaalbaar blijft dankzij de permutatie-structuur.
• Grootte van Steekproef: Met toenemende steekproefgrootte ($T$) verbetert de prestatie van alle methoden, maar TS-BOSS behoudt zijn voordeel in recall.

---

5. Betekenis en Conclusie

Dit paper is significant omdat het een principiële brug slaat tussen de theorie van permutatie-gebaseerde causale learning (die sterk is voor statische data) en dynamische settings.

• Paradigmaverschuiving: Het toont aan dat score-based methoden, die vaak als minder robuust worden gezien bij complexe afhankelijkheden, juist zeer effectief kunnen zijn in tijdreeksen, mits ze correct worden aangepast voor temporele orde en stationariteit.
• Oplossing voor Autocorrelatie: Het biedt een oplossing voor het probleem dat constraint-based methoden (zoals PCMCI+) worstelen met hoge autocorrelatie, omdat deze methoden afhankelijk zijn van goed gekalibreerde conditionele onafhankelijkheidstests die in deze setting vaak falen.
• Toekomstperspectief: De auteurs benadrukken dat hoewel constraint-based methoden voordelen hebben bij het omgaan met fouten in de "orientation faithfulness", score-based methoden zoals TS-BOSS beter paralleliseerbaar zijn en beter schalen voor grote systemen.

Samenvattend introduceert TS-BOSS een hoogpresterende, schaalbare en theoretisch onderbouwde methode voor het leren van causale structuren in tijdreeksen, die een sterke concurrent is voor en in veel gevallen een superieur alternatief biedt voor bestaande constraint-based benaderingen.