Fairness of Classifiers in the Presence of Constraints between Features

A continuación se presenta un resumen técnico detallado del artículo "Justicia de los clasificadores en presencia de restricciones entre características" de Martin C. Cooper e Imane Bousdira.

1. Planteamiento del Problema

El artículo aborda una brecha crítica en la definición y evaluación de la justicia en los clasificadores de Aprendizaje Automático: la presencia de restricciones lógicas entre características.

• Contexto: Las definiciones estándar de justicia (por ejemplo, Justicia a través de la Desatención) a menudo asumen que una decisión es justa si no depende de características protegidas (por ejemplo, género, raza).
• El Problema: En escenarios del mundo real, las características rara vez son independientes. Existen restricciones debido a:
  • Codificación: por ejemplo, codificación one-hot donde exactamente una característica booleana debe ser verdadera.
  • Lógica del mundo real: por ejemplo, "Si una persona está de licencia por maternidad, debe ser mujer y estar empleada".
• La Consecuencia: Ignorar estas restricciones puede conducir a falsos positivos (considerar injusto a un clasificador justo) o falsos negativos (considerar justo a un clasificador injusto).
  • Ejemplo: Un modelo podría parecer depender del género porque la salida del modelo cambia cuando el género cambia, pero si la restricción implica que cambiar el género también fuerza un cambio en otra característica (como el estado laboral), la decisión podría ser en realidad independiente del género en el espacio de características válido.
• Objetivo: Definir formalmente la justicia en presencia de restricciones ($C$) y analizar la complejidad computacional de verificar estas definiciones.

2. Metodología y Conceptos Centrales

Los autores utilizan Explicaciones Abductivas (AXp) e Implicantes Primos (PI) dentro de un espacio de características restringido.

Definiciones Clave

• Espacio de Características ($F$): El producto cartesiano de los dominios de las características.
• Restricciones ($C$): Un conjunto de reglas lógicas que restringen las instancias válidas. El espacio válido es $F[C]$.
• Características Protegidas ($P$) vs. No Protegidas ($N$): $P$ contiene atributos sensibles (por ejemplo, género); $N$ contiene los demás.
• Explicación Abductiva (AXp): Un subconjunto de características $S$ tal que fijar los valores de $S$ a los de la instancia $x$ garantiza la salida del clasificador $\kappa(x)$, considerando solo instancias en $F[C]$.
• Explicación de Implicante Primo (PI-explicación): Una AXp que no está estrictamente subsumida por otra AXp. En espacios restringidos, la subsumción se define por la implicación lógica dentro de $F[C]$, no solo por la inclusión de conjuntos.
• PI-explicación justa: Una PI-explicación que no contiene ninguna característica protegida ($S \cap P = \emptyset$).

Definiciones Propuestas de Justicia

El artículo propone tres definiciones distintas para la justicia de un clasificador $\kappa$:

1. Justicia a través de la Desatención Restringida (FTU):

   • Para todo $x, y \in F[C]$, si $x_N = y_N$ (las características no protegidas son idénticas), entonces $\kappa(x) = \kappa(y)$.
   • Esto asegura que la decisión depende solo de las características no protegidas dentro del espacio válido.

2. Justicia Existencial:

   • Para cada decisión $\kappa(x) = c$, existe al menos una PI-explicación justa.
   • Significado: Hay alguna razón válida para la decisión que no depende de características protegidas.

3. Justicia Universal:

   • Para cada decisión $\kappa(x) = c$, todas las PI-explicaciones son justas.
   • Significado: Cada razón mínima para la decisión evita las características protegidas.

Análisis Teórico

Los autores analizan las relaciones entre estas definiciones bajo diferentes escenarios de restricciones:

• Restricciones entre $P$ y $N$: Ignorarlas puede alterar drásticamente las evaluaciones de justicia. Una decisión puede ser universalmente justa en $F[C]$ pero parecer injusta en $F$ sin restricciones, o viceversa.
• Restricciones solo dentro de $P$: Si las restricciones existen solo entre características protegidas, la existencia de una PI-explicación justa se preserva de espacios sin restricciones a espacios restringidos (Proposición 1).
• Restricciones solo dentro de $N$: La existencia de una PI-explicación justa es independiente de estas restricciones (Proposición 2). Sin embargo, las restricciones dentro de $N$ pueden crear PI-explicaciones injustas que no existían en el espacio sin restricciones (Ejemplo 7).

Condiciones Especiales para la Equivalencia

