🤖 AI

A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases

Cet article introduit un cadre déclaratif basé sur des règles qui utilise la programmation par ensembles de réponses pour spécifier et calculer les relations de priorité entre des faits conflictuels pour l'interrogation de bases de connaissances inconsistantes, en abordant les défis des préférences cycliques par une analyse d'acyclicité et des techniques pragmatiques de suppression de cycles.

Auteurs originaux : Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean

Publié 2026-08-04

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean

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 soyez le bibliothécaire d'une bibliothèque massive et chaotique où certains livres ont été accidentellement collés ensemble avec des pages contradictoires. Un livre dit : « Le ciel est bleu », tandis qu'un autre, collé sur la même étagère, soutient que « Le ciel est vert ». Dans le monde de l'informatique, on appelle cela une « base de connaissances inconsistante ». Lorsqu'un ordinateur essaie de répondre à une question en utilisant cette bibliothèque désordonnée, il se retrouve bloqué. Pour résoudre cela, les scientifiques ont développé une méthode appelée « réparation ». Considérez cela comme un bibliothécaire qui, au lieu de jeter toute la bibliothèque, découpe soigneusement les pages conflictuelles pour créer une version propre et cohérente de l'histoire. Mais voici la partie délicate : si vous avez cent pages conflictuelles, il existe des milliers de façons de les découper. Quelle version de l'histoire l'ordinateur devrait-il croire ?

Habituellement, l'ordinateur essaie d'être super prudent et n'accepte que les réponses qui apparaissent dans chaque version propre possible. Mais parfois, nous savons que certains faits sont plus fiables que d'autres. Peut-être que le livre sur le « ciel bleu » a été écrit par un astronome célèbre, tandis que celui sur le « ciel vert » est le gribouillage d'un enfant. Si nous pouvions dire à l'ordinateur : « Faites confiance à l'astronome plutôt qu'au gribouillage », il pourrait choisir la meilleure version de l'histoire. C'est là qu'intervient le nouvel article. Il s'attaque au problème de savoir comment dire à l'ordinateur quels faits sont meilleurs sans forcer un humain à classer manuellement chaque page de la bibliothèque.

Les auteurs, une équipe de chercheurs de France et du Japon, ont construit un nouveau système ingénieux qui permet aux utilisateurs d'écrire de simples « règles de préférence » pour résoudre ce casse-tête. Au lieu de trier manuellement des milliers de faits, vous pouvez simplement écrire des instructions telles que : « Si deux faits entrent en conflit, conservez le plus récent », ou « Si un fait provient d'une source fiable, conservez-le plutôt qu'un fait provenant d'une source inconnue ». L'article introduit un cadre où ces règles génèrent automatiquement une liste de priorité, indiquant à l'ordinateur quels faits sauvegarder et lesquels écarter lorsque des conflits surviennent.

Cependant, il y a un piège. Si vous écrivez trop de règles, elles pourraient entrer dans une boucle. Par exemple, la Règle A dit que le « Fait 1 est meilleur que le Fait 2 », la Règle B dit que le « Fait 2 est meilleur que le Fait 3 », mais la Règle C dit que le « Fait 3 est meilleur que le Fait 1 ». Cela crée un argument circulaire où rien n'est véritablement le meilleur. La découverte principale de l'article est un ensemble de stratégies pour briser ces boucles. Les auteurs proposent quatre méthodes différentes pour démêler ces nœuds, allant d'une méthode « ascendante » (en donnant la priorité aux règles les plus importantes en premier) à une méthode « ancrée » (en ne faisant confiance qu'aux faits qui ne font pas partie d'une boucle déroutante). Ils ont testé ces méthodes à l'aide d'un programme informatique appelé « Programmation par ensembles de réponses » (Answer Set Programming), qui est comme un solveur logique super intelligent.

Les chercheurs ont constaté que bien que leur système soit puissant et flexible, il peut être un peu lent par rapport aux méthodes plus anciennes et plus rigides, surtout lorsqu'il traite d'énormes bibliothèques de données. Dans leurs expériences, ils ont testé des scénarios comprenant jusqu'à 2 millions de faits et ont constaté que leur système pouvait réussir à démêler des conflits complexes et à répondre à des questions, même lorsque les conflits étaient désordonnés et non binaires (impliquant plus de deux faits). Ils ont également prouvé mathématiquement que pour certains types de règles simples, vous pouvez être sûr à 100 % que le système ne restera pas bloqué dans une boucle, mais que pour des règles plus complexes, vous devrez peut-être utiliser leurs stratégies de « rupture de boucle ». En fin de compte, cet article ne propose pas seulement une nouvelle façon de réparer des données désordonnées ; il offre un moyen pour les humains d'exprimer leur logique en règles de langage courant, laissant l'ordinateur gérer le travail complexe de décider quelle version de la vérité croire.

