Explaining Rankings with Hidden Group Bonuses

Résumé Technique : Explication des Classements avec Bonus de Groupe Cachés

Formulation du Problème
L'article aborde le problème d'expliquer les classements observés de candidats lorsque le mécanisme de notation sous-jacent implique une fonction d'utilité linéaire augmentée de bonus de groupe additifs cachés. Dans de nombreux scénarios réels (par exemple, les admissions universitaires, le recrutement), les classements sont déterminés non seulement par des attributs de notation observables (par exemple, les scores aux tests), mais aussi par des attributs sensibles (par exemple, le genre, le statut socioéconomique) qui déclenchent des augmentations additives spécifiques au groupe pour promouvoir l'équité ou la diversité. Ces attributs sensibles et les valeurs exactes des bonus sont souvent inobservés par les auditeurs externes.

Les auteurs formalisent deux variantes de ce problème d'« explication de classement » :

1. Bonus de Groupe Singleton pour Classement Linéaire (SGBLR) : Étant donné un ensemble de données et un classement cible, déterminer s'il existe une fonction d'utilité linéaire et un vecteur de bonus avec au plus $k$ entrées non nulles (bonus arbitraires attribués à des éléments individuels) qui reproduisent le classement.
2. Bonus de Groupe $g$ pour Classement Linéaire ($g$-GBLR) : Étant donné un ensemble de données, un classement cible et un budget de $g$ groupes, déterminer s'il existe une fonction d'utilité linéaire et un ensemble de $g$ groupes disjoints, chacun recevant un bonus additif spécifique, qui reproduisent le classement.

Méthodologie
L'article propose une approche duale combinant des algorithmes géométriques et la Programmation Linéaire en Nombres Entiers Mixtes (MILP).

1. Algorithme Géométrique (ERMB) :

   • Pour le problème SGBLR, les auteurs utilisent le concept d'arrangements d'hyperplans. Ils définissent des « hyperplans de comparaison » dans l'espace des poids de dimension $d$ où deux tuples ont des scores égaux. Ces hyperplans partitionnent l'espace des poids en régions, chacune correspondant à un classement linéaire unique.
   • L'algorithme énumère ces régions pour trouver tous les classements linéaires réalisables. Pour chaque classement réalisable, il calcule la plus longue sous-séquence commune (LCS) avec le classement cible. Les tuples ne faisant pas partie de la LCS sont identifiés comme des candidats pour recevoir le bonus additif.
   • Cette approche est étendue à la variante $g$-GBLR en augmentant l'espace des caractéristiques de $g$ dimensions (une par groupe) et en employant une routine de programmation dynamique LCS budgétisée.
   • Complexité : L'algorithme s'exécute en temps $O(n^{2d+1} \log n)$, ce qui est polynomial pour des dimensions $d$ et des groupes $g$ constants, mais exponentiel en $d$.

2. Formulations MILP :

   • Pour résoudre les problèmes d'évolutivité inhérents à l'approche géométrique pour des ensembles de données plus volumineux, les auteurs formulent le problème comme un Programme Linéaire en Nombres Entiers Mixtes (MILP).
   • MILPBase : Une formulation générique codant les contraintes de classement, la capacité des groupes et les indicateurs d'appartenance binaire.
   • MILPRefined : Une formulation améliorée intégrant des contraintes spécifiques au domaine pour améliorer l'efficacité du solveur et la stabilité numérique. Les raffinements clés incluent :
     • Un ordre strict avec une petite tolérance $\epsilon$ pour éviter les égalités.
     • Des bonus additifs bornés pour empêcher la domination des caractéristiques linéaires.
     • Des poids de caractéristiques non négatifs (courant dans les contextes de notation).
     • Élagage par Skyline : Une étape de prétraitement qui identifie les tuples « dominés » (ceux avec des scores plus faibles dans toutes les caractéristiques mais un rang plus élevé) et force l'attribution d'un bonus, réduisant considérablement l'espace de recherche.

