Résumé Technique : Raisonnement de Chemin Conforme (CPR)

1. Énoncé du Problème

La Réponse aux Questions sur les Graphes de Connaissances (KGQA) permet un raisonnement interprétable en traçant des chemins à travers des triplets structurés d'entités et de relations. Cependant, dans des domaines à haut risque (par exemple, le diagnostic médical, la finance), fournir une seule réponse déterministe est souvent insuffisant en raison des ambiguïtés inhérentes aux graphes relationnels. Les approches existantes manquent d'évaluations rigoureuses de la fiabilité.

Bien que la Prédiction Conforme (CP) offre un cadre pour générer des ensembles de prédictions avec des garanties de couverture statistique, son application à la KGQA multi-sauts présente deux défis critiques :

1. Violation de l'Échangeabilité : La CP standard suppose que les échantillons d'étalonnage et de test sont échangeables (indépendants et identiquement distribués). Dans les Graphes de Connaissances (GK), le raisonnement multi-sauts crée des dépendances séquentielles ; l'ensemble de prédictions au saut $k$ détermine les entités accessibles au saut $k+1$. Cela crée une chaîne de dépendance de Markov qui viole la prémisse d'indépendance requise pour les garanties conformes standard.
2. Notation Non Discriminante : Les méthodes existantes reposent souvent sur une similarité sémantique locale ou des scores au niveau des nœuds atomiques. Ces derniers échouent à capturer la cohérence globale des chemins multi-sauts, forçant les mécanismes conformes à adopter des seuils excessivement conservateurs pour satisfaire la couverture. Cela se traduit par des ensembles de prédictions excessivement grands qui manquent d'utilité pratique.

2. Méthodologie : Raisonnement de Chemin Conforme (CPR)

Les auteurs proposent le Raisonnement de Chemin Conforme (CPR), un cadre qui déplace l'unité d'étalonnage des sauts individuels vers des chemins de raisonnement complets, couplé à un mécanisme de notation discriminante appris.

2.1. Prédiction Conforme Échangeable par Requête (QE-CP)

Pour résoudre la violation de l'échangeabilité, le CPR traite l'ensemble du processus de raisonnement pour une seule requête comme l'unité d'étalonnage.

• Indépendance au Niveau de la Requête : Bien que les chemins au sein d'une requête soient dépendants, les requêtes individuelles sont des échantillons indépendants tirés de la même distribution. En agrégeant les scores de chemins par requête, le CPR préserve l'échangeabilité au niveau de la requête.
• Définition du Score de Non-Conformité : Pour une requête $q$, le score de non-conformité $S(q)$ est défini comme le score de chemin minimum parmi tous les chemins récupérés qui se terminent par une entité de réponse correcte. Si aucun chemin correct n'est trouvé, le score est $+\infty$.
• Étalonnage : Un seuil $\hat{\tau}_\alpha$ est calculé comme le quantile $(1-\alpha)$ des scores issus d'un ensemble d'étalonnage. L'ensemble de prédictions final inclut tous les chemins ayant des scores inférieurs à ce seuil, garantissant que l'ensemble contient au moins un chemin de raisonnement correct avec une probabilité $1-\alpha$.

2.2. Notation Discriminante de Chemins via RCVNet

Pour garantir que les ensembles de prédictions soient compacts (haute efficacité), le CPR introduit le Réseau de Valeur Conforme Résiduel (RCVNet), entraîné pour produire des scores de chemins hautement discriminants.

• Collecte de Trajectoires Guidée par PUCT : Pour pallier la rareté des chemins d'entraînement de vérité terrain, les auteurs emploient Predictor + Upper Confidence bounds applied to Trees (PUCT). Cette stratégie d'exploration équilibre la pertinence sémantique avec l'exploration de relations peu visitées.
  • Elle génère des paires de chemins positifs-négatifs : Les chemins positifs incluent les chemins de raisonnement de vérité terrain et des chemins valides alternatifs ; les chemins négatifs partagent des préfixes corrects mais dévient au dernier saut.
  • Elle accumule des priors structurels au niveau des relations (priors conjugués Beta-Bernoulli) indiquant le taux de réussite empirique de relations spécifiques.
