🤖 AI

Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

Cet article propose un cadre quantitatif pour l'interrogation de bases de connaissances de logique de description pondérées et inconsistantes en définissant des réponses certaines et possibles basées sur des interprétations à coût borné ou à coût optimal, et fournit une analyse exhaustive de la complexité computationnelle de ces problèmes à travers des logiques allant de ELbot à ALCO.

Auteurs originaux : Meghyn Bienvenu, Camille Bourgaux, Robin Jean

Publié 2026-08-04

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Meghyn Bienvenu, Camille Bourgaux, 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

La réalité désordonnée de la logique parfaite

Imaginez que vous essayiez de résoudre un puzzle géant, mais que quelqu'un ait secrètement échangé quelques pièces ou peint par-dessus les bords. Dans le monde de l'informatique, plus précisément dans un domaine appelé Représentation des Connaissances, nous construisons de gigantesques puzzles numériques appelés « Bases de Connaissances ». Ce sont comme de grands manuels d'instructions qui expliquent à l'ordinateur comment le monde fonctionne, mélangeant un ensemble de règles générales (comme « tous les oiseaux peuvent voler ») avec des faits spécifiques (comme « Tweety est un oiseau »).

Habituellement, ces puzzles sont conçus pour être parfaits. Si les règles et les faits ne s'entrechoquent pas, l'ordinateur peut facilement vous donner la réponse à n'importe quelle question que vous lui posez. Mais dans le monde réel, les données sont désordonnées. Parfois, les faits contredisent les règles, ou deux faits se combattent. Dans l'ancienne méthode, si un ordinateur trouvait une seule petite contradiction, il levait les mains au ciel en criant : « J'abandonne ! Puisque tout est cassé, n'importe quoi pourrait être vrai. » C'est un problème car cela signifie que l'ordinateur cesse de vous donner des réponses utiles.

Pour corriger cela, des chercheurs ont essayé différentes stratégies. Certains tentent de retirer chirurgicalement les mauvaises pièces pour rendre le puzzle cohérent à nouveau. D'autres disent : « Regardons simplement le plus gros morceau du puzzle qui s'emboîte réellement. » Mais ces méthodes traitent souvent chaque donnée comme étant d'égale importance, ou imposent un choix binaire : soit une règle est une loi absolue, soit c'est un déchet. Et si certaines règles étaient juste « généralement vraies », que certains faits étaient « très probables » tandis que d'autres étaient « peut-être » ? Cet article explore une nouvelle façon de gérer ces puzzles contradictoires et désordonnés en attribuant un « prix » à chaque erreur.

L'approche du « Prix » pour les puzzles brisés

Dans cet article, les auteurs présentent une nouvelle méthode ingénieuse pour interroger ces bases de connaissances désordonnées et incohérentes. Au lieu de chercher à forcer la perfection du puzzle, ils le traitent comme un jeu où vous pouvez enfreindre les règles, mais à chaque fois que vous le faites, vous devez payer une amende.

Imaginez votre base de connaissances comme un videur strict à l'entrée d'un club. Dans l'ancien temps, si vous violiez ne serait-ce qu'une seule règle, le videur vous expulsait et refusait de vous parler. Dans ce nouveau système, le videur possède un grand livre de comptes. Certaines règles sont des « Lois Strictes » (comme « Il faut avoir 21 ans pour entrer ») et enfreindre ces lois coûte une somme infinie — il est donc impossible de le faire. D'autres règles sont des « Suggestions Souples » (comme « Portez une cravate »). Enfreindre une règle souple coûte des frais minimes, disons 5 dollars. Si un fait est très fiable, il coûte cher à ignorer ; si un fait est incertain, il coûte très peu.

L'ordinateur examine ensuite toutes les manières possibles d'interpréter les données. Certaines interprétations peuvent enfreindre quelques règles souples, ce qui coûte un peu d'argent. D'autres peuvent en briser beaucoup, ce qui coûte une fortune. L'ordinateur calcule le « coût total » pour chaque scénario possible.

Les auteurs définissent deux manières principales de trouver des réponses basées sur ce coût :

L'approche du « Meilleur Prix » : L'ordinateur ne regarde que les scénarios qui coûtent le montant absolument minimum. Il demande : « Qu'est-ce qui est vrai de la manière la plus économique et la plus efficace de donner un sens à ce désordre ? »
L'approche du « Budget » : L'ordinateur fixe une limite de dépenses (un budget). Il demande : « Qu'est-ce qui est vrai dans n'importe quel scénario qui reste sous ce budget ? » Cela est utile si vous voulez savoir quelles réponses sont « robustes », c'est-à-dire qu'elles restent vraies même si vous êtes prêt à payer un peu plus pour corriger les données.

