📊 statistics

Statistical Guarantees in the Search for Less Discriminatory Algorithms

Dieser Beitrag adressiert die rechtliche Verpflichtung von Unternehmen, weniger diskriminierende Algorithmen zu finden, indem er die Suche als ein Problem des optimalen Stoppens formalisiert und einen adaptiven Algorithmus vorschlägt, der statistische Garantien bietet, um zu zertifizieren, wann eine weitere Neukalibrierung des Modells unwahrscheinlich signifikante Verbesserungen bei der Verringerung disparater Auswirkungen erzielen wird.

Ursprüngliche Autoren: Chris Hays, Ben Laufer, Solon Barocas, Manish Raghavan

Veröffentlicht 2026-05-21

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Chris Hays, Ben Laufer, Solon Barocas, Manish Raghavan

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 Problem: Das Dilemma des „ungerechten Algorithmus"

Stellen Sie sich vor, Sie sind Bankmanager und müssen entscheiden, wer einen Kredit erhält. Sie verwenden ein Computerprogramm (einen Algorithmus), um diese Entscheidungen zu treffen. Kürzlich hat das Gesetz gesagt: „Wenn Ihr Computerprogramm versehentlich eine bestimmte Gruppe von Menschen diskriminiert (wie eine bestimmte Rasse oder ein bestimmtes Geschlecht), haben Sie Schwierigkeiten. Aber wenn Sie nachweisen können, dass Sie nach einer besseren Version dieses Programms gesucht haben – einer, die den gleichen Gewinn erzielt, aber Menschen fairer behandelt – und Sie einfach keine finden konnten, kommen Sie vielleicht davon."

Dies wird als Suche nach einer weniger diskriminierenden Alternative (LDA) bezeichnet.

Der Haken:
Computermodelle sind ein bisschen wie Würfeln. Selbst wenn Sie exakt denselben Code und exakt dieselben Daten verwenden, können Sie bei zwei Durchläufen des Trainingsprozesses zwei leicht unterschiedliche Ergebnisse erhalten. Manchmal ist eine Version sehr fair, und eine andere ist etwas weniger fair, obwohl beide gleichermaßen gut darin sind, vorherzusagen, wer den Kredit zurückzahlen wird.

Das Problem lautet: Wie oft müssen Sie würfeln, bevor Sie sagen können: „Okay, ich habe genug versucht. Ich kann keine bessere finden, also höre ich auf"?

Wenn Sie zu früh aufhören, könnte ein Richter sagen: „Sie haben es nicht genug versucht." Wenn Sie ewig weitermachen, verschwenden Sie Geld und Zeit. Das Papier fragt: Wie wissen Sie, wann Sie genug gesucht haben, um zu beweisen, dass Sie in „gutem Glauben" gehandelt haben?

Die Lösung: Der „kluge Käufer"-Algorithmus

Die Autoren schlagen ein mathematisches Werkzeug (einen Algorithmus) vor, der wie ein sehr kluger, vorsichtiger Käufer agiert.

Die Analogie: Auf der Suche nach dem besten Angebot
Stellen Sie sich vor, Sie kaufen einen bestimmten Artikel, sagen wir einen Toaster. Sie wollen den, der am wenigsten kostet, aber genauso gut funktioniert wie die anderen.

Sie gehen in den ersten Laden und sehen einen Toaster für 50 $.
Sie gehen in den zweiten Laden und sehen einen für 48 $. Sie kaufen ihn.
Sie gehen in einen dritten Laden und sehen einen für 47 $. Sie kaufen diesen.

Aber Sie können nicht jeden Laden der Welt besuchen. Irgendwann müssen Sie aufhören. Wie wissen Sie, dass Sie nicht noch einen weiteren Laden besuchen müssen, nur für den Fall, dass dort ein 40-$-Toaster versteckt ist?

Der Algorithmus des Papiers ist wie ein statistischer Kompass, der Ihnen sagt, wann Sie aufhören sollen zu suchen. Er berechnet: „Basierend auf den Preisen, die ich bisher gesehen habe, ist die Chance, in dem nächsten Laden einen deutlich günstigeren Toaster zu finden, so winzig, dass es den Spritpreis nicht wert ist, dorthin zu fahren."

Wie das Werkzeug des Papiers funktioniert

Die Autoren zerlegen dies in drei Hauptideen:

1. Der „Stopp"-Knopf (Optimaler Stopp)
Sie behandeln die Suche nach einem fairen Algorithmus wie ein Spiel, bei dem Sie weiterspielen, bis die Belohnung die Kosten nicht mehr wert ist.

