Résumé technique : Le théorème Pokémon et autres résultats d'impossibilité de l'équité

Énoncé du problème

L'article aborde les limitations fondamentales de l'équité algorithmique, en investiguant spécifiquement si les résultats d'impossibilité connus (tels que la dichotomie Kleinberg–Mullainathan–Raghavan) sont des artefacts de critères scalaires spécifiques ou des propriétés structurelles inhérentes aux distributions présentant des taux de base inégaux. Deux questions principales sont posées :

1. Limite de la liste de contrôle finie : Une collection finie de critères d'équité moyenne linéaires (par exemple, la parité démographique, les chances égales) peut-elle certifier que deux distributions de groupes sont identiques, ou une violation résiduelle restera-t-elle toujours présente ?
2. Limite de l'apprentissage de représentations : L'apprentissage équitable de caractéristiques (apprendre un encodeur qui supprime l'information de groupe) peut-il contourner ces impossibilités en produisant une représentation où les prédicteurs en aval héritent de l'équité sans sacrifier l'utilité ?

La littérature existante présente souvent ces impossibilités comme des conflits entre des statistiques scalaires (par exemple, l'étalonnage contre l'équilibre des taux d'erreur). Les auteurs soutiennent que ce cadre scalaire obscurcit la structure géométrique sous-jacente et laisse ouverte la question de savoir si « plus » de critères pourraient combler l'écart.

Méthodologie

Les auteurs unifient ces contraintes d'équité en utilisant les espaces de Hilbert à noyau reproduisant (RKHS) et les encodages moyens.

• Géométrie RKHS : Ils modélisent les critères d'équité comme des contraintes linéaires sur les encodages moyens conditionnels $\mu_{P} = \mathbb{E}[\phi(X)]$ au sein d'un espace de Hilbert $\mathcal{H}$.
• Noyaux caractéristiques : En utilisant des noyaux caractéristiques, ils s'assurent que des distributions distinctes se mappent sur des encodages moyens distincts ($\mu_P \neq \mu_Q \iff P \neq Q$).
• Couplage de l'espérance totale : Le mécanisme central à l'origine des résultats d'impossibilité est la loi de l'espérance totale, qui couple les espérances conditionnelles de groupe à l'écart des taux de base ($\Delta p = p_a - p_b$).
• Analyse spectrale : L'article emploie des hypothèses de régularité spectrale (décroissance polynomiale des valeurs propres de l'opérateur de covariance regroupé et conditions de source) pour quantifier le taux auquel les violations résiduelles décroissent à mesure que le nombre de critères d'équité augmente.

Contributions clés

1. Théorème KMR renforcé

Les auteurs renforcent le résultat d'impossibilité classique de Kleinberg–Mullainathan–Raghavan (KMR). Ils démontrent que la contradiction entre l'étalonnage et l'équilibre conditionnel par classe tient même sous la condition plus faible d'impartialité conditionnelle par groupe ($\mathbb{E}[S|G=g] = p_g$), plutôt que d'exiger un étalonnage complet au sein du groupe. Cela montre que des scores mal étalonnés qui se contentent de suivre le taux de base moyen du groupe sont toujours soumis à l'impossibilité.

2. Le théorème Pokémon

Nommé d'après le slogan « Attrapez-les tous », ce théorème aborde la question de la liste de contrôle finie.

• Résultat qualitatif : Pour toute paire de groupes distincts ($P_a \neq P_b$) et tout ensemble fini de critères d'équité moyenne linéaires $\{v_1, \dots, v_m\}$ satisfaits par les groupes, il existe une violation résiduelle dans le complément orthogonal. Cette violation est témoin par le vecteur témoin de la Discrepancy Maximale Moyenne (MMD) $\delta / \|\delta\|_{\mathcal{H}}$.
• Résultat quantitatif : Sous régularité spectrale (décroissance polynomiale des valeurs propres) et une condition de source, la violation résiduelle minimax décroît au taux de Kolmogorov $m$-largeur $\Theta(m^{-2\alpha r})$. Cela implique que, bien que l'ajout de plus de critères réduise la violation maximale, elle ne disparaît jamais complètement pour un $m$ fini, sauf si les distributions sont identiques.

3. Impossibilité de l'apprentissage de caractéristiques équitable

L'article prouve que l'apprentissage de représentations équitables ne peut pas simultanément atteindre :

1. Parité distributionnelle : $\Phi(P_a) = \Phi(P_b)$ (la représentation est invariante par groupe).
2. Séparation conditionnelle par classe : La représentation préserve les distributions conditionnelles par classe distinctes ($\Phi(X) \perp\!\!\!\perp G | Y$).
3. Signal non trivial : La représentation conserve un pouvoir prédictif pour la variable de résultat $Y$.

Si les taux de base diffèrent ($p_a \neq p_b$), imposer à la fois la parité distributionnelle et la séparation conditionnelle par classe force un effondrement de classe ($\Phi(X) \perp\!\!\!\perp Y$), rendant la représentation inutile pour la prédiction.

4. Équité approximative et pont Pokémon–KMR

Les auteurs dérivent des bornes quantitatives pour l'équité approximative :

• Apprentissage de caractéristiques approximatif : Ils établissent une frontière de Pareto où le signal en aval utilisable (écart moyen conditionnel par classe) est borné par $(\epsilon + \rho) / |p_a - p_b|$, où $\epsilon$ est la violation de parité et $\rho$ la violation de séparation.
• Pont vers KMR : Ils montrent que lorsque le nombre de critères d'audit $m \to \infty$ et que les violations résiduelles s'annulent, les conditions approximatives retrouvent l'impossibilité exacte de KMR (la prédiction parfaite est la seule solution).

Résultats expérimentaux

L'article valide ces bornes théoriques sur des benchmarks d'équité standards (Adult Income, COMPAS, ACS PUMS) :

• Décroissance spectrale : Les graphiques empiriques de la MMD résiduelle par rapport au nombre de critères $m$ confirment le taux de décroissance polynomiale prédit par le théorème Pokémon. Le « budget » de MMD nécessaire pour satisfaire les critères varie selon le jeu de données (par exemple, COMPAS se concentre plus rapidement en raison d'une dimensionnalité plus faible).
• Frontières de Pareto : Les graphiques empiriques d'erreur par rapport à l'écart de parité démographique pour les classifieurs imposant la séparation s'alignent sur la borne inférieure théorique dérivée dans la section 6.2.
• Région interdite : Les expériences avec des encodeurs équitables (LFR, Fair-VAE, Debiasing Adversarial) montrent qu'aucune méthode ne remplit avec succès la région « interdite » en haut à gauche du graphique (faible écart de parité avec un fort signal conditionnel par classe), confirmant l'impossibilité de l'effondrement de classe.

Signification et affirmations

L'article prétend fournir un cadre géométrique unifié pour les résultats d'impossibilité de l'équité.

• Insight structurel : Il reformule les impossibilités de l'équité non pas comme un conflit de métriques scalaires spécifiques, mais comme une conséquence structurelle de la loi de l'espérance totale agissant sur des distributions avec des taux de base inégaux.
• Allocation de budget : Il reformule l'audit d'équité comme un problème d'allocation de budget où le « budget » total est la MMD entre les groupes. L'équité exacte nécessite d'épuiser ce budget, ce qui est impossible sans sacrifier l'utilité si les taux de base diffèrent.
• Implication pratique : Les résultats suggèrent que lorsque les groupes sont distributionnellement distincts, les interventions algorithmiques seules ne peuvent pas simultanément atteindre une équité parfaite et une utilité. L'article implique que des interventions politiques ou des disparités de traitement explicites peuvent être nécessaires dans de tels régimes, plutôt que de compter uniquement sur le nettoyage des caractéristiques ou l'optimisation sous contraintes.

Les auteurs maintiennent une position modeste, notant que leurs résultats sont observationnels et ne proposent pas de nouveaux algorithmes. Au lieu de cela, ils fournissent un « théorème d'impossibilité » théorique qui définit les limites de ce qui est réalisable dans l'apprentissage automatique équitable sous des taux de base inégaux.