🤖 machine learning

CQD-SHAP: Explainable Complex Query Answering via Shapley Values

Le document propose CQD-SHAP, un nouveau cadre qui exploite les valeurs de Shapley issues de la théorie des jeux coopératifs pour fournir une réponse explicable aux requêtes complexes sur des graphes de connaissances incomplets en quantifiant la contribution de chaque partie de la requête au classement des réponses, adressant ainsi les limites d'interprétabilité des modèles existants de type boîte noire et neurosymboliques.

Auteurs originaux : Parsa Abbasi, Stefan Heindorf

Publié 2026-06-23

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Parsa Abbasi, Stefan Heindorf

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

La vue d'ensemble : Le détective face à la « boîte noire »

Imaginez que vous avez une immense bibliothèque désordonnée (un Graphe de Connaissance) où les livres sont reliés par des fils. Parfois, il manque des pages ou des livres entiers dans cette bibliothèque (elle est incomplète).

Lorsque vous posez une question simple comme « Qui a écrit Harry Potter ? », un ordinateur peut généralement trouver la réponse en suivant simplement les fils. Mais que se passe-t-il si vous posez une question complexe comme : « Quels médicaments traitent le diabète ET provoquent une toxicité rénale ? »

Pour répondre à cela, l'ordinateur doit faire deux choses :

Suivre les fils (approche symbolique) : Chercher les médicaments qui traitent certainement le diabète et qui causent certainement une toxicité rénale dans la bibliothèque existante.
Deviner les liens manquants (approche neuronale) : Puisque la bibliothèque est incomplète, l'ordinateur utilise un « devineur intelligent » (un réseau de neurones) pour inférer des connexions qui devraient être là, mais qui ne sont pas encore écrites.

Le problème ? Le « devineur intelligent » est une boîte noire. Il vous donne une liste de réponses (comme « Insuline »), mais il ne vous dit pas pourquoi il a choisi cette réponse. L'a-t-il choisie parce que la bibliothèque le disait explicitement ? Ou l'a-t-il deviné parce que l'ordinateur pense que l'insuline est liée à la toxicité rénale, même si ce fait est absent de la bibliothèque ?

CQD-SHAP est un nouvel outil conçu pour ouvrir cette boîte noire et expliquer exactement à quel point chaque partie de la question a contribué à la réponse finale.

L'idée centrale : L'analogie du « Score d'équipe »

Les auteurs utilisent un concept issu de la théorie des jeux appelé Valeurs de Shapley. Voyez cela comme un projet de groupe où une équipe d'étudiants (les atomes de la question) travaille ensemble pour obtenir une note (le classement de la réponse).

Dans notre exemple de question (« Médicaments pour le diabète ET toxicité rénale »), il y a deux « étudiants » (atomes) :

Étudiant A : « Médicaments pour le diabète. »
Étudiant B : « Médicaments pour la toxicité rénale. »

