🤖 machine learning

Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies

Ce papier présente une méthode d'attribution ancrée sur les contraintes pour les politiques d'optimisation combinatoire neuronale qui décompose les décisions via des duaux de relaxation linéaire, certifie les contre-factuels à l'aide de modèles de faisabilité combinatoire et borne les tailles d'explications suffisantes avec des tests PAC corrigés par Bonferroni, démontrant une précision nettement supérieure à celle des gradients de substitution sur plusieurs domaines de problèmes.

Auteurs originaux : Sohaib Lafifi

Publié 2026-05-26

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Sohaib Lafifi

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 que vous disposiez d'un répartiteur robotique ultra-intelligent qui planifie des itinéraires de livraison ou établit des plannings d'usines. Il est incroyablement performant dans son travail, surpassant souvent les experts humains. Mais c'est une « boîte noire » : vous lui demandez, « Pourquoi as-tu envoyé le camion à cette maison en premier ? » et il répond simplement, « Parce que mes mathématiques l'ont dit. »

Ce papier présente une nouvelle méthode pour ouvrir cette boîte noire, appelée Attribution Ancrée aux Contraintes (CAX). Imaginez-la comme un traducteur qui convertit les mathématiques complexes du robot en une histoire sur des règles plutôt que sur de simples chiffres.

Voici comment le papier explique ce système en utilisant trois outils principaux :

1. Le Traducteur « Livre de Règles » (Attribution Λ)

