Explaining Rankings with Hidden Group Bonuses

Resumen Técnico: Explicación de Clasificaciones con Bonificaciones Ocultas de Grupo

Formulación del Problema
El artículo aborda el problema de explicar las clasificaciones observadas de candidatos cuando el mecanismo de puntuación subyacente implica una función de utilidad lineal aumentada por bonificaciones aditivas ocultas y específicas de grupo. En muchos escenarios del mundo real (por ejemplo, admisiones universitarias, contratación), las clasificaciones no se determinan únicamente por atributos de puntuación observables (por ejemplo, puntuaciones de exámenes), sino también por atributos sensibles (por ejemplo, género, estatus socioeconómico) que desencadenan bonificaciones aditivas específicas de grupo para promover la equidad o la diversidad. Estos atributos sensibles y los valores exactos de las bonificaciones a menudo no son observados por auditores externos.

Los autores formalizan dos variantes de este problema de "explicación de clasificaciones":

1. Bonificación Lineal de Grupo Único (SGBLR): Dado un conjunto de datos y una clasificación objetivo, determinar si existe una función de utilidad lineal y un vector de bonificaciones con a lo sumo $k$ entradas no nulas (bonificaciones arbitrarias a elementos individuales) que reproduzca la clasificación.
2. Bonificación Lineal de $g$ Grupos ($g$-GBLR): Dado un conjunto de datos, una clasificación objetivo y un presupuesto de $g$ grupos, determinar si existe una función de utilidad lineal y un conjunto de $g$ grupos disjuntos, cada uno recibiendo una bonificación aditiva específica, que reproduzca la clasificación.

Metodología
El artículo propone un enfoque dual que combina algoritmos geométricos y Programación Lineal Entera Mixta (MILP).

1. Algoritmo Geométrico (ERMB):

   • Para el problema SGBLR, los autores utilizan el concepto de arreglos de hiperplanos. Definen "hiperplanos de comparación" en el espacio de pesos de $d$ dimensiones donde dos tuplas tienen puntuaciones iguales. Estos hiperplanos dividen el espacio de pesos en regiones, cada una correspondiente a una clasificación lineal única.
   • El algoritmo enumera estas regiones para encontrar todas las clasificaciones lineales realizables. Para cada clasificación realizable, calcula la Subsecuencia Común Más Larga (LCS) con la clasificación objetivo. Las tuplas que no forman parte de la LCS se identifican como candidatas para recibir la bonificación aditiva.
   • Este enfoque se extiende a la variante $g$-GBLR aumentando el espacio de características con $g$ dimensiones (una por grupo) y empleando una rutina de programación dinámica de LCS con presupuesto.
   • Complejidad: El algoritmo se ejecuta en un tiempo $O(n^{2d+1} \log n)$, que es polinomial para dimensiones $d$ y grupos $g$ constantes, pero exponencial en $d$.

2. Formulaciones MILP:

   • Para abordar los problemas de escalabilidad inherentes al enfoque geométrico en conjuntos de datos más grandes, los autores formulan el problema como un Programa Lineal Entero Mixto (MILP).
   • MILPBase: Una formulación genérica que codifica restricciones de clasificación, capacidad de grupo e indicadores de membresía binaria.
   • MILPRefined: Una formulación mejorada que incorpora restricciones específicas del dominio para mejorar la eficiencia del solucionador y la estabilidad numérica. Las refinaciones clave incluyen:
     • Ordenamiento estricto con una pequeña tolerancia $\epsilon$ para evitar empates.
     • Bonificaciones aditivas acotadas para evitar la dominancia sobre las características lineales.
     • Pesos de características no negativos (comunes en contextos de puntuación).
     • Poda del Horizonte (Skyline Pruning): Un paso de preprocesamiento que identifica tuplas "dominadas" (aquellas con puntuaciones más bajas en todas las características pero más altas en la clasificación) y las obliga a recibir una bonificación, reduciendo significativamente el espacio de búsqueda.

