Technisch Samenvatting: Een Regelgebaseerde Aanpak voor het Specificeren van Voorkeuren over Conflicterende Feiten en het Opvragen van Inconsistente Kennisbases

Probleemstelling

Inconsistentie-tolerante semantiek, met name die gebaseerd op subset-reparaties, is een standaardmethode voor het opvragen van kennisbases (KB's) die beperkingen schenden. Hoewel er kaders bestaan om "optimale reparaties" te definiëren met behulp van een prioriteitsrelatie tussen conflicterende feiten (bijv. het geprioriteerde database-framework van Staworko et al.), blijft er een kritiek gat: hoe men de prioriteitsrelatie zelf op een gemakkelijke manier kan specificeren.

De bestaande literatuur gaat ervan uit dat de prioriteitsrelatie gegeven is, maar het is onrealistisch om van gebruikers te verwachten dat zij handmatig een binaire relatie tussen alle conflicterende feiten invoeren. Bovendien kunnen de regels waarmee gebruikers voorkeuren proberen te specificeren cycli induceren (bijv. feit A heeft voorrang op B, B op C, en C op A), waardoor de relatie ongeldig wordt aangezien prioriteitsrelaties acyclisch moeten zijn. Het artikel adresseert de uitdaging van het declaratief specificeren van deze voorkeuren en het oplossen van de resulterende cycli om praktisch gebruik van inconsistente kennisbases mogelijk te maken.

Methodologie

1. Regelgebaseerde Voorkeurspecificatie

De auteurs introduceren een declaratief framework waarbij prioriteitsrelaties worden afgeleid van voorkeursregels die worden geëvalueerd over een dataset $D$ en een meta-database $M$.

• Meta-database: Een dataset $F$ met metadata (bijv. datums, betrouwbaarheid van bronnen) die via unieke identificatoren aan feiten in $D$ is gekoppeld.
• Voorkeursregels: Regels van de vorm $Cond(x_1, x_2) \to pref(x_1, x_2)$, waarbij de body $Cond$ naar het volgende kan verwijzen:
  • De aanwezigheid/afwezigheid van feiten in $D$.
  • Metadata in $F$ (bijv. het vergelijken van datums of betrouwbaarheidsscores).
  • Ontologie-axioma's (bijv. subclass-relaties).
  • Negatie en ongelijkheden.
• Geïnduceerde Relatie: Een regel induceert een voorkeur $pref(id(\alpha), id(\beta))$ als de conditie standhoudt. De werkelijke prioriteitsrelatie $\succ_{\Sigma, K, M}$ wordt gevormd door deze geïnduceerde voorkeuren te filteren om alleen paren $(\alpha, \beta)$ op te nemen die samen in een conflict voorkomen.

2. Omgaan met Cycli

Omdat geïnduceerde relaties cycli kunnen bevatten, stelt het artikel twee complementaire strategieën voor:

• Statische Acyclische Controle: Onderzoeken of een verzameling regels gegarandeerd een acyclische relatie produceert voor elke dataset.
  • Het artikel bewijst dat voor de algemene taal $PL_{DL}$, het controleren van acycliciteit onbeslisbaar is.
  • Echter, voor een beperkte taal $PL_{pos}$ (positieve regels zonder ontologie-atomen of negatie) en binaire ontkenningsbeperkingen, is het probleem beslisbaar in coNP.
  • Het concept sterke acycliciteit wordt geïntroduceerd: een verzameling regels is sterk acyclisch als de geïnduceerde relatie acyclisch is voor elke KB en meta-database, ongeacht conflicten.
• Pragmatische Cyclusresolutie: Wanneer regels niet gegarandeerd acyclisch zijn, staat het systeem gebruikers toe om regels te partitioneren in prioriteitsniveaus ($\Sigma_1, \dots, \Sigma_n$), waarbij lagere indices een hogere prioriteit aangeven. Vier strategieën zijn gedefinieerd om een acyclische sub-relatie te extraheren:
  1. Omhoog gaan ($\succ_u$): Iteratief niveaus toevoegen beginnend bij het laagste index (hoogste prioriteit, $\Sigma_1$), stoppen als het toevoegen van het volgende niveau een cyclus zou vormen.
  2. Omlaag gaan ($\succ_d$): Beginnen met de unie van alle niveaus en iteratief paren verwijderen uit de hoogste index (laagste prioriteit) niveaus die deelnemen aan cycli totdat acycliciteit is bereikt.
  3. Verfijnd Omhoog gaan ($\succ_{ru}$): Een variant die cycli binnen een niveau verwijdert voordat het volgende niveau wordt toegevoegd.
  4. Gegrond ($\succ_g$): Een fixpunt-benadering geïnspireerd door gegronde extensies in argumentatie-frameworks.
  • Het artikel legt theoretische relaties vast tussen deze strategieën (bijv. $\succ_u \subseteq \succ_d \subseteq \succ_g$) en koppelt ze aan bestaande concepten zoals possibilistische reparaties en non-defeated reparaties.

3. Implementatie

De auteurs hebben een end-to-end systeem geïmplementeerd met behulp van Answer Set Programming (ASP):

• Input Codering: Logische programma's coderen de dataset, de meta-database, de beperkingen, queries en voorkeursregels.
• Conflict & Oorzaak Berekening: Het systeem berekent conflicten en oorzaken (minimale inconsistente deelverzamelingen) met behulp van ASP. Opvallend genoeg handelt deze implementatie niet-binaire conflicten af (conflicten van willekeurige grootte), terwijl veel bestaande tools beperkt zijn tot binaire conflicten.
• Prioriteitsberekening: De cyclusresolutie-strategieën zijn gecodeerd als ASP-programma's om de uiteindelijke prioriteitsrelatie af te leiden.
• Query Beantwoording: Het systeem evalueert queries onder verschillende semantieken (Brave, AR, IAR) gecombineerd met reparatietypes (Subset, Pareto-optimaal, Completion-optimaal).

Belangrijkste Resultaten

Theoretische Bijdragen

• Onbeslisbaarheid: Bewezen dat het controleren of een algemene verzameling voorkeursregels een acyclische relatie oplevert onbeslisbaar is.
• Beslisbaarheid: Bewezen dat voor positieve regels zonder ontologie-atomen ($PL_{pos}$) en binaire ontkenningsbeperkingen, acycliciteitscontrole beslisbaar is in coNP.
• Strategie Equivalentie: Vastgesteld dat de voorgestelde cyclusresolutie-strategieën overeenkomen met bekende reparatieconcepten in de literatuur (Possibilistisch, Non-defeated, Grounded) wanneer ze worden gemapt naar een specifieke KB-structuur.

Experimentele Evaluatie

Het systeem werd geëvalueerd op de CQAPri benchmark (synthetische DL-Lite KB's) met variërende groottes (tot ~2M feiten) en conflict-densiteiten.

• Prestaties van Cyclusresolutie:
  • De Going Down ($\succ_d$) strategie bleek in de meeste scenario's aanzienlijk sneller te berekenen dan $\succ_g$ en $\succ_u$, terwijl deze vaak vergelijkbare resultaten produceerde (in veel gevallen samenvallend).
  • De Refined Going Up ($\succ_{ru}$) strategie veroorzaakte geheugenoverstromingen zelfs op kleine datasets vanwege de complexiteit van de ASP-codering.
  • Het systeem slaagde erin prioriteitsrelaties te berekenen voor datasets met hoge conflict-proporties (tot 46%) en een groot aantal voorkeursfeiten.
• Prestaties van Query Beantwoording:
  • Het ASP-gebaseerde systeem was over het algemeen trager dan de bestaande SAT-gebaseerde tool ORBITS (met ordes van grootte op grote datasets) voor het berekenen van antwoorden onder optimale reparatie-semantiek.
  • Echter, het ASP-systeem slaagde er wel in om queries te beantwoorden onder C-AR en C-brave semantiek in gevallen waar ORBITS faalde (time-out of geheugenoverstroming).
  • Het systeem is de eerste die optimale reparatie-gebaseerde semantiek implementeert voor niet-binaire conflicten.

Betekenis en Claims

Het artikel beweert het eerste declaratieve, regelgebaseerde framework te bieden voor het specificeren van prioriteitsrelaties in inconsistente kennisbases, waarmee een gat wordt gedicht dat de praktische adoptie van geprioriteerde reparatie-semantiek heeft belemmerd.

• Flexibiliteit: Door regels te laten verwijzen naar metadata en ontologie-axioma's, biedt het framework een flexibele manier om inconsistentie-managementbeleid te definiëren zonder handmatige binaire relatie-input.
• Cyclusbeheer: Het artikel biedt een pragmatische oplossing voor het cyclusprobleem, met meerdere resolutiestrategieën en theoretische garanties voor specifieke regelklassen.
• Implementatie: De implementatie demonstreert de haalbaarheid van het gebruik van ASP voor deze taak, met name de mogelijkheid om niet-binaire conflicten te behandelen, een functie die ontbreekt in huidige state-of-the-art tools zoals ORBITS.
• Bescheidenheid: De auteurs erkennen dat hoewel hun ASP-implementatie minder efficiënt is dan SAT-gebaseerde benaderingen voor binaire conflicten, het een grotere expressiviteit biedt (behandeling van willekeurige conflictgroottes) en modulariteit (bijv. gemakkelijker uit te breiden naar andere reparatieberekeningen). Ze beweren niet de SAT te hebben overtroffen in pure snelheid, maar benadrukken de unieke capaciteiten van hun aanpak.

Het werk concludeert door toekomstige richtingen te identificeren, waaronder het uitbreiden van statische analyse naar bredere theoretische klassen, het onderzoeken van de uniciteit van optimale reparaties, en het bouwen van een volledig geautomatiseerde pijplijn om logische programma's te genereren uit standaard dataformaten.