🤖 machine learning

The Pokémon Theorem and other Fairness Impossibility Results

Dieser Artikel vereinheitlicht verschiedene Unmöglichkeitsergebnisse zur Fairness unter einer gemeinsamen RKHS-Geometrie und zeigt, dass ungleiche Basisraten dazu führen, dass lineare Fairnessbedingungen überbestimmt werden, was zu neuen Erkenntnissen über die Kleinberg–Mullainathan–Raghavan-Dichotomie, einem „Pokémon-Theorem" bezüglich mit MMD gemessenen Restverletzungen, sowie zu fundamentalen Grenzen des fairen Merkmalslernens führt.

Ursprüngliche Autoren: Daniel Matsui Smola, Alex Smola

Veröffentlicht 2026-05-12

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Daniel Matsui Smola, Alex Smola

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Die „ungerechte" Mathematik der Fairness

Stellen Sie sich vor, Sie bauen eine Maschine, die Entscheidungen trifft (wie die Bewilligung von Krediten oder die Vorhersage, ob jemand erneut straffällig wird), die zwei verschiedenen Personengruppen, nennen wir sie Gruppe A und Gruppe B, vollkommen gerecht werden.

Seit Jahrzehnten diskutieren Forscher darüber, was „fair" eigentlich bedeutet. Manche sagen, die Maschine müsse für beide Gruppen die gleiche Anzahl an Fehlern machen. Andere sagen, die Vorhersagen der Maschine müssen für beide Gruppen gleich genau sein.

Dieses Papier argumentiert, dass, wenn Gruppe A und Gruppe B in ihren realen Statistiken grundlegend unterschiedlich sind (zum Beispiel, wenn Gruppe A von Natur aus eine höhere Erfolgsrate hat als Gruppe B), man nicht alle Fairness-Definitionen gleichzeitig erfüllen kann. Es ist nicht nur ein Fehler im Code; es ist ein Gesetz der Mathematik.

Die Autoren verwenden ein ausgeklügeltes mathematisches Werkzeug namens RKHS (Reproduzierender Kernel-Hilbertraum), um dies zu beweisen. Stellen Sie sich RKHS als eine riesige, unendlich dimensionale Karte vor, auf der jede mögliche Art, „Fairness" zu messen, eine spezifische Richtung auf der Karte ist.

1. Das stärkere „KMR"-Theorem: Die „Durchschnitts"-Falle

Die alte Idee: Frühere Forschung (Kleinberg, Mullainathan, Raghavan) zeigte, dass wenn man von einer Maschine verlangt, sie sei perfekt „kalibriert" (ihre Vorhersagen stimmen exakt mit der Realität überein) UND über die Gruppen hinweg ausgeglichen ist, man dies nicht erreichen kann, es sei denn, die Gruppen sind identisch oder die Maschine ist eine perfekte Glaskugel.

Die neue Erkenntnis: Dieses Papier sagt: „Man braucht nicht einmal eine perfekte Kalibrierung, um an eine Wand zu stoßen."

Die Analogie: Stellen Sie sich vor, Sie sind ein Lehrer, der zwei verschiedene Klassen benotet. Klasse A hat einen natürlichen Durchschnitt von 80, und Klasse B hat einen natürlichen Durchschnitt von 60.
Die Regel: Sie versprechen, dass Ihr Benotungssystem „im Durchschnitt unvoreingenommen" ist (der von Ihnen gegebene Durchschnitt für Klasse A entspricht ihren 80, und für Klasse B ihren 60).
Das Ergebnis: Das Papier beweist, dass, wenn Sie auch verlangen, dass Ihr Benotungssystem die „Top-Schüler" und „Schwächsten" beider Klassen exakt gleich behandelt, Ihre einzige Option darin besteht, das Benoten ganz einzustellen und die Endnoten der Schüler einfach nur basierend darauf zu raten, wer sie sind. Sie verlieren die Fähigkeit, die individuelle Leistung tatsächlich zu messen.
Fazit: Man kann kein System haben, das im Durchschnitt fair ist, Untergruppen gleich behandelt und dennoch etwas Nützliches über Individuen aussagt, es sei denn, die Gruppen sind bereits identisch.

