Technische Samenvatting: Onbevooroordeelde Binning voor Eerlijkheidsbewuste Attribuutrepresentatie

1. Probleemdefinitie

Het artikel behandelt het probleem van attribuut-binning (of bucketisatie), een veelvoorkomende voorverwerkingsstap waarbij continue kenmerken worden gediscretiseerd in intervallen voordat datasets worden gedeeld of modellen worden getraind. Hoewel binning wordt gebruikt voor privacybescherming en ruisonderdrukking, stellen de auteurs dat standaard binningmethoden (zoals binning met gelijke grootte of gelijke frequentie) onbedoeld bias kunnen introduceren of versterken tegen specifieke demografische groepen.

De kern van het probleem wordt geformuleerd als het vinden van een $k$-binning (het verdelen van een attribuut in $k$ buckets) die voldoet aan groepspariteit.

• Onbevooroordeelde Binning: Een binning is onbevooroordeeld als de ratio van elke demografische groep binnen elke bucket gelijk is aan de globale ratio van die groep in de gehele dataset.
• Doelstelling: Het primaire doel (Probleem 1) is het vinden van een onbevooroordeelde binning die de afwijking van een initiële binning met gelijke grootte minimaliseert (specifiek het minimaliseren van het verschil tussen de maximale en minimale bucketgrootte).
• $\epsilon$-Bevooroordeelde Binning: In het besef dat perfect onbevooroordeelde binning mogelijk niet bestaat of een hoge "prijs voor eerlijkheid" (significante afwijking van gelijke groottes) kan met zich meebrengen, introduceren de auteurs een versoepeld probleem: het vinden van een binning waarbij de groepsdispariteit in elke bucket maximaal $\epsilon$ is.

2. Methodologie

Het artikel stelt een reeks algoritmen voor die zijn afgestemd op verschillende beperkingen en datasetgroottes.

2.1 Exacte Oplossing voor Onbevooroordeelde Binning (Gelijke Grootte)

Voor het specifieke geval van het vinden van een onbevooroordeelde binning die de grootteafwijking van een baseline met gelijke grootte minimaliseert, ontwikkelen de auteurs een Dynamic Programming (DP) benadering.

• Grenskandidaten: Het algoritme identificeert eerst een set "grenskandidaten". Een index $i$ is een kandidaat als de cumulatieve ratio van een specifieke groep tot $i$ overeenkomt met de globale ratio van die groep. De auteurs bewijzen (Theorema 1) dat elke optimale onbevooroordeelde binning haar grenzen uitsluitend uit deze set moet halen.
• DP-formulering: Het algoritme gebruikt een recursieve functie $OPT(j, \kappa)$ om de eerste $j$ grenskandidaten te verdelen in $\kappa$ onbevooroordeelde buckets, waarbij de maximale en minimale bucketbreedtes worden bijgehouden om hun verschil te minimaliseren.
• Complexiteit: Het algoritme draait in $O(n \log n + m^2 k)$ tijd en $O(mk)$ ruimte, waarbij $n$ de datasetgrootte is, $m$ het aantal grenskandidaten is en $k$ het aantal buckets is.

2.2 Oplossingen voor $\epsilon$-Bevooroordeelde Binning

Omdat het concept van grenskandidaten niet uitgebreid kan worden naar de versoepelde $\epsilon$-bevooroordeelde setting, en de exacte DP-benadering voor deze setting een kwadratische tijdscomplexiteit heeft ($O(n^2 k)$), stellen de auteurs een praktisch schaalbare tweestapsbenadering voor:

1. Verdeel-en-Heers (D&C):

   • Dit algoritme verdeelt de data recursief in twee "super-buckets" om snel een geldige $\epsilon$-bevooroordeelde oplossing te vinden.
   • Het begint met een middelpunt-grens en breidt de zoekstraal iteratief uit totdat een $\epsilon$-bevooroordeelde splitsing wordt gevonden.
   • Theorema 4 bewijst dat als een geldige $\epsilon$-bevooroordeelde binning bestaat, D&C deze zal vinden.
   • Complexiteit: $O(n \log k)$ (bijna lineair), wat het zeer schaalbaar maakt.

2. Lokale Zoektocht (LS):

   • Om de optimale $\epsilon$-bevooroordeelde binning te vinden (minimalisering van de grootteafwijking), gebruikt LS de oplossing van D&C als een bovengrens.
   • Het definieert een zoekvenster rond de grenzen van de initiële binning met gelijke grootte, beperkt door de objectieve waarde van de D&C-oplossing.
   • Het controleert exhaustief combinaties binnen dit venster om een oplossing met een lagere objectieve waarde te vinden.
   • Complexiteit: $O(n \log n + (w_{dnc})^{k-1})$, waarbij $w_{dnc}$ de objectieve waarde van de D&C-oplossing is. Hoewel dit theoretisch exponentieel is in $k$, merken de auteurs op dat het in de praktijk efficiënt is omdat adversariële gevallen met een grote $w_{dnc}$ zeldzaam zijn.