Die Kosten: Jedes Mal, wenn Sie ein Modell neu trainieren, kostet es Zeit und Rechenleistung.
Die Belohnung: Jedes Mal, wenn Sie ein Modell finden, das etwas weniger diskriminierend ist, gewinnen Sie „Fairness-Punkte".
Die Regel: Der Algorithmus trainiert so lange neue Modelle, wie der erwartete Gewinn an Fairness höher ist als die Kosten des Trainings. Sobald die Mathematik sagt, dass das nächste Modell wahrscheinlich nicht viel helfen wird, drückt er den „Stopp"-Knopf.

2. Das „Sicherheitsnetz" (Statistische Garantien)
Die Autoren raten nicht einfach, wann sie aufhören sollen. Sie haben ein „Sicherheitsnetz" (mathematischer Beweis) gebaut, das mit sehr hoher Sicherheit (wie 95 % oder 99 %) garantiert, dass Sie kein „magisches" Modell verpasst haben, das viel besser gewesen wäre.

Denken Sie daran wie an eine Wettervorhersage. Sie können die Zukunft nicht zu 100 % sicher kennen, aber wenn die Vorhersage sagt, dass es zu 99 % nicht regnen wird, können Sie Ihren Regenschirm zuversichtlich zu Hause lassen.
Dies ermöglicht einem Unternehmen, vor Gericht zu sagen: „Wir haben die Suche nicht eingestellt, weil wir aufgegeben haben, sondern weil unsere Mathematik mit 99-prozentiger Sicherheit beweist, dass eine weitere Suche nicht geholfen hätte."

3. Der „Realitäts-Test"
Die Autoren haben dies mit echten Daten über Kreditwesen und Wohnen getestet. Sie simulierten Tausende verschiedener Szenarien, in denen sie Modelle immer wieder neu trainierten.

Was sie fanden: In vielen Fällen müssen Sie nicht ewig suchen. Nach dem Training von etwa 60 verschiedenen Versionen eines Modells sinken die „Fairness-Gewinne" normalerweise auf fast Null. Es ist, als würden Sie feststellen, dass nach dem Überprüfen von 60 Geschäften der Preis des Toasters nicht mehr unter 47 $ gefallen ist.
Sie stellten auch fest, dass Sie bei einigen Datentypen möglicherweise nur 10 Modelle überprüfen müssen, bevor Sie sicher aufhören können.

Warum dies wichtig ist

Dieses Papier gibt Unternehmen ein Zertifikat guten Glaubens.

Bevor dies möglich war, könnte ein Unternehmen verklagt werden und raten müssen: „Haben wir es genug versucht?" Jetzt können sie dieses Werkzeug nutzen, um einen Bericht zu erstellen, der sagt: „Wir haben 60 Modelle trainiert. Unsere statistische Garantie zeigt, dass die Chance, in den nächsten 60 Versuchen ein deutlich faireres Modell zu finden, weniger als 1 % beträgt. Daher war unsere Suche angemessen und ausreichend."

Es verwandelt ein vages rechtliches Argument über „genug versucht" in eine konkrete, mathematisch fundierte Entscheidung, die einem Richter oder einer Aufsichtsbehörde vorgelegt werden kann.

Zusammenfassung in einem Satz

Das Papier bietet ein mathematisches „Stoppschild", das Unternehmen genau sagt, wann sie genug nach einem faireren Algorithmus gesucht haben, um dem Gesetz zu beweisen, dass sie verantwortungsvoll gehandelt haben, ohne unendliche Ressourcen für eine Suche zu verschwenden, die nie enden wird.

Technische Zusammenfassung: Statistische Garantien bei der Suche nach weniger diskriminierenden Algorithmen

Problemstellung
Das US-amerikanische Diskriminierungsrecht, insbesondere die Doktrin der unverhältnismäßigen Wirkung (disparate impact), kann Unternehmen haftbar machen, wenn sie keine „weniger diskriminierende Alternative" (LDA) einführen – eine Entscheidungspolitik, die gleichwertige geschäftliche Ziele erreicht und gleichzeitig die unverhältnismäßige Wirkung auf geschützte Gruppen verringert. Jüngste wissenschaftliche Arbeiten deuten darauf hin, dass diese Doktrin Unternehmen verpflichtet, proaktiv nach solchen Algorithmen in hochriskanten Bereichen wie Beschäftigung, Kreditvergabe und Wohnraum zu suchen.