• Architecture RCVNet : Un réseau résiduel léger qui prend en entrée des caractéristiques de chemin (similarité sémantique, embeddings de chemin et priors de relations appris).
  • Il est optimisé à l'aide d'une perte de classement par paires pour garantir que les chemins corrects reçoivent des scores plus bas (plus fiables) que les incorrects.
  • Il utilise des couches FiLM pour injecter des informations contextuelles de haute dimension dans le traitement de caractéristiques scalaires.

2.3. Récupération TreeG

Lors de l'inférence, le CPR utilise TreeG, une méthode de récupération basée sur les arbres qui exploite les scores RCVNet augmentés par des indices de relations générés par un LLM. TreeG développe les chemins saut par saut, classe les candidats globalement pour conserver un ensemble compact de chemins actifs pour l'étape suivante, assurant ainsi une récupération en ligne efficace sans la surcharge stochastique de PUCT.

3. Contributions Clés

1. Étalonnage Conforme Échangeable par Requête : Une stratégie d'étalonnage novatrice qui encapsule les dépendances multi-sauts dans des scores au niveau de la requête, préservant l'hypothèse d'échangeabilité requise pour des garanties statistiques valides en KGQA.
2. Notation Discriminante de Chemins Apprise : L'introduction du RCVNet, entraîné sur des trajectoires collectées par PUCT, qui apprend à distinguer les chemins corrects des négatifs plausibles en utilisant la cohérence globale des chemins et des priors structurels, conduisant à des ensembles de prédictions nettement plus serrés.
3. Validation Empirique : Démonstration que le CPR atteint des garanties de couverture valides tout en réduisant substantiellement la taille des ensembles de prédictions par rapport aux bases conformes existantes.

4. Résultats Expérimentaux

Des expériences ont été menées sur les benchmarks WebQSP et ComplexWebQuestions (CWQ).

• Couverture et Efficacité : Le CPR surpasse nettement les bases (incluant UaG, CLM et LoFreeCP).
  • Sur WebQSP au niveau de risque $\alpha=0.5$, le CPR a atteint un Taux de Couverture Empirique (ECR) de 61,4 % avec une Taille Moyenne de l'Ensemble de Prédictions (APSS) de 7,14. En revanche, la base de l'état de l'art UaG a atteint un ECR plus faible de 51,8 % avec une APSS beaucoup plus grande de 14,29.
  • Sur le jeu de données plus difficile CWQ, UaG n'a pas réussi à satisfaire les garanties de couverture pour $\alpha \le 0.5$ et a produit des ensembles de prédictions massifs (APSS > 120). Le CPR a maintenu une couverture valide sur tous les niveaux de risque avec une APSS de 8,35 à $\alpha=0.6$.
• Efficacité de Couverture : Le CPR a démontré une amélioration de 140 % de l'Efficacité de Couverture (rapport ECR/APSS) par rapport à UaG sur WebQSP et une amélioration de 15 fois sur CWQ.
• Études d'Ablation : Le retrait de l'orientation PUCT ou du RCVNet a entraîné une dégradation des performances, confirmant que des trajectoires d'entraînement de haute qualité et une notation discriminante sont essentielles pour des ensembles de prédictions compacts et valides.

5. Importance et Revendications

L'article revendique que le CPR fournit un cadre fiable pour la KGQA en comblant le fossé entre la validité statistique formelle de la Prédiction Conforme et la complexité du raisonnement multi-sauts.

• Fiabilité : Il offre des garanties de couverture rigoureuses, assurant que la vérité terrain est contenue dans l'ensemble de prédictions à un niveau de risque spécifié par l'utilisateur.
• Praticité : En réduisant la taille des ensembles de prédictions d'environ 40 % par rapport aux bases conformes tout en améliorant la couverture de 34 %, le CPR rend les prédictions sous forme d'ensemble actionnables pour les systèmes d'aide à la décision.
• Portée : Les auteurs positionnent le CPR comme un outil d'aide à la décision pour des applications à haut risque (santé, finance) où une confiance calibrée est critique. Ils notent explicitement que les garanties de couverture sont statistiques et dépendent de la qualité du graphe de connaissances sous-jacent, et que le CPR ne doit pas remplacer le jugement d'expert dans des domaines critiques pour la sécurité.