Towards a Fairer Non-negative Matrix Factorization

Dit artikel introduceert een min-max formulering voor niet-negatieve matrixfactorisatie (NMF) om de eerlijkheid in machine learning te verbeteren, waarbij twee optimalisatiemethoden worden gepresenteerd en geëvalueerd met synthetische en reële data, terwijl ook wordt erkend dat eerlijkheid niet-universeel is en soms ten koste gaat van individuele nauwkeurigheid.

De kern

Titel: Een eerlijkere manier om data te ontrafelen: De "Fairer-NMF" methode

Stel je voor dat je een enorme, rommelige berg met verschillende soorten speelgoed hebt: blokken, poppen, auto's en puzzels. Je wilt deze berg in twee dozen doen: één doos met de "onderdelen" (de basisvormen) en één doos met de "handleiding" (hoe je de speelgoedstukken uit die onderdelen bouwt). Dit is wat wiskundigen NMF (Non-negative Matrix Factorization) noemen. Het is een slimme manier om grote hoeveelheden data te versimpelen en patronen te vinden, bijvoorbeeld in medische dossiers of nieuwsartikelen.

Het probleem? De standaardmethode is vaak onrechtvaardig.

Het Probleem: De "Grootste Stem" wint

Stel je voor dat je die speelgoedberg probeert in te delen. Er zijn veel meer auto's dan poppen. De standaardmethode kijkt naar de gemiddelde fout. Omdat er zoveel auto's zijn, zal de computer proberen de auto's perfect in te delen, zelfs als dat betekent dat de poppen er heel slecht uit komen. De poppen (de kleinere groep) worden "opgeofferd" om de auto's (de grote groep) tevreden te stellen.

In de echte wereld betekent dit: als een algoritme medische data analyseert, kan het heel goed zijn voor de meeste mensen, maar heel slecht voor een minderheidsgroep (bijvoorbeeld vrouwen of een specifieke etnische groep). Ze krijgen dan een "slechte diagnose" of een onnauwkeurige voorspelling, terwijl de rest van de wereld er goed vanaf komt.

De Oplossing: De "Min-Max" Strategie

De auteurs van dit paper, Lara Kassab en haar team, zeggen: "Laten we dat niet laten gebeuren." Ze hebben een nieuwe manier bedacht om die speelgoeddozen in te delen, genaamd Fairer-NMF.

Hun idee is gebaseerd op een simpele, maar krachtige regel: "We kijken niet naar het gemiddelde, maar naar de slechtste situatie."

Stel je voor dat je een klas hebt met leerlingen. De standaardmethode zorgt dat de gemiddelde cijfer van de klas 8 is, maar dan heeft één leerling een 2 en de rest een 9. Dat is niet eerlijk.
De nieuwe methode (Fairer-NMF) zegt: "We gaan proberen het cijfer van de leerling met de 2 zo hoog mogelijk te krijgen, zelfs als dat betekent dat de leerlingen met de 9 iets zakken naar een 8,5."

Ze gebruiken een min-max strategie:

• Minimaliseren van de Maximale onrechtvaardigheid.
• Ze proberen te voorkomen dat één groep er echt slecht aan toe is, in plaats van te proberen dat iedereen gemiddeld goed zit.

Hoe werkt het? (De Twee Gereedschappen)

Om dit te bereiken, hebben de auteurs twee nieuwe "gereedschappen" (algoritmen) ontwikkeld:

1. De Alternatieve Minimatie (AM): Dit is als een zeer nauwkeurige, maar trage timmerman. Hij meet alles heel zorgvuldig, past de planken stukje bij beetje aan en zorgt dat het perfect past. Het resultaat is vaak heel goed en stabiel, maar het kost veel tijd en energie (rekenkracht).
2. De Multiplicatieve Updates (MU): Dit is als een snelle, behendige timmerman. Hij werkt met een snelle, slimme techniek waarbij hij de planken vermenigvuldigt en aanpast in plaats van ze stap voor stap te meten. Hij is veel sneller (veel minder rekenkracht nodig) en komt vaak bijna op hetzelfde goede resultaat uit, maar soms kan hij een beetje "wankelen" voordat hij stabiel is.

Wat leerden ze uit hun experimenten?

De auteurs hebben dit getest met synthetische data (gemaakte data) en echte data (zoals hartziektedossiers en nieuwsartikelen).

