🤖 machine learning

Diverse and Plausible Algorithmic Recourse via Tractable Recourse Distributions

L'article propose des « Distributions de Recours Traitables », un cadre probabiliste qui modélise l'espace du recours algorithmique réalisable sous la forme d'une distribution en forme fermée sur les issues favorables, permettant ainsi la génération d'alternatives diverses, plausibles et exploitables sans réentraîner le modèle sous-jacent.

Auteurs originaux : Anagha Sabu, Hrithik Suresh, Narayanan C. Krishnan

Publié 2026-08-06

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Anagha Sabu, Hrithik Suresh, Narayanan C. Krishnan

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un monde où un ordinateur décide de votre avenir. Il est le gardien de votre prêt, de votre entretien d'embauche ou de votre admission à l'université. Parfois, il dit « non ». Dans le passé, si vous demandiez pourquoi, l'ordinateur aurait pu donner une réponse vague ou simplement une liste de règles que vous avez enfreintes. Mais savoir pourquoi vous avez échoué ne vous aide pas à vous corriger. Vous avez besoin d'une carte. Vous avez besoin de savoir exactement quels changements vous pouvez opérer pour transformer ce « non » en un « oui ». C'est le cœur d'un domaine appelé le Recours Algorithmique. Voyez cela comme un GPS pour les décisions de vie : au lieu de simplement vous dire que vous êtes perdu, il suggère un itinéraire pour vous mener à votre destination.

Cependant, il y a un piège. La plupart des systèmes GPS ne proposent qu'un seul itinéraire. Mais dans la vie réelle, il existe souvent de nombreuses façons d'arriver au même endroit. Peut-être pouvez-vous obtenir un prêt en remboursant une carte de crédit, ou peut-être en obtenant un emploi mieux rémunéré, ou en trouvant un co-signataire. Différentes personnes ont différents outils, temps et contraintes. Un bon système ne devrait pas seulement vous donner un chemin rigide ; il devrait offrir un menu d'options réalistes et diverses qui s'adaptent réellement à votre vie. C'est le problème qu'un nouvel article de chercheurs de l'Institut Indien de Technologie de Palakkad tente de résoudre. Ils veulent s'éloigner de la recherche d'une seule réponse « parfaite » pour créer un paysage entier de solutions possibles, vous montrant les nombreuses voies vers la réussite.

L'ancienne méthode : chercher une aiguille unique dans une botte de foin

Imaginez que vous essayiez de trouver une clé spécifique dans une immense pièce désordonnée (la pièce représentant tous les changements que vous pourriez apporter à votre vie). L'ancienne méthode consistait à y envoyer un robot muni d'une lampe de poche pour trouver l'unique clé la plus proche de l'endroit où vous vous tenez actuellement. Le robot scannerait le sol, calculerait les distances et choisirait le meilleur emplacement. Si le robot trouvait une clé, tant mieux ! Mais qu'en est-il si cette clé se trouvait dans une partie de la pièce qui était en fait verrouillée ou dangereuse ? Ou si le robot passait à côté d'une clé parfaitement bonne située à quelques pas de lui parce qu'il était trop concentré sur la première ?

Les chercheurs soulignent que les méthodes existantes fonctionnent de cette manière. Elles traitent le problème comme un casse-tête mathématique pour trouver un ou quelques « contre-factuels » spécifiques (un mot savant pour les scénarios de type « et si »). Elles tentent de forcer la solution à être proche de votre situation actuelle et à impliquer le moins de changements possible. Mais ce faisant, elles passent souvent à côté du tableau d'ensemble. Elles pourraient vous donner une solution mathématiquement proche mais totalement irréaliste pour votre vie, ou elles pourraient vous donner dix solutions qui sont essentiellement la même chose, juste légèrement modifiées. C'est comme un GPS qui ne montrerait que l'itinéraire le plus court, même si cet itinéraire est une impasse, tout en ignorant les alternatives pittoresques et viables.

