Fairness under Graph Uncertainty: Achieving Interventional Fairness with Partially Known Causal Graphs over Clusters of Variables

Die Autoren stellen einen Lernrahmen vor, der interventionelle Fairness auch bei nur teilweise bekannter kausaler Struktur erreicht, indem er auf einem Graphen über Variablenclustern basiert und eine effiziente Kernel-Methode nutzt, um die Diskrepanz zwischen Interventionsverteilungen zu minimieren.

Das Wesentliche

Titel: Wie man faire Entscheidungen trifft, auch wenn man die Welt nicht ganz versteht

Stellen Sie sich vor, Sie sind ein Chef, der neue Mitarbeiter einstellen muss. Sie wollen die besten Kandidaten finden, aber Sie wollen auch sicherstellen, dass niemand wegen seines Geschlechts oder seiner Herkunft benachteiligt wird. Das ist das Ziel von „Fairness" in der künstlichen Intelligenz (KI).

Das Problem ist: Um wirklich fair zu sein, muss die KI verstehen, warum bestimmte Dinge passieren. Sie muss die „Ursache und Wirkung" (Kausalität) verstehen. Aber in der echten Welt ist das wie ein riesiges Labyrinth, von dem wir oft nur die Wände sehen, nicht aber den genauen Weg.

Hier kommt diese neue Forschung vor. Sie bietet einen cleveren Trick, um fair zu sein, auch wenn man die Landkarte nur unvollständig hat.

1. Das Problem: Die perfekte Landkarte gibt es nicht

Normalerweise versuchen KI-Entwickler, eine perfekte Landkarte aller Zusammenhänge zu zeichnen. Sie wollen genau wissen: „Wenn Person A eine bestimmte Ausbildung hat, führt das zu Job X, und wenn sie Geschlecht B hat, führt das zu Job Y?"

Das ist aber extrem schwer. Es ist, als würde man versuchen, das gesamte Straßennetz einer ganzen Stadt auf einem einzigen Blatt Papier zu zeichnen, ohne jemals dort gewesen zu sein. Oft macht man Fehler bei dieser Landkarte, und wenn die Landkarte falsch ist, ist auch die „Fairness"-Regel falsch.

2. Die Lösung: Statt der ganzen Stadt nur die Stadtteile

Die Autoren dieses Papiers sagen: „Lass uns nicht versuchen, jede einzelne Straße zu kennen."

Statt jedes einzelne Haus (jedes Detail) zu betrachten, fassen sie die Stadt in Stadtteilen (Clustern) zusammen.

• Statt: „Wie beeinflusst dieses eine Detail des Lebenslaufes den Job?"
• Sagen sie: „Wie beeinflusst der gesamte Bereich 'Bildung' den Job?"

Das ist viel einfacher zu verstehen! Es ist wie der Unterschied zwischen einem detaillierten Satellitenbild, das jeden Baum zeigt, und einer vereinfachten Karte, die nur die großen Viertel zeigt. Man verliert zwar ein bisschen Detail, gewinnt aber massive Übersicht und Zuverlässigkeit.

3. Der Trick: Der „Worst-Case"-Plan

Da die Karte der Stadtteile nicht perfekt ist (man weiß nicht genau, welche Straße in welchem Viertel wohin führt), gibt es mehrere Möglichkeiten, wie die Welt funktionieren könnte.

Die neue Methode macht folgendes:
Sie denkt sich alle möglichen Versionen dieser Stadtteile-Karte aus.

• Szenario A: Die Bildung führt direkt zum Job.
• Szenario B: Die Bildung führt erst über die Gesundheit zum Job.

Anstatt nur eine dieser Versionen zu wählen, sagt die KI: „Ich werde so lernen, dass ich fair bin, egal welche dieser Versionen der Wahrheit entspricht."