• Het resultaat: De nieuwe methode zorgt ervoor dat de kleinere groepen (zoals vrouwen in de hartziektedata of specifieke nieuwsrubrieken) veel eerlijker worden behandeld. Hun "foutmarge" wordt veel kleiner.
• De prijs: Er is een kleine prijs. Soms moet de grote groep (de auto's) een klein beetje "inleveren" om de kleine groep (de poppen) te helpen. De gemiddelde fout voor de hele berg speelgoed kan dus iets stijgen.
• De les: Eerlijkheid is niet altijd hetzelfde als "het beste gemiddelde". Soms moet je een compromis sluiten om niemand achter te laten.

Waarom is dit belangrijk?

In onze wereld worden algoritmen gebruikt om beslissingen te nemen over wie een hypotheek krijgt, wie een baan krijgt, of wie medische zorg krijgt. Als die systemen "onbewust" de grote groepen bevoordelen, is dat gevaarlijk voor de democratie en de rechtvaardigheid.

Dit paper laat zien dat we wiskundige modellen kunnen aanpassen om eerlijker te zijn. Het is geen perfecte oplossing voor alles (er is nooit één oplossing die voor iedereen perfect werkt), maar het is een enorme stap in de goede richting. Het geeft ons de tools om te zeggen: "Nee, we accepteren niet dat de kleine groepen er altijd slecht uitkomen."

Kort samengevat:
De auteurs hebben een nieuwe manier bedacht om data te ontrafelen die niet kijkt naar wat voor de "meeste" mensen goed is, maar naar wat erger is voor de "minste" mensen. Ze hebben twee methoden bedacht om dit te doen: één die heel nauwkeurig is (maar traag) en één die heel snel is. Het doel is een wereld waarin algoritmen niet alleen slim zijn, maar ook eerlijk.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Towards a Fairer Non-negative Matrix Factorization" in het Nederlands.

Titel: Towards a Fairer Non-negative Matrix Factorization

Auteurs: Lara Kassab, Erin George, Deanna Needell, Haowen Geng, Nika Jafar Nia, Aoxi Li.

---

1. Het Probleem

Machine Learning (ML) algoritmes worden steeds vaker ingezet in kritieke domeinen zoals medische diagnostiek, strafrecht en sociaal beleid. Een groot probleem is dat deze algoritmes vaak onbedoeld bias (vooroordeel) en onrechtvaardigheid reproduceren, vooral ten opzichte van minderheidsgroepen.

De auteurs focussen zich op Non-negative Matrix Factorization (NMF), een veelgebruikte techniek voor dimensiereductie en topic modeling. De standaard NMF-minimaliseert de gemiddelde reconstructiefout over de hele dataset. Dit leidt tot een fundamenteel onrechtvaardigheidsprobleem:

• Dominantie van meerderheden: Groepen met een groot aantal samples of complexe datastructuren kunnen de optimalisatie domineren.
• Verwaarlozing van minderheden: Kleinere groepen of groepen met een complexere onderliggende structuur (hogere rang) ondervinden vaak een veel hogere reconstructiefout, omdat de algoritme prioriteit geeft aan het verkleinen van de totale fout in plaats van de fout per groep.
• Gevolg: Dit resulteert in slechte prestaties voor ondervertegenwoordigde groepen, wat in toepassingen zoals gezondheidszorg of justitie tot ernstige schade kan leiden.

2. Methodologie: Fairer-NMF

Het artikel introduceert een nieuwe doelstelling voor NMF, genaamd Fairer-NMF, gebaseerd op een min-max framework (geïnspireerd door "Fair PCA").

De Kern van de Methode:
In plaats van de som van de fouten te minimaliseren, streeft Fairer-NMF ernaar om de maximale gemiddelde reconstructieverlies over alle groepen te minimaliseren.

• Definitie van Verlies: Het verlies voor een groep $\ell$ wordt gedefinieerd als de genormaliseerde reconstructiefout ten opzichte van wat die groep zou bereiken als het model alleen op die groep was getraind.
  $$\text{Loss}_\ell = \frac{\|X_\ell - W_\ell H\| - E_\ell}{\|X_\ell\|}$$
  Waarbij $E_\ell$ een schatting is van de optimale fout voor groep $\ell$ (verkregen via een gerandomiseerde standaard NMF op alleen die groep).
• Doelfunctie:
  $$\min_{W, H} \max_{\ell \in \{1, \dots, L\}} \left( \frac{\|X_\ell - W_\ell H\| - E_\ell}{\|X_\ell\|} \right)$$
  Dit zorgt ervoor dat de groep met het slechtste verlies (de "bottleneck") wordt verbeterd, zelfs als dit ten koste gaat van de totale gemiddelde fout.

Algoritmen:
De auteurs ontwikkelen twee specifieke algoritmen om dit niet-convexe optimalisatieprobleem op te lossen:

1. Alternating Minimization (AM) Scheme:

   • Dit is een iteratief proces waarbij $H$ en $W$ om de beurt worden geoptimaliseerd.
   • Het minimaliseren van $H$ wordt geformuleerd als een Second-Order Cone Program (SOCP).
   • Het minimaliseren van $W$ is een Non-Negative Least Squares (NNLS) probleem.
   • Voordeel: Garandeert een monotoon dalende verliesfunctie en convergeert betrouwbaar.
   • Nadeel: Rekenkundig zeer duur (vereist zware convex solvers zoals ECOS of SCS).

2. Multiplicative Updates (MU) Scheme:

   • Een adaptatie van de klassieke Lee & Seung MU-regels.
   • Het introduceert een gewichtingsvector $c$ die de groep met het hoogste verlies identificeert en de update-stappen voor die groep versterkt.
   • Voordeel: Zeer efficiënt, vereist alleen matrixvermenigvuldigingen, en is veel sneller dan AM.
   • Nadeel: Kan minder stabiel zijn in de convergentie vergeleken met AM, maar presteert in de praktijk goed.

3. Belangrijkste Bijdragen

1. Analyse van Onrechtvaardigheid in NMF: Het artikel demonstreert kwantitatief hoe standaard NMF systematisch minderheidsgroepen of groepen met complexe datastructuren benadeelt.
2. Fairer-NMF Formulering: Het introduceert een nieuwe min-max doelstelling die rekening houdt met zowel de grootte als de complexiteit (rang) van de data-groepen.
3. Algoritmische Implementatie: Het levert twee praktische oplossingen (AM en MU) voor dit specifieke probleem, inclusief methoden om de basisfout $E_\ell$ te schatten.
4. Empirische Validatie: Uitgebreide experimenten op synthetische en echte datasets tonen aan dat de methode de ongelijkheid in reconstructiefouten kan verminderen.

4. Resultaten

De auteurs testen hun methode op diverse datasets:

• Synthetische Data:
  • In scenario's met groepen van verschillende complexiteit (rang), verlaagt Fairer-NMF de fout voor de complexe groep aanzienlijk, terwijl de fout voor de eenvoudige groep iets toeneemt (een noodzakelijke trade-off).
  • In scenario's met overlappende subruimtes, zorgt Fairer-NMF voor een veel gelijkere verdeling van de fouten tussen de groepen dan standaard NMF.
• Hartziekte Dataset (Medisch):
  • Bij stratificatie op geslacht (man/vrouw) toonde standaard NMF een voorkeur voor vrouwen (lagere fout). Fairer-NMF egaliseerde de fouten tussen beide geslachten, hoewel dit soms leidde tot een iets hogere fout voor de oorspronkelijk "bevoordeelde" groep.
  • Opmerkelijk: In sommige gevallen (bij hoge rang) presteerde Fairer-NMF zelfs beter voor individuele groepen dan een model dat alleen op die groep was getraind.
• 20Newsgroups Dataset (Tekst):
  • Standaard NMF gaf de "Sale"-groep (kleinste groep) de hoogste fout. Fairer-NMF slaagde erin de fouten voor alle zes onderwerpen (Computer, Sale, etc.) te egaliseren, waardoor de "Sale"-groep een significante verbetering ervoer.

Vergelijking Algoritmen:

• AM is nauwkeuriger en convergeert consistenter naar een lage verlieswaarde, maar is traag (kan >1 uur duren voor grote datasets).
• MU is aanzienlijk sneller (seconden tot enkele minuten) en levert vergelijkbare resultaten, waardoor het de voorkeursmethode is voor grootschalige toepassingen.

5. Betekenis en Discussie

• Geen "Perfecte" Fairness: De auteurs benadrukken dat er geen universele oplossing voor eerlijkheid bestaat. Fairer-NMF is een "fairer" (eerlijker) aanpak, maar niet noodzakelijk "fair" in alle contexten.
• Trade-offs: Het minimaliseren van de maximale fout kan leiden tot een toename van de fout voor individuen die oorspronkelijk goed werden bediend. Dit is een ethische afweging die afhankelijk is van de specifieke toepassing (bijv. is het acceptabel dat een meerderheidsgroep iets minder nauwkeurig wordt behandeld om een minderheidsgroep te beschermen?).
• Praktische Toepasbaarheid: De methode biedt ML-praktici een concreet instrument om bias in onbewaakte leeropdrachten (zoals topic modeling) te detecteren en te mitigeren.
• Toekomstperspectief: Een uitdaging blijft het a priori kennen van de groepen. De auteurs suggereren dat clustering of reconstructiefout-analyse kan worden gebruikt om groepen dynamisch te identificeren als deze niet bekend zijn.

Conclusie:
Dit werk is een belangrijke stap richting transparante en eerlijke ML-algoritmes. Het toont aan dat door de doelstelling van NMF te wijzigen van "gemiddelde optimalisatie" naar "min-max optimalisatie", we systematische ongelijkheden kunnen verminderen, zij het met de nodige aandacht voor de inherente trade-offs in prestaties.