🤖 AI

Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

Dit artikel stelt een kwantitatief kader voor het opvragen van inconsistente gewogen beschrijvingslogica-kennisbasen door zekere en mogelijke antwoorden te definiëren op basis van kostenbegrensde of optimaal-kosten interpretaties, en biedt een uitgebreide analyse van de computationele complexiteit voor deze problemen over logica's variërend van ELbot tot ALCO.

Oorspronkelijke auteurs: Meghyn Bienvenu, Camille Bourgaux, Robin Jean

Gepubliceerd 2026-08-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Meghyn Bienvenu, Camille Bourgaux, Robin Jean

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De rommelige realiteit van perfecte logica

Stel je voor dat je probeert een enorme puzzel op te lossen, maar iemand heeft stiekem een paar stukjes verwisseld of de randen overgeschilderd. In de wereld van de informatica, specifal in een vakgebied genaamd Knowledge Representation (kennisrepresentatie), bouwen we enorme digitale puzzels die "Knowledge Bases" worden genoemd. Dit zijn als gigantische instructiehandleidingen die computers vertellen hoe de wereld werkt, waarbij een reeks algemene regels (zoals "alle vogels kunnen vliegen") wordt gemengd met specifieke feiten (zoals "Tweety is een vogel").

Meestal zijn deze puzzels ontworpen om perfect te zijn. Als de regels en feiten niet botsen, kan de computer gemakkelijk het antwoord geven op elke vraag die je stelt. Maar in de echte wereld is data rommelig. Soms spreken de feiten de regels tegen, of vechten twee feiten met elkaar. Op de oude manier van doen, als een computer zelfs maar één klein klein beetje tegenstrijdigheid vond, gooide hij zijn digitale handen omhoog en zei: "Ik geef het op! Omdat alles kapot is, kan alles waar zijn." Dit is een probleem, want het betekent dat de computer je geen nuttige antwoorden meer geeft.

Om dit op te lossen, hebben onderzoekers verschillende strategieën geprobeerd. Sommigen proberen de slechte stukjes chirurgisch te verwijderen om de puzzel weer consistent te maken. Anderen zeggen: "Laten we gewoon kijken naar het grootste deel van de puzzel dat wel past." Maar deze methoden behandelen elk stukje data vaak als even belangrijk, of ze dwingen een binaire keuze af: of een regel is een absolute wet, of het is afval. Wat als sommige regels gewoon "meestal waar" zijn en sommige feiten "zeer waarschijnlijk" terwijl andere "misschien" zijn? Dit artikel onderzoekt een nieuwe manier om deze rommelige, tegenstrijdige puzzels aan te pakken door een "prijskaartje" aan elke fout toe te kennen.

De prijskaart-aanpak voor kapotte puzzels

In dit artikel introduceren de auteurs een slimme nieuwe manier om deze rommelige, inconsistente kennisbases te bevragen. In plaats van te proberen de puzzel perfect te maken, behandelen ze het als een spel waarbij je de regels mag breken, maar waarbij je elke keer dat je dat doet, een boete moet betalen.

Beschouw je kennisbase als een strenge uitsmijter bij een club. In de oude dagen, als je zelfs maar één regel overtrad, schopte de uitsmijter je eruit en weigerde hij überhaupt met je te praten. In dit nieuwe systeem heeft de uitsmijter een grootboek. Sommige regels zijn "Hard Laws" (zoals "Je moet 21 zijn om binnen te mogen"), en het breken ervan kost een oneindige hoeveelheid geld — dus dat kun je simpelweg niet doen. Andere regels zijn "Soft Suggestions" (zoals "Draag een stropdas"). Het breken van een zachte regel kost een kleine vergoeding, zeg 5 dollar. Als je een feit hebt dat zeer betrouwbaar is, kost het veel om dat te negeren; als een feit wankel is, kost het heel weinig om dat te negeren.

De computer kijkt vervolgens naar alle mogelijke manieren om de data te interpreteren. Sommige interpretaties breken een paar zachte regels, wat een klein bedrag kost. Andere breken veel regels, wat een fortuin kost. De computer berekent de "totale kosten" voor elk mogelijk scenario.

De auteurs definiëren twee belangrijke manieren om antwoorden te vinden op basis van deze kosten:

De "Best Deal"-benadering: De computer kijkt alleen naar de scenario's die de absoluut minimale hoeveelheid geld kosten. Het vraagt: "Wat is waar op de goedkoopste, meest efficiënte manier om deze chaos zin te geven?"
De "Budget"-benadering: De computer stelt een uitgavenlimiet in (een budget). Het vraagt: "Wat is waar in elk scenario dat onder dit budget blijft?" Dit is nuttig als je wilt weten welke antwoorden "robuust" zijn — wat betekent dat ze standhouden, zelfs als je bereid bent om wat extra te betalen om de data te herstellen.

