Technische Samenvatting: De Causale Beschrijvingskloof

Probleemstelling

Pearls causale hiërarchie stelt vast dat observationele, interventionele en contrafactualle queries kwalitatief verschillend zijn, waarbij de Causale Hiërarchie-stelling bewijst dat queries van een hoger niveau over het algemeen niet kunnen worden beantwoord op basis van informatie van een lager niveau. Echter, de bestaande literatuur behandelt deze niet-identificeerbaarheid als een binaire obstructie: óf een antwoord van een hoger niveau wordt bepaald door data van een lager niveau, óf dat is niet het geval.

Dit artikel stelt een kwantitatieve versie van deze vraag: Hoeveel extra bits informatie zijn er nodig om een causaal antwoord van een hoger niveau te specificeren zodra de antwoorden van een lager niveau bekend zijn? De auteurs formaliseren deze "causale beschrijvingskloof" om de resterende informatie te meten die nodig is om ambiguïteit op te lossen wanneer identificatie faalt.

Methodologie

De auteurs introduceren een raamwerk gebaseerd op Kolmogorov-complexiteit om de informatie-inhoud van causale antwoordorakels te kwantificeren.

1. Beschrijvingslengte van Query-klasse: Voor een Structureel Causaal Model (SCM) $M$ en een query-klasse $Q$ (bijvoorbeeld observationeel, interventie op één knoop, contrafactualle) wordt de beschrijvingslengte $DL(Q; M)$ gedefinieerd als de Kolmogorov-complexiteit van het antwoordorakel $Ans_Q(M)$, geconditioneerd op de systeemgrootte $n$.
2. Causale Beschrijvingskloof: De kloof $\Delta(Q_2 | Q_1; M)$ is de conditionele Kolmogorov-complexiteit van het antwoord van een hoger niveau gegeven het antwoord van een lager niveau:
   $$\Delta(Q_2 | Q_1; M) := K(Ans_{Q_2}(M) \mid Ans_{Q_1}(M), n)$$
3. Principe van Ambiguïteit-naar-Bits: Het artikel stelt een algemeen stelling op die beschrijvingskloven koppelt aan de grootte van de ambiguïteitsset. Als een antwoord van een lager niveau $a$ consistent is met $N$ verschillende antwoordorakels van een hoger niveau, dan is de beschrijvingskloof ten minste $\log_2 N$ (tot op termen van lagere orde). Dit geldt zowel in het worst-case scenario (Kolmogorov) als in het average-case scenario (Shannon-entropie).

De auteurs construeren specifieke families van binaire, acyclische SCMs om deze kloven te concretiseren, en tonen aan dat de kloven polynomiaal kunnen schalen met de systeemgrootte $n$.

Belangrijkste Bijdragen en Resultaten

1. Scheidingen tussen Observationeel en Interventieel

Het artikel construeert SCM-families waarbij de observationele verdeling een constante beschrijvingslengte heeft ($O(1)$), terwijl het interventionele antwoordorakel aanzienlijk meer bits vereist.

• Constructie met Gewortelde Boom ($\Theta(n \log n)$):

  • Opzet: Variabelen vormen een verborgen gewortelde boom waarbij de wortel willekeurig is en kinderen hun ouders kopiëren.
  • Resultaat: Alle bomen produceren dezelfde observationele verdeling (perfecte correlatie). Echter, interventies op één enkele knoop onthullen de afstammingsverzamelingen, waardoor de boomstructuur uniek wordt geïdentificeerd.
  • Kloof: De kloof is $\Theta(n \log n)$, wat overeenkomt met de informatie die nodig is om een gelabelde boom te coderen (via Prüfer-sequenties). Dit is orde-optimaal voor SCMs met een begrenste indegree ($d=O(1)$).

• Constructie met Bipartiete Grafiek ($\Theta(n^2)$):

  • Opzet: Een verborgen bipartiete grafiek $G$ tussen lagen $A$ en $B$. Laag $A$ kopieert de wortel; Laag $B$ berekent AND-poorten op basis van de randen in $G$.
  • Resultaat: Observationeel leveren alle grafieken dezelfde verdeling op (alleen 0'en of alleen 1'en). Interventies op knopen in laag $A$ onthullen hun buren in laag $B$, wat effectief de benvolgingsmatrix van $G$ decodeert.
  • Kloof: De kloof is $\Theta(n^2)$ (specifiek $\approx m^2$ waar $n=2m+1$). Dit is orde-optimaal voor dichte mechanismen waar indegree $d = \Theta(n)$.
  • Robuustheid: Deze kwadratische scheiding blijft bestaan zelfs onder $\epsilon$-accurate total-variation-beschrijvingen voor elke vaste $\epsilon < 1/4$.

