Proportionally Representative Clustering

Résumé Technique : Regroupement Proportionnellement Représentatif

Énoncé du Problème
L'article traite du problème de l'équité dans le regroupement de centroïdes (centroid clustering), une tâche fondamentale de l'apprentissage non supervisé où l'objectif est de sélectionner un sous-ensemble de $k$ centres (centroïdes) à partir d'un espace métrique pour servir un ensemble de $n$ points de données (agents). Les objectifs standards tels que $k$-means, $k$-medians et $k$-center optimisent le bien-être global, mais échouent souvent à capturer une équité de représentation proportionnelle. Les concepts d'équité existants dans le regroupement, tels que la Proportionnalité Équitable (PF) et la Core Fairness, présentent des limites : ils peuvent ne pas être réalisables pour chaque instance, et ils ne satisfont pas une exigence intuitive minimale connue sous le nom de « proportionnalité unanime » (où un groupe d'agents situés au même emplacement a droit à un nombre de centres proportionnel à sa taille). De plus, les algorithmes existants pour le regroupement équitable reposent souvent sur des attributs protégés pré-spécifiés, alors que ce travail recherche des propriétés d'équité applicables à des groupes définis de manière endogène par la distribution des données.

Méthodologie
Les auteurs adoptent une approche axiomatique, proposant un nouveau concept d'équité appelé Équité Proportionnellement Représentative (PRF). Ce concept est conçu pour les contextes de regroupement non contraints (continus) et discrets.

1. Définition Axiomatique (PRF) :

   • Contexte Non Contraint : Un résultat $X$ satisfait la PRF si, pour tout ensemble d'agents $S$ de taille au moins $\ell n/k$ avec une distance maximale par paire $y$, il y a au moins $\ell$ centres dans $X$ à une distance $y$ d'au moins un agent de $S$.
   • Contexte Discret : La définition est adaptée pour tenir compte de la granularité de l'ensemble des candidats $M$. S'il y a $\ell'$ candidats dans $M$ à une distance $y$ de tous les agents d'un groupe $S$ (où $|S| \ge \ell n/k$), alors au moins $\ell'$ centres du résultat doivent être à une distance $y$ de certains agents de $S$.

2. Conception de l'Algorithme (SEAR) :
   Les auteurs introduisent SEAR (Spatial Expanding Approval Rule), un algorithme en temps polynomial inspiré de la règle d'approbation par expansion (Expanding Approvals Rule - EAR) du vote multi-vainqueur, mais adapté aux données spatiales.

   • Mécanisme : L'algorithme étend de manière itérative les rayons de voisinage basés sur les distances triées entre les agents et les candidats. Les agents se voient assigner des poids initiaux. Lorsqu'un candidat centre est sélectionné et couvre un groupe d'agents dont le poids total est d'au moins $n/k$, ce centre est ajouté à la solution, et les poids des agents couverts sont réduits de $n/k$.
   • Implémentation :
     • Algorithme 1 (Non contraint) : Les candidats sont restreints aux emplacements des agents. Il s'exécute en $O(n^2 \log n + kn^2)$.
     • Algorithme 2 (Discret) : Les candidats sont tirés d'un ensemble fini $M$. Il s'exécute en $O(|M|n \log n + k|M|n)$.

Contributions Clés et Résultats

• Existence et Propriétés de la PRF : L'article prouve qu'un résultat PRF est garanti d'exister dans les contextes non contraints et discrets. La PRF satisfait plusieurs propriétés désirables : elle implique la proportionnalité unanime, est robuste aux valeurs aberrantes (outliers), est invariante à l'échelle et ne nécessite pas de groupes protégés pré-spécifiés.
• Approximation de la Proportionnalité Équitable (PF) :
  • Non contraint : L'algorithme SEAR pour le contexte non contraint fournit une 3-approximation de la Proportionnalité Équitable. C'est le premier algorithme d'approximation connu en temps polynomial pour la PF dans des espaces métriques généraux. L'article établit également une borne serrée de $\frac{3+\sqrt{17}}{2} \approx 3.56$ pour l'existence générale des résultats PRF concernant la PF.
  • Discret : L'algorithme SEAR pour le contexte discret fournit une $(1+\sqrt{2})$-approximation de la PF, égalant le meilleur facteur d'approximation connu pour la PF dans le contexte discret, tout en satisfaisant l'axiome plus fort de la PRF.
• Résultats d'Impossibilité :
  • L'article démontre que les algorithmes de regroupement standards ($k$-means, $k$-median, $k$-center) et les précédents algorithmes de regroupement équitable (comme Greedy Capture) ne satisfont pas la PRF.
  • Stratégie-compatibilité (Strategyproofness) : Les auteurs prouvent une incompatibilité entre la PRF et la stratégie-compatibilité. Plus précisément, il n'existe aucun algorithme qui soit à la fois de type statistique-ordre stratégiquement compatible et satisfaisant la PRF, même pour $k=2$ dans le contexte discret. Ceci est démontré via une réduction du vote de comité par approbation, liant la PRF à l'axiome de Représentation Justifiée Proportionnelle (PJR), qui est connu pour être incompatible avec la stratégie-compatibilité.

Signification

L'article revendique une importance dans trois domaines principaux :

1. Avancée Conceptuelle : Il introduit la PRF comme un concept d'équité axiomatique robuste qui surmonte les lacunes des définitions existantes de la proportionnalité équitable, particulièrement l'échec à garantir la proportionnalité unanime.
2. Percée Algorithmique : Il fournit les premiers algorithmes d'approximation en temps polynomial pour la Proportionnalité Équitable dans des espaces métriques généraux (contexte non contraint) et égale les meilleures bornes connues pour le contexte discret, tout en satisfaisant l'axiome plus fort de la PRF.
3. Limites Théoriques : Il établit rigoureusement le compromis entre l'équité (spécifiquement la PRF) et l'incitation à la stratégie (strategyproofness), montrant que satisfaire les axiomes de représentation proportionnelle entre intrinsèquement en conflit avec la prévention de la manipulation dans la sélection de centroïdes.

Ce travail se positionne comme un pont entre la théorie du choix social (spécifiquement le vote multi-vainqueur) et l'apprentissage non supervisé, utilisant l'information spatiale pour prendre des décisions synchronisées que les règles de vote traditionnelles ou les objectifs de regroupement standards ne peuvent atteindre.