Proportionally Representative Clustering

Technische Samenvatting: Proportioneel Representatieve Clustering

Probleemstelling
Het artikel behandelt het probleem van eerlijkheid in centroid-clustering, een fundamentele taak in ongesuperviseerd machine learning waarbij het doel is om een deelverzameling van $k$ centra (centroids) te selecteren uit een metriekere de ruimte om een verzameling van $n$ datapunten (agenten) te bedienen. Terwijl standaarddoelstellingen zoals $k$-means, $k$-medianen en $k$-center de globale welvaart optimaliseren, schieten ze vaak tekort in het vatten van proportionele representatieve eerlijkheid. Bestaande eerlijkheidsconcepten in clustering, zoals Proportionele Eerlijkheid (PF) en Core Fairness, hebben beperkingen: ze zijn mogelijk niet haalbaar voor elke instantie en voldoen niet aan een minimale intuïtieve vereiste die bekend staat als "unanieme proportionaliteit" (waarbij een groep agenten op dezelfde locatie recht heeft op een aantal centra dat proportioneel is aan hun omvang). Bovsamen met bestaande algoritmen voor eerlijke clustering, die vaak afhankelijk zijn van vooraf gespecificeerde beschermde attributen, streeft dit werk naar eerlijkheidseigenschappen die toepasbaar zijn op willekeurig gedefinieerde groepen die endogeen door de datadistributie worden bepaald.

Methodologie
De auteurs hanteren een axiomatische benadering en stellen een nieuw eerlijkheidsconcept voor genaamd Proportionally Representative Fairness (PRF). Dit concept is ontworpen voor zowel onbeperkte (continue) als discrete clustering-omgevingen.

1. Axiomatische Definitie (PRF):

   • Onbeperkte Setting: Een uitkomst $X$ voldoet aan PRF als, voor elke verzameling agenten $S$ van grootte ten minste $\ell n/k$ met een maximale paarafstand $y$, er ten minste $\ell$ centra in $X$ zijn binnen afstand $y$ van ten minste één agent in $S$.
   • Discrete Setting: De definitie is aangepast om rekening te houden met de grove structuur van de kandidaatverzameling $M$. Als er $\ell'$ kandidaten in $M$ zijn binnen afstand $y$ van alle agenten in een groep $S$ (waarbij $|S| \ge \ell n/k$), dan moeten er ten minste $\ell'$ centra in de uitkomst zijn binnen afstand $y$ van een bepaalde agent in $S$.

2. Algoritmeontwerp (SEAR):
   De auteurs introduceren SEAR (Spatial Expanding Approval Rule), een polynomial-tijd algoritme geïnspireerd door de Expanding Approvals Rule (EAR) uit multi-winner stemmingen, maar aangepast voor ruimtelijke data.

   • Mechanisme: Het algoritme breidt iteratief de buurtradii uit op basis van de gesorteerde afstanden tussen agenten en kandidaten. Agenten krijgen initiële gewichten toegewezen. Wanneer een kandidaat-centrum wordt geselecteerd dat een groep agenten dekt met een totale gewicht van ten minste $n/k$, wordt dit centrum aan de oplossing toegevoegd en wordt het gewicht van de gedekte agenten met $n/k$ verminderd.
   • Implementatie:
     • Algoritme 1 (Onbeperkt): Kandidaten worden beperkt tot de locaties van de agenten. Het draait in $O(n^2 \log n + kn^2)$.
     • Algoritme 2 (Discreet): Kandidaten worden getrokken uit een eindige verzameling $M$. Het draait in $O(|M|n \log n + k|M|n)$.

Belangrijkste Bijdragen en Resultaten

• Bestaan en Eigenschappen van PRF: Het artikel bewijst dat een PRF-uitkomst gegarandeerd bestaat in zowel onbeperkte als discrete settings. PRF voldoet aan verschillende gewenste eigenschappen: het impliceert unanieme proportionaliteit, is robuust tegen uitschieters, is schaalinvariant en vereist geen vooraf gespecificeerde beschermde groepen.
• Approximatie van Proportional Fairness (PF):
  • Onbeperkt: Het SEAR-algoritme voor de onbeperkte setting biedt een 3-approximatie voor Proportional Fairness. Dit is de eerste bekende polynomial-tijd benaderingsalgoritme voor PF in algemene metriekere ruimten. Het artikel stelt ook een strikte bovengrens vast van $\frac{3+\sqrt{17}}{2} \approx 3.56$ voor het algemene bestaan van PRF-uitkomsten met betrekking tot PF.
  • Discreet: Het SEAR-algoritme voor de discrete setting biedt een $(1+\sqrt{2})$-approximatie voor PF, wat overeenkomt met de beste bekende benaderingsfactor voor PF in de discrete setting, terwijl het aanvullend het sterkere PRF-axioma bevredigt.
• Onmogelijkheidsresultaten:
  • Het artikel toont aan dat standaard clustering-algoritmen ($k$-means, $k$-median, $k$-center) en voorgaande eerlijke clustering-algoritmen (zoals Greedy Capture) niet aan PRF voldoen.
  • Strategieproofheid: De auteurs bewijzen een incompatibiliteit tussen PRF en strategieproofheid. Specifiek is er geen algoritme dat zowel order-statistiek strategieproof is als aan PRF voldoet, zelfs niet voor $k=2$ in de discrete setting. Dit wordt aangetoond via een reductie van approval-gebaseerde commissieverkiezingen, waarbij PRF wordt gekoppeld aan het Proportional Justified Representation (PJR) axioma, dat bekend staat als incompatibel met strategieproofheid.

Significantie
Het artikel claimt significantie in drie primaire gebieden:

1. Conceptuele Vooruitgang: Het introduceert PRF als een robuust, axiomatisch eerlijkheidsconcept dat de tekortkomingen van bestaande proportionele eerlijkheidsdefinities overwint, met name het falen om unanieme proportionaliteit te garanderen.
2. Algoritmische Doorbraak: Het biedt de eerste polynomial-tijd benaderingsalgoritmen voor Proportional Fairness in algemene metriekere ruimten (onbeperkte setting) en evenaart de best bekende grenzen voor de discrete setting, terwijl het tegelijkertijd het sterkere PRF-axioma bevredigt.
3. Theoretische Limieten: Het stelt rigoureus de afruil vast tussen eerlijkheid (specifiek PRF) en prikkelcompatibiliteit (strategieproofheid), waarbij wordt aangetoond dat het voldoen aan proportionele representatie-axioma's inherent botst met het voorkomen van manipulatie in de selectie van centroiden.

Dit werk positioneert zichzelf als een brug tussen sociale keuzetheorie (met name multi-winner stemmingen) en ongesuperviseerd machine learning, waarbij ruimtelijke informatie wordt gebruikt om gesynchroniseerde beslissingen te nemen die traditionele stemregels of standaard clustering-doelstellingen niet kunnen bereiken.