La note finale (le classement de l'« Insuline ») dépend de la performance de l'étudiant A et de l'étudiant B. Mais quel crédit accorder à l'étudiant A par rapport à l'étudiant B ?

CQD-SHAP agit comme un arbitre équitable. Il réalise des milliers de mini-expériences pour déterminer le score :

Scénario 1 : L'étudiant A effectue le travail via la « Marche dans la Bibliothèque » (Symbolique), et l'étudiant B utilise le « Devineur Intelligent » (Neural).
Scénario 2 : L'étudiant A utilise le « Devineur Intelligent », et l'étudiant B effectue la « Marche dans la Bibliothèque ».
Scénario 3 : Les deux utilisent la « Marche dans la Bibliothèque ».
Scénario 4 : Les deux utilisent le « Devineur Intelligent ».

En comparant ces scénarios, CQD-SHAP calcule exactement à quel point le « Devineur Intelligent » a amélioré la note finale pour chaque étudiant.

Le moment « Eurêka ! » : Pourquoi est-ce important ?

L'article affirme que cette méthode révèle quelque chose de surprenant. Parfois, le « Devineur Intelligent » fait tout le gros du travail, et parfois, il nuit au résultat.

L'analogie du « Voisin bruyant » :
Imaginez que vous essayiez de trouver une maison spécifique (la réponse).

La Marche dans la Bibliothèque revient à lire l'annuaire officiel. C'est précis, mais le livre peut être obsolète si la maison n'y est plus répertoriée.
Le Devineur Intelligent revient à demander à un voisin qui connaît le quartier. Il peut savoir que la maison existe même si elle n'est pas dans l'annuaire.

CQD-SHAP pourrait vous dire :

« Pour la réponse "Insuline", la partie "Toxicité Rénale" de votre question a reçu un énorme bonus (+450 points) parce que le Devineur Intelligent a deviné la connexion. Cependant, la partie "Diabète" a en fait subi une légère pénalité (-10 points) car le Devineur Intelligent s'est trompé et a suggéré de mauvais voisins. »

Sans CQD-SHAP, vous verriez simplement « Insuline » en haut de la liste et supposeriez que l'ordinateur en est sûr à 100 %. Avec CQD-SHAP, vous réalisez : « Attendez, l'ordinateur est principalement en train de deviner pour la partie rénale. Je devrais vérifier ce fait. »

Comment ils l'ont testé (Le « Test de résistance »)

Les auteurs ont testé cette méthode sur des jeux de données réels (comme Freebase et NELL) en utilisant divers types de questions complexes (certaines avec des « ET », d'autres avec des « OU »).

Ils ont comparé leur méthode à d'autres façons de deviner quelle partie de la question était importante (comme choisir la première partie, la dernière partie, ou la partie ayant le score le plus bas).

Les résultats :

Explications nécessaires : Si vous retirez le « Devineur Intelligent » de la partie la plus importante de la question, le rang de la réponse devrait chuter considérablement. CQD-SHAP était bien meilleur pour identifier ces parties critiques que les autres méthodes.
Explications suffisantes : Si vous utilisez uniquement le « Devineur Intelligent » sur la partie la plus importante, le rang de la réponse devrait augmenter de manière significative. Là encore, CQD-SHAP a gagné.

En termes simples, CQD-SHAP est la seule méthode qui identifie systématiquement la bonne partie de la question pour expliquer pourquoi une réponse est classée haut ou bas.

Points clés à retenir

Il ne s'agit pas seulement de la réponse, mais du « Pourquoi » : Il explique pourquoi une requête complexe a renvoyé un résultat spécifique en décomposant la contribution de chaque étape logique.
Il mesure le « Pouvoir de devinette » : Il quantifie spécifiquement à quel point la capacité du réseau neuronal à « deviner » des faits manquants a aidé (ou nui) au classement final par rapport à la simple consultation des faits existants.
Il est mathématiquement équitable : Il utilise une formule mathématique rigoureuse (les Valeurs de Shapley) pour garantir que le « crédit » est distribué équitablement entre les parties de la question.
Il détecte les erreurs : Il peut révéler quand une réponse bien classée repose en fait sur une supposition faible ou bruitée, aidant ainsi l'utilisateur à accorder moins de confiance aveugle au système.

Ce qu'il n'est PAS (Basé strictement sur l'article)

Il ne prétend pas guérir des maladies ou diagnostiquer des patients. L'exemple du « médicament » n'est qu'une métaphore de son fonctionnement.
Il ne dit pas que cela remplacera les médecins ou les avocats. C'est un outil pour aider à comprendre comment un modèle d'IA réfléchit.
Il ne prétend pas résoudre le problème de la « boîte noire » pour toute l'IA, mais seulement pour ce type spécifique de système de réponse à des requêtes complexes.

En résumé, CQD-SHAP est un outil de transparence qui agit comme une « fiche de score » pour les détectives de l'IA, montrant précisément quelles indices (parties de la requête) étaient des faits réels et lesquels étaient des devinettes intelligentes, afin que vous sachiez à qui faire confiance.

Résumé Technique : CQD-SHAP

Énoncé du Problème

Le traitement de requêtes complexes (CQA - Complex Query Answering) sur les graphes de connaissances (KG - Knowledge Graphs) va au-delà de la simple prédiction de liens pour gérer des requêtes nécessitant un raisonnement multi-sauts et des opérateurs logiques (conjonction, disjonction). Bien que des approches neurosymboliques comme CQD (Complex Query Decomposition) aient émergé pour traiter l'incomplétude des graphes de connaissances réels en inférant des liens manquants, elles fonctionnent principalement comme des modèles « boîte noire ». Les méthodes d'explicabilité existantes pour la prédiction de liens se concentrent sur l'identification de triplets ou de chemins importants pour des prédictions à un seul saut et ne s'appliquent pas directement aux requêtes complexes. De plus, les méthodes actuelles de CQA neurosymbolique manquent de transparence concernant la contribution spécifique des différents composants de la requête (atomes) au classement final d'une réponse. Cette opacité entrave la confiance de l'utilisateur, le débogage et la capacité des experts métier à identifier les lacunes dans le graphe de connaissances ou à affiner les requêtes.

Méthodologie : CQD-SHAP

L'article propose CQD-SHAP, un cadre qui explique les résultats des modèles de CQA neurosymboliques (spécifiquement CQD) en quantifiant la contribution de chaque atome de la requête au classement d'une entité réponse spécifique en utilisant les valeurs de Shapley issues de la théorie des jeux coopératifs.

Définitions Fondamentales

Joueurs : Les atomes (parties constituantes) d'une requête complexe $Q$ sont traités comme des joueurs dans un jeu coopératif.
Coalitions : Un sous-ensemble d'atomes $S$ est exécuté via l'approche neurale (inférence de liens manquants via un prédicteur de liens), tandis que les atomes restants sont exécutés via une approche symbolique (se basant strictement sur les faits observés dans le KG).
Fonction de Valeur : La valeur d'une coalition $S$ $S$ pour une entité cible $e_i$ $e_{i}$ est définie par la Quantité d'Intérêt (QoI) de $\Delta$ Rang. Elle mesure l'amélioration de la position de rang de $e_i$ $e_{i}$ lorsque les atomes de $S$ $S$ sont exécutés de manière neurale par rapport à une exécution purement symbolique de l'ensemble de la requête.
- Formellement : $val_{e_i}(Q_S) = r_i(Q_{\emptyset}) - r_i(Q_S)$ , où $r_i$ est le rang d'une entité $e_i$ dans un contexte filtré.
Calcul de la Valeur de Shapley : La contribution d'un atome $a$ spécifique est calculée comme la contribution marginale moyenne de cet atome à travers toutes les coalitions possibles des autres atomes. Cela satisfait les axiomes fondamentaux de Shapley, incluant l'efficacité (la somme de toutes les contributions des atomes est égale à l'amélioration totale du rang obtenue par l'exécution neurale complète).

Détails d'Exécution

Exécution Neurale : Utilise un prédicteur de liens (par exemple, issu de CQD) pour attribuer des scores aux entités, permettant l'inférence sur des graphes incomplets.
Exécution Symbolique : Effectue un parcours de graphe sur le KG observé (incomplet), attribuant des scores constants aux faits existants et des scores faibles aux faits inexistants.
Calcul Exact : En raison du faible nombre d'atomes dans les requêtes complexes (typiquement $\le 4$ ), l'article calcule les valeurs de Shapley exactes sans approximation.

Principales Contributions

Première Explication basée sur Shapley pour la CQA : À la connaissance des auteurs, il s'agit de la première approche expliquant les modèles de réponse de requêtes complexes neuronaux en utilisant les valeurs de Shapley.
Définition Formelle des Explications au Niveau de l'Atome : L'article définit un cadre d'explication formel au niveau des atomes de la requête, se distinguant des explications au niveau du triplet ou du chemin utilisées pour la prédiction de liens.
Nouvelle Métrique (CQD-SHAP) : Introduit une méthode pour quantifier la part de l'exécution neurale d'un atome spécifique dans l'amélioration du classement d'une réponse cible par rapport à l'exécution symbolique.
Redéfinition des Critères d'Évaluation : Étend les concepts d'explications Nécessaires et Suffisantes de la prédiction de liens au domaine de la CQA :
- Nécessaire : Remplacer l'atome le plus important par une exécution symbolique provoque une chute significative du rang de la réponse (mesurée par $\Delta$ MRR).
- Suffisante : Exécuter uniquement l'atome le plus important de manière neurale (pendant que les autres sont symboliques) améliore significativement le classement par rapport à une ligne de base entièrement symbolique.

Résultats Expérimentaux

Les auteurs ont évalué CQD-SHAP sur FB15k-237, NELL995, et leurs variantes plus difficiles (+H) à travers divers types de requêtes (projections, intersections, unions).

Performance : CQD-SHAP a systématiquement surpassé toutes les lignes de base (First, Last, Random, et sélection basée sur le score) dans les scénarios d'évaluation nécessaires et suffisants.
- Dans le scénario Nécessaire, CQD-SHAP a réduit le Mean Reciprocal Rank (MRR) jusqu'à 45,70 % (pour les requêtes 2u sur NELL995), soit nettement plus que la meilleure ligne de base.
- Dans le scénario Suffisant, il a augmenté le MRR jusqu'à 58,90 % (pour les requêtes 2u sur NELL995+H).
Sensibilité à la Structure de la Requête : La méthode a démontré une plus grande efficacité pour les requêtes d'intersection (ex: 3i, 4i) par rapport aux requêtes de projection. Les auteurs attribuent cela à la nature structurelle des intersections (utilisant des t-normes), où une seule branche critique agit comme un filtre puissant, tandis que les requêtes de projection disposent souvent de chemins alternatifs.
Efficacité : Malgré la nature NP-difficile des valeurs de Shapley, le faible nombre d'atomes a permis un calcul exact avec une faible latence (moyenne de ~30–140 ms par paire requête-réponse selon le jeu de données).
Aperçu : L'analyse a révélé que l'atome le plus important n'est pas toujours un « lien manquant ». Dans certains cas, un atome correspondant à un fait existant dans le KG peut être le principal moteur du classement en raison de la proximité des plongements (embeddings) ou du bruit introduit par l'exécution neurale des autres parties.

Signification et Revendications

L'article affirme que CQD-SHAP fournit un moyen mathématiquement rigoureux et efficace d'interpréter la réponse de requêtes neurosymboliques. En satisfaisant les axiomes de Shapley, il assure une attribution équitable du crédit aux composants de la requête. Les auteurs affirment que cette approche :

Aide les experts métier à identifier les lacunes dans les KG en révélant quelles parties de la requête dépendent fortement des connaissances inférées.
Aide au débogage des requêtes en montrant quels atomes influencent le plus le classement final.
Fournit une vue transparente de la manière dont les prédicteurs neuronaux exploitent les données incomplètes par rapport à la récupération symbolique.

Les auteurs déclarent explicitement qu'il s'agit du premier travail appliquant les valeurs de Shapley pour expliquer les résultats de réponses de requêtes complexes, dépassant ainsi les limites des méthodes d'explication de prédiction de liens existantes. Ils notent que si le présent travail se concentre sur les explications locales (réponse unique), les directions futures incluent les explications globales et la génération de langage naturel pour rendre ces valeurs lisibles par l'humain.