Het artikel stelt niet alleen dit idee voor; het test ook rigoureus hoe moeilijk het voor een computer is om deze wiskunde uit te voeren. De auteurs analyseerden de "complexiteit" van het probleem, wat in essentie een maatstaf is voor hoeveel rekenkracht en tijd het zou kosten om deze puzzels op te lossen naarmate ze groter worden. Ze keken naar verschillende soorten logicasystemen, variërend van eenvoudige systemen (zoals basiscategorie-regels) tot zeer complexe systemen (met getallen, specifieke namen en ingewikkelde relaties).

Hun bevindingen zijn een mix van goed nieuws en "het hangt ervan af". Ze bewezen dat voor de meest complexe soorten logica, het uitrekenen van de antwoorden ongelooflijk moeilijk is voor computers — het behoort tot een klasse problemen die een exponentiële hoeveelheid tijd in beslag kan nemen naarmate de data groeit. Echter, voor eenvoudigere, meer voorkomende soorten logica die in veel real-world toepassingen worden gebruikt, is het probleem beheersbaar, hoewel nog steeds lastig. Ze ontdekten ook dat de manier waarop je de "kosten" opschrijft (of je nu een simpele telling gebruikt of een enorm getal) bepaalt hoe moeilijk het probleem is voor de computer.

