Uncovering Discrimination Clusters: Quantifying and Explaining Systematic Fairness Violations

1. El Problema: Más allá de la Discriminación Individual

El trabajo aborda una limitación crítica en las técnicas actuales de verificación de equidad (fairness) para sistemas de aprendizaje automático, específicamente Redes Neuronales Profundas (DNN).

• Limitación del estado del arte: La mayoría de los métodos se centran en la equidad individual, que busca pares de entradas que difieren únicamente en atributos protegidos (raza, género) pero producen resultados distintos. Esto detecta casos aislados de discriminación.
• La brecha: Estos enfoques fallan en capturar patrones más amplios de discriminación sistemática y agrupada. Un sistema podría no violar la equidad individual en un par específico, pero podría mostrar una "arbitrariedad" significativa en un vecindario de entrada, donde pequeñas variaciones en atributos protegidos conducen a múltiples resultados divergentes y no coherentes para individuos similares.
• Definición del problema: Los autores proponen generalizar la violación de equidad individual a un concepto de agrupación de discriminación (discrimination clustering). Un sistema es k-discriminante si, dentro de un grupo de $K$ entradas que comparten los mismos atributos no protegidos pero difieren en los protegidos, el modelo produce $k$ resultados distintos ($2 \le k \le K$).

2. Metodología: El Marco Híbrido HYFAIR

Los autores presentan HYFAIR, una técnica híbrida que combina verificación formal y búsqueda estocástica para detectar, cuantificar y explicar estos clusters de discriminación. El flujo de trabajo consta de tres fases principales:

A. Certificación de Equidad 2-Fair (Búsqueda de Semillas)

• Enfoque: Utiliza Programación Lineal Entera Mixta (MILP) para verificar formalmente la propiedad de equidad individual (2-fairness).
• Mecanismo: Codifica la DNN como un problema de optimización lineal. Si el solver encuentra una solución factible, genera un contraejemplo (un par de entradas con 2 resultados distintos).
• Ventaja: A diferencia de los métodos basados en SMT (como FAIRIFY), el uso de MILP permite encontrar contraejemplos más rápidamente y en regiones diferentes del espacio de búsqueda, sirviendo como "semillas" robustas para la siguiente fase.

B. Búsqueda de Máxima k-Discriminación (Cuantificación)

• Estrategia: Una vez obtenida una semilla (un caso de discriminación 2), HYFAIR inicia una búsqueda aleatoria local para maximizar el valor de $k$.
• Algoritmos: Compara tres estrategias:
  1. Random Walk (RW): Búsqueda aleatoria sin guía.
  2. Simulated Annealing (SA): Utiliza un algoritmo de recocido simulado para escapar de óptimos locales y explorar el espacio de entrada.
  3. SA + KNN: Combina SA con vecinos más cercanos para refinar la búsqueda.
• Objetivo: Identificar la región del espacio de entrada donde las perturbaciones en los atributos protegidos generan el mayor número de clusters de resultados distintos, revelando la magnitud de la arbitrariedad del modelo.

C. Explicación y Mitigación (Depuración)

• Innovación: Para explicar por qué ocurren estos clusters, los autores proponen un método novedoso que va más allá de las explicaciones locales estándar (como LIME).
• Técnica:
  1. Genera muestras en el vecindario de los casos de máxima discriminación.
  2. Entrena un árbol de decisión para clasificar estas muestras en "alta discriminación" vs. "baja discriminación".
  3. Extrae reglas lógicas (predicados) que definen las condiciones de los atributos no protegidos que desencadenan la discriminación arbitraria.
• Mitigación: Estas reglas se utilizan como "guardarraíles" (guardrails) para bloquear consultas sensibles o para reentrenar el modelo con datos aumentados, reduciendo así la discriminación.

3. Contribuciones Clave

1. Nuevo Concepto de Equidad: Introducción de la noción de $k$-discriminante, que cuantifica la severidad de la discriminación mediante la identificación de clusters de resultados divergentes, superando la visión binaria de la equidad individual.
2. Marco Híbrido (HYFAIR): Integración de verificación formal (MILP) y búsqueda estocástica (Simulated Annealing) para lograr tanto garantías formales (ausencia de violaciones) como la detección de violaciones severas que los métodos puramente simbólicos no pueden escalar.
3. Explicabilidad Interpretativa: Desarrollo de un método de explicación basado en árboles de decisión que identifica las condiciones lógicas compartidas en los casos de discriminación agrupada, ofreciendo reglas accionables para los desarrolladores.
4. Validación Empírica: Demostración de que el enfoque híbrido supera a las técnicas de vanguardia en la detección de casos y en la generación de explicaciones robustas.

4. Resultados Experimentales

Los autores evaluaron HYFAIR en 20 DNNs (benchmarks de Kaggle y literatura) utilizando conjuntos de datos como Adult Census y Bank Marketing.

• RQ1 (Eficiencia vs. FAIRIFY): HYFAIR (MILP) superó a FAIRIFY (SMT) en el 85% de los casos, encontrando más instancias de discriminación individual (IDs) en menos tiempo. En 5 casos, FAIRIFY no encontró ninguna instancia, mientras que HYFAIR sí.
• RQ2 (Búsqueda de k): El algoritmo de Simulated Annealing (SA) fue superior a Random Walk y SA+KNN, identificando instancias con el máximo $k$ en el 94% de los casos y encontrando el primer caso de máxima discriminación más rápido en el 72% de los benchmarks.
• RQ3 (Explicabilidad): Comparado con LIME, HYFAIR proporcionó explicaciones más concisas (menor tamaño) y robustas (mayor diferencia en $k$ al perturbar características). Además, cubrió un volumen de espacio de entrada significativamente mayor, lo que indica una mejor generalización de las reglas de discriminación.
• RQ4 (Mitigación): La aplicación de reglas derivadas de los árboles de decisión como guardarraíles redujo la tasa de éxito de reproducción de errores de equidad (de 87.7% a 36.3% en el benchmark AC2) y disminuyó el número de instancias discriminatorias. Se observó que la simple reentrenación sin reglas a menudo fallaba o incluso aumentaba la arbitrariedad máxima ($k$), mientras que la combinación de reglas y reentrenamiento fue más efectiva.

5. Significado e Impacto

Este trabajo es fundamental porque cambia el paradigma de la detección de sesgos en IA:

• De lo aislado a lo sistémico: Permite a los ingenieros de software no solo encontrar "bugs" de equidad aislados, sino entender la estructura y severidad de la discriminación sistemática.
• Acción Correctiva: Al proporcionar explicaciones lógicas (reglas de árbol de decisión) en lugar de solo puntuaciones de importancia de características, facilita la implementación de parches concretos y la reentrenamiento dirigido.
• Escalabilidad: Demuestra que la combinación de métodos formales y estocásticos es la vía más prometedora para analizar la equidad en modelos complejos y no lineales donde los métodos puramente formales fallan por costo computacional.

En resumen, HYFAIR ofrece una herramienta integral para diagnosticar, cuantificar y mitigar la discriminación algorítmica profunda, revelando patrones de arbitrariedad que de otro modo permanecerían ocultos bajo las métricas tradicionales de equidad individual.