Fairness of Classifiers in the Presence of Constraints between Features

1. Enunciato del Problema

Il paper affronta una lacuna critica nella definizione e nella valutazione dell'equità nei classificatori di Machine Learning: la presenza di vincoli logici tra le caratteristiche.

• Contesto: Le definizioni standard di equità (ad esempio, Equità attraverso l'ignoranza) spesso assumono che una decisione sia equa se non dipende da caratteristiche protette (ad esempio, genere, razza).
• Il Problema: In scenari reali, le caratteristiche raramente sono indipendenti. Esistono vincoli dovuti a:
  • Codifica: ad esempio, la codifica one-hot in cui esattamente una caratteristica booleana deve essere vera.
  • Logica reale: ad esempio, "Se una persona è in congedo di maternità, deve essere di sesso femminile e impiegata".
• La Conseguenza: Ignorare questi vincoli può portare a falsi positivi (dichiarare equo un classificatore non equo) o falsi negativi (dichiarare non equo un classificatore equo).
  • Esempio: Un modello potrebbe apparire dipendente dal genere perché l'output del modello cambia quando il genere viene invertito, ma se il vincolo implica che invertire il genere forza anche un cambiamento in un'altra caratteristica (come lo stato occupazionale), la decisione potrebbe essere effettivamente indipendente dal genere nello spazio delle caratteristiche valido.
• Obiettivo: Definire formalmente l'equità in presenza di vincoli ($C$) e analizzare la complessità computazionale della verifica di queste definizioni.

2. Metodologia e Concetti Chiave

Gli autori utilizzano Spiegazioni Abductive (AXp) e Implicanti Primi (PI) all'interno di uno spazio di caratteristiche vincolato.

Definizioni Chiave

• Spazio delle Caratteristiche ($F$): Il prodotto cartesiano dei domini delle caratteristiche.
• Vincoli ($C$): Un insieme di regole logiche che restringono le istanze valide. Lo spazio valido è $F[C]$.
• Caratteristiche Protette ($P$) vs. Caratteristiche Non Protette ($N$): $P$ contiene attributi sensibili (ad esempio, genere); $N$ contiene gli altri.
• Spiegazione Abductive (AXp): Un sottoinsieme di caratteristiche $S$ tale che fissare i valori di $S$ a quelli dell'istanza $x$ garantisce l'output del classificatore $\kappa(x)$, considerando solo le istanze in $F[C]$.
• Spiegazione Implicante Primo (PI-explanation): Un AXp che non è strettamente assorbito da un altro AXp. Negli spazi vincolati, l'assorbimento è definito dall'implicazione logica all'interno di $F[C]$, non solo dall'inclusione insiemistica.
• PI-explanation Equa: Una PI-explanation che non contiene nessuna caratteristica protetta ($S \cap P = \emptyset$).

Definizioni Proposte di Equità

Il paper propone tre distinte definizioni per l'equità di un classificatore $\kappa$:

1. Equità attraverso l'Ignoranza Vincolata (Constrained FTU):

   • Per ogni $x, y \in F[C]$, se $x_N = y_N$ (le caratteristiche non protette sono identiche), allora $\kappa(x) = \kappa(y)$.
   • Questo garantisce che la decisione dipenda solo dalle caratteristiche non protette all'interno dello spazio valido.

2. Equità Esistenziale:

   • Per ogni decisione $\kappa(x) = c$, esiste almeno una PI-explanation equa.
   • Significato: Esiste alcuna ragione valida per la decisione che non si basa su caratteristiche protette.

3. Equità Universale:

   • Per ogni decisione $\kappa(x) = c$, tutte le PI-explanation sono eque.
   • Significato: Ogni motivo minimo per la decisione evita le caratteristiche protette.

Analisi Teorica

Gli autori analizzano le relazioni tra queste definizioni in diversi scenari di vincoli:

• Vincoli tra $P$ e $N$: Ignorarli può alterare drasticamente le valutazioni dell'equità. Una decisione può essere universalmente equa in $F[C]$ ma apparire non equa in $F$ non vincolato, o viceversa.
• Vincoli solo all'interno di $P$: Se i vincoli esistono solo tra le caratteristiche protette, l'esistenza di una PI-explanation equa è preservata dagli spazi non vincolati a quelli vincolati (Proposizione 1).
• Vincoli solo all'interno di $N$: L'esistenza di una PI-explanation equa è indipendente da questi vincoli (Proposizione 2). Tuttavia, i vincoli all'interno di $N$ possono creare PI-explanation non eque che non esistevano nello spazio non vincolato (Esempio 7).

Condizioni Speciali per l'Equivalenza

Il paper identifica le condizioni in cui le definizioni complesse (Esistenziale/Universale) si semplificano nella più facile da verificare Constrained FTU:

• Vincoli Lassi: Se nessuna assegnazione parziale di una caratteristica protetta assorbe strettamente l'assegnazione di tutte le caratteristiche non protette, allora la Constrained FTU implica l'Equità Esistenziale.
• Classificatori Svincolati (Disentangled): Un classificatore è "svincolato" se l'insieme delle caratteristiche non protette $N$ è un AXp debole non strettamente assorbito da alcun AXp non equo. Questo garantisce l'Equità Esistenziale.

3. Contributi Chiave

1. Formalizzazione dell'Equità con Vincoli: Il paper va oltre la definizione standard di "ignoranza" integrando i vincoli logici direttamente nella definizione delle spiegazioni (PI-explanation).
2. Dimostrazione dell'Impatto dei Vincoli: Attraverso molteplici esempi (ad esempio, congedo di maternità, agenzie di adozione), gli autori dimostrano che ignorare i vincoli porta a valutazioni dell'equità errate.
3. Gerarchia delle Definizioni di Equità: Il paper stabilisce le relazioni logiche tra Constrained FTU, Equità Esistenziale ed Equità Universale.
   • Universale $\implies$ Esistenziale $\implies$ Constrained FTU.
   • Le implicazioni inverse generalmente non valgono a meno che non siano soddisfatte condizioni specifiche (come "vincoli lassi" o "nessun vincolo tra P e N").
4. Analisi della Complessità: Gli autori mappano la complessità computazionale della verifica di queste nozioni di equità all'interno della Gerarchia Polinomiale.

4. Risultati e Analisi della Complessità

Il paper fornisce un'analisi rigorosa della complessità per testare queste definizioni di equità:

Insight Chiave sulla Complessità:

• Testare la Constrained FTU è computazionalmente fattibile (coNP-completo) e può essere gestito da risolutore SAT standard.
• Testare l'Equità Esistenziale/Universale è significativamente più difficile ($\Pi^P_3$ o $\Pi^P_4$), richiedendo risolutore di Formule Booleane Quantificate (QBF).
• Implicazione Pratica: Gli autori propongono di utilizzare controlli di "Vincoli Lassi" o "Classificatori Svincolati" (che sono $\Pi^P_2$) come condizioni sufficienti per garantire l'Equità Esistenziale, permettendo l'uso di risolutore SAT più semplici invece di risolutore QBF.

5. Significato e Conclusione

• Fondamento Teorico: Il paper stabilisce che l'equità non può essere valutata nel vuoto; la struttura logica dello spazio delle caratteristiche (vincoli) altera fondamentalmente la definizione di una "ragione" per una decisione.
• Guida Pratica: Avverte i professionisti che gli strumenti standard di equità (che spesso ignorano i vincoli) possono produrre risultati fuorvianti.
• Compromesso: Esiste un compromesso tra la rigidità della definizione di equità e la tracciabilità computazionale.
  • Equità Universale è la più rigorosa ma la più difficile da verificare.
  • Constrained FTU è la più facile da verificare ma potrebbe non cogliere casi in cui una decisione dipende tecnicamente da caratteristiche protette tramite vincoli.
• Direzioni Future: Gli autori suggeriscono di estendere questo quadro logico per gestire le correlazioni statistiche ed esplorare la "scelta delle caratteristiche protette" utilizzando grafi causali (Equità attraverso l'Indipendenza Causale - FTCI).

In sintesi, questo paper sostiene che l'equità è dipendente dal contesto dei vincoli delle caratteristiche. Fornisce un quadro formale per definire l'equità tramite spiegazioni implicanti prime e offre una roadmap per verificare queste definizioni, bilanciando rigore teorico e fattibilità computazionale.