Cruciaal is dat de auteurs laten zien dat deze nieuwe methode niet slechts een gok is; het is een wiskundig bewezen framework. Ze hebben aangetoond dat als je data toevallig perfect is (geen tegenstrijdigheden), hun methode exact dezelfde antwoorden geeft als de traditionele, perfecte methoden. Maar wanneer de data kapot is, geeft hun methode een gerangschikte lijst van antwoorden: sommige zijn "zeker" (ze verschijnen in de goedkoopste, beste scenario's), en sommige zijn "mogelijk" (ze verschijnen in ten minste één goedkoop scenario).

Kortom, dit artikel biedt een wiskundige toolkit waarmee computers kunnen zeggen: "Oké, de data is rommelig, maar als we de minst belangrijke fouten negeren, is dit wat er waarschijnlijk waar is." Het verandert een "systeemcrash" in een "onderhandeling", waardoor we nuttige antwoorden kunnen krijgen, zelfs wanneer de informatie die we hebben verre van perfect is.

Technische Samenvatting: Kostengebaseerde Semantiek voor het Opvragen van Inconsistente Gewogen Kennisbases

Probleemstelling
Ontologie-gestuurde query-beantwoording (OMQA) leunt op Description Logic (DL) kennisbases (KB's) bestaande uit een TBox (ontologie) en een ABox (data). Klassieke OMQA-semantiek, gebaseerd op eerste-orde logica, slaagt er niet in om informatieve antwoorden te geven wanneer de KB inconsistent is, aangezien alles volgt uit een contradictie. Ho ben bestaande benaderingen gaan inconsistentie af via reparaties (bijv. AR en brave semantiek), maar deze gaan doorgaans ervan uit dat de TBox betrouwbaar is en wijzigen alleen de ABox. Bovendien behandelen standaard reparatie-semantieken alle beweringen vaak als even betrouwbaar of vertrouwen ze op cardinaliteit-gebaseerde maximaliteit, waarbij een genuanceerde manier ontbreekt om conflicterende informatie te prioriteren op basis van variërende gradaties van vertrouwen.

Dit artikel pakt de uitdaging aan van het bevragen van inconsistente DL-kennisbases door een kwantitatief framework te introduceren. Het kernprobleem is het definiëren van betekenisvolle zekere en mogelijke antwoorden wanneer zowel TBox-axioma's als ABox-beweringen geschonden kunnen worden, waarbij schendingen worden bestraft volgens toegewezen gewichten.

Methodologie en Framework
De auteurs stellen een Weighted Knowledge Base (WKB) framework voor, aangeduid als $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$ .

Gewichten: Een kostenfunctie $\omega$ wijst een waarde toe in $\mathbb{N}_{>0} \cup \{+\infty\}$ aan elk axioma in $\mathcal{T}$ en elke bewering in $\mathcal{A}$ . Oneindige gewichten vertegenwoordigen "harde" restricties die voldaan moeten worden, terwijl eindige gewichten "zachte" restricties vertegenwoordigen waarbij hogere waarden een grotere betrouwbaarheid aangeven.
Kosten van Interpretatie: De kosten van een interpretatie $I$ worden gedefinieerd als de som van de gewichten van alle geschonden axioma's en beweringen. Specifiek is de kosten voor een concept-inclusie $\tau$ : $\omega_\tau \times |vio_\tau(I)|$ , waarbij $vio_\tau(I)$ de verzameling domeinelementen is die de inclusie schenden. Beweringen kunnen maximaal één keer geschonden worden.
Semantiek: Het artikel definieert vier query-afleidingssemantieken gebaseerd op de kosten van interpretaties:
1. $k$ -cost-bounded certain ( $K_\omega \models^k_c q$ ): $q$ geldt in alle interpretaties met kosten $\le k$ .
2. $k$ -cost-bounded possible ( $K_\omega \models^k_p q$ ): $q$ geldt in ten minste één interpretatie met kosten $\le k$ .
3. Opt-cost certain ( $K_\omega \models^{opt}_c q$ ): $q$ geldt in alle interpretaties met minimale kosten ( $optc(K_\omega)$ ).
4. Opt-cost possible ( $K_\omega \models^{opt}_p q$ ): $q$ geldt in ten minste één interpretatie met minimale kosten.

Het framework generaliseert bestaande reparatie-semantieken. Specifiek, wanneer TBox-axioma's oneindige gewichten hebben, komt de opt-cost certain semantiek overeen met de $\le_\omega$ -AR semantiek (Bienvenu, Bourgaux, en Goasdoué 2014), die reparaties selecteert die de som van de gewichten van behouden beweringen maximaliseren.

Belangrijkste Bijdragen
De primaire bijdrage is een uitgebreide analyse van de gecombineerde en data-complexiteit van de belangrijkste beslissingsproblemen in deze setting:

Bounded Cost Satisfiability (BCS): Bepalen of er een interpretatie met kosten $\le k$ bestaat.
Certain en Possible Answer Recognition: Beslissen van afleiding onder de vier gedefinieerde semantieken.

De studie bestrijkt een reeks Description Logics van de lichte $\mathcal{EL}^\bot$ tot de expressieve $\mathcal{ALCO}$ (en $\mathcal{ALCO}^\mathcal{Q}$ voor upper bound bewijzen), waarbij zowel Instance Queries (IQs) als Conjunctive Queries (CQs) worden behandeld.

Complexiteitsresultaten
Het artikel stelt nauwe complexiteitsgrenzen vast, samengevat als volgt:

Gecombineerde Complexiteit:
- De meeste problemen zijn EXPTIME-compleet.
- Certain answer recognition voor CQs (zowel bounded als opt-cost) is 2EXPTIME-compleet. Deze hoge complexiteit komt voort uit de noodzaak om afleiding te verifiëren over alle modellen van een specifieke kosten, wat gerelateerd is aan gecircumscribeerde KB's.
- Deze grenzen gelden zelfs wanneer gewichten en de kostenlimiet $k$ in binair zijn gecodeerd.
Data-complexiteit:
- Bounded Cost Satisfiability (BCS): NP-compleet.
- Bounded Cost Answering (IQs/CQs): NP-compleet (possible) en coNP-compleet (certain).
- Optimal Cost Answering: De complexiteit hangt sterk af van de codering van de gewichten:
  - Als gewichten in unair zijn gecodeerd of onafhankelijk van de ABox-grootte zijn begrensd, zijn de problemen $\Theta^p_2$ -compleet (oplosbaar in polynomiale tijd met logaritmische aanroepen aan een NP-oracle).
  - Als gewichten in binair zijn gecodeerd en exponentieel ten opzichte van de ABox-grootte kunnen zijn, worden de problemen $\Delta^p_2$ -compleet (oplosbaar in polynomiale tijd met toegang tot een NP-oracle).
- Het artikel merkt op dat voor opt-cost certain semantiek met binaire gewichten de bovenliggende grens openstaat, hoewel de ondergrenzen $\Delta^p_2$ -hard zijn.

Betekenis en Claims
De auteurs claimen een "bijna volledig beeld" te bieden van het complexiteitslandschap voor het bevragen van inconsistente kennisbases onder een kostengebaseerde semantiek. De betekenis van het werk ligt in:

Kwantitatieve Flexibiliteit: Voorbij gaan aan binaire consistentie naar een gegradeerde aanpak waarbij antwoorden gerankt of gefilterd kunnen worden op basis van hun "robuustheid" (d.w.z. of ze gelden in interpretaties nabij de optimale kosten).
Generalisatie: Het verenigen van concepten uit soft constraints in databases (Carmeli et al. 2021) en gewogen reparaties in ontologieën, waarbij wordt aangetoond dat optimale kosten-semantiek geprefereerde reparatie-semantiek natuurlijk generaliseert.
Technische Diepgang: De complexiteitsbewijzen maken gebruik van en passen geavanceerde technieken uit DL-redeneren aan, waaronder:
- Filtratie en bounded model eigenschappen om upper bounds vast te stellen.
- Reducties van cardinaliteit query-beantwoording en gecircumscribeerde KB's om lower bounds vast te stellen.
- Adaptaties van "interlacing" en "quotient" constructies uit de counting query literatuur (Manière 2022) om de specifieke beperkingen van gewogen schendingen te behandelen.

Het artikel concludeert door toekomstige richtingen te identificeren, specifweg de uitbreiding van deze resultaten naar DL's met inverse rollen, role inclusions en functionele rollen (bijv. de DL-Lite familie), waarbij wordt opgemerkt dat de huidige technieken voor upper bounds niet gemakkelijk overdraagbaar zijn naar deze constructen. Het benadrukt ook de uitdaging van het ontwikkelen van praktische algoritmen voor implementatie.

De rommelige realiteit van perfecte logica

De prijskaart-aanpak voor kapotte puzzels

Meer zoals dit