L'article ne se contente pas de proposer cette idée ; il teste rigoureusement la difficulté pour un ordinateur d'effectuer ces calculs. Les auteurs ont analysé la « complexité » du problème, ce qui est essentiellement une mesure de la puissance de calcul et du temps nécessaires pour résoudre ces puzzles à mesure qu'ils grandissent. Ils ont examiné différents types de systèmes logiques, allant de simples (comme des règles de catégories de base) à très complexes (avec des nombres, des noms spécifiques et des relations intriquées).

Leurs conclusions sont un mélange de bonnes nouvelles et de « cela dépend ». Ils ont prouvé que pour les types de logique les plus complexes, déterminer les réponses est incroyablement difficile pour les ordinateurs — c'est une classe de problèmes qui pourrait prendre un temps exponentiel à mesure que les données augmentent. Cependant, pour les types de logique plus simples et plus courants utilisés dans de nombreuses applications réelles, le problème est gérable, bien que toujours délicat. Ils ont également découvert que la manière dont vous inscrivez les « coûts » (que vous utilisiez un simple décompte ou un nombre immense) modifie la difficulté du problème pour l'ordinateur.

Crucialement, les auteurs démontrent que cette nouvelle méthode n'est pas qu'une supposition ; c'est un cadre mathématiquement prouvé. Ils ont démontré que si vos données s'avèrent parfaites (sans contradictions), leur méthode donne exactement les mêmes réponses que les méthodes traditionnelles et parfaites. Mais quand les données sont brisées, leur méthode fournit une liste classée de réponses : certaines sont « certaines » (elles apparaissent dans les scénarios les moins chers et les meilleurs), et d'autres sont « possibles » (elles apparaissent dans au moins un scénario peu coûteux).

En résumé, cet article fournit un outil mathématique permettant aux ordinateurs de dire : « D'accord, les données sont désordonnées, mais si nous ignorons les erreurs les moins importantes, voici ce qui est le plus susceptible d'être vrai. » Cela transforme un « plantage système » en une « négociation », nous permettant d'obtenir des réponses utiles même lorsque les informations dont nous disposons sont loin d'être parfaites.

Résumé technique : Sémantique basée sur les coûts pour l'interrogation de bases de connaissances pondérées inconsistantes

Énoncé du problème
L'interrogation de requêtes médiée par des ontologies (OMQA) repose sur des bases de connaissances (KB) de logique de description (DL) composées d'une TBox (ontologie) et d'une ABox (données). La sémantique classique de l'OMQA, basée sur la logique du premier ordre, ne parvient pas à fournir des réponses informatives lorsque la KB est inconsistante, car tout est entraîné à partir d'une contradiction. Bien que les approches existantes gèrent l'inconsistance via des réparations (par exemple, les sémantiques AR et brave), celles-ci supposent généralement que la TBox est fiable et ne modifient que l'ABox. De plus, les sémantiques de réparation standard traitent souvent toutes les assertions comme étant d'une fiabilité égale ou reposent sur une maximalité basée sur la cardinalité, manquant ainsi d'un moyen nuancé de hiérarchiser les informations conflictuelles selon des degrés de confiance variables.

Cet article aborde le défi de l'interrogation des KB de DL inconsistantes en introduisant un cadre quantitatif. Le problème central est de définir des réponses certaines et possibles significatives lorsque tant les axiomes de la TBox que les assertions de l'ABox peuvent être violés, les violations étant pénalisées selon des poids assignés.

Méthodologie et cadre
Les auteurs proposent un cadre de Base de Connaissances Pondérée (WKB), noté $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$ .

Poids : Une fonction de coût $\omega$ assigne une valeur dans $\mathbb{N}_{>0} \cup \{+\infty\}$ à chaque axiome de $\mathcal{T}$ et chaque assertion de $\mathcal{A}$ . Les poids infinis représentent des contraintes « dures » qui doivent être satisfaites, tandis que les poids finis représentent des contraintes « douces » où des valeurs plus élevées indiquent une plus grande fiabilité.
Coût d'interprétation : Le coût d'une interprétation $I$ est défini comme la somme des poids de tous les axiomes et assertions violés. Plus précisément, pour une inclusion de concept $\tau$ , le coût inclut $\omega_\tau \times |vio_\tau(I)|$ , où $vio_\tau(I)$ est l'ensemble des éléments du domaine violant l'inclusion. Les assertions peuvent être violées au plus une fois.
Sémantique : L'article définit quatre sémantiques d'implication de requêtes basées sur le coût des interprétations :
1. $k$ -coût-borné certain ( $K_\omega \models^k_c q$ ) : $q$ est vrai dans toutes les interprétations de coût $\le k$ .
2. $k$ -coût-borné possible ( $K_\omega \models^k_p q$ ) : $q$ est vrai dans au moins une interprétation de coût $\le k$ .
3. Coût-opt-certain ( $K_\omega \models^{opt}_c q$ ) : $q$ est vrai dans toutes les interprétations de coût minimal ( $optc(K_\omega)$ ).
4. Coût-opt-possible ( $K_\omega \models^{opt}_p q$ ) : $q$ est vrai dans au moins une interprétation de coût minimal.