Résumé technique : Une approche par règles pour la spécification de préférences sur des faits conflictuels et l'interrogation de bases de connaissances incohérentes

Énoncé du problème

La sémantique tolérante à l'incohérence, particulièrement celle basée sur les réparations de sous-ensembles (subset repairs), est une approche standard pour interroger des bases de connaissances (BC) qui violent des contraintes. Bien que des cadres existent pour définir des « réparations optimales » en utilisant une relation de priorité entre des faits conflictuels (par exemple, le cadre de bases de données prioritaires de Staworko et al.), un fossé critique subsiste : comment spécifier commodément la relation de priorité elle-même.

La littérature existante suppose que la relation de priorité est donnée, mais il est irréaliste de s'attendre à ce que les utilisateurs saisissent manuellement une relation binaire entre tous les faits conflictuels. De plus, lorsque les utilisateurs tentent de spécifier des préférences via des règles, ces règles peuvent induire des cycles (par exemple, le fait A est préféré à B, B à C, et C à A), rendant la relation invalide puisque les relations de priorité doivent être acycliques. Le papier traite le défi de la spécification déclarative de ces préférences et de la résolution des cycles qui en résultent afin de permettre l'interrogation pratique de bases de connaissances incohérentes.

Méthodologie

1. Spécification de préférences par règles

Les auteurs introduisent un cadre déclaratif où les relations de priorité sont dérivées de règles de préférence évaluées sur un ensemble de données $D$ et une métabase $M$ .

Métabase : Un ensemble de données $F$ contenant des métadonnées (ex: dates, fiabilité de la source) liées aux faits dans $D$ via des identifiants uniques.
Règles de préférence : Des règles de la forme $Cond(x_1, x_2) \to pref(x_1, x_2)$ $C o n d (x_{1}, x_{2}) \to p r e f (x_{1}, x_{2})$ , où le corps $Cond$ peut référencer :
- La présence/absence de faits dans $D$ .
- Des métadonnées dans $F$ (ex: comparaison de dates ou de scores de fiabilité).
- Des axiomes d'ontologie (ex: relations de sous-classe).
- La négation et les inégalités.
Relation induite : Une règle induit une préférence $pref(id(\alpha), id(\beta))$ si la condition est remplie. La relation de priorité réelle $\succ_{\Sigma, K, M}$ est formée en filtrant ces préférences induites pour n'inclure que les paires $(\alpha, \beta)$ qui apparaissent ensemble dans un conflit.

2. Gestion des cycles

Puisque les relations induites peuvent contenir des cycles, le papier propose deux stratégies complémentaires :