3. Belangrijkste Bijdragen

• Probleemformulering: Het artikel definieert formeel het probleem van Onbevooroordeelde Binning en het versoepelde $\epsilon$-Bevooroordeelde Binning probleem, waarbij het gat in de literatuur met betrekking tot eerlijkheid tijdens de datapreparatie wordt benadrukt.
• Theoretische Garanties:
  • Bewijs dat de grenzen van de optimale onbevoordeelde binning tot een specifieke set kandidaten behoren.
  • Bewijs dat het D&C-algoritme compleet is (het vindt een oplossing als er een bestaat).
• Algoritmisch Pakket:
  • Een exact DP-algoritme voor onbevooroordeelde binning met gelijke grootte.
  • Een schaalbaar D&C-algoritme voor het vinden van geldige $\epsilon$-bevooroordeelde oplossingen in bijna lineaire tijd.
  • Een Local Search-algoritme dat D&C gebruikt om efficiënt optimale $\epsilon$-bevooroordeelde oplossingen te vinden.
• Algemene Toepasbaarheid: In tegen tegenover de DP-oplossing voor onbevooroordeelde binning, zijn de D&C- en LS-algoritmen algemeen en niet beperkt tot binning met gelijke grootte; ze kunnen fungeren als post-processing stappen voor elke black-box bucketisatie-methode.

4. Experimentele Resultaten

De auteurs hebben hun algoritmen geëvalueerd op real-world datasets (German Credit, COMPAS) en synthetische datasets.

• Impact op Eerlijkheid: Experimenten toonden aan dat standaard binning zonder aandacht voor eerlijkheid meetbare bias introduceert. Het toepassen van $\epsilon$-bevooroordeelde binning verminderde de groepsonrechtvaardigheid (Disparate Impact, Statistical Parity Difference, Equal Opportunity Difference) in downstream modellen (Logistische Regressie en SVM) aanzienlijk.
• Prijs van Eerlijkheid: Het halveren van de bias resulteerde in substantiële verbeteringen van de eerlijkheidsmetrieken, terwijl de modelnauwkeurigheid gelijk bleef of zelfs licht verbeterde. De "prijs van eerlijkheid" (afwijking van de buckets van gelijke grootte) bleek in veel gevallen verwaarloosbaar.
• Individuele Eerlijkheid: De studie observeerde dat terwijl de groepsgerechtigheid aanzienlijk verbeterde, de individuele eerlijkheid (gemeten aan de hand van consistentie) grotendeens stabiel bleef, wat suggereert dat onbevooroordeelde binning de eerlijkheid op individueel niveau niet schaadt.
• Schaalbaarheid: De D&C- en LS-algoritmen vertoonden een hoge efficiëntie op grote datasets, terwijl de kwadratische-tijd DP-oplossing beperkt was tot kleinere settings.
• Integratie: Het combineren van $\epsilon$-bevooroordeelde binning met downstream FairML-technieken (Exponentiated Gradient) liet zien dat datapreparatie de interventies op modelniveau kan aanvullen, hoewel de marginale winst kleiner was wanneer de data al vooraf was bewerkt voor eerlijkheid.

5. Betekenis en Claims

Het artikel positioneert onbevooroordeelde binning als een noodzakelijk, zij het onvoldoende, onderdeel van een verantwoorde data-analysepijplijn.

• Complementaire Rol: De auteurs stellen expliciet dat onbevooroordeelde binning geen vervanging is voor FairML-technieken (zoals het trainen van eerlijke modellen), maar dient als een cruciale voorverwerkingsstap om de propagatie van bias te voorkomen voordat de modeltraining begint.
• Praktische Relevantie: Het werk betoogt dat bias die wordt geïntroduceerd tijdens de datapreparatie een tastbare bron is van downstream onrechtvaardigheid. Door dit vroegtijdig aan te pakken, kunnen beoefenaars de last op downstream eerlijkheidsinterventies aanzienlijk verminderen.
• Bescheiden Claims: De auteurs merken voorzichtig op dat hoewel hun methoden de bias verminderen en de eerlijkheidsmetrieken verbeteren, ze geen eerlijkheid in alle downstream taken garanderen. De effectiviteit hangt af van de specifieke datadistributie en de gekozen $\epsilon$-drempelwaarde. Het artikel benadrukt dat het bereiken van eerlijke uitkomsten vereist dat eerlijkheidsbewuste datapreparatie wordt gekoppeld aan eerlijke algoritmeontwikkeling.