Habituellement, lorsque nous tentons d'expliquer l'IA, nous examinons des entrées individuelles (comme « la distance jusqu'à la maison » ou « le poids du colis »). Le papier soutient que c'est comme blâmer une brique unique pour l'effondrement d'un bâtiment, alors qu'en réalité, c'est la fondation ou le toit qui ont cédé.

Dans ces problèmes, les décisions sont pilotées par des familles de règles (par exemple : « Ne pas dépasser la charge du camion », « Ne pas arriver après 17 h », « Ne pas conduire trop loin »).

L'Ancienne Méthode : Elle examine chaque chiffre individuellement et devine quelle règle a compté. Elle se trompe souvent car certains chiffres semblent « plus forts » (ont plus de données) même s'ils ne sont pas la véritable raison de la décision.
La Nouvelle Méthode (CAX) : Elle examine les « prix ombres » (un terme mathématique sophistiqué désignant dans quelle mesure une règle comprime la solution). Elle demande : « Quelle famille de règles est la plus sollicitée en ce moment ? »
Le Résultat : Elle identifie correctement que la décision a été pilotée par la règle « Fenêtre de temps », et non simplement par la règle « Distance », même si les données de distance étaient massives.

2. Le Contrôle de Réalité « Et Si » (Contrefactuels Certifiés de Faisabilité)

Une méthode courante pour expliquer l'IA consiste à demander : « Quel petit changement ferait que le robot ferait quelque chose de différent ? »

Le Problème des Anciennes Méthodes : Elles pourraient suggérer, « Si le colis pesait -50 kg, le robot irait ailleurs. » C'est impossible ! On ne peut pas avoir un poids négatif. Ces « contrefactuels » sont mathématiquement valides mais physiquement absurdes.
La Solution CAX : Le papier utilise un « certificat de faisabilité ». Avant d'accepter une explication, il effectue un test strict (comme un inspecteur de sécurité) pour s'assurer que le scénario « Et si » est réellement possible dans le monde réel.
L'Analogie : Imaginez demander : « Pourquoi as-tu pris le pont ? » L'ancienne IA répond : « Parce que si tu avais pris le tunnel, tu aurais eu un accident. » L'IA CAX répond : « Parce que si tu avais pris le tunnel, tu aurais eu un accident ET le tunnel est en réalité ouvert et praticable. » Elle filtre les scénarios impossibles.

3. Le Test « Preuve Minimale » (Sous-ensembles Bonferroni-PAC)

Parfois, nous voulons savoir : « Quelle est la plus petite quantité d'informations dont le robot avait besoin pour prendre cette décision ? »

La Méthode : Le papier utilise un tour de passe-passe statistique (correction de Bonferroni) pour trouver un petit groupe de nœuds (comme quelques maisons spécifiques sur un itinéraire) tels que, si vous ne connaissiez que ceux-ci, le robot prendrait exactement le même choix.
Le Résultat : Il prouve que le robot n'avait pas besoin de regarder toute la carte ; il lui suffisait de regarder un tout petit cluster spécifique de 5 emplacements pour être sûr à 95 % de sa décision. Cela maintient l'explication courte et ciblée.

Le Grand Test : Est-ce que ça a fonctionné ?

Les auteurs ont testé cela sur trois problèmes différents :

Itinéraires de Livraison (CVRPTW) : Camions avec fenêtres de temps et limites de poids.
Collecte de Prix (OP) : Visiter autant d'endroits à haute valeur que possible sans manquer d'essence.
Planification d'Usine (FJSP) : Attribuer des tâches à différentes machines.

Les Constatations :

Sur les Itinéraires de Livraison : L'ancienne méthode (regarder les chiffres bruts) était juste seulement 75 % du temps. La nouvelle méthode CAX était juste 97 % du temps. Elle a correctement détecté la règle « Fenêtre de temps » que l'ancienne méthode avait manquée.
Sur la Collecte de Prix : L'ancienne méthode était juste seulement 35 % du temps. CAX a bondi à 77 %.
Sur la Planification d'Usine : Les deux méthodes étaient parfaitement d'accord (100 %). Cela a confirmé la théorie : lorsque les données et les règles s'alignent bien, l'ancienne méthode fonctionne, mais lorsqu'elles deviennent désordonnées, CAX est la seule à avoir raison.

En Bref

Ce papier nous offre un moyen d'expliquer les décisions complexes des robots en :

Groupant les raisons par règles (et non par simples chiffres).
Vérifiant que les histoires « Et si » sont physiquement possibles.
Trouvant le plus petit ensemble de faits nécessaire pour justifier la décision.

Il transforme une sortie mathématique confuse en une histoire claire et fiable sur pourquoi le robot a fait le choix qu'il a fait, garantissant que l'explication est ancrée dans les règles réelles du jeu, et non simplement dans du bruit statistique.

Résumé technique : Attribution ancrée sur les contraintes pour les politiques neuronales de CO

Énoncé du problème

Les politiques neuronales pour l'optimisation combinatoire (CO) sont de plus en plus efficaces pour résoudre des problèmes de routage et de planification, mais leurs processus de prise de décision restent opaques. Les méthodes standard d'IA explicable (XAI), telles que l'attribution de caractéristiques basée sur le gradient (par exemple, Integrated Gradients, DeepLIFT), échouent dans le domaine de la CO car elles opèrent au niveau des caractéristiques plutôt qu'au niveau des contraintes. Les problèmes de CO sont définis par des familles de contraintes (par exemple, capacité, fenêtres de temps, précédence), qui s'étendent souvent sur plusieurs tenseurs de caractéristiques de rangs variables. Par conséquent, les tenseurs de caractéristiques de haut rang peuvent accumuler une masse de gradient excessive même lorsqu'ils ne représentent pas la contrainte liante qui guide une décision, conduisant à des attributions désalignées.

Les explications spécifiques à la CO existantes reposent souvent sur des contre-factuels non contraints qui violent la faisabilité du problème (par exemple, une demande négative ou des fenêtres de temps inversées) ou ciblent des modèles de substitution statiques plutôt que le processus de décodage autorégressif des politiques neuronales. Il manque des méthodes qui décomposent les décisions neuronales de CO par familles de contraintes tout en fournissant des garanties formelles de faisabilité.

Méthodologie : Attribution ancrée sur les contraintes (CAX)

L'article propose CAX, un cadre comprenant trois primitives qui relient les explications neuronales à la structure d'optimisation sous-jacente :

1. Attribution $\Lambda$

Cette méthode décompose le gradient de décision d'une politique par famille de contraintes plutôt que par caractéristiques individuelles. Pour une décision $a_t$ à l'étape $t$ , l'attribution à la famille de contraintes $c_k$ est calculée comme suit :
$\Lambda_k(t) = \lambda^*_k(x) \cdot \sum_{i \in F(c_k)} \sum_j |\nabla_{x^{(i)}_j} \log \pi_\theta(a_t | s_t) \cdot x^{(i)}_j|$
Ici, $\lambda^*_k$ représente le multiplicateur de Lagrange (valeur duale) issu de la relaxation par Programmation Linéaire (LP) du problème, agrégée par famille. Ce facteur d'échelle garantit que l'attribution reflète la « pression liante » de la contrainte. Le cadre prend en charge trois backends pour estimer $\lambda^*$ :

LP : Valeurs duales issues de la relaxation LP.
Subgrad : Ascension du sous-gradient de Lagrange sur un sous-problème relaxé.
Proxy : Pondération uniforme ( $\lambda_k=1$ ), équivalente à un gradient partitionné par contrainte $\times$ caractéristique.

2. Sous-ensemble suffisant Bonferroni-PAC

Pour déterminer l'ensemble minimal de nœuds nécessaire pour préserver la décision argmax de la politique, la méthode adapte l'approche de Koriche et al. pour les décodeurs de CO. Elle cherche le plus petit sous-ensemble $S$ tel que la probabilité que la politique maintienne sa décision sous des perturbations gaussiennes soit d'au moins $1-\epsilon$ .

Un algorithme glouton parcourt l'ordre d'attribution pour trouver le plus petit $k$ où le taux de préservation empirique dépasse $1-\epsilon$ .
Pour contrôler le taux d'erreur familial à travers des requêtes adaptatives (jusqu'à $k_{max}$ ), une correction de Bonferroni est appliquée à la borne de Hoeffding. Cela produit une taille d'échantillon $M_{bonf}$ qui garantit une borne $(1-\delta)$ -PAC le long de l'ordre glouton.

