Integrating Background Knowledge for Scalable Causal Discovery

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, ein riesiges Rätsel zu lösen: herauszufinden, wie genau eine Gruppe verschiedener Variablen (wie Wetter, Verkehr und Kaffeeverkäufe) einander beeinflussen. Sie haben ein riesiges Netz aus Hinweisen, aber das Netz ist so verworren, dass der Versuch, jede einzelne Verbindung auf einmal abzubilden, ein Leben lang dauern würde. Dies ist das Problem der kausalen Entdeckung (Causal Discovery) – der Versuch, die wahre Ursache-Wirkungs-Karte aus Daten zu finden.

Normalerweise, wenn Detektive gegen eine Wand laufen, bitten sie einen Experten um Hilfe. Vielleicht sagt Ihnen ein lokaler Barista: „Kaffeeverkäufe verursachen definitiv keinen Regen“ oder „Regen kommt definitiv vor Staus durch schlechtes Wetter“. In der Welt der Informatik wird dies als Hintergrundwissen (Background Knowledge, BK) bezeichnet.

Lange Zeit behandelten die meisten Computerprogramme diesen Expertenrat wie einen Post-it, den sie erst an die Wand klebten, nachdem sie ihre unordentliche Arbeit erledigt hatten. Sie erstellten zuerst eine riesige, verwirrende Karte und sagten dann: „Oh, der Experte sagte, diese Kante sei falsch? Okay, lassen wir sie einfach weg.“ Dies ist so, als würde man ein Haus bauen, es komplett streichen und dann feststellen, dass man vergessen hat, eine Wand einzureißen, von der der Architekt gesprochen hatte. Es ist eine Verschwendung von Zeit und Energie.

Die große Idee: Fragen Sie den Experten, während Sie bauen

Die Autoren dieser Arbeit, ein Team von Universitäten aus den Niederlanden und Deutschland, haben einen klügeren Weg gefunden. Sie haben ein neues Framework entwickelt, das es dem Computer ermöglicht, den Experten um Hilfe zu bitten, während der Untersuchung, nicht erst am Ende.

Stellen Sie sich das wie ein Spiel wie „Wer bin ich?“ oder „20 Fragen“ vor, bei dem man ein Geheimobjekt erraten muss.

• Der alte Weg: Sie stellen 20 Fragen zu allem, schreiben alle möglichen Antworten auf und stellen dann fest: „Oh, der Experte sagte, es ist kein Lebewesen“, und werfen dann die Hälfte Ihrer Notizen weg.
• Der neue Weg (dieses Paper): Sie fragen den Experten zu Beginn: „Ist es lebendig?“ Er sagt: „Nein.“ Sie hören sofort auf, nach Fell, Federn oder Schwänzen zu fragen. Sie fragen nur noch nach Steinen, Autos und Stühlen. Sie lösen das Rätsel schneller und mit weniger Fragen.

Die drei magischen Tricks

Das Paper zeigt, dass durch die Integration dieses Expertenwissens während der Algorithmus läuft, drei spezifische Dinge passieren:

1. Das Offensichtliche überspringen: Wenn der Experte sagt: „Variable A und Variable B sind definitiv miteinander verbunden“, hört der Computer auf, Zeit damit zu verschwenden, zu beweisen, dass sie nicht verbunden sind. Er akzeptiert die Verbindung einfach und macht weiter.
2. Den Suchraum einschränken: Wenn der Computer versucht herauszufinden, warum A und B unterschiedlich sind, muss er normalerweise hunderte anderer Variablen prüfen, um zu sehen, ob sie der „Schuldige“ sind. Der Experte kann sagen: „Es ist definitiv nicht C oder D.“ Der Computer ignorit C und D sofort und schrumpft den Suchraum von einem Stadion auf ein einzelnes Zimmer.
3. Mit den „Lücken“ umgehen: Manchmal sagt der Experte: „A und B sind definitiv nicht miteinander verbunden.“ Das Paper fand heraus, dass man, wenn man diese Verbindung sofort löscht, versehentlich die Logik beschädigen könnte, die nötig ist, um später die Richtung anderer Pfeile zu bestimmen. Daher ist ihre neue Methode clever: Sie wartet einen winzigen Moment, um den „Beweis“ (eine trennende Menge/separating set) zu finden, der erklärt, warum sie nicht verbunden sind, aber tut dies mit einer viel kleineren Liste von Verdächtigen. Dies verhindert, dass der Algorithmus abstürzt oder verwirrt wird.

Die Ergebnisse: Schneller und intelligenter