• Optimaliteit Afhankelijk van Graad:
  De auteurs bewijzen een algemene bovengrens voor SCMs met eindige poort-schema's en indegree $d$:
  $$\Delta_{2|1} \le O\left( nd \log \frac{en}{d} + n \log n \right)$$
  Dit bevestigt dat de $\Theta(n \log n)$ boomconstructie optimaal is voor begrenste graad, en dat de $\Theta(n^2)$ bipartiete constructie optimaal is voor dichte graad.

2. Scheiding van Contrafactualle

Zelfs met volledige kennis van alle "hard-do" interventionele verdelingen (het volledige interventionele orakel), kunnen contrafactualle queries ambigu blijven.

• Constructie met Modulaire-XOR ($\Theta(n)$):
  • Opzet: $m$ onafhankelijke modules, waarbij elke module ofwel een "geen-effect" mechanisme is (onafhankelijke variabelen) of een "XOR" mechanisme ($Y = X \oplus U$).
  • Resultaat: Beide mechanismen produceren identieke observationele en interventionele verdelingen. Ze verschillen echter in contrafactualle: onder het geen-effect mechanisme blijft $Y$ ongewijzigd als er op $X$ wordt ingegrepen; onder XOR draait $Y$ om.
  • Kloof: De kloof tussen het volledige interventionele orakel en het contrafactualle orakel is $\Theta(n)$, wat overeenkomt met de verborgen string $s \in \{0,1\}^m$ die het type mechanisme bepaalt.

3. Gevolgen voor Lerende Theorie

Het artikel leidt een "no-free-lunch"-resultaat af voor observationeel leren. In de bipartiete familie, aangezien alle mechanismen dezelfde observationele verdeling delen, is de wederzijdse informatie tussen de verborgen grafiek en elke observationele dataset gelijk aan nul. Bijgevolg:

• Geen enkele observationele leraar kan het interventionele orakel identificeren met een waarschijnlijkheid die beter is dan raden ($2^{-m^2}$).
• Elke voorspeller die uitsluitend gebaseerd is op observationele data heeft een verwachte absolute fout van ten minste $1/4$ voor interventionele queries.

Betekenis en Claims

Het artikel claimt Pearls kwalitatieve hiërarchie te transformeren in een kwantitatieve informatiehiërarchie. De primaire betekenis ligt in:

1. Verfijning van Niet-Identificeerbaarheid: Het gaat voorbij aan de Booleaanse vraag "is het identificeerbaar?" naar een precieze maatstaf van "hoeveel informatie ontbreekt er?".
2. Orde-Optimale Grenzen: Het biedt expliciete constructies die aantonen dat de informatiekloof kwadratisch kan schalen met de systeemgrootte ($\Theta(n^2)$) voor dichte mechanismen en lineair ($\Theta(n)$) voor contrafactualle, zelfs wanneer observationele data perfect is.
3. Informatietheoretische Grenzen: Het toont aan dat deze kloven geen artefacten zijn van computationele moeilijkheid of eindige data; het zijn fundamentele informatie-theoretische barrières. Zelfs met oneindige observationele data blijft de resterende ambiguïteit bestaan, wat interventies noodzakelijk maakt om de kloof te dichten.
4. Algemeen Principe: De "Ambiguïteit-naar-Bits"-stelling verenigt deze resultaten en toont aan dat de beschrijvingskloof fundamenteel de logaritme is van de grootte van de resterende ambiguïteitsset.

De auteurs merken op dat hun constructies adversariaal zijn (binair, acyclisch, mogelijk in strijd met positiviteit of trouw) om aan te tonen dat observationele adequaatheid alleen geen kleine causale-beschrijvingsgrens oplegt zonder verdere structurele aannames. Zij suggereren dat toekomstig werk moet onderzoeken hoe sparsiteit, ruis of aannames van trouw deze resterende ambiguïteiten kunnen verkleinen.