Proportionally Representative Clustering

Sintesi Tecnica: Clustering Proporzionalmente Rappresentativo

Problema
Il documento affronta il problema dell'equità nel clustering dei centroidi, un compito fondamentale nell'apprendimento automatico non supervisionato in cui l'obiettivo è selezionare un sottoinsieme di $k$ centri (centroidi) da uno spazio metrico per servire un insieme di $n$ punti dati (agenti). Mentre gli obiettivi standard come $k$-means, $k$-medians e $k$-center ottimizzano il benessere globale, essi spesso non riescono a catturare una rappresentanza equa e proporzionale. I concetti di equità esistenti nel clustering, come la Proportional Fairness (PF) e la Core Fairness, presentano dei limiti: possono non essere realizzabili per ogni istanza e non soddisfano un requisito intuitivo minimo noto come "proporzionalità unanime" (dove un gruppo di agenti nella stessa posizione ha diritto a un numero di centri proporzionale alla propria dimensione). Inoltre, gli algoritmi esistenti per il clustering equo si affidano spesso ad attributi protetti pre-specificati, mentre questo lavoro cerca proprietà di equità applicabili a gruppi arbitrariamente definiti e determinati endogenamente dalla distribuzione dei dati.

Metodologia
Gli autori adottano un approccio assiomatico, proponendo un nuovo concetto di equità chiamato Proportionally Representative Fairness (PRF). Questo concetto è progettato sia per contesti di clustering non vincolati (continui) che discreti.

1. Definizione Assiomatica (PRF):

   • Contesto Non Vincolato: Un esito $X$ soddisfa la PRF se, per ogni insieme di agenti $S$ di dimensione almeno $\ell n/k$ con una distanza massima tra coppie pari a $y$, ci sono almeno $\ell$ centri in $X$ entro la distanza $y$ da almeno un agente in $S$.
   • Contesto Discreto: La definizione è adattata per tenere conto della natura grossolana del insieme dei candidati $M$. Se ci sono $\ell'$ candidati in $M$ entro la distanza $y$ da tutti gli agenti in un gruppo $S$ (dove $|S| \ge \ell n/k$), allora almeno $\ell'$ centri nell'esito devono essere entro la distanza $y$ da qualche agente in $S$.

2. Design dell'Algoritmo (SEAR):
   Gli autori introducono SEAR (Spatial Expanding Approval Rule), un algoritmo in tempo polinomiale ispirato alla Expanding Approvals Rule (EAR) del voto multi-vincitore, ma adattato per i dati spaziali.

   • Meccanismo: L'algoritmo espande iterativamente i raggi di vicinato basandosi sulle distanze ordinate tra agenti e candidati. Agli agenti vengono assegnati pesi iniziali. Quando un centro candidato copre un gruppo di agenti con un peso totale di almeno $n/k$, quel centro viene aggiunto alla soluzione e i pesi degli agenti coperti vengono ridotti di $n/k$.
   • Implementazione:
     • Algoritmo 1 (Non Vincolato): I candidati sono limitati alle posizioni degli agenti. Esegue in $O(n^2 \log n + kn^2)$.
     • Algoritmo 2 (Discreto): I candidati sono tratti da un insieme finito $M$. Esegue in $O(|M|n \log n + k|M|n)$.

Contributi Chiave e Risultati

• Esistenza e Proprietà della PRF: Il documento dimostra che un esito PRF è garantito esistere sia nei contesti non vincolati che in quelli discreti. La PRF soddisfa diverse proprietà desiderabili: implica la proporzionalità unanime, è robusta rispetto agli outlier, è invariante alla scala e non richiede gruppi protetti pre-specificati.
• Approssimazione della Proportional Fairness (PF):
  • Non Vincolato: L'algoritmo SEAR per il contesto non vincolato fornisce una 3-approssimazione alla Proportional Fairness. Questo è il primo algoritmo di approssimazione in tempo polinomiale noto per la PF in spazi metrici generali. Il documento stabilisce anche un limite stretto di $\frac{3+\sqrt{17}}{2} \approx 3.56$ per l'esistenza generale di esiti PRF rispetto alla PF.
  • Discreto: L'algoritmo SEAR per il contesto discreto fornisce una $(1+\sqrt{2})$-approssimazione alla PF, eguagliando il miglior fattore di approssimazione noto per la PF nel contesto discreto, pur soddisfacendo l'assioma più forte della PRF.
• Risultati di Impossibilità:
  • Il documento dimostra che gli algoritmi di clustering standard ($k$-means, $k$-median, $k$-center) e i precedenti algoritmi di fair clustering (come il Greedy Capture) non soddisfano la PRF.
  • Strategia-correttezza (Strategyproofness): Gli autori dimostrano un'incompatibilità tra la PRF e la strategia-correttezza. Nello specifico, non esiste un algoritmo che sia sia order-statistic strategyproof sia soddisfi la PRF, anche per $k=2$ nel contesto discreto. Ciò è dimostrato tramite una riduzione dal voto di comitati basato sull'approvazione, collegando la PRF all'assioma della Proportional Justified Representation (PJR), noto per essere incompatibile con la strategia-correttezza.

Significatività
Il lavoro rivendica importanza in tre aree primarie:

1. Avanzamento Concettuale: Introduce la PRF come un concetto di equità assiomatico e robusto che supera le carenze delle definizioni di equità proporzionale esistenti, in particolare il fallimento nel garantire la proporzionalità unanime.
2. Svolta Algoritmica: Fornisce i primi algoritmi di approssimazione in tempo polinomiale per la Proportional Fairness in spazi metrici generali (contesto non vincolato) e eguaglia i migliori limiti noti per il contesto discreto, il tutto soddisfacendo l'assioma più forte della PRF.
3. Limiti Teorici: Stabilisce rigorosamente il compromesso tra equità (specificamente la PRF) e l'incentivo alla correttezza (strategia-correttezza), mostrando che soddisfare gli assiomi di rappresentanza proporzionale entra intrinsecamente in conflitto con la prevenzione della manipolazione nella selezione dei centroidi.

L'opera si pone come un ponte tra la teoria della scelta sociale (specificamente il voto multi-vincitore) e l'apprendimento automatico non supervisionato, utilizzando informazioni spaziali per prendere decisioni sincronizzate che le regole di voto tradizionali o gli standard obiettivi di clustering non possono raggiungere.