Die Autoren testeten diese Idee auf mehreren verschiedenen Detektiv-Algorithmen (benannt: PC, SNAP, MB-by-MB, LDECC und LOAD). Sie führten Simulationen mit 100 Variablen (Knoten) durch und testeten sie mit verschiedenen Arten von Daten, einschließlich linearer Gaußscher (glatte Kurven) und binärer (Ja/Nein) Daten.

Hier ist, was sie in ihren Simulationen fanden:

• Geschwindigkeit: Die neuen Methoden waren signifikant schneller. Für einige Algorithmen, wie PC-BK und LDECC+-BK, sank die Zeit, um das Rätsel zu lösen, um eine Größenordnung (das heißt: 10-mal schneller!), wenn sie Hintergrundwissen verwendeten.
• Weniger Fragen: Die Anzahl der „bedingten Unabhängigkeitstests“ (die Fragen, die der Computer an die Daten stellt) sank drastisch. In einigen Fällen sank die Anzahl der Tests von Hunderttausenden auf nur wenige Tausend.
• Bessere Genauigkeit: Wenn das Hintergrundwissen korrekt war, waren die finalen Karten genauer. Die „Interventionsdistanz“ (ein Maß dafür, wie nah die geschätzte Ursache-Wirkung an der Wahrheit liegt) verbesserte sich, was bedeutet, dass die Vermutungen des Computers darüber, was passiert, wenn man eine Variable ändert, viel näher an der Realität lagen.

Was sie explizit ausschließen

Das Paper ist sehr deutlich darüber, was nicht funktioniert oder was sie nicht machen:

• Keine reine „Nachbearbeitung“: Sie argumentieren, dass es ineffizient ist, bis zum Ende zu warten, um Expertenwissen zu nutzen. Während dies in einer perfekten Welt vielleicht die gleiche Karte liefern würde, verschwendet es eine Menge Rechenleistung, um dorthin zu gelangen.
• Keine Magie bei schlechten Daten: Sie testeten, was passiert, wenn der Experte falsch liegt (unvollkommenes Wissen). Sie fanden heraus, dass die Algorithmen im Allgemeinen robust sind, aber wenn der Experte zu viele falsche Antworten gibt (wie z. B. 30 % Fehler), gerät der Computer in Verwirrung, und die Zeit, die zum Lösen des Rätsels benötigt wird, kann für einige Methoden (wie SNAP) sogar steigen.
• Keine „gelöste“ Problematik für verborgene Variablen: Das Paper konzentriert sich auf Situationen, in denen es keine verborgenen „Confounder“ (geheime Variablen, die alles beeinflussen) gibt. Sie geben zu, dass der Umgang mit verborgenen Variablen viel schwieriger ist und dass ihre aktuelle Methode dies noch nicht vollständig löst. Sie arbeiten noch daran.

Wie sicher sind sie?

Die Autoren sind sehr zuversichtlich in ihre Mathematik. Sie haben nicht nur geraten; sie haben bewiesen, dass ihre neuen Methoden „sound“ (sie liefern kein falsches Ergebnis, wenn die Daten und der Experte perfekt sind) und „vollständig“ (sie werden die richtige Antwort finden, wenn sie existiert) sind.

• Bewiesen: Die Logik hinter ihren neuen Algorithmen (PC-BK, SNAP-BK, MB-by-MB-BK) ist mathematisch bewiesen, unter idealen Bedingungen korrekt zu funktionieren.
• Gemessen: Die Ergebnisse bezüglich Geschwindigkeit und Genauigkeit stammen aus diesen Computersimulationen. Sie haben 100 Experimente für jedes Szenario durchgeführt und die jeweils besten und schlechtesten 5 Ergebnisse entfernt, um einen soliden Durchschnitt zu erhalten. Sie testeten auf synthetischen Daten (gemachten Graphen) und realitätsnahen Daten aus dem bnlearn Repository (Netzwerke wie MAGIC-NIAB mit 4-4-Knoten und ARTH150 mit 107 Knoten).
• Simuliert: Die Ergebnisse bezüglich Geschwindigkeit und Genauigkeit basieren auf diesen Computersimulationen. Sie haben dies noch nicht an einem realen medizinischen Test oder einem Börsencrash getestet, aber die Mathematik legt nahe, dass es dort auch funktionieren sollte.

Das Fazit

Dieses Paper legt nahe, dass man, wenn man Ursache-Wirkungs-Beziehungen in einem komplexen System verstehen will, die Experten nicht erst am Ende ignorieren sollte. Indem man den Computer während des Denkprozesses den Experten zuhören lässt, kann man das Rätsel 10-mal schneller lösen und mit viel weniger Aufwand. Es ist wie ein GPS, das einem nicht nur sagt, wo man ist, sondern einen aktiv um Staus herumleitet, bevor man überhaupt in den Stau gerät.