2. Das „Pokémon-Theorem": Man kann sie nicht alle fangen

Das Konzept: Dies ist der berühmteste Beitrag des Papiers. Es adressiert eine verbreitete Hoffnung: „Vielleicht haben wir noch nicht genug Fairness-Regeln geprüft. Wenn wir 10, oder 100, oder 1.000 Regeln prüfen, können wir vielleicht beweisen, dass das System fair ist."

Die Analogie: Stellen Sie sich vor, Sie spielen Pokémon. Sie haben eine Liste von „Fairness-Checks" (wie „Gleiche Fehlerraten", „Gleiche Bewilligungsraten" usw.). Sie prüfen Ihr System gegen diese Regeln.

Der Haken: Das Papier beweist, dass egal wie lang Ihre Checkliste ist (selbst wenn sie 100 Punkte hat), wenn Gruppe A und Gruppe B unterschiedlich sind, es immer mindestens eine weitere Fairness-Regel gibt, die Sie noch nicht geprüft haben und die versagen wird.
Der „MMD-Zeuge": Stellen Sie sich den Unterschied zwischen den beiden Gruppen als ein verstecktes Monster vor, das im Schatten lauert. Ihre Checkliste mit 100 Regeln ist wie das Scheinen einer Taschenlampe in 100 verschiedene Richtungen. Wenn das Monster in der 101. Richtung versteckt ist, verfehlt Ihre Taschenlampe es.
Der Zerfall: Das Papier berechnet, wie schnell dieses „versteckte Monster" kleiner wird, wenn man mehr Regeln hinzufügt. Es stellt sich heraus, dass selbst bei einer riesigen Anzahl von Regeln immer eine winzige, nachweisbare „Verletzung" übrig bleibt. Man kann die Ungerechtigkeit nie vollständig „fangen"; man kann sie nur in eine Ecke drängen, wo sie sehr klein wird, aber nie null.

3. Die Unmöglichkeit des „fairen Feature-Learnings": Das „gesäuberte" Signal

Das Konzept: Viele moderne KI-Forscher versuchen, Fairness zu „reparieren", indem sie dem Computer beibringen, die Gruppenzugehörigkeit zu vergessen (z. B. „Schau nicht auf Rasse oder Geschlecht, schau nur auf die Fähigkeiten"). Sie hoffen, dass wenn der Computer die Gruppe nicht sieht, er nicht voreingenommen sein kann.

Die Analogie: Stellen Sie sich vor, Sie versuchen, einen Kuchen zu backen (das Ergebnis vorherzusagen) mit Zutaten (Features), die von jedem „Gruppen-Geschmack" (soziodemografische Merkmale) gereinigt wurden.

Das Problem: Das Papier beweist, dass, wenn die beiden Gruppen unterschiedliche natürliche Erfolgsraten haben (unterschiedliche Basisraten), man keine „gesäuberte" Version der Daten erstellen kann, die:
1. Fair ist (für beide Gruppen gleich aussieht).
2. Nützlich ist (immer noch sagt, wer erfolgreich sein wird).
Das Ergebnis: Wenn man die Daten zwingt, für beide Gruppen identisch auszusehen, löscht man unbeabsichtigt das Signal darüber, wer erfolgreich sein wird. Der Kuchen wird geschmacklos. Der Computer lernt, dass Gruppe A und Gruppe B nicht unterscheidbar sind, also hört er auf, für jemanden etwas Nützliches vorherzusagen.
Fazit: Man kann nicht beides haben. Wenn die Gruppen statistisch unterschiedlich sind, zerstört der Versuch, die Daten gegenüber diesen Unterschieden „blind" zu machen, die Fähigkeit, genaue Vorhersagen zu treffen.

4. Die Trade-off-Grenze: Das „Budget" der Fairness