3. Resultados de Dureza:

   • Los autores demuestran que SGBLR es NP-difícil mediante una reducción desde el problema Max-1-in-2-SAT. Esto establece que la dependencia exponencial de la dimensión $d$ en el algoritmo geométrico es inevitable (asumiendo $P \neq NP$).

Contribuciones Clave

• Marco Formal: El artículo inicia el estudio formal del aprendizaje de funciones de utilidad lineal con bonificaciones aditivas ocultas de grupo para explicar clasificaciones, distinguiéndolo de trabajos anteriores que asumen visibilidad completa de las características o se centran únicamente en restricciones de equidad en la selección de los $k$ primeros.
• Soluciones Algorítmicas:
  • Un algoritmo exacto y constructivo (ERMB) basado en arreglos de hiperplanos para dimensiones constantes.
  • Un marco escalable basado en MILP (MILPRefined) que aprovecha solucionadores modernos y heurísticas de dominio (poda del horizonte) para manejar datos reales a gran escala.
• Análisis de Complejidad: Establecimiento de la NP-dificultad para el problema general, aclarando los límites teóricos de las soluciones exactas.
• Validación Empírica: Experimentos extensos en datos sintéticos y del mundo real (específicamente un conjunto de datos de 384.977 candidatos al examen JEE).

Resultados Experimentales

• Escalabilidad: El algoritmo geométrico ERMB está limitado a instancias pequeñas (por ejemplo, $n \le 5.000$ para datos 2D) debido a su alta complejidad. Por el contrario, las formulaciones MILP demuestran una fuerte escalabilidad.
  • Para datos sintéticos, MILPRefined manejó con éxito hasta 75.000 tuplas en 2D y hasta 50.000 tuplas en dimensiones de hasta $d=17$ (para $g=1$).
  • En el conjunto de datos real JEE ($\approx 300.000$ tuplas), MILPRefined resolvió con éxito el problema $g$-GBLR para $g=1$ y $g=2$ dentro del tiempo límite de 1800 segundos.
• Calidad de la Solución: Los métodos basados en MILP recuperaron exactamente las estructuras de bonificación ocultas y los pesos en configuraciones sintéticas donde se conocía la verdad fundamental. Superaron significativamente a las líneas base (Regresión Ordinal, Regresión Logística y Búsqueda Local), que requirieron asignar bonificaciones a muchas más tuplas para explicar las mismas clasificaciones.
• Sensibilidad: Se encontró que el tiempo de ejecución de los solucionadores MILP es sensible al parámetro de tamaño de grupo $k$ y a la dimensionalidad $d$, disminuyendo la efectividad de la poda del horizonte a medida que aumenta $d$.

Significado y Afirmaciones
Los autores posicionan este trabajo como una contribución a la ciencia de datos confiable y responsable, específicamente en los dominios de auditoría algorítmica y explicabilidad.

• Auditoría: El método sirve como una herramienta para verificar si una clasificación observada se adhiere a las restricciones de equidad previstas. Si el método no puede encontrar una función lineal con las bonificaciones de grupo requeridas que explique la clasificación, proporciona evidencia de que la clasificación puede violar las políticas de equidad.
• Interpretabilidad: Cuando una clasificación puede ser explicada por el modelo, los pesos aprendidos revelan la importancia relativa de los atributos, mientras que las bonificaciones inferidas cuantifican la ventaja asignada a grupos específicos.
• Novelty: El artículo afirma ser el primero en abordar la variante específica de explicación de clasificaciones donde las características sensibles no son observadas pero influyen en los resultados a través de bonificaciones aditivas de grupo, capturando un desafío matizado en los sistemas de clasificación justa que los modelos lineales anteriores no abordaron.

El artículo concluye modestamente, señalando que, aunque su enfoque es efectivo para modelos lineales, extender estos métodos a funciones de utilidad no lineales o modelos de bonificación multiplicativa sigue siendo una dirección de investigación abierta. También destacan la conexión con la dureza de aproximación, sugiriendo que diseñar algoritmos de aproximación eficientes para este problema puede ser teóricamente desafiante.