I-CAM-UV: Integrating Causal Graphs over Non-Identical Variable Sets Using Causal Additive Models with Unobserved Variables

Die Arbeit stellt I-CAM-UV vor, eine Methode zur Integration von Kausalgraphen aus mehreren Datensätzen mit nicht identischen Variablenmengen unter Verwendung von Causal Additive Models mit unbeobachteten Variablen, um durch eine effiziente kombinatorische Suche konsistente Kausalstrukturen zu identifizieren, die von herkömmlichen Ansätzen aufgrund versteckter Confounder übersehen werden.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, das Geheimnis eines komplexen Maschinenwerks zu lüften – sagen wir, wie die verschiedenen Teile eines Autos zusammenarbeiten, um es zu bewegen. Sie wollen herausfinden: Was verursacht was? Dreht sich das Rad, weil der Motor läuft, oder dreht sich der Motor, weil das Rad rollt?

Das ist genau das, was Wissenschaftler bei der kausalen Entdeckung tun: Sie versuchen aus Beobachtungsdaten zu erraten, wer der „Verursacher" und wer die „Folge" ist.

Hier ist das Problem: Oft haben wir nicht eine perfekte Liste aller Teile.

• In Datensatz A sehen wir nur den Motor und das Lenkrad.
• In Datensatz B sehen wir nur das Lenkrad und die Räder.
• In Datensatz C sehen wir nur den Motor und die Bremsen.

Zusätzlich gibt es unsichtbare Teile (wie eine geheime Steuerungssoftware), die wir in keinem Datensatz sehen können, aber die trotzdem alles beeinflussen.

Das alte Problem: Das Puzzle, das nicht passt

Früher haben Forscher versucht, diese Puzzles einfach übereinanderzulegen.