Vérification d'acyclicité statique : Étudier si un ensemble de règles garantit la production d'une relation acyclique pour n'importe quel ensemble de données.
- Le papier prouve que pour le langage général $PL_{DL}$ , la vérification de l'acyclicité est indécidable.
- Cependant, pour un langage restreint $PL_{pos}$ (règles positives sans atomes d'ontologie ni négation) et des contraintes de déni binaires, le problème est décidable en coNP.
- Le concept d'acyclicité forte est introduit : un ensemble de règles est fortement acyclique si la relation induite est acyclique pour n'importe quelle BC et métabase, indépendamment des conflits.
Résolution pragmatique des cycles : Lorsque les règles ne sont pas garanties acycliques, le système permet aux utilisateurs de partitionner les règles en niveaux de priorité ( $\Sigma_1, \dots, \Sigma_n$ $Σ_{1}, \dots, Σ_{n}$ ), où les indices plus bas dénotent une priorité plus élevée. Quatre stratégies sont définies pour extraire une sous-relation acyclique :
1. Montée ( $\succ_u$ ) : Ajout itératif des niveaux en partant du plus bas indice (priorité la plus haute, $\Sigma_1$ ), en s'arrêtant si l'ajout du niveau suivant formerait un cycle.
2. Descente ( $\succ_d$ ) : Partir de l'union de tous les niveaux et retirer itérativement les paires des niveaux d'indice le plus élevé (priorité la plus basse) qui participent à des cycles jusqu'à ce que l'acyclicité soit atteinte.
3. Montée raffinée ( $\succ_{ru}$ ) : Une variante qui supprime les cycles au sein d'un même niveau avant d'ajouter le niveau suivant.
4. Fondée ( $\succ_g$ ) : Une approche de point fixe inspirée des extensions fondées dans les cadres d'argumentation.
- Le papier établit des relations théoriques entre ces stratégies (ex: $\succ_u \subseteq \succ_d \subseteq \succ_g$ ) et les lie à des notions de réparation existantes comme les réparations possibilistes et les réparations non défaites.

3. Implémentation

Les auteurs ont implémenté un système de bout en bout utilisant la programmation de l'ensemble des modèles (ASP - Answer Set Programming) :

Encodage des entrées : Les programmes logiques encodent l'ensemble de données, la métabase, les contraintes, les requêtes et les règles de préférence.
Calcul des conflits et des causes : Le système calcule les conflits et les causes (sous-ensembles inconsistants minimaux) en utilisant l'ASP. Notamment, cette implémentation gère les conflits non binaires (conflits de taille arbitraire), alors que de nombreux outils existants sont limités aux conflits binaires.
Calcul de la priorité : Les stratégies de résolution de cycles sont encodées sous forme de programmes ASP pour dériver la relation de priorité finale.
Réponse aux requêtes : Le système évalue les requêtes sous diverses sémantiques (Brave, AR, IAR) combinées à divers types de réparations (Subset, Pareto-optimal, Completion-optimal).

Résultats clés

Contributions théoriques

Indécidabilité : Prouvé qu'un ensemble général de règles de préférence produisant une relation acyclique est indécidable.
Décidabilité : Prouvé que pour les règles positives sans atomes d'ontologie ( $PL_{pos}$ ) et les contraintes de déni binaires, la vérification de l'acyclicité est décidable en coNP.
Équivalence des stratégies : Établi que les stratégies de résolution de cycles proposées correspondent à des notions de réparation connues dans la littérature (Possibiliste, Non-défaite, Fondée) lorsqu'elles sont appliquées à une structure de BC spécifique.

Évaluation expérimentale

Le système a été évalué sur le benchmark CQAPri (BC DL-Lite synthétiques) avec des tailles variables (jusqu'à ~2M de faits) et des densités de conflit variables.

Performance de la résolution de cycles :
- La stratégie Descente ( $\succ_d$ ) s'est avérée nettement plus rapide à calculer que $\succ_g$ et $\succ_u$ dans la plupart des scénarios, tout en produisant souvent des résultats similaires (coïncidant dans de nombreux cas).
- La stratégie Montée raffinée ( $\succ_{ru}$ ) a provoqué des dépassements de mémoire (memory overflows) même sur de petits jeux de données en raison de la complexité de l'encodage ASP.
- Le système a réussi à calculer des relations de priorité pour des ensembles de données présentant des proportions de conflits élevées (jusqu'à 46 %) et un grand nombre de faits de préférence.
Performance de réponse aux requêtes :
- Le système basé sur l'ASP est généralement plus lent que l'outil existant basé sur le SAT, ORBITS (de plusieurs ordres de grandeur sur de grands ensembles de données) pour calculer les réponses sous des sémantiques de réparation optimales.
- Cependant, le système ASP a réussi à répondre aux requêtes sous les sémantiques C-AR et C-brave dans des cas où ORBITS a échoué (dépassement de temps ou de mémoire).
- Le système est le premier à implémenter des sémantiques de réparation optimale pour les conflits non binaires.

Signification et revendications

Le papier affirme fournir le premier cadre déclaratif et basé sur des règles pour spécifier les relations de priorité dans les BC incohérentes, comblant ainsi un vide qui a entravé l'adoption pratique des sémantiques de réparation prioritaires.

Flexibilité : En permettant aux règles de référencer des métadonnées et des axiomes d'ontologie, le cadre offre un moyen flexible de définir des politiques de gestion de l'incohérence sans saisie manuelle de relations binaires.
Gestion des cycles : Le papier propose une solution pragmatique au problème des cycles, offrant plusieurs stratégies de résolution et des garanties théoriques pour des classes de règles spécifiques.
Implémentation : L'implémentation démontre la faisabilité de l'utilisation de l'ASP pour cette tâche, notamment sa capacité à gérer les conflits non binaires, une fonctionnalité absente des outils de pointe actuels comme ORBITS.
Modestie : Les auteurs reconnaissent que, bien que leur implémentation ASP soit moins efficace que les approches basées sur le SAT pour les conflits binaires, elle offre une plus grande expressivité (gestion de conflits de tailles arbitraires) et une meilleure modularité (ex: facilité d'extension à d'autres calculs de réparation). Ils ne prétendent pas avoir surpassé le SAT en vitesse brute, mais soulignent les capacités uniques de leur approche.

Le travail conclut en identifiant des directions futures, notamment l'extension de l'analyse statique à des classes de théories plus larges, l'étude de l'unicité des réparations optimales, et la construction d'un pipeline entièrement automatisé pour générer des programmes logiques à partir de formats de données standards.