Eine zentrale Herausforderung ergibt sich jedoch aus der Modell-Multiplizität: Das erneute Trainieren von Modellen mit unterschiedlichen Zufallssamen oder Datenteilmengen führt häufig zu Prädiktoren mit vergleichbarer Genauigkeit, aber materiell unterschiedlicher unverhältnismäßiger Wirkung. Zwar können Unternehmen mehrere Modelle abtasten, um ein weniger diskriminierendes zu finden, doch können sie nicht unendlich oft neu trainieren. Das Kernproblem besteht darin, den rechtlichen Standard des „guten Glaubens" operationalisierbar zu machen: Wann ist eine Suche nach LDAs ausreichend, um zu belegen, dass eine weitere Suche unwahrscheinlich zu bedeutenden Verbesserungen führt? Die derzeitigen rechtlichen und regulatorischen Leitlinien fehlen präzise Kriterien, um zu bestimmen, wann die Grenzkosten einer zusätzlichen Suche den Grenznutzen einer verringerten Diskriminierung überwiegen.

Methodik
Die Autoren formalisieren die LDA-Suche als ein Problem des optimalen Stoppens. Ein Unternehmen trainiert eine Sequenz von Modellen $h_1, h_2, \dots$ , indem es aus einem randomisierten Trainingsverfahren $\mathcal{A}$ unter der Bedingung eines festen Datensatzes $D$ abtastet. Das Ziel ist es, das Training zum Zeitpunkt $\tau$ zu stoppen, wenn der erwartete Grenznutzen des Trainings eines zusätzlichen Modells (in Bezug auf die Verringerung der unverhältnismäßigen Wirkung) unter einen Kostenschwellenwert $\gamma$ fällt (definiert als das Verhältnis der Trainingskosten zum Nutzen einer Einheit Verbesserung der unverhältnismäßigen Wirkung).

Der Rahmen adressiert zwei Quellen der Unsicherheit:

Unbekannte Verteilung: Die Verteilung der Modellleistung (unverhältnismäßige Wirkung) ist unbekannt.
Begrenzte Daten: Die wahre unverhältnismäßige Wirkung eines Modells kann nicht direkt beobachtet werden; verfügbar ist nur eine empirische Schätzung auf einem Testset.

Um dies zu lösen, entwickelt das Papier adaptive Stoppalgorithmen, die Garantien mit hoher Wahrscheinlichkeit bieten. Der Ansatz zerlegt den erwarteten Grenznutzen $g(u)$ in zwei Komponenten:

Verbesserungswahrscheinlichkeit ( $p$ ): Die Wahrscheinlichkeit, dass eine neue Stichprobe strikt besser ist als das aktuelle Beste.
Bedingter erwarteter Verbesserungswert (CEI, $\mu$ ): Der erwartete Umfang der Verbesserung, gegeben, dass eine neue Stichprobe besser ist.

Die Autoren konstruieren zu jedem Zeitpunkt gültige obere Schranken für diese Größen:

Schranken für $p$ : Sie nutzen eine neuartige Sequenz, die die Wahrscheinlichkeit des Beobachtens eines neuen Minimums in einer Sequenz von i.i.d. Zufallsvariablen nach oben beschränkt (Lemma 3.2). Diese Schranke gilt für alle Zeitschritte $t$ gleichzeitig mit der Wahrscheinlichkeit $1-\delta$ .
Schranken für $\mu$ : Sie schlagen mehrere Schranken vor, die auf Verteilungsannahmen basieren (Tabelle 1). Eine universelle Schranke ( $\bar{\mu}(u) = u$ ) erfordert keine Annahmen. Engere Schranken werden unter Annahmen wie einem sub-uniformen linken Schwanz, einem exponentiellen linken Schwanz oder einer bekannten unteren Schranke für die unverhältnismäßige Wirkung hergeleitet.
Korrektur für begrenzte Daten: Um die Lücke zwischen empirischer und wahrer unverhältnismäßiger Wirkung zu behandeln, führen die Autoren eine Annahme eines nicht-abnehmenden Selektionseffekts ein (Annahme 3.4), was impliziert, dass der Regression-zum-Mittel-Effekt nicht zunimmt, wenn die beobachtete Leistung sich verbessert.

Hauptbeiträge