Le cadre généralise les sémantiques de réparation existantes. Plus précisément, lorsque les axiomes de la TBox ont des poids infinis, la sémantique de coût-opt-certain coïncide avec la sémantique $\le_\omega$ -AR (Bienvenu, Bourgaux et Goasdoué 2014), qui sélectionne les réparations maximisant la somme des poids des assertions conservées.

Principales contributions
La principale contribution est une analyse complète de la complexité combinée et de la complexité des données des principaux problèmes de décision dans ce contexte :

Satisfaisabilité à coût borné (BCS) : Déterminer s'il existe une interprétation de coût $\le k$ .
Reconnaissance de réponses certaines et possibles : Décider de l'implication sous les quatre sémantiques définies.

L'étude couvre une gamme de logiques de description allant de la version légère $\mathcal{EL}^\bot$ à la version expressive $\mathcal{ALCO}$ (et $\mathcal{ALCO}^\mathcal{Q}$ pour les preuves de bornes supérieures), traitant à la fois les requêtes d'instance (IQ) et les requêtes conjonctives (CQ).

Résultats de complexité
L'article établit des bornes de complexité serrées, résumées comme suit :

Complexité combinée :
- La plupart des problèmes sont EXPTIME-complets.
- La reconnaissance de réponses certaines pour les CQ (tant bornées que coût-opt) est 2EXPTIME-complète. Cette haute complexité provient de la nécessité de vérifier l'implication à travers tous les modèles d'un coût spécifique, ce qui est lié aux KB circonscrites.
- Ces bornes tiennent même lorsque les poids et la borne de coût $k$ sont encodés en binaire.
Complexité des données :
- Satisfaisabilité à coût borné (BCS) : NP-complète.
- Réponse à coût borné (IQ/CQ) : NP-complète (possible) et coNP-complète (certaine).
- Réponse à coût optimal : La complexité dépend fortement de l'encodage des poids :
  - Si les poids sont encodés en unaire ou sont bornés indépendamment de la taille de l'ABox, les problèmes sont $\Theta^p_2$ -complets (solvables en temps polynomial avec un nombre logarithmique d'appels à un oracle NP).
  - Si les poids sont encodés en binaire et peuvent être exponentiels par rapport à la taille de l'ABox, les problèmes deviennent $\Delta^p_2$ -complets (solvables en temps polynomial avec accès à un oracle NP).
- L'article note que pour la sémantique de coût-opt-certain avec des poids binaires, la borne supérieure reste ouverte, bien que les bornes inférieures soient $\Delta^p_2$ -dures.

Signification et affirmations
Les auteurs affirment fournir un « tableau presque complet » du paysage de la complexité pour l'interrogation des KB inconsistantes sous une sémantique basée sur les coûts. La signification de ce travail réside dans :

Flexibilité quantitative : Passer d'une consistance binaire à une approche graduée où les réponses peuvent être classées ou filtrées en fonction de leur « robustesse » (c'est-à-dire si elles sont vraies dans des interprétations proches du coût optimal).
Généralisation : Unifier les concepts de contraintes douces dans les bases de données (Carmeli et al. 2021) et les réparations pondérées dans les ontologies, montrant que les sémantiques de coût optimal généralisent naturellement les sémantiques de réparation préférées.
Profondeur technique : Les preuves de complexité exploitent et adaptent des techniques avancées de raisonnement en DL, notamment :
- La filtration et les propriétés de modèles bornés pour établir des bornes supérieures.
- Des réductions à partir de la réponse aux requêtes de cardinalité et des KB circonscrites pour établir des bornes inférieures.
- Des adaptations des constructions d'« entrelacement » et de « quotient » de la littérature sur les requêtes de comptage (Manière 2022) pour gérer les contraintes spécifiques des violations pondérées.

L'article conclut en identifiant des directions futures, spécifiquement l'extension de ces résultats aux DL avec rôles inverses, inclusions de rôles et rôles fonctionnels (par exemple, la famille DL-Lite), notant que les techniques actuelles pour les bornes supérieures ne se transfèrent pas aisément à ces constructions. Il souligne également le défi du développement d'algorithmes pratiques pour l'implémentation.

La réalité désordonnée de la logique parfaite

L'approche du « Prix » pour les puzzles brisés

Articles similaires