Sintesi Tecnica: Binning Inosservato per la Rappresentazione di Attributi Consapevole della Fairness

1. Definizione del Problema

Il documento affronta il problema del binning di attributi (o bucketizzazione), un comune passaggio di pre-elaborazione in cui le caratteristiche continue grezze vengono discretizzate in intervalli prima della condivisione dei dataset o dell'addestramento dei modelli. Sebbene il binning venga utilizzato per la preservazione della privacy e la riduzione del rumore, gli autori sostengono che i metodi di binning standard (come il binning a dimensione uguale o a frequenza uguale) possano involontariamente introdurre o amplificare il pregiudizio (bias) contro specifici gruppi demografici.

Il problema centrale è formulato come la ricerca di un $k$-binning (partizionamento di un attributo in $k$ bucket) che soddisfi la parità di gruppo (group parity).

• Binning Inosservato (Unbiased): Un binning è inosservato se il rapporto di ogni gruppo demografico all'interno di ogni bucket è uguale al rapporto globale di quel gruppo nell'intero dataset.
• Obiettivo: L'obiettivo primario (Problema 1) è trovare un binning inosservato che minimizzi la deviazione da un iniziale binning a dimensione uguale (specificamente, minimizzando la differenza tra la dimensione massima e minima dei bucket).
• Binning $\epsilon$-Biased: Riconoscendo che un perfetto binning inosservato potrebbe non esistere o potrebbe comportare un alto "prezzo della fairness" (una significativa deviazione dalle dimensioni uguali), gli autori introducono un problema rilassato: trovare un binning in cui la disparità di gruppo in ogni bucket sia al massimo $\epsilon$.

2. Metodologia

Il documento propone una serie di algoritmi adattati a diversi vincoli e dimensioni di dataset.

2.1 Soluzione Esatta per il Binning Inosservato (Dimensione Uguale)

Per il caso specifico di trovare un binning inosservato che minimizzi la deviazione dimensionale da un baseline a dimensione uguale, gli autori sviluppano un approccio di Programmazione Dinamica (DP).

• Candidati ai Confini (Boundary Candidates): L'algoritmo identifica innanzitutto un insieme di "candidati ai confini". Un indice $i$ è un candidato se il rapporto cumulativo di un gruppo specifico fino a $i$ corrisponde al rapporto globale di quel gruppo. Gli autori dimostrano (Teorema 1) che qualsiasi binning inosservato ottimale deve attingere i suoi confini esclusivamente da questo insieme.
• Formulazione DP: L'algoritmo utilizza una funzione ricorsiva $OPT(j, \kappa)$ per partizionare i primi $j$ candidati ai confini in $\kappa$ bucket inosservati, tracciando la larghezza massima e minima per minimizzare la loro differenza.
• Complessità: L'algoritmo opera in un tempo $O(n \log n + m^2 k)$ e uno spazio $O(mk)$, dove $n$ è la dimensione del dataset, $m$ è il numero di candidati ai confini e $k$ è il numero di bucket.

2.2 Soluzioni per il Binning $\epsilon$-Biased

Poiché il concetto di candidati ai confini non si estende al contesto rilassato del binning $\epsilon$-biased, e poiché l'approccio DP esatto per questo setting ha una complessità temporale quadratica ($O(n^2 k)$), gli autori propongono un approccio in due fasi scalabile in termini pratici:

1. Divide-and-Conquer (D&C):

   • Questo algoritmo partiziona ricorsivamente i dati in due "super bucket" per trovare rapidamente una soluzione $\epsilon$-biased valida.
   • Inizia con un confine centrale e espande iterativamente il raggio di ricerca finché non viene trovato uno split $\epsilon$-biased.
   • Il Teorema 4 dimostra che se esiste un binning $\epsilon$-biased valido, il D&C lo troverà.
   • Complessità: $O(n \log k)$ (quasi lineare), rendendolo altamente scalabile.

2. Ricerca Locale (Local Search - LS):

   • Per trovare il binning $\epsilon$-biased ottimale (minimizzando la deviazione dimensionale), LS utilizza la soluzione del D&C come limite superiore.
   • Definisce una finestra di ricerca attorno ai confini del binning iniziale a dimensione uguale, vincolata dal valore dell'obiettivo della soluzione D&C.
   • Controlla esaustivamente le combinazioni all'interno di questa finestra per trovare una soluzione con un valore di obiettivo inferiore.
   • Complessità: $O(n \log n + (w_{dnc})^{k-1})$, dove $w_{dnc}$ è il valore dell'obiettivo della soluzione D&C. Sebbene teoricamente esponenziale in $k$, gli autori notano che è efficiente in pratica poiché i casi avversari con un $w_{dnc}$ elevato sono rari.