3. Résultats de Dureté :

   • Les auteurs prouvent que SGBLR est NP-difficile via une réduction depuis le problème Max-1-in-2-SAT. Cela établit que la dépendance exponentielle à la dimension $d$ dans l'algorithme géométrique est inévitable (en supposant $P \neq NP$).

Contributions Clés

• Cadre Formel : L'article initie l'étude formelle de l'apprentissage de fonctions d'utilité linéaires avec des bonus de groupe additifs cachés pour expliquer les classements, se distinguant des travaux antérieurs qui supposent une visibilité complète des caractéristiques ou se concentrent uniquement sur les contraintes d'équité dans la sélection top-$k$.
• Solutions Algorithmiques :
  • Un algorithme exact et constructif (ERMB) basé sur les arrangements d'hyperplans pour des dimensions constantes.
  • Un cadre évolutif basé sur le MILP (MILPRefined) qui exploite les solveurs modernes et les heuristiques de domaine (élagage par skyline) pour gérer des données réelles à grande échelle.
• Analyse de Complexité : Établissement de la NP-difficulté pour le problème général, clarifiant les limites théoriques des solutions exactes.
• Validation Empirique : Expériences extensives sur des données synthétiques et réelles (spécifiquement un ensemble de données de 384 977 candidats aux examens JEE).

Résultats Expérimentaux

• Évolutivité : L'algorithme géométrique ERMB est limité à de petites instances (par exemple, $n \le 5\,000$ pour des données 2D) en raison de sa haute complexité. En revanche, les formulations MILP démontrent une forte évolutivité.
  • Pour des données synthétiques, MILPRefined a géré avec succès jusqu'à 75 000 tuples en 2D et jusqu'à 50 000 tuples dans des dimensions allant jusqu'à $d=17$ (pour $g=1$).
  • Sur l'ensemble de données JEE réel ($\approx 300\,000$ tuples), MILPRefined a résolu avec succès le problème $g$-GBLR pour $g=1$ et $g=2$ dans le délai de 1800 secondes.
• Qualité de la Solution : Les méthodes basées sur le MILP ont récupéré exactement les structures de bonus cachées et les poids dans des paramètres synthétiques où la vérité terrain était connue. Elles ont nettement surpassé les bases de référence (Régression Ordinale, Régression Logistique et Recherche Locale), qui nécessitaient beaucoup plus de tuples pour se voir attribuer des bonus afin d'expliquer les mêmes classements.
• Sensibilité : Le temps d'exécution des solveurs MILP s'est avéré sensible au paramètre de taille de groupe $k$ et à la dimensionalité $d$, l'efficacité de l'élagage par skyline diminuant à mesure que $d$ augmente.

Signification et Revendications
Les auteurs positionnent ce travail comme une contribution à la science des données digne de confiance et responsable, spécifiquement dans les domaines de l'audit algorithmique et de l'explicabilité.

• Audit : La méthode sert d'outil pour vérifier si un classement observé respecte les contraintes d'équité prévues. Si la méthode ne peut pas trouver une fonction linéaire avec les bonus de groupe requis qui explique le classement, elle fournit des preuves que le classement peut violer les politiques d'équité.
• Interprétabilité : Lorsqu'un classement peut être expliqué par le modèle, les poids appris révèlent l'importance relative des attributs, tandis que les bonus inférés quantifient l'avantage attribué à des groupes spécifiques.
• Nouveauté : L'article revendique être le premier à aborder la variante spécifique d'explication de classement où les caractéristiques sensibles sont inobservées mais influencent les résultats par le biais de bonus de groupe additifs, capturant un défi nuancé dans les systèmes de classement équitables que les modèles linéaires précédents n'avaient pas abordé.

L'article conclut modestement, notant que bien que leur approche soit efficace pour les modèles linéaires, l'extension de ces méthodes à des fonctions d'utilité non linéaires ou à des modèles de bonus multiplicatifs reste une direction de recherche ouverte. Ils soulignent également le lien avec la dureté d'approximation, suggérant que la conception d'algorithmes d'approximation efficaces pour ce problème pourrait être théoriquement difficile.