Formalisierung der LDA-Suche: Das Papier formalisiert die Suche nach weniger diskriminierenden Algorithmen als ein Problem des optimalen Stoppens und bietet einen statistischen Rahmen, um die Angemessenheit einer Suche zu zertifizieren.
Adaptiver Stoppalgorithmus (Algorithmus 1): Die Autoren präsentieren einen Algorithmus, der Modelle adaptiv trainiert und stoppt, wenn das Produkt der nach oben beschränkten Verbesserungswahrscheinlichkeit und der nach oben beschränkten CEI unter den Kostenschwellenwert $\gamma$ fällt.
Statistische Garantien (Satz 3.5): Das Haupttheoretische Ergebnis liefert eine Garantie mit hoher Wahrscheinlichkeit ( $1-\delta$ ), dass, wenn der Algorithmus stoppt, der erwartete Grenznutzen weiteren Trainings tatsächlich unter dem Kostenschwellenwert liegt. Dies ermöglicht es Unternehmen, Gerichten oder Regulierungsbehörden ein „Zertifikat" vorzulegen, dass eine weitere Suche unwahrscheinlich hilfreich sein wird.
Datengetriebene Schranken (Algorithmus 2): Das Papier erweitert den Rahmen, um die CEI-Schranke aus Daten zu schätzen (unter Annahme 3.6), was engere Schranken ohne vorherige Spezifikation von Verteilungsparametern ermöglicht, obwohl dies eine Vereinigungsschranke über Konfidenzbudgets erfordert.
Empirische Validierung: Der Ansatz wird an realen Kreditdaten (Adult, Folktables) und Wohnungsdaten (HMDA) unter Verwendung von logistischer Regression, Random Forests und Gradient Boosted Trees validiert.

Ergebnisse

Modell-Multiplizität: Die empirische Analyse bestätigt eine signifikante Variation der unverhältnismäßigen Wirkung über Modelle hinweg, die mit identischen Verfahren, aber unterschiedlichen Samen trainiert wurden, während die Variation der Genauigkeit gering bleibt. Dies stützt die Prämisse, dass ein erneutes Training weniger diskriminierende Modelle „kostenlos" (ohne Genauigkeitsverlust) hervorbringen kann.
Stopp-Performance: In Experimenten stoppt der Algorithmus typischerweise nach dem Training einer relativ kleinen Anzahl von Modellen (oft weniger als 60). Darüber hinaus sinken die marginalen Gewinne bei der Verringerung der unverhältnismäßigen Wirkung auf Hundertstelpunkte pro Modell.
Vergleich mit der Grundwahrheit: Im Vergleich zu einem „Vollinformations"-Regime (bei dem die wahre Verteilung bekannt ist) „überschießt" die Stoppzeit des Algorithmus die optimale Stoppzeit im Durchschnitt um Dutzende von Modellen leicht. Die Autoren stellen jedoch fest, dass die logarithmische Skala der Grenznutzen bedeutet, dass dieses Überschießen eine polynomiale Abnahme des Wertes darstellt, und der Algorithmus erfolgreich den Punkt identifiziert, an dem die Renditen signifikant abnehmen.
Fairness-bewusste Methoden: Die Methode zeigt vergleichbare Leistung, wenn sie auf Modelle angewendet wird, die mit fairness-bewussten Frameworks (z. B. Fairlearn) trainiert wurden, im Vergleich zum standardmäßigen „naiven" Training.

Bedeutung und Behauptungen
Das Papier behauptet, die ersten statistischen Werkzeuge bereitzustellen, um die Angemessenheit einer LDA-Suche unter Modell-Multiplizität zu quantifizieren und zu zertifizieren. Indem sie die Suche als ein Problem des optimalen Stoppens mit Schranken hoher Wahrscheinlichkeit rahmen, bieten die Autoren einen Mechanismus für Unternehmen, Regulierungsbehörden und Gerichten „glaubhafte" Bemühungen nachzuweisen, ohne unendliche Ressourcen zu erfordern.

Die Autoren sind bescheiden hinsichtlich des Umfangs ihres Beitrags und stellen fest, dass:

Ihr Verfahren eine Komponente einer breiteren Suche ist, die qualitative Überlegungen (z. B. Merkmalsauswahl, Modellannahmen) einschließt.
Der Rahmen ein festes Kosten-Nutzen-Verhältnis annimmt; die Bestimmung dieser Werte bleibt Gegenstand anhaltender rechtlicher und wirtschaftlicher Debatten.
Die empirischen Ergebnisse illustrativ sind, basieren auf öffentlich zugänglichen Datensätzen und spezifischen Modellklassen und können sich in industriellen Umgebungen mit massiven Datensätzen und komplexen Pipelines unterscheiden.
Der Rahmen auf andere Probleme des optimalen Stoppens erweitert werden kann (z. B. Hyperparameter-Tuning, Prompt-Engineering für LLMs), sich das Papier jedoch spezifisch auf den LDA-Kontext konzentriert.

Letztendlich schließt die Arbeit die Lücke zwischen der Rechtsdoktrin, die eine Suche nach weniger diskriminierenden Alternativen erfordert, und den praktischen Grenzen der Entwicklung von maschinellem Lernen, indem sie eine rigorose statistische Methode bietet, um zu bestimmen, wann eine Suche „gut genug" ist.