• Sie nahmen das Bild von Datensatz A, legten das von B darauf und hofften, dass die Kanten (die Verbindungen) passen.
• Das Problem: Wenn ein unsichtbares Teil (ein „Geister-Verursacher") beide Teile beeinflusst, denken die alten Methoden fälschlicherweise, dass die beiden Teile direkt miteinander verbunden sind. Oder sie lassen wichtige Verbindungen weg, weil sie in keinem einzelnen Datensatz gleichzeitig zu sehen waren.

Es ist, als würde man versuchen, ein riesiges Puzzle zu lösen, indem man nur die Ecken betrachtet, die man zufällig in verschiedenen Schachteln gefunden hat, und die Mitte ignoriert.

Die neue Lösung: I-CAM-UV (Der „Detektiv mit Röntgenblick")

Die Autoren dieses Papers haben eine neue Methode namens I-CAM-UV entwickelt. Hier ist, wie sie funktioniert, mit ein paar einfachen Analogien:

1. Der Röntgenblick für Unsichtbares (CAM-UV)

Stellen Sie sich vor, jeder einzelne Datensatz wird von einem Spezialisten analysiert, der nicht nur sieht, was da ist, sondern auch spürt, was fehlt.

• Wenn zwei Teile (z. B. Motor und Lenkrad) in Datensatz A zusammenhängen, aber keine direkte Verbindung haben, sagt der Spezialist: „Aha! Da muss ein unsichtbares Teil dazwischen sein, das beide steuert!"
• Er markiert diese unsichtbaren Verbindungen nicht als Fehler, sondern als Hinweise. Er sagt: „Hier gibt es eine unsichtbare Kette" oder „Hier gibt es eine unsichtbare Rückkopplung".

2. Das große Zusammensetzen (I-CAM-UV)

Jetzt kommt der eigentliche Trick. Anstatt die Puzzles einfach zu stapeln, nimmt I-CAM-UV alle diese Hinweise von allen Datensätzen und versucht, alle möglichen Welten zu konstruieren, die mit diesen Hinweisen vereinbar sind.

• Die Analogie des Detektivs: Stellen Sie sich vor, Sie haben drei Zeugen (die Datensätze). Zeuge 1 sagt: „Der Täter war am Tatort." Zeuge 2 sagt: „Der Täter hatte einen blauen Mantel." Zeuge 3 sagt: „Der Täter war links vom Haus."
• Ein alter Detektiv würde sagen: „Okay, der Täter war links am Haus mit blauem Mantel." (Das ist die einfache Überlappung).
• Der I-CAM-UV-Detektiv sagt: „Moment mal. Vielleicht war der Täter gar nicht links, aber Zeuge 3 hat ihn von rechts gesehen, und der blaue Mantel war eigentlich ein Schal. Ich werde alle Szenarien durchspielen, die mit den Aussagen der Zeugen vereinbar sind."

Das Ergebnis ist keine einzelne Antwort, sondern eine Liste von möglichen Welten (eine Liste von Graphen).

3. Der effiziente Suchalgorithmus (Der „Best-First"-Sucher)

Da es theoretisch Milliarden von Möglichkeiten geben könnte, wie diese Teile zusammenhängen, wäre eine Suche nach dem perfekten Bild zu langsam.

• I-CAM-UV nutzt einen cleveren Trick: Es sucht nicht zufällig. Es beginnt mit der „einfachsten" Version (wo alle Unsicherheiten noch offen sind) und arbeitet sich dann schrittweise zu komplexeren Versionen vor.
• Es nutzt eine Art Rangliste. Es prüft zuerst die Szenarien, die am wenigsten Widersprüche zu den Zeugenberichten haben. Wenn es ein Szenario findet, das perfekt passt, stoppt es die Suche nach noch besseren (da es keine besseren gibt) und gibt alle Szenarien aus, die fast perfekt sind.

Warum ist das wichtig?

1. Es fängt das Unfassbare ein: Es kann Zusammenhänge finden, die in keinem einzelnen Datensatz zu sehen waren, weil sie durch unsichtbare Teile verdeckt wurden.
2. Es ist ehrlich: Statt eine falsche Gewissheit vorzutäuschen, gibt es eine Liste von Möglichkeiten aus. Das ist wie ein Wetterbericht, der sagt: „Es könnte regnen, es könnte schneien, oder die Sonne könnte scheinen" – basierend auf allen verfügbaren Daten – anstatt einfach nur „Sonne" zu sagen, wenn man sich nicht sicher ist.
3. Es funktioniert auch bei kleinen Datenmengen: Oft haben wir nicht genug Daten, um alles auf einmal zu sehen. I-CAM-UV nutzt die kleinen Stücke aus verschiedenen Quellen, um das große Bild zu vervollständigen.

Fazit in einem Satz

I-CAM-UV ist wie ein super-intelligenter Puzzle-Löser, der nicht nur die sichtbaren Teile zusammenfügt, sondern auch die unsichtbaren Lücken im Bild erkennt und uns eine Liste aller möglichen, logisch korrekten Bilder gibt, die aus unseren lückenhaften Beobachtungen entstehen können.

Das Paper zeigt, dass diese Methode viel genauer ist als alte Techniken, besonders wenn wir mit unvollständigen Daten und geheimnisvollen, unsichtbaren Einflussfaktoren zu tun haben.

Technische Zusammenfassung

1. Problemstellung

Die Entdeckung kausaler Beziehungen aus reinen Beobachtungsdaten ist eine fundamentale Aufgabe in vielen wissenschaftlichen Disziplinen. Die meisten bestehenden Methoden sind jedoch auf einen einzelnen Datensatz ausgelegt und gehen oft davon aus, dass keine unbeobachteten Confounder (versteckte gemeinsame Ursachen) existieren.

In der Praxis treten jedoch zwei wesentliche Herausforderungen auf:

1. Mehrere Datensätze mit nicht-identischen Variablenmengen: Oft liegen mehrere Datensätze vor, die dasselbe Ziel verfolgen, aber unterschiedliche Variablen messen (z. B. aufgrund unterschiedlicher Messgeräte oder experimenteller Einschränkungen).
2. Existenz unbeobachteter Variablen: In realen Systemen sind oft nicht alle relevanten Variablen messbar. Diese unbeobachteten Variablen können als Confounder wirken und die Identifizierbarkeit kausaler Beziehungen einschränken.

Bestehende Ansätze zur Integration mehrerer Datensätze (wie ION, IOD, COmbINE) erzeugen oft nur partielle Ancestral Graphs (PAGs), die Unsicherheiten enthalten, oder sind auf lineare Modelle beschränkt (wie CD-MiNi). Ein naiver Ansatz, einzelne Graphen zu schätzen und zu überlappen, scheitert daran, dass unbeobachtete Variablen in den einzelnen Datensätzen als Confounder wirken können und kausale Beziehungen zwischen Variablenpaaren, die in keinem Datensatz gleichzeitig beobachtet wurden, nicht identifiziert werden können.

2. Methodik: I-CAM-UV

Die Autoren schlagen I-CAM-UV (Integrating Causal Additive Models with Unobserved Variables) vor, einen Ansatz zur Integration von Ergebnissen des CAM-UV-Algorithmus über mehrere Datensätze hinweg.

Grundlagen: CAM-UV

Das zugrundeliegende Modell ist das Causal Additive Model with Unobserved Variables (CAM-UV).

• Es modelliert nicht-lineare kausale Beziehungen.
• Es erlaubt die Existenz unbeobachteter Variablen ($U$).
• CAM-UV liefert für einen Datensatz einen gemischten Graphen $G = (V \setminus U, A, N)$, wobei $N$ eine Menge ungerichteter Kanten ist. Eine Kante $\{v_i, v_j\} \in N$ signalisiert, dass die kausale Beziehung aufgrund einer unbeobachteten kausalen Pfad (UCP) oder eines unbeobachteten Backdoor-Pfads (UBP) nicht identifiziert werden kann.

Das Integrationsproblem

Gegeben sind $m$ Datensätze mit unterschiedlichen Variablenmengen $V_1, \dots, V_m$. Das Ziel ist es, einen kausalen Graphen über die vereinigte Variablenmenge $\hat{V} = \bigcup V_k$ zu schätzen.

• Herausforderung: Es gibt Variablenpaare, die in keinem Datensatz gleichzeitig beobachtet wurden ($E_{uno}$), sowie Paare, die zwar beobachtet wurden, aber durch UCP/UBP verdeckt sind ($E_{imp}$).
• Lösungsansatz: I-CAM-UV enumeriert (zählt auf) alle konsistenten DAGs (gerichtete azyklische Graphen). Ein DAG ist konsistent, wenn er strukturell mit den CAM-UV-Ergebnissen jedes einzelnen Datensatzes übereinstimmt. Das bedeutet:
  • Für Paare mit identifizierter Kante in einem CAM-UV-Ergebnis darf kein UCP/UBP im integrierten Graphen existieren.
  • Für Paare mit ungerichteter Kante (in $N$) muss ein UCP oder UBP im integrierten Graphen existieren.

Algorithmus: Best-First Search

Da die Anzahl möglicher Graphen exponentiell wächst (jedes unentschiedene Paar kann eine von drei Optionen haben: $v_i \to v_j$, $v_j \to v_i$ oder keine Kante), wurde ein effizienter Suchalgorithmus entwickelt:

1. Konsistenzkosten (Inconsistency Cost): Um mit realen Daten umzugehen, die Schätzfehler enthalten können, wird eine Kostenfunktion $C(\tilde{G})$ definiert. Diese zählt die Anzahl der Variablenpaare, bei denen die Konsistenzbedingung verletzt ist.
2. Monotonie-Eigenschaft: Die Autoren beweisen, dass die Konsistenzkosten monoton mit dem Fortschritt der Suche nicht abnehmen.
3. Best-First Search: Der Algorithmus verwendet einen Heap (Prioritätswarteschlange), um Zustände in aufsteigender Reihenfolge ihrer unteren Schranke für die Konsistenzkosten zu erweitern.
   • Dies ermöglicht es, Graphen mit minimalen Kosten zuerst zu finden.
   • Die Suche kann gestoppt werden, sobald die Kosten einen vom Benutzer definierten Schwellenwert ($C^* + b$) überschreiten.
4. Effiziente Suche nach UCP/UBP: Es werden polynomielle Algorithmen (basierend auf Breitensuche) vorgestellt, um UCPs und UBP in einem gegebenen Graphen schnell zu finden, was die Berechnung der Kosten pro Zustand effizient macht.

3. Wichtige Beiträge

1. Neuer Ansatz (I-CAM-UV): Entwicklung einer Methode zur Enumeration integrierter kausaler Graphen aus mehreren Datensätzen mit nicht-identischen Variablenmengen unter Berücksichtigung unbeobachteter Variablen.
2. Theoretische Fundierung: Beweis, dass der wahre kausale Graph (Ground Truth) unter idealen Bedingungen konsistent mit den CAM-UV-Ergebnissen ist.
3. Effizienter Algorithmus: Vorstellung eines Best-First-Search-Algorithmus, der die Monotonie der Inkonsistenzkosten nutzt, um die Suchraumgröße drastisch zu reduzieren und Graphen nach ihrer Qualität zu sortieren.
4. Fähigkeit zur Orientierung unbeobachteter Paare: Der Ansatz kann kausale Richtungen für Variablenpaare bestimmen, die in keinem einzelnen Datensatz gleichzeitig beobachtet wurden ($E_{uno}$), indem er die strukturellen Einschränkungen aller Datensätze kombiniert.

4. Ergebnisse (Experimente)

Die Autoren führten Experimente mit synthetischen Daten durch und verglichen I-CAM-UV mit Baselines wie einfachem Überlappen (CAM-UV-OVL), PC-Algorithmus-Überlappung, Imputation und CD-MiNi.

• Wiederherstellung verpasster Beziehungen (Q1 & Q2): I-CAM-UV zeigte eine überlegene Recall-Rate im Vergleich zu allen Wettbewerbern. Es konnte kausale Beziehungen erfolgreich wiederherstellen, die von CAM-UV in einzelnen Datensätzen übersehen wurden, und neue Beziehungen zwischen unbeobachteten Variablenpaaren entdecken.
• Präzision und F1-Score: Obwohl die Präzision leicht abnahm (mehr False Positives im Vergleich zum reinen Überlappen), blieb der F1-Score insgesamt ähnlich hoch wie bei der Baseline. Dies deutet darauf hin, dass die Methode mehr wahre Zusammenhänge findet, ohne die Gesamtgenauigkeit drastisch zu verschlechtern.
• Anzahl der DAGs und Genauigkeitsverteilung (Q3): Die Anzahl der enumerierten DAGs variierte stark. Wichtig ist jedoch, dass die Genauigkeitsverteilung der gefundenen DAGs oft einen einzigen Cluster bildete. Das bedeutet, dass selbst bei einer großen Anzahl von Lösungen die meisten von ihnen eine ähnliche (hohe) Genauigkeit aufweisen. Eine zufällige Stichprobe aus den Ergebnissen könnte daher für praktische Anwendungen ausreichen.
• Rechenzeit (Q4): Der Enumerationsprozess ist in den meisten Fällen schnell genug und vergleichbar mit anderen Methoden. Da der Algorithmus exponentiell skaliert, ist er für kleine bis mittlere Graphen (z. B. 10 Variablen) gut geeignet, erfordert jedoch Vorsicht bei sehr großen Variablenmengen.

5. Bedeutung und Fazit

I-CAM-UV ist ein bedeutender Fortschritt im Bereich der kausalen Entdeckung, da es zwei der größten praktischen Hürden adressiert: die Integration heterogener Datensätze und den Umgang mit unbeobachteten Confoundern.

• Praktische Relevanz: Die Methode ermöglicht es Forschern, Daten aus verschiedenen Quellen (z. B. unterschiedliche Studien oder Sensoren) zu kombinieren, um ein vollständigeres kausales Bild zu erhalten, als es mit einem einzelnen Datensatz möglich wäre.
• Robustheit: Durch die Einführung von Inkonsistenzkosten ist die Methode robust gegenüber Schätzfehlern in den einzelnen CAM-UV-Läufen.
• Einschränkungen: Die Genauigkeit hängt stark von der Qualität der zugrundeliegenden CAM-UV-Schätzungen ab. Zudem kann die Ausgabe einer großen Anzahl von DAGs die manuelle Interpretation erschweren, was zukünftige Arbeiten zu komprimierten Darstellungen erfordert.

Zusammenfassend bietet I-CAM-UV einen leistungsfähigen Rahmen, um kausale Strukturen in komplexen, realen Szenarien mit unvollständigen Daten und versteckten Variablen zu entschlüsseln.