Das Konzept: Da wir perfekte Fairness nicht erreichen können, was sollten wir tun? Das Papier schlägt vor, Fairness wie ein Budget zu behandeln.

Das Budget: Das „Budget" ist die Gesamtmenge des statistischen Unterschieds zwischen Gruppe A und Gruppe B.
Ausgaben: Jedes Mal, wenn Sie eine Fairness-Regel durchsetzen (wie „Gleiche Fehlerraten"), geben Sie einen Teil dieses Budgets aus.
Die Grenze: Das Papier zieht eine Linie (eine Grenze), die den Trade-off zeigt. Wenn Sie sehr fair sein wollen (viel vom Budget ausgeben), muss Ihre Genauigkeit (Fehlerrate) steigen. Wenn Sie eine hohe Genauigkeit wollen, müssen Sie eine gewisse Ungerechtigkeit akzeptieren.
Die „verbotene Ecke": Es gibt einen bestimmten Bereich auf dem Graphen (niedrige Fehlerrate + hohe Fairness), der mathematisch unerreichbar ist. Das Papier zeigt, dass reale Experimente diese verbotene Zone nie betreten; sie bleiben immer auf der „unmöglichen" Seite der Linie.

Zusammenfassung

Das Papier nutzt fortgeschrittene Mathematik, um uns eine harte Wahrheit zu sagen: Wenn zwei Personengruppen von Natur aus unterschiedlich sind, kann kein Algorithmus nach jeder Definition vollkommen fair sein und gleichzeitig nützlich.

Man kann nicht genug Regeln prüfen, um totale Fairness zu beweisen (Pokémon-Theorem).
Man kann die Daten nicht säubern, um die Gruppen zu verstecken, ohne die nützlichen Informationen zu zerstören (Faires Feature-Learning).
Man muss eine Balance wählen zwischen dem, wie fair man sein will, und wie genau man sein muss (Die Grenze).

Die Autoren kommen zu dem Schluss, dass wir statt auf einen magischen Algorithmus zu hoffen, der alles repariert, diese mathematischen Grenzen akzeptieren und politische Entscheidungen darüber treffen müssen, welche Trade-offs für die Gesellschaft akzeptabel sind.

Technische Zusammenfassung: Das Pokémon-Theorem und andere Unmöglichkeitsergebnisse für Fairness

Problemstellung

Die Arbeit behandelt die grundlegenden Grenzen algorithmischer Fairness und untersucht speziell, ob die bekannten Unmöglichkeitsergebnisse (wie die Dichotomie nach Kleinberg–Mullainathan–Raghavan) Artefakte spezifischer skalärer Kriterien oder inhärente strukturelle Eigenschaften von Verteilungen mit ungleichen Basisraten sind. Zwei Hauptfragen werden gestellt:

Grenze der endlichen Checkliste: Kann eine endliche Sammlung linearer Kriterien für die Mittelwert-Fairness (z. B. demografische Parität, ausgeglichene Odds) zertifizieren, dass zwei Gruppenverteilungen identisch sind, oder bleibt stets eine residuelle Verletzung bestehen?
Grenze des Repräsentationslernens: Kann faires Feature-Lernen (das Erlernen eines Encoders, der Gruppeninformationen entfernt) diese Unmöglichkeiten umgehen, indem es eine Repräsentation erzeugt, bei der nachgelagerte Prädiktoren Fairness erben, ohne die Nützlichkeit zu opfern?

Die bestehende Literatur fasst diese Unmöglichkeiten oft als Konflikte zwischen skalaren Statistiken (z. B. Kalibrierung vs. Ausgewogenheit der Fehlerrate) auf. Die Autoren argumentieren, dass diese skalare Rahmung die zugrunde liegende geometrische Struktur verschleiert und offen lässt, ob „mehr" Kriterien die Lücke schließen könnten.

Methodik

Die Autoren vereinheitlichen diese Fairness-Beschränkungen mithilfe von Reproduzierenden Kernel-Hilberträumen (RKHS) und Mean Embeddings.

RKHS-Geometrie: Sie modellieren Fairness-Kriterien als lineare Beschränkungen für bedingte Mean Embeddings $\mu_{P} = \mathbb{E}[\phi(X)]$ innerhalb eines Hilbertraums $\mathcal{H}$ .
Charakteristische Kernel: Durch die Verwendung charakteristischer Kernel stellen sie sicher, dass sich verschiedene Verteilungen auf verschiedene Mean Embeddings abbilden ( $\mu_P \neq \mu_Q \iff P \neq Q$ ).
Totaler Erwartungswert-Coupling: Der Kernmechanismus, der die Unmöglichkeitsergebnisse antreibt, ist das Gesetz des totalen Erwartungswerts, das gruppenbedingte Erwartungswerte mit der Lücke der Basisraten koppelt ( $\Delta p = p_a - p_b$ ).
Spektralanalyse: Die Arbeit verwendet spektrale Regularitätsannahmen (polynomieller Eigenwertzerfall des gepoolten Kovarianzoperators und Quellbedingungen), um die Rate zu quantifizieren, mit der residuelle Verletzungen abnehmen, wenn die Anzahl der Fairness-Kriterien steigt.

Hauptbeiträge

1. Stärkeres KMR-Theorem

Die Autoren stärken das klassische Unmöglichkeitsergebnis nach Kleinberg–Mullainathan–Raghahan (KMR). Sie zeigen, dass der Widerspruch zwischen Kalibrierung und klassenbedingter Ausgewogenheit bereits unter der schwächeren Bedingung der gruppenbedingten Unverzerrtheit ( $\mathbb{E}[S|G=g] = p_g$ ) gilt, anstatt eine vollständige Kalibrierung innerhalb der Gruppe zu erfordern. Dies zeigt, dass nicht-kalibrierte Scores, die lediglich den durchschnittlichen Basisratenwert der Gruppe verfolgen, dennoch diesem Unmöglichkeitsergebnis unterliegen.

2. Das Pokémon-Theorem

Benannt nach dem Slogan „Gotta Catch 'Em All" (Fang sie alle), adressiert dieses Theorem die Frage der endlichen Checkliste.

Qualitatives Ergebnis: Für jedes Paar unterschiedlicher Gruppen ( $P_a \neq P_b$ ) und jede endliche Menge linearer Kriterien für die Mittelwert-Fairness $\{v_1, \dots, v_m\}$ , die von den Gruppen erfüllt werden, existiert eine residuelle Verletzung im orthogonalen Komplement. Diese Verletzung wird durch den Witness-Vektor der Maximum Mean Discrepancy (MMD) $\delta / \|\delta\|_{\mathcal{H}}$ nachgewiesen.
Quantitatives Ergebnis: Unter spektraler Regularität (polynomieller Eigenwertzerfall) und einer Quellbedingung nimmt die minimax-residuelle Verletzung mit der Kolmogorov- $m$ -Breiten-Rate $\Theta(m^{-2\alpha r})$ ab. Dies impliziert, dass das Hinzufügen weiterer Kriterien zwar die Worst-Case-Verletzung reduziert, sie aber für endliches $m$ niemals vollständig verschwindet, es sei denn, die Verteilungen sind identisch.

3. Unmöglichkeit des fairen Feature-Lernens

Die Arbeit beweist, dass faires Repräsentationslernen nicht gleichzeitig folgendes erreichen kann:

Verteilungsparität: $\Phi(P_a) = \Phi(P_b)$ (die Repräsentation ist gruppeninvariant).
Klassenbedingte Trennung: Die Repräsentation erhält verschiedene klassenbedingte Verteilungen bei ( $\Phi(X) \perp\!\!\!\perp G | Y$ ).
Nichttriviales Signal: Die Repräsentation behält die Vorhersagekraft für das Ergebnis $Y$ bei.

Wenn die Basisraten unterschiedlich sind ( $p_a \neq p_b$ ), erzwingt die Durchsetzung sowohl der Verteilungsparität als auch der klassenbedingten Trennung einen Klassenzusammenbruch ( $\Phi(X) \perp\!\!\!\perp Y$ ), was die Repräsentation für Vorhersagen unbrauchbar macht.

4. Approximative Fairness und die Pokémon–KMR-Brücke

Die Autoren leiten quantitative Schranken für approximative Fairness ab:

Approximatives Feature-Lernen: Sie etablieren eine Pareto-Front, bei der das nutzbare nachgelagerte Signal (Lücke der klassenbedingten Mittelwerte) durch $(\epsilon + \rho) / |p_a - p_b|$ begrenzt ist, wobei $\epsilon$ die Paritätsverletzung und $\rho$ die Trennungsverletzung darstellt.
Brücke zu KMR: Sie zeigen, dass, wenn die Anzahl der Audit-Kriterien $m \to \infty$ geht und die residuellen Verletzungen verschwinden, die approximativen Bedingungen die exakte KMR-Unmöglichkeit wiederherstellen (perfekte Vorhersage ist die einzige Lösung).

Experimentelle Ergebnisse

Die Arbeit validiert diese theoretischen Schranken an Standard-Fairness-Benchmarks (Adult Income, COMPAS, ACS PUMS):

Spektraler Zerfall: Empirische Plots der residuellen MMD gegen die Anzahl der Kriterien $m$ bestätigen die vom Pokémon-Theorem vorhergesagte polynomielle Zerfallsrate. Das für die Erfüllung der Kriterien benötigte „Budget" an MMD variiert je nach Datensatz (z. B. konzentriert sich COMPAS aufgrund geringerer Dimensionalität schneller).
Pareto-Fronten: Empirische Plots von Fehler gegen demografische Paritätslücke für Trennung erzwingende Klassifikatoren stimmen mit der in Abschnitt 6.2 hergeleiteten theoretischen Untergrenze überein.
Verbotene Region: Experimente mit fairen Encodern (LFR, Fair-VAE, Adversarial Debiasing) zeigen, dass keine Methode erfolgreich die „verbotene" obere linke Region des Plots (geringe Paritätslücke bei hohem klassenbedingtem Signal) besetzt, was die Unmöglichkeit des Klassenzusammenbruchs bestätigt.

Bedeutung und Behauptungen

Die Arbeit beansprucht, einen vereinheitlichten geometrischen Rahmen für Unmöglichkeitsergebnisse der Fairness zu liefern.

Strukturelle Einsicht: Sie rahmt Fairness-Unmöglichkeiten nicht als Konflikt spezifischer skalärer Metriken um, sondern als strukturelle Konsequenz des Gesetzes des totalen Erwartungswerts, das auf Verteilungen mit ungleichen Basisraten wirkt.
Budget-Allokation: Sie stellt Fairness-Auditing als ein Budget-Allokationsproblem dar, bei dem das gesamte „Budget" die MMD zwischen den Gruppen ist. Exakte Fairness erfordert die Erschöpfung dieses Budgets, was ohne Opferung der Nützlichkeit unmöglich ist, wenn die Basisraten unterschiedlich sind.
Praktische Implikation: Die Ergebnisse legen nahe, dass, wenn Gruppen verteilungsmäßig unterschiedlich sind, alleinige algorithmische Eingriffe nicht gleichzeitig perfekte Fairness und Nützlichkeit erreichen können. Die Arbeit impliziert, dass in solchen Regimen politische Eingriffe oder explizite Behandlungsunterschiede notwendig sein könnten, anstatt sich ausschließlich auf das Bereinigen von Features oder die Optimierung von Beschränkungen zu verlassen.

Die Autoren nehmen eine bescheidene Haltung ein und stellen fest, dass ihre Ergebnisse beobachtender Natur sind und keine neuen Algorithmen vorschlagen. Stattdessen liefern sie ein theoretisches „No-Go"-Theorem, das die Grenzen dessen definiert, was im fairen maschinellen Lernen unter ungleichen Basisraten erreichbar ist.