3. Contributi Chiave

• Formulazione del Problema: Il documento definisce formalmente il problema del Binning Inosservato e il problema rilassato del Binning $\epsilon$-Biased, evidenziando la lacuna nella letteratura riguardante la fairness nella fase di preparazione dei dati.
• Garanzie Teoriche:
  • Dimostrazione che i confini del binning inosservato ottimale devono appartenere a un set specifico di candidati.
  • Dimostrazione che l'algoritmo D&C è completo (trova una soluzione se questa esiste).
• Suite Algoritmica:
  • Un algoritmo DP esatto per il binning inosservato a dimensione uguale.
  • Un algoritmo D&C scalabile per trovare soluzioni $\epsilon$-biased valide in tempo quasi lineare.
  • Un algoritmo di Ricerca Locale (LS) che sfrutta il D&C per trovare soluzioni $\epsilon$-biased ottimali in modo efficiente.
• Applicabilità Generale: A differenza della soluzione DP per il binning inosservato, gli algoritmi D&C e LS sono generali e non limitati al binning a dimensione uguale; possono agire come passaggi di post-elaborazione per qualsiasi metodo di bucketizzazione black-box.

4. Risultati Sperimentali

Gli autori hanno valutato i loro algoritmi su dataset reali (German Credit, COMPAS) e dataset sintetici.

• Impatto sulla Fairness: Gli esperimenti hanno dimostrato che il binning standard privo di consapevolezza della fairness introduce un bias misurabile. L'applicazione del binning $\epsilon$-biased ha ridotto significativamente le metriche di unfairness di gruppo (Disparate Impact, Statistical Parity Difference, Equal Opportunity Difference) nei modelli a valle (Logistic Regression e SVM).
• Prezzo della Fairness: Ridurre il bias della metà ha portato a miglioramenti sostanziali nelle metriche di fairness mantenendo o migliorando leggermente l'accuratezza del modello. Il "prezzo della fairness" (deviazione dalle dimensioni uguali dei bucket) è risultato trascurabile in molti casi.
• Fairness Individuale: Lo studio ha osservato che mentre la fairness di gruppo è migliorata significativamente, la fairness individuale (misurata come consistenza) è rimasta ampiamente stabile, suggerendo che il binning inosservato non danneggia la fairness a livello individuale.
• Scalabilità: Gli algoritmi D&C e LS hanno dimostrato un'alta efficienza su grandi dataset, mentre la soluzione DP a tempo quadratico era limitata ad ambiti più piccoli.
• Integrazione: Combinare il binning $\epsilon$-biased con tecniche di FairML a valle (Exponentiated Gradient) ha mostrato che la preparazione dei dati può complementare gli interventi a livello di modello, sebbene il guadagno marginale fosse minore quando i dati erano già stati pre-elaborati per la fairness.

5. Significato e Rivendicazioni

Il documento posiziona il binning inosservato come una componente necessaria, sebbene non sufficiente, di una pipeline di analisi dati responsabile.

• Ruolo Complementare: Gli autori dichiarano esplicitamente che il binning inosservato non sostituisce le tecniche di FairML (come l'addestramento di modelli equi), ma serve come un passaggio critico di pre-elaborazione per prevenire la propagazione del bias prima che l'addestramento del modello abbia inizio.
• Rilevanza Pratica: Il lavoro sostiene che il bias introdotto durante la preparazione dei dati è una fonte tangibile di unfairness a valle. Affrontandolo precocemente, i professionisti possono ridurre significativamente il carico sugli interventi di fairness successivi.
• Rivendicazioni Modeste: Gli autori sottolineano con cautela che, sebbene i loro metodi riducano il bias e migliorino le metriche di fairness, non garantiscono la fairness in tutti i compiti a valle. L'efficacia dipende dalla specifica distribuzione dei dati e dalla soglia $\epsilon$ scelta. Il documento enfatizza che ottenere risultati equi richiede l'accoppiamento della preparazione dei dati consapevole della fairness con lo sviluppo di algoritmi equi.