Sie sucht nach dem schlimmsten Fall (dem „Worst-Case"). Wenn die KI in diesem schlimmsten Fall immer noch fair entscheidet, dann ist sie in allen anderen Fällen erst recht fair. Das ist wie ein Sicherheitsnetz: Man baut einen Damm nicht nur gegen ein kleines Hochwasser, sondern gegen das schlimmste Hochwasser, das man sich vorstellen kann. Wenn der Damm das übersteht, ist man sicher.

4. Die Waage: Gerechtigkeit vs. Genauigkeit

Ein großes Problem bei Fairness ist: Wenn man zu streng auf Fairness achtet, wird die KI vielleicht dumm und trifft schlechte Entscheidungen (z. B. lehnt sie gute Kandidaten ab, nur um sicherzugehen).

Die neue Methode ist wie eine geschickte Waage. Sie erlaubt es dem Nutzer, den Hebel zu bewegen:

• Willst du mehr Genauigkeit? Dann wiegt die Fairness etwas weniger.
• Willst du maximale Fairness? Dann akzeptierst du vielleicht ein paar kleine Fehler bei der Genauigkeit.

Das Besondere ist: Diese Methode findet das beste Gleichgewicht, auch wenn die Landkarte (die Daten) unvollständig ist. Bessere Methoden, die eine perfekte Landkarte voraussetzen, scheitern oft, weil sie in der Realität keine perfekte Landkarte finden.

Zusammenfassung in einer Metapher

Stellen Sie sich vor, Sie sind ein Koch, der ein Gericht für eine große Gruppe kocht.

• Die alten Methoden versuchen, jeden einzelnen Geschmackstoff (Salz, Pfeffer, Zimt) exakt zu messen. Wenn sie den Pfeffer falsch messen, ist das ganze Gericht verdorben.
• Diese neue Methode sagt: „Ich kenne die genauen Mengen nicht, aber ich weiß, dass die Gewürze in drei Schalen (Stadtteile) sind."
• Sie probiert das Gericht so, dass es für alle möglichen Kombinationen von Gewürzmengen schmeckt, die in diesen Schalen sein könnten.
• Das Ergebnis: Ein Gericht, das fast immer gut schmeckt und niemanden (keine Gruppe) benachteiligt, auch wenn man nicht genau weiß, wie viel Salz in welcher Schale war.

Fazit: Diese Forschung zeigt, dass man faire KI bauen kann, ohne alles perfekt zu verstehen. Man muss nur klug genug sein, um mit den Unwägbarkeiten der Welt umzugehen und für den „schlimmsten Fall" zu planen. Das macht die KI robuster und fairer für uns alle.

Technische Zusammenfassung

1. Problemstellung

Algorithmische Entscheidungssysteme (z. B. bei Kreditvergabe oder Einstellungen) müssen nicht nur genau, sondern auch fair bezüglich sensibler Attribute wie Geschlecht oder Ethnie sein. Kausale Fairnesskonzepte, insbesondere die interventionelle Fairness, gelten als rechtlich robust, da sie kausale Pfade zwischen sensiblen Attributen und Entscheidungen modellieren.

Das zentrale Problem besteht jedoch in der Unsicherheit des kausalen Graphen:

• Die meisten bestehenden Methoden für interventionelle Fairness setzen voraus, dass der exakte kausale Graph auf Variablenebene (Variable-Level Causal Graph) bekannt ist.
• In der Praxis ist die vollständige Rekonstruktion dieses Graphen aus Beobachtungsdaten extrem schwierig, besonders in hochdimensionalen Szenarien. Sie erfordert eine enorme Anzahl von bedingten Unabhängigkeitstests und ist anfällig für Fehler, die die Fairness-Garantien untergraben.
• Selbst Methoden, die teilweise gerichtete azyklische Graphen (CPDAGs) nutzen, stoßen bei hoher Dimensionalität an Grenzen, da die Inferenzfehler akkumulieren.

Die Autoren stellen die Frage: Kann interventionelle Fairness erreicht werden, wenn nur ein kausaler Graph auf Cluster-Ebene (Cluster CPDAG) bekannt ist, während die interne Struktur innerhalb der Cluster unbekannt bleibt?

2. Methodik

Das Paper schlägt einen Lernrahmen vor, der Fairness durch die Nutzung von Cluster-CPDAGs (Cluster Conditional Partially Directed Acyclic Graphs) sicherstellt. Diese Graphen sind über Gruppen (Cluster) von Variablen definiert und sind wesentlich einfacher zu schätzen als Graphen auf Variablenebene.

A. Anpassungsmengen-Enumeration (Adjustment Set Enumeration)

Da ein Cluster-CPDAG mehrere mögliche kausale DAGs (eine Markov-Äquivalenzklasse) repräsentiert, kann keine einzelne Anpassungsmenge (Adjustment Set) garantiert werden.

• Algorithmus: Die Autoren entwickeln einen grafischen Algorithmus, um eine Menge von Anpassungs-Cluster-Sets $\{Z_1, \dots, Z_M\}$ zu enumerieren. Mindestens eines dieser Sets ermöglicht die korrekte Identifikation der Interventionsverteilungen für den wahren Cluster-DAG.
• Neuheiten: Der Algorithmus berücksichtigt explizit Unabhängigkeitsbögen (Independence Arcs) und Verbindungs-/Trennungs-Marken (Connection/Separation Marks), die in Cluster-CPDAGs vorkommen, um bedingte Unabhängigkeiten korrekt zu interpretieren.
• Verfeinerung: Falls der Graph unidentifizierbare Fälle enthält, wird eine Verfeinerungsmethode angewendet, bei der Cluster in einzelne Knoten aufgespalten werden, um gültige Sets zu finden.

B. Worst-Case-Straffunktion (Worst-Case Penalty)

Um Fairness zu gewährleisten, wird eine Straffunktion $g_\theta$ in das Lernziel integriert, die die Diskrepanz zwischen Interventionsverteilungen minimiert.

• Da nicht bekannt ist, welches der Sets $Z_m$ das korrekte ist, wird die schlechtmögliche Fairness (Worst-Case) über alle enumerierten Sets betrachtet.
• Das Ziel ist es, die maximale Diskrepanz zwischen den Verteilungen $P(\hat{Y} | do(A=a), do(X_{ad}=x_{ad}))$ für verschiedene Werte der sensiblen Attribute $A$ zu minimieren.

C. Effiziente Schätzung mittels Barycenter Kernel MMD

Die direkte Berechnung der Worst-Case-Diskrepanz ist rechnerisch prohibitiv ($O(M \cdot N_A^2 \cdot n^2)$). Die Autoren führen zwei Optimierungen ein:

1. Barycenter-Zerlegung: Die Summe der paarweisen Maximum Mean Discrepancies (MMD) wird in eine Summe von MMDs zu einer gemischten Verteilung (dem Barycenter) umgewandelt. Dies reduziert die Komplexität bezüglich der Anzahl der sensitiven Attribute von quadratisch ($N_A^2$) auf linear ($N_A$).
2. Random Fourier Features (RFF): Die Kernel-Mapping-Funktion wird durch RFF approximiert, was die Berechnung der MMD von $O(n^2)$ auf $O(n \cdot d_{RFF})$ reduziert.
3. Gewichtete Schätzung: Zur Schätzung der Interventionsverteilungen wird Inverse Probability Weighting (IPW) in Kombination mit RFF verwendet.

Das finale Lernziel minimiert die Vorhersagefehler (Loss) plus die maximale gewichtete Barycenter-MMD über alle Kandidaten-Sets.

3. Wichtige Beiträge

1. Grafischer Algorithmus für Cluster-CPDAGs: Entwicklung eines Verfahrens zur Enumeration von Anpassungs-Cluster-Sets, das die spezifischen Eigenschaften von Cluster-CPDAGs (Unabhängigkeitsbögen, Marken) nutzt, um Fairness auch bei unbekannter innerer Cluster-Struktur zu garantieren.
2. Rechen-effiziente Fairness-Strafe: Einführung einer Barycenter Kernel MMD, die sowohl mit der Anzahl der sensitiven Attribute als auch mit der Stichprobengröße gut skaliert und somit die Anwendung in hochdimensionalen Szenarien ermöglicht.
3. Lernframework (C-IFair): Ein umfassendes Framework, das Worst-Case-Unfairness über mehrere mögliche Graphen-Strukturen hinweg bestraft, ohne den vollständigen Variablen-Level-Graphen zu kennen.
4. Empirische Validierung: Umfassende Experimente zeigen, dass die Methode einen besseren Kompromiss zwischen Genauigkeit und Fairness findet als existierende Ansätze, die auf unvollständigen oder fehlerhaften CPDAGs basieren.

4. Ergebnisse

Die Methode (C-IFair) wurde auf synthetischen und realen Datensätzen (Adult, German Credit, OULAD) getestet und mit sechs Baselines verglichen (inkl. Oracle, Unaware, $\epsilon$-IFair, $\ell$-IFair).

• Synthetische Daten: C-IFair erzielt in allen Szenarien (linear und nicht-linear, verschiedene Cluster-Anzahlen) die beste Balance zwischen RMSE (Genauigkeit) und Unfairness. Besonders in hochdimensionalen Settings ($d=15$) übertrifft sie Methoden, die auf Variablen-CPDAGs basieren ($\ell$-IFair), da diese anfälliger für Inferenzfehler sind.
• Reale Daten: Auf den Adult- und German-Credit-Datensätzen erreicht C-IFair die höchste AUC bei gleichzeitig niedrigster Unfairness unter den nicht-orakel-basierten Methoden.
• Robustheit: Die Methode bleibt auch dann effektiv, wenn die Annahmen für die Cluster-Partition verletzt werden (z. B. inadmissible partitions) oder wenn dichte Graphen vorliegen.
• Effizienz: Die Inferenz von Cluster-CPDAGs mittels CLOC ist deutlich schneller und stabiler als die Inferenz von Variablen-CPDAGs mittels PC-Algorithmus, was die Praxistauglichkeit unterstreicht.

5. Bedeutung und Fazit

Dieses Paper adressiert eine kritische Lücke in der Forschung zu algorithmischer Fairness: Die Abhängigkeit von perfekt bekannten kausalen Modellen.

• Praktische Relevanz: Da die vollständige Rekonstruktion kausaler Graphen in der Realität oft unmöglich ist, bietet der Ansatz eine realistische Alternative. Die Nutzung von Cluster-Graphen reduziert die Komplexität der Inferenz drastisch.
• Theoretischer Fortschritt: Die Arbeit zeigt, dass interventionelle Fairness auch dann erreicht werden kann, wenn die kausale Struktur nur auf einer aggregierten Ebene bekannt ist. Der entwickelte Algorithmus zur Enumeration von Anpassungsmengen unter Unsicherheit ist ein wichtiger theoretischer Baustein.
• Zukunftsperspektive: Die Methode ebnet den Weg für Fairness-Anwendungen in komplexen Domänen, wo nur begrenzte kausales Wissen verfügbar ist, und demonstriert, dass ein "Worst-Case"-Ansatz über mehrere plausible Graphenstrukturen robustere Ergebnisse liefert als die Annahme eines einzigen, möglicherweise fehlerhaften Graphen.

Zusammenfassend stellt C-IFair einen robusten, skalierbaren und theoretisch fundierten Rahmen dar, um Fairness in algorithmischen Entscheidungssystemen auch unter erheblicher Unsicherheit bezüglich der zugrunde liegenden kausalen Struktur zu gewährleisten.