Technische Samenvatting: Het Pokémon-theorema en andere Onmogelijkheidsresultaten voor Fairness

Probleemstelling

Het artikel behandelt de fundamentele beperkingen van algoritmische fairness, met name het onderzoeken of de bekende onmogelijkheidsresultaten (zoals de Kleinberg–Mullainathan–Raghavan-dichotomie) artefacten zijn van specifieke scalare criteria of inherente structurele eigenschappen van verdelingen met ongelijke basisraten. Er worden twee hoofdvragen gesteld:

1. Beperking van een eindige checklist: Kan een eindige verzameling lineaire criteria voor middengemiddelde-fairness (zoals demografische pariteit, equalized odds) certificeren dat twee groepsverdelingen identiek zijn, of zal er altijd een resterende overtreding overblijven?
2. Beperking van representatieleren: Kan eerlijk feature-leren (het leren van een encoder die groepsinformatie verwijdert) deze onmogelijkheden omzeilen door een representatie te produceren waarbij downstream-predictoren fairness erven zonder in te leveren op bruikbaarheid?

Bestaande literatuur presenteert deze onmogelijkheden vaak als conflicten tussen scalare statistieken (bijvoorbeeld kalibratie versus balans van foutpercentages). De auteurs betogen dat deze scalare framing de onderliggende geometrische structuur verdoezelt en de vraag openlaat of "meer" criteria de kloof zouden kunnen dichten.

Methodologie

De auteurs verenigen deze fairness-beperkingen met behulp van Reproducing Kernel Hilbert Ruimtes (RKHS) en middengemiddelde-inbeddingen.

• RKHS-geometrie: Ze modelleren fairness-criteria als lineaire beperkingen op conditionele middengemiddelde-inbeddingen $\mu_{P} = \mathbb{E}[\phi(X)]$ binnen een Hilbertruimte $\mathcal{H}$.
• Karakteristieke kernen: Door gebruik te maken van karakteristieke kernen zorgen ze ervoor dat verschillende verdelingen worden afgebeeld op verschillende middengemiddelde-inbeddingen ($\mu_P \neq \mu_Q \iff P \neq Q$).
• Koppeling van totale verwachting: Het centrale mechanisme dat de onmogelijkheidsresultaten aandrijft, is de wet van totale verwachting, die groepsconditionele verwachtingen koppelt aan de kloof in basisraten ($\Delta p = p_a - p_b$).
• Spectrale analyse: Het artikel maakt gebruik van spectrale regulariteitsaannames (polynomiale eigenwaarde-afname van de gepoolde covariantie-operator en broncondities) om de snelheid te kwantificeren waarmee resterende overtredingen afnemen naarmate het aantal fairness-criteria toeneemt.

Belangrijkste Bijdragen

1. Sterker KMR-theorema

De auteurs versterken het klassieke onmogelijkheidsresultaat van Kleinberg–Mullainathan–Raghavan (KMR). Ze tonen aan dat de tegenstrijdigheid tussen kalibratie en class-conditionele balans geldt zelfs onder de zwakkere voorwaarde van groepsconditionele onbevooroordeeldheid ($\mathbb{E}[S|G=g] = p_g$), in plaats van volledige kalibratie binnen de groep te vereisen. Dit toont aan dat niet-gekalibreerde scores die slechts het gemiddelde basisrate van de groep volgen, nog steeds onderhevig zijn aan de onmogelijkheid.

2. Het Pokémon-theorema

Vernoemd naar de slogan "Gotta Catch 'Em All" (Ze moeten allemaal gevangen worden), behandelt dit theorema de vraag over de eindige checklist.

• Kwalitatief resultaat: Voor elk paar verschillende groepen ($P_a \neq P_b$) en elke eindige verzameling lineaire criteria voor middengemiddelde-fairness $\{v_1, \dots, v_m\}$ die door de groepen worden voldaan, bestaat er een resterende overtreding in het orthogonale complement. Deze overtreding wordt waargenomen door de Maximum Mean Discrepancy (MMD)-witnessvector $\delta / \|\delta\|_{\mathcal{H}}$.
• Kwantitatief resultaat: Onder spectrale regulariteit (polynomiale eigenwaarde-afname) en een bronconditie, neemt de minimax-resterende overtreding af met de Kolmogorov $m$-breedte-rate $\Theta(m^{-2\alpha r})$. Dit impliceert dat hoewel het toevoegen van meer criteria de ergste overtreding vermindert, deze nooit volledig verdwijnt voor een eindige $m$, tenzij de verdelingen identiek zijn.

