Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations

Titel: Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations

Auteurs: Ranit Debnath Akash et al. (UIC, CU Boulder, Penn State)

---

1. Het Probleem: Beperkingen van Bestaande Fairness-Methoden

Huidige methoden voor het verifiëren van eerlijkheid in algoritmische besluitvorming (zoals Deep Neural Networks of DNN's) focussen voornamelijk op individuele eerlijkheid (individual fairness). Dit concept stelt dat vergelijkbare individuen vergelijkbare uitkomsten moeten krijgen. Een schending hiervan wordt meestal gedetecteerd door te zoeken naar een enkel paar van invoeren die alleen verschillen in beschermde attributen (zoals ras of geslacht), maar tot sterk verschillende uitkomsten leiden.

De kernproblemen met deze aanpak zijn:

• Isolatie: Het detecteert geïsoleerde gevallen van onrechtvaardigheid, maar mist bredere patronen van systematische discriminatie.
• Binair perspectief: Het behandelt eerlijkheid als een binair concept (wel/niet schending), terwijl real-world systemen vaak complexe, geclusterde patronen van willekeur vertonen.
• Gebrek aan kwantificering: Het kan niet meten hoe ernstig de discriminatie is binnen een subgroep. Als een systeem willekeurig beslist over een groep van 10 vergelijkbare personen, waarbij 5 een gunstige en 5 een ongunstige uitkomst krijgen, wordt dit door traditionele methoden mogelijk niet als een ernstig, gestructureerd probleem herkend.

Het paper introduceert het concept "Discrimination Clustering": het identificeren van regio's in de invoerruimte waar kleine verstoringen in beschermde attributen leiden tot $k$ significant verschillende clusters van uitkomsten, in plaats van slechts één paar.

---

2. Methodologie: HYFAIR Framework

De auteurs presenteren HYFAIR, een hybride framework dat formele verificatie combineert met gerichte willekeurige zoektochten om discriminatie te detecteren, kwantificeren en verklaren. Het proces verloopt in drie fasen:

A. Formele Verificatie (Certificering van 2-Fairness)

• Doel: Bewijzen of een DNN voldoet aan individuele eerlijkheid (2-fairness).
• Techniek: Het model wordt geëncodeerd als een Mixed-Integer Linear Programming (MILP) probleem.
• Werking: In plaats van alleen te zoeken naar één tegenvoorbeeld (counterexample), gebruikt HYFAIR een MILP-oplosser om te bepalen of er een paar van invoeren bestaat dat de eerlijkheid schendt.
• Voordeel: Als de MILP-oplosser aangeeft dat er geen tegenvoorbeeld bestaat, is de eerlijkheid formeel gegarandeerd. Als er wel een tegenvoorbeeld is, dient dit als "zaad" (seed) voor de volgende fase.

B. Gerichte Zoektocht naar $k$-Discriminatie

• Doel: De ernst van de discriminatie kwantificeren door de maximale waarde van $k$ te vinden (het aantal verschillende uitkomsten binnen een groep van $K$ counterfactuals).
• Techniek: Een gecombineerde zoekstrategie die gebruikmaakt van:
  1. Random Walk (RW): Basis willekeurige verkenning.
  2. Simulated Annealing (SA): Een optimalisatie-algoritme dat helpt om lokale minima te vermijden en naar regio's met hoge discriminatie te zoeken.
  3. SA + KNN: Een variant die ook gebruikmaakt van de K-Nearest Neighbors van de huidige oplossing om de zoekruimte efficiënter te verkennen.
• Proces: Het algoritme start bij de gevonden 2-discriminanten en zoekt lokaal naar invoeren die leiden tot de maximale $k$-waarde (maximale willekeur).

C. Verklaring en Mitigatie (Debugging)

• Doel: De onderliggende oorzaken van deze geclusterde discriminatie begrijpen.
• Techniek:
  • Het genereert een lokaal omgevingsdataset rondom de $k$-discriminante invoeren.
  • Het labelt deze invoeren als "hoog-k" (sterk discriminerend) of "laag-k".
  • Een Decision Tree wordt getraind om logische predicates (voorwaarden) te vinden die de "hoog-k" gevallen onderscheiden.
  • Deze regels worden gebruikt om te begrijpen welke combinaties van niet-beschermde attributen leiden tot willekeurige beslissingen op basis van beschermde attributen.
• Mitigatie: De afgeleide regels worden gebruikt als "guardrails" om het model te beperken of om het model opnieuw te trainen met data-augmentatie om de unfairness te verminderen.

---

3. Belangrijkste Bijdragen

1. Nieuw Fairness-Concept ($k$-discriminant): Een kwantitatieve generalisatie van individuele discriminatie die systematische, geclusterde patronen van onrechtvaardigheid kan detecteren.
2. Hybride Framework (HYFAIR): Een innovatieve combinatie van formele verificatie (MILP) voor garanties en gerichte willekeurige zoektochten (Simulated Annealing) voor het vinden van complexe, zeldzame bugs.
3. Interpreteerbare Verklaringen: Een nieuwe methode om decision trees te gebruiken die logische voorwaarden genereren die specifiek zijn voor clusters van discriminatie, in plaats van alleen individuele uitleg.
4. Empirische Validatie: Uitgebreide experimenten op 20 DNN-benchmarks (o.a. Adult Census Income, Bank Marketing) die aantonen dat HYFAIR superieur is aan state-of-the-art tools.

---

4. Resultaten

De experimenten tonen aan dat HYFAIR significant beter presteert dan bestaande methoden zoals FAIRIFY (SMT-gebaseerd) en LIME (uitleg-gebaseerd):

• Detectie van Discriminatie (RQ1): HYFAIR vond in 85% van de gevallen meer individuele discriminatie-instanties dan FAIRIFY en deed dit sneller. Waar FAIRIFY vaak geen tegenvoorbeeld vond, vond HYFAIR er vaak tientallen.
• Kwantificering van $k$-Discriminatie (RQ2): De Simulated Annealing (SA) strategie bleek de meest effectieve methode om de maximale $k$-waarde te vinden. HYFAIR ontdekte in veel benchmarks clusters met een veel hogere $k$-waarde (meer verschillende uitkomsten voor vergelijkbare personen) dan andere zoekalgoritmen.
• Verklaringen (RQ3): In vergelijking met LIME leverde HYFAIR succinctere en robuustere verklaringen. De gegenereerde regels dekten een grotere deelruimte van de invoer (hogere coverage) en waren stabieler bij het testen van perturbaties.
• Mitigatie (RQ4): Het toepassen van de gegenereerde decision-tree regels als guardrails op het originele model resulteerde in een reductie van de $k$-discriminatie in 89% van de gevallen. Hoewel het opnieuw trainen van het model (debiased models) soms de succes率 van het vinden van bugs verlaagde, bleek het toevoegen van regels aan het originele model vaak effectiever om de ernst van de discriminatie te verminderen zonder de algehele nauwkeurigheid significant te schaden (maximaal 2% daling).

---

5. Betekenis en Impact

Dit paper is significant omdat het de definitie van algoritmische eerlijkheid uitbreidt van een binair, individueel niveau naar een systematisch, kwantitatief niveau.

• Van "Bug" naar "Patroon": Het stelt ontwikkelaars in staat om niet alleen te zeggen "er is een fout", maar "er is een regio waar het systeem willekeurig en systematisch discrimineert".
• Betrouwbaarheid: Door formele verificatie te combineren met zoektochten, biedt het zowel garanties (als er geen fouten zijn) als diepgaande inzichten (als er fouten zijn).
• Actiegericht: De gegenereerde verklaringen zijn direct bruikbaar voor het implementeren van "guardrails" of het hertrainen van modellen, waardoor het een praktische tool is voor het verbeteren van ethische AI-systemen in hoog-risico domeinen zoals leningverlening, werving en justitie.

Kortom, HYFAIR biedt een holistische aanpak om de "willekeur" (arbitrariness) in AI-beslissingen op te sporen, te meten en op te lossen, wat een cruciale stap is voor het bouwen van eerlijker en transparantere systemen.