La nouvelle idée : une carte de probabilité des possibilités

Les auteurs, Anagha Sabu, Hrithik Suresh et Narayanan C. Krishnan, proposent une approche totalement différente. Au lieu de traquer une seule aiguille, ils veulent dessiner une carte de toute la pièce, montrant où toutes les bonnes clés sont susceptibles de se trouver. Ils appellent cela une Distribution de Recours Traitable (TRD).

Voyez cela comme ceci : imaginez que vous ayez une carte magique et lumineuse de toutes les façons d'obtenir l'approbation d'un prêt. Cette carte n'est pas seulement une liste de points ; c'est une carte de chaleur. Les zones les plus brillantes et les plus chaudes de la carte représentent les changements qui ont la plus grande probabilité de fonctionner, qui sont les plus proches de votre vie actuelle et qui ne nécessitent pas de changer trop de choses à la fois. Les zones plus sombres sont toujours possibles, mais elles nécessitent des sauts plus importants.

La magie de leur méthode réside dans la façon dont ils créent cette carte. Ils partent d'un modèle de ce à quoi ressemblent les personnes « réussies » (la distribution de la classe positive). Ensuite, ils utilisent un tour mathématique appelé inclinaison exponentielle (exponential tilting). Imaginez que vous ayez un sac de billes représentant tous les futurs possibles. La plupart des billes sont aléatoires. Mais vous voulez trouver celles qui sont proches de votre situation actuelle. Alors, vous placez un aimant sur le sac. L'aimant attire les billes qui sont proches de vous (proximité) et celles qui ne nécessitent pas de changer beaucoup de caractéristiques (parcimonie) vers le haut. Les billes qui sont loin ou qui nécessitent des changements massifs coulent vers le bas.

Parce qu'ils utilisent un type spécifique de structure mathématique appelée Circuit Probabiliste, ils peuvent effectuer ce tri et ce rapprochement de manière exacte et instantanée. Ils n'ont pas besoin de réentraîner tout le système pour chaque personne. Ils prennent simplement la carte existante, appliquent l'aimant (l'inclinaison), et voilà — vous avez une carte personnalisée pour cette personne spécifique.

Ce qu'ils ont découvert : un menu d'options réalistes

Les chercheurs ont testé cette idée sur des ensembles de données standards utilisés pour l'approbation de prêts et les scores de crédit, ainsi que sur des images (transformer l'image d'un 8 en un 0, ou d'un 7 en un 1). Voici ce qu'ils ont découvert :

1. La diversité sans le chaos
Lorsqu'ils ont laissé leur système échantillonner à partir de cette nouvelle carte, il a naturellement produit une grande variété de solutions différentes. Certaines personnes pourraient changer leurs revenus, d'autres leur dette, et d'autres encore leur historique d'emploi. Le système n'avait pas besoin d'une règle spéciale de « diversité » pour forcer cette variété ; la carte elle-même était diverse. En fait, ils ont constaté que même s'ils choisissaient simplement des échantillons aléatoires de la carte, ils obtenaient un bon mélange d'options. La seule chose qu'ils ont ajoutée est une étape de « regroupement » (clustering) pour s'assurer que la liste finale ne soit pas composée de dix copies de la même recommandation.

2. Rester réaliste (Plausibilité)
L'une des plus grandes craintes concernant ces systèmes est qu'ils puissent suggérer des changements fous ou impossibles, comme « déménager dans un autre pays » ou « changer d'âge ». Les chercheurs ont constaté que leur méthode maintenait les suggestions ancrées dans la réalité. Parce que la carte partait de données réelles sur des personnes ayant réussi, chaque suggestion était un scénario réaliste. Dans leurs tests, la « pire » suggestion de leur liste était toujours bien plus plausible que les suggestions des autres méthodes. Par exemple, sur l'ensemble de données German Credit, leur méthode maintenait la « pire » suggestion très plausible, alors que d'autres méthodes suggéraient des changements qui étaient mathématiquement possibles mais pratiquement absurdes.