El artículo identifica condiciones donde las definiciones complejas (Existencial/Universal) se simplifican a la FTU Restringida, más fácil de verificar:

• Restricciones Laxas: Si ninguna asignación parcial de una característica protegida subsume estrictamente la asignación de todas las características no protegidas, entonces la FTU Restringida implica Justicia Existencial.
• Clasificadores Desenredados: Un clasificador es "desenredado" si el conjunto de características no protegidas $N$ es una AXp débil no estrictamente subsumida por ninguna AXp injusta. Esto garantiza la Justicia Existencial.

3. Contribuciones Clave

1. Formalización de la Justicia con Restricciones: El artículo va más allá de la definición estándar de "desatención" integrando las restricciones lógicas directamente en la definición de explicaciones (PI-explicaciones).
2. Demostración del Impacto de las Restricciones: A través de múltiples ejemplos (por ejemplo, licencia por maternidad, agencias de adopción), los autores demuestran que ignorar las restricciones conduce a evaluaciones de justicia incorrectas.
3. Jerarquía de Definiciones de Justicia: El artículo establece las relaciones lógicas entre FTU Restringida, Justicia Existencial y Justicia Universal.
   • Universal $\implies$ Existencial $\implies$ FTU Restringida.
   • Las implicaciones inversas generalmente no se sostienen a menos que se cumplan condiciones específicas (como "restricciones laxas" o "sin restricciones entre P y N").
4. Análisis de Complejidad: Los autores mapean la complejidad computacional de verificar estas nociones de justicia dentro de la Jerarquía Polinómica.

4. Resultados y Análisis de Complejidad

El artículo proporciona un análisis riguroso de la complejidad para probar estas definiciones de justicia:

Noción de Justicia	Clase de Complejidad	Notas
Existencia de PI-explicación justa (para una sola decisión)	$\Sigma^P_3$	Implica alternancia de cuantificadores $\exists \forall \exists$.
Existencia de PI-explicación injusta	$\Sigma^P_3$	Complemento de lo anterior.
Prueba de Justicia Existencial (Clasificador)	$\Pi^P_4$	Requiere verificar todas las instancias ($\forall x$) para la propiedad $\Sigma^P_3$.
Prueba de Justicia Universal (Clasificador)	$\Pi^P_3$	Equivalente a verificar que no existe ninguna explicación injusta para ninguna instancia.
Prueba de FTU Restringida	coNP-completo	Se puede resolver mediante una sola llamada a un solucionador SAT (verificando si $\exists x, y$ con la misma $N$ pero salidas diferentes).

Insight Clave de Complejidad:

• Probar la FTU Restringida es computacionalmente viable (coNP-completo) y puede manejarse con solucionadores SAT estándar.
• Probar la Justicia Existencial/Universal es significativamente más difícil ($\Pi^P_3$ o $\Pi^P_4$), requiriendo solucionadores de Fórmulas Booleanas Cuantificadas (QBF).
• Implicación Práctica: Los autores proponen utilizar verificaciones de "Restricciones Laxas" o "Desenredados" (que son $\Pi^P_2$) como condiciones suficientes para garantizar la Justicia Existencial, permitiendo el uso de solucionadores SAT más simples en lugar de solucionadores QBF.

5. Significado y Conclusión

• Fundamento Teórico: El artículo establece que la justicia no puede evaluarse en el vacío; la estructura lógica del espacio de características (restricciones) altera fundamentalmente la definición de una "razón" para una decisión.
• Guía Práctica: Advierte a los profesionales que las herramientas estándar de justicia (que a menudo ignoran las restricciones) pueden producir resultados engañosos.
• Compensación: Existe una compensación entre la rigurosidad de la definición de justicia y la viabilidad computacional.
  • La Justicia Universal es la más estricta pero la más difícil de verificar.
  • La FTU Restringida es la más fácil de verificar pero puede pasar por alto casos donde una decisión depende técnicamente de características protegidas a través de restricciones.
• Direcciones Futuras: Los autores sugieren extender este marco lógico para manejar correlaciones estadísticas y explorar la "elección de características protegidas" utilizando gráficos causales (Justicia a través de la Independencia Causal - FTCI).

En resumen, este artículo argumenta que la justicia depende del contexto de las restricciones de características. Proporciona un marco formal para definir la justicia mediante explicaciones de implicantes primos y ofrece una hoja de ruta para verificar estas definiciones, equilibrando el rigor teórico con la viabilidad computacional.