3. Contre-factuels certifiés CSP (CF)

Contrairement aux contre-factuels standards de style Wachter qui minimisent les normes de perturbation sans garanties de faisabilité, CAX impose un certificat de faisabilité combinatoire.

Processus : Un échantillonneur génère des perturbations pour inverser la décision argmax. Les candidats subissent d'abord des vérifications arithmétiques (par exemple, limites de champ).
Certification : Le meilleur candidat est vérifié par rapport à un modèle de décision de faisabilité par Programmation par Contraintes (CP) (implémenté via CP-SAT).
Signal d'arbitrage : La famille portant la plus grande masse $L_1$ dans une perturbation d'inversion certifiée CSP sert de signal de vérité terrain pour la sensibilité locale de la politique. Ce signal est invariant aux normes de perturbation ( $L_1, L_2, L_\infty$ ) et à la normalisation dimensionnelle.

Contributions clés

Décomposition au niveau des contraintes : CAX est la première méthode à décomposer les décisions de politiques neuronales de CO par familles de contraintes en utilisant les duaux de relaxation LP, corrigeant ainsi les problèmes de mauvais classement inhérents à l'attribution au niveau des caractéristiques.
Contre-factuels certifiés de faisabilité : Elle introduit un processus de génération de contre-factuels qui adhère strictement aux contraintes du problème via des modèles de décision de faisabilité CSP, la distinguant des méthodes XAI non contraintes.
Sous-ensembles PAC suffisants : Elle fournit une borne contrôlée par Hoeffding et corrigée par Bonferroni sur la taille des sous-ensembles d'explication suffisants pour les politiques neuronales de CO.
Arbitrage empirique : Le cadre utilise le signal dérivé des CF pour valider les backends d'attribution, démontrant que les duaux LP sauvegardent la précision de l'attribution lorsque les rangs de tenseurs de caractéristiques et les familles de contraintes liantes sont désalignés.

Résultats expérimentaux

Le cadre a été évalué sur trois problèmes de CO distincts : le problème de routage de véhicules avec capacités et fenêtres de temps (CVRPTW), le problème d'orientation (OP) et le problème d'ordonnancement flexible d'ateliers (FJSP).

Accord avec le signal CF :
- CVRPTW : L'attribution $\Lambda$ ancrée sur LP a correspondu au signal dérivé des CF dans 96,5 % des cas ( $n_{cert}=344$ ), surpassant significativement le gradient proxy (75,0 %). La différence (+0,215) était statistiquement significative (McNemar $p \le 10^{-14}$ ).
- OP : L'attribution ancrée sur LP a atteint un accord de 77,2 % ( $n_{cert}=281$ ) contre 35,2 % pour le proxy (différence de +0,420, $p \le 10^{-14}$ ).
- FJSP : Dans ce régime « rangs-alignés » où les tenseurs de grande masse correspondent aux familles liantes, les backends LP et proxy ont tous deux atteint un accord de 100 % sur les 59 inversions certifiées, confirmant la prédiction théorique selon laquelle les duaux LP n'ajoutent aucune information supplémentaire lorsque les rangs sont alignés.
Taux de faisabilité : Les contre-factuels certifiés CSP ont maintenu une haute faisabilité. Le filtrage arithmétique seul a validé 100 % des gagnants, tandis qu'une base de référence non contrainte appariée n'a validé que 19,3 % des candidats.
Sous-ensembles PAC : Sur CVRPTW, les sous-ensembles PAC corrigés par Bonferroni ont moyenné 5,0 nœuds par étape ( $M=70, \epsilon=\delta=0,2$ ).

Importance et affirmations

L'article affirme que CAX fournit une approche rigoureuse et ancrée sur les contraintes pour expliquer les politiques neuronales de CO. Son importance principale réside dans la démonstration que les duaux LP sont nécessaires pour une attribution précise uniquement lorsque les rangs de tenseurs de caractéristiques sont désalignés par rapport à la famille de contraintes liante. Lorsqu'ils sont alignés, des méthodes plus simples suffisent ; lorsqu'ils sont désalignés, les méthodes au niveau des caractéristiques échouent, et les méthodes ancrées sur LP récupèrent le signal correct au niveau des contraintes.

Le cadre est modeste dans son portée : il ne nécessite qu'un modèle de faisabilité (implémenté ici comme CSP) et fonctionne comme un outil d'analyse a posteriori. Il ne prétend pas résoudre l'optimisation complète du treillis de sous-ensembles (les sous-ensembles optimaux PAC exacts restent un problème ouvert) mais fournit une borne conservatrice et certifiée via un ordre glouton. Ce travail établit une nouvelle référence pour l'évaluation de l'XAI en CO en utilisant des contre-factuels certifiés CSP comme signal d'arbitrage, allant au-delà de l'importance heuristique des caractéristiques vers une validité basée sur les contraintes.