3. Le contrôle des compromis
Les chercheurs ont montré qu'ils pouvaient contrôler la carte. En ajustant la force de l'« aimant » (les paramètres d'inclinaison), ils pouvaient dire au système : « Donnez-moi les changements les plus proches possibles, même si je dois changer quelques choses », ou « Donnez-moi des changements qui affectent le moins de parties de ma vie possible, même s'ils sont un peu plus éloignés ». Ils ont constaté que l'utilisation de ces deux contrôles ensemble donnait les meilleurs résultats, offrant des solutions qui étaient à la fois proches de la vie actuelle de l'utilisateur et nécessitaient des changements minimaux.

4. Cela fonctionne aussi sur les images
Ils ont même essayé cela sur des images. Si vous avez l'image du chiffre 8 et que vous voulez la transformer en 0, le système ne se contente pas de deviner. Il crée une distribution de toutes les façons de transformer un 8 en 0. À mesure qu'ils augmentaient la force de l'« inclinaison », les images générées conservaient davantage de pixels du 8 original, rendant le changement plus petit et plus subtil. Cependant, ils ont noté un compromis : si l'on incline trop fortement, l'image ressemble trop au 8 original et ne parvient pas à être reconnue comme un 0. Cela a montré que la méthode fonctionne dans des espaces complexes et de haute dimension, et pas seulement dans de simples tableaux de chiffres.

L'essentiel

L'article conclut que cette approche est un moyen pratique et puissant d'aider les gens. Elle ne vous donne pas seulement une réponse ; elle vous offre un menu d'options diverses, réalistes et exploitables. C'est comme avoir un agent de voyage qui ne se contente pas de vous réserver le vol le moins cher, mais qui vous montre cinq itinéraires différents, explique les avantages et les inconvénients de chacun, et vous laisse choisir celui qui convient à votre emploi du temps et à votre budget.

Les chercheurs précisent avec prudence que ce n'est pas une baguette magique qui résout tous les problèmes. Le système repose sur l'« échantillonnage par rejet », ce qui signifie qu'il génère de nombreuses possibilités et écarte celles qui ne fonctionnent pas. Si les règles sont trop strictes (comme des lois très complexes sur les changements autorisés), il peut être plus difficile de trouver un bon chemin. Mais pour les ensembles de données qu'ils ont testés, cela a remarquablement bien fonctionné, offrant à chaque personne testée au moins une option valide et réaliste. Ils suggèrent qu'à l'avenir, ils pourraient intégrer ces règles strictes directement dans la carte elle-même, rendant le processus encore plus fluide.

En bref, ce papier nous fait passer d'un monde où les ordinateurs nous disent « voici la seule chose que vous devez faire » à un monde où ils disent : « voici toutes les différentes façons dont vous pourriez faire en sorte que cela fonctionne, et voici la meilleure pour vous ».

Résumé Technique : Recours Algorithmique Diversifié et Plausible via des Distributions de Recours Traitables

Énoncé du Problème

Le recours algorithmique (AR) vise à aider les individus à inverser des décisions automatisées défavorables en recommandant des changements exploitables sur leurs attributs. Bien que la littérature existante reconnaisse que de multiples chemins distincts existent souvent pour obtenir un résultat favorable, les approches actuelles d'AR traitent principalement le recours comme un problème d'optimisation. Ces méthodes construisent généralement un contrefactuel unique ou un petit ensemble fixe de contrefactuels en optimisant explicitement des objectifs tels que la validité, la proximité, la parcimonie et la plausibilité.

Les auteurs identifient trois limitations principales dans ce paradigme d'optimisation ponctuelle :

Absence de Modélisation Distributionnelle : Les méthodes existantes traitent les recours comme des points isolés plutôt que de modéliser l'espace sous-jacent des alternatives réalisables disponibles pour un individu.
Compromis : En pratique, ces méthodes sacrifient souvent la diversité, la plausibilité ou la faisabilité pour garantir les autres.
Diversité Rigide : Lorsque plusieurs recommandations sont générées, la diversité est souvent imposée via des objectifs explicites ou de l'énumération, échouant à capturer la vraisemblance relative de différentes stratégies ou la structure globale de l'espace de solution.

Méthodologie : Distributions de Recours Traitables (TRD)

Le papier propose les Distributions de Recours Traitables (TRD), un cadre probabiliste qui reformule l'AR comme la construction d'une distribution de probabilité individualisée sur les issues favorables pour une instance factuelle donnée.

Cadre Fondamental

Distribution de Base : La méthode commence par une distribution de probabilité apprise sur la classe positive, notée $p_+$ . Cette distribution encode la plausibilité des issues favorables basées sur la variété des données (data manifold).
Inclinaison Exponentielle (Exponential Tilting) : Pour personnaliser $p_+$ pour une instance factuelle spécifique $x^-$ (qui a reçu une prédiction défavorable), les auteurs appliquent une inclinaison exponentielle. Ils définissent une fonction de coût d'intervention spécifique au fait $G_{\delta,\nu}(x; x^-)$ comprenant :
- Coût de Proximité : $\delta \|x - x^-\|_1$ (magnitude des changements).
- Coût de Parcimonie : $\nu \|x - x^-\|_0$ (nombre de caractéristiques modifiées).
La TRD résultante est définie par :
$\tilde{p}_{\delta,\nu}(x | x^-) = \frac{p_+(x) \exp\{-G_{\delta,\nu}(x; x^-)\}}{Z(\delta, \nu; x^-)}$
où $Z$ est la constante de normalisation. Cette transformation concentre la masse de probabilité sur les issues favorables qui nécessitent des changements plus faibles et moins nombreux par rapport à l'instance factuelle.
Traitabilité via les Circuits Probabilistes (PC) :
- La distribution de la classe positive $p_+$ est représentée par un circuit probabiliste (PC) lisse et décomposable.
- Le coût d'intervention $G$ est additivement séparable par caractéristique.
- Résultat Théorique Clé : Les auteurs prouvent que les PC lisses et décomposables sont clos sous inclinaison exponentielle par des coûts additivement séparables. Cela permet de construire la TRD exactement comme un nouveau PC avec la même topologie que le modèle de base.
- Implication : Cette construction permet une normalisation exacte, l'évaluation de la vraisemblance, le conditionnement et l'échantillonnage sans réentraîner le modèle ni effectuer d'optimisation par instance.
Application de la Faisabilité :
- Actionnabilité : Les contraintes strictes (caractéristiques immuables, monotonie) sont imposées via le conditionnement sur l'ensemble actionnable $A(x^-)$ . Comme les PC supportent le conditionnement exact, cela est effectué efficacement.
- Validité et Causalité : La validité du classifieur (score de prédiction) et les contraintes causales sont imposées via l'échantillonnage par rejet. Des échantillons sont tirés de la TRD actionnable et acceptés uniquement s'ils satisfont le seuil du classifieur et les règles causales.
Construction d'un Ensemble de Recours Diversifié :
- Au lieu de résoudre un problème d'optimisation pour la diversité, la méthode échantillonne un pool de contrefactuels réalisables à partir de la TRD.
- Pour éviter la redondance, le pool est regroupé par k-médoïdes, et la médoïde de chaque groupe est retournée.
- Le nombre de groupes $k$ est déterminé de manière adaptative à l'aide du score de silhouette, permettant au nombre de recours retournés de varier selon la structure de la distribution échantillonnée.

Contributions Clés

Formulation Distributionnelle : Introduction de la TRD, qui représente les alternatives favorables comme une distribution de probabilité individualisée plutôt que comme un ensemble fixe de points optimisés.
Construction Exacte : Démonstration que les PC lisses et décomposables sont clos sous inclinaison exponentielle par des coûts additifs. Cela produit une construction de TRD exacte pour les objectifs de proximité et de parcimonie tout en préservant les propriétés d'inférence traitables sans réentraînement.
Caractérisation Théorique : Preuve que l'inclinaison exponentielle concentre la masse de probabilité vers les interventions à moindre coût, garantissant théoriquement que la distribution favorise les contrefactuels proximaux et parcimonieux.
Validation Empirique : Démonstration sur des benchmarks tabulaires (Adult, German Credit, GMSC) et MNIST que la TRD génère des ensembles de recours diversifiés et plausibles avec un contrôle conjoint sur la proximité et la parcimonie, tout en maintenant une masse de probabilité réalisable suffisante pour un échantillonnage par rejet pratique.

Résultats Expérimentaux

Les auteurs ont évalué la TRD par rapport aux méthodes de pointe (DiCE, LiCE et MIO) sur des benchmarks tabulaires standards et MNIST.

Équilibre des Métriques : La TRD atteint un équilibre constant entre diversité, plausibilité et faisabilité. Contrairement à DiCE (qui maximise la diversité mais viole souvent la faisabilité) ou LiCE (qui maximise la plausibilité mais s'effondre sur une stratégie unique), la TRD retourne plusieurs stratégies distinctes qui restent plausibles et réalisables.
Couverture : La TRD a atteint une couverture de 100 % (Pourcentage Servi) sur tous les jeux de données, fournissant au moins un contrefactuel réalisable pour chaque instance factuelle évaluée dans un budget d'échantillonnage fixe.
Plausibilité : La TRD a maintenu une faible Log-Vraisemblance Négative (NLL) sur l'ensemble du groupe retourné (meilleur, moyen et pire), indiquant que la diversité n'a pas été obtenue en ajoutant des instances implausibles.
Diversité : Bien qu'elle ne soit pas toujours la plus élevée en termes de Diversité de Compte, la TRD a retourné plusieurs stratégies d'intervention distinctes ( $k_{eff}$ ) qui sont actionnables et causalement cohérentes.
Contrôle : Les expériences ont confirmé que les inclinaisons de proximité et de parcimonie offrent un contrôle complémentaire ; l'inclinaison conjointe a produit les distances et les changements de caractéristiques les plus faibles par rapport à une inclinaison à terme unique.
Extension MNIST : Dans les tâches d'images de haute dimension, la TRD a démontré avec succès le compromis entre proximité (force d'inclinaison) et validité, montrant que le mécanisme s'étend au-delà des données tabulaires.

Signification et Revendications

Le papier affirme que la TRD offre une alternative fondée sur des principes à l'optimisation ponctuelle en modélisant l'espace des alternatives réalisables plutôt qu'en cherchant simplement des points à l'intérieur de celui-ci.

Efficacité : Le cadre ne nécessite aucun réentraînement ni optimisation par instance, ce qui le rend très efficace lors du déploiement.
Diversité Intrinsèque : La diversité est montrée comme étant intrinsèque à la distribution de recours ; le regroupement (clustering) sert uniquement à résumer cette diversité existante plutôt qu'à la créer via des objectifs explicites.
Praticité : Les auteurs affirment que la TRD conserve une masse de probabilité suffisante sur les contrefactuels réalisables pour faire de l'échantillonnage par rejet une alternative pratique à l'optimisation répétée, même sous des contraintes strictes.

Les auteurs notent modestement une limitation : l'efficacité de l'échantillonnage par rejet dépend de la masse de probabilité réalisable, qui peut diminuer sous des contraintes de validité ou causales très restrictives. Des travaux futurs sont suggérés pour investiguer la compilation directe des contraintes dans le circuit et l'adaptation des forces d'inclinaison aux factuels individuels.