3. Onmogelijkheid van eerlijk feature-leren

Het artikel bewijst dat eerlijk representatieleren niet gelijktijdig kan bereiken:

1. Verdelingspariteit: $\Phi(P_a) = \Phi(P_b)$ (de representatie is groepsinvariant).
2. Class-conditionele scheiding: De representatie behoudt verschillende class-conditionele verdelingen ($\Phi(X) \perp\!\!\!\perp G | Y$).
3. Niet-triviale signaal: De representatie behoudt voorspellende kracht voor de uitkomst $Y$.

Als basisraten verschillen ($p_a \neq p_b$), dwingt het afdwingen van zowel verdelingspariteit als class-conditionele scheiding class-collaps af ($\Phi(X) \perp\!\!\!\perp Y$), waardoor de representatie nutteloos wordt voor voorspelling.

4. Benaderende Fairness en de Pokémon–KMR-brug

De auteurs leiden kwantitatieve grenzen af voor benaderende fairness:

• Benaderend feature-leren: Ze stellen een Pareto-frontier vast waarbij het bruikbare downstream-signaal (class-conditionele middengemiddelde-kloof) wordt begrensd door $(\epsilon + \rho) / |p_a - p_b|$, waarbij $\epsilon$ de pariteitsovertreding is en $\rho$ de scheidingsovertreding.
• Brug naar KMR: Ze tonen aan dat naarmate het aantal audit-criteria $m \to \infty$ en de resterende overtredingen verdwijnen, de benaderende voorwaarden het exacte KMR-onmogelijkheidsresultaat herstellen (perfecte voorspelling is de enige oplossing).

Experimentele Resultaten

Het artikel valideert deze theoretische grenzen op standaard fairness-benchmarks (Adult Income, COMPAS, ACS PUMS):

• Spectrale afname: Empirische plots van de resterende MMD tegen het aantal criteria $m$ bevestigen de door het Pokémon-theorema voorspelde polynomiale afname. Het "budget" aan MMD dat nodig is om criteria te voldoen, varieert per dataset (bijvoorbeeld, COMPAS concentreert sneller vanwege lagere dimensionaliteit).
• Pareto-frontieren: Empirische plots van fout versus demografische pariteitskloof voor scheiding-afdwingende classifiers sluiten aan bij de theoretische ondergrens afgeleid in Sectie 6.2.
• Verboden gebied: Experimenten met eerlijke encoders (LFR, Fair-VAE, Adversarial Debiasing) tonen aan dat geen enkele methode het "verboden" linkerbovenste gebied van de plot succesvol bevolkt (lage pariteitskloof met hoog class-conditioneel signaal), wat de onmogelijkheid van class-collaps bevestigt.

Betekenis en Claims

Het artikel claimt een unificerend geometrisch kader te bieden voor onmogelijkheidsresultaten voor fairness.

• Structureel inzicht: Het herformuleert fairness-onmogelijkheden niet als een conflict van specifieke scalare metrieken, maar als een structureel gevolg van de wet van totale verwachting die inwerkt op verdelingen met ongelijke basisraten.
• Budgettoewijzing: Het presenteert fairness-auditing als een probleem van budgettoewijzing waarbij het totale "budget" de MMD tussen groepen is. Exacte fairness vereist dat dit budget volledig wordt uitgeput, wat onmogelijk is zonder in te leveren op bruikbaarheid als basisraten verschillen.
• Praktische implicatie: De resultaten suggereren dat wanneer groepen verdelingsmatig verschillend zijn, algoritmische interventies alleen niet gelijktijdig perfecte fairness en bruikbaarheid kunnen bereiken. Het artikel impliceert dat beleidsinterventies of explicite behandelsverschillen noodzakelijk kunnen zijn in dergelijke regimes, in plaats van uitsluitend te vertrouwen op het wissen van features of het optimaliseren van beperkingen.

De auteurs handhaven een bescheiden standpunt, waarbij ze opmerken dat hun resultaten observationeel zijn en geen nieuwe algoritmen voorstellen. In plaats daarvan bieden ze een theoretisch "no-go"-theorema dat de grenzen definieert van wat haalbaar is in eerlijk machine learning onder ongelijke basisraten.