Model Change for Description Logic Concepts

Dit artikel introduceert een formeel kader voor het wijzigen van beschrijvingslogica-concepten door middel van evictie, receptie en revisie, en toont aan dat revisie niet eenvoudigweg als een combinatie van de eerste twee kan worden opgevat, terwijl het ook resultaten presenteert over de compatibiliteit van deze operaties voor EL en ALC.

De kern

Stel je voor dat je een recept schrijft voor een gerecht, bijvoorbeeld "Pannenkoek". In de wereld van kunstmatige intelligentie en kennismanagement noemen we zo'n recept een concept. Dit concept beschrijft precies wat er in de pan moet zitten om een pannenkoek te maken.

Maar wat gebeurt er als je tijdens het koken merkt dat je recept niet helemaal klopt met de werkelijkheid? Misschien heb je gedacht dat je alleen bloem en eieren nodig hebt, maar je ziet iemand anders een pannenkoek maken met ook nog eens spek erin. Of misschien heb je gedacht dat je spek nodig hebt, maar blijkt dat je dat juist niet mag gebruiken als je een vegetarische versie wilt.

Dit artikel van Ana Ozaki en Jandson S. Ribeiro gaat over hoe we die recepten (concepten) kunnen aanpassen als we nieuwe informatie krijgen. Ze noemen dit "Model Change" (Modelverandering).

Hier is hoe ze dit uitleggen, vertaald naar alledaagse taal:

1. De Drie Manieren om je Recept te Wijzigen

De auteurs onderscheiden drie manieren om je "recept" aan te passen aan de werkelijkheid:

• Eviction (Het Verjagen):

  • De situatie: Je dacht dat je pannenkoek met spek lekker was, maar je proeft het en het is vreselijk. Je moet die optie uit je recept verwijderen.
  • In het artikel: Je haalt specifieke scenario's (modellen) uit je concept. Je zegt: "Pannenkoek is niet met spek."
  • Het probleem: Soms is het lastig om alleen het spek weg te halen zonder per ongeluk ook de bloem of het ei te verwijderen. Je moet heel voorzichtig zijn om je recept zo klein mogelijk te veranderen.

• Reception (Het Ontvangen):

  • De situatie: Je dacht dat pannenkoek alleen met bloei en eieren ging, maar je ziet iemand een pannenkoek met spek eten die ook heel lekker is. Je moet je recept dus uitbreiden om deze nieuwe optie toe te staan.
  • In het artikel: Je voegt nieuwe scenario's toe aan je concept. Je zegt: "Pannenkoek kan wel met spek."
  • Het probleem: Als je te veel toevoegt, wordt je recept misschien te vaag. Je wilt alleen de specifieke nieuwe optie toevoegen, niet per ongeluk ook "pannenkoek met pizza" toestaan.

• Revision (Het Herzienen - De Gouden Middenweg):

  • De situatie: Dit is het lastigste. Je dacht dat pannenkoek alleen met spek ging (verkeerd), maar je ziet nu dat de beste pannenkoek zonder spek is, maar met kaas. Je moet dus het spek verwijderen én de kaas toevoegen in één beweging.
  • In het artikel: Dit noemen ze Revision. Je verwijdert een set van scenario's en voegt er direct een andere set aan toe.
  • De verrassing: De auteurs ontdekten iets heel belangrijks: Revision is niet gewoon het samenvoegen van Verjagen en Ontvangen. Je kunt ze niet simpelweg achter elkaar doen. Als je eerst het spek verwijdert en daarna de kaas toevoegt, kan het zijn dat je per ongeluk weer het spek erbij haalt of dat je recept in de war raakt. Het is een complexe dans waarbij je alles in één keer moet herschikken.

2. De Uitdaging: De "Kleinste Verandering"

Het grootste doel is om minimale verandering aan te brengen.
Stel je voor dat je een recept hebt voor "Hond".

• Je ziet een hond die geen staart heeft.
• Je wilt je recept aanpassen zodat "geen staart" mogelijk is.
• Maar je wilt niet dat je recept nu ook "vliegende honden" of "honden met drie poten" toelaat.

In de wiskunde van dit artikel (beschreven als Description Logic) proberen ze te bewijzen of het altijd mogelijk is om zo'n perfect, minimaal aangepast recept te maken.

3. Wat Vonden Ze? (De Resultaten)

Ze keken naar twee soorten "recepten" (logische talen):

1. EL- (Eenvoudig): Dit is als een simpele boodschappenlijst.
2. ALC (Compleks): Dit is als een recept met ingewikkelde regels, zoals "als je vlees hebt, dan mag je geen vis hebben, tenzij..."

De bevindingen:

• Bij de simpele recepten (EL-) lukt het vaak wel om dingen netjes te verwijderen of toe te voegen zonder dat alles in de war raakt.
• Bij de complexe recepten (ALC) is het veel lastiger. Soms is het onmogelijk om precies die ene specifieke verandering te maken zonder dat je per ongeluk andere dingen verandert. Het is alsof je probeert een ingewikkeld LEGO-kasteel aan te passen door één steentje weg te halen, maar door de structuur van het kasteel valt er dan een hele muur op.

4. Waarom is dit belangrijk?

Dit onderzoek is cruciaal voor het bouwen van kennisbanken (zoals voor medische diagnoses, robotica of zoekmachines).

• Als een robot denkt dat een "stoel" altijd vier poten heeft, en hij ziet een drie-potige stoel, moet hij zijn kennis kunnen aanpassen zonder dat hij denkt dat een "tafel" nu ook een stoel is.
• Dit artikel geeft wiskundige regels om te zeggen: "Ja, dit is een veilige manier om je kennis te updaten" of "Nee, hier zit een valkuil, je kunt niet zomaar dit specifieke ding aanpassen."

Samenvattend in één zin:

Dit artikel legt uit hoe we onze digitale "recepten" voor de wereld kunnen aanpassen als we nieuwe feiten leren, en waarschuwt dat het combineren van het weghalen van oude ideeën en het toevoegen van nieuwe ideeën vaak ingewikkelder is dan het lijkt, vooral bij complexe regels.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Model Change for Description Logic Concepts" van Ana Ozaki en Jandson S. Ribeiro, geschreven in het Nederlands.

Titel: Model Change voor Beschrijvingslogica Concepten

Auteurs: Ana Ozaki (Universiteit van Oslo) en Jandson S. Ribeiro (Cardiff University)

---

1. Probleemstelling

Het artikel adresseert het probleem van het aanpassen van concepten binnen Beschrijvingslogica (Description Logic - DL) op basis van veranderingen in de onderliggende modellen. In plaats van veranderingen te specificeren via formules (zoals in traditionele geloofsverandering), worden veranderingen hier gespecificeerd door sets van gepunte interpretaties (pointed interpretations), die fungeren als waarnemingen van mogelijke werelden.

De auteurs onderscheiden drie fundamentele soorten modelveranderingen:

1. Eviction (Verjaging): Het verwijderen van een specifieke set modellen uit de huidige conceptuele basis.
2. Reception (Ontvangst): Het integreren van een nieuwe set modellen in de huidige basis.
3. Revision (Herziening): Een gecombineerde operatie waarbij modellen tegelijkertijd worden verwijderd en toegevoegd in één enkele stap.

De kernuitdaging is het garanderen van minimale verandering: de nieuwe conceptuele basis moet zo dicht mogelijk bij de oude blijven, terwijl de nieuwe modelvereisten worden voldaan en de basis eindig representabel blijft (d.w.z. uitgedrukt kan worden als een eindige DL-formule).

---

2. Methodologie

De auteurs gebruiken een formele raamwerk gebaseerd op satisfactie-systemen (satisfaction systems) om logica en modellen te definiëren. Ze analyseren twee veelgebruikte DL's:

• $\mathcal{EL}^\bot$: Een lichtgewicht logica met conjunctie, existentiële restricties en de lege verzameling ($\bot$), maar zonder negatie.
• $\mathcal{ALC}$: Een expressievere logica die ook negatie, disjunctie en universele restricties toestaat.

Belangrijke concepten in de methodologie:

• Rationaliteitspostulaten: De auteurs definiëren een reeks postulaten (succes, persistentie, eindige temperantie, uniformiteit, leegte-expansie, leegte-verwijdering, en circumspectie) om te eisen dat veranderingen "rationeel" en minimaal zijn.
• Compatibiliteit: Een klasse van modellen wordt "compatibel" genoemd als er voor elke input een eindig representabel resultaat bestaat dat aan de rationaliteitspostulaten voldoet.
• Symmetrisch Verschil: Voor revisie wordt gebruik gemaakt van het symmetrisch verschil ($\oplus$) tussen sets van modellen om de "kosten" van verandering te meten en de dichtstbijzijnde eindige representatie te selecteren.
• Bisimulatie: Voor $\mathcal{ALC}$ wordt gebruik gemaakt van het concept van bisimulatie, aangezien $\mathcal{ALC}$-concepten invariant zijn onder bisimulatie. Dit speelt een cruciale rol bij het bepalen van welke modellen onderscheiden kunnen worden.

---

3. Belangrijkste Bijdragen

A. Formele Definitie van Modelherziening (Revision)

De auteurs introduceren een nieuwe operator voor modelherziening. Ze tonen aan dat herziening niet simpelweg een opeenvolgende combinatie van eviction en reception is.

• Reden: Het toepassen van eerst eviction en dan reception (of andersom) kan leiden tot situaties waarbij modellen die verwijderd moesten worden, per ongeluk weer worden toegevoegd, of vice versa, vanwege de beperkte expressiviteit van de logica.
• Ze definiëren een symmetrisch-differentiële revisie-operator die direct de minimale verandering berekent door zowel toevoegingen als verwijderingen simultaan te beschouwen.

B. Compatibiliteitsresultaten voor $\mathcal{EL}^\bot$ en $\mathcal{ALC}$

De auteurs onderzoeken onder welke voorwaarden eviction, reception en revision mogelijk zijn (compatibel zijn) voor de twee logische systemen.

• $\mathcal{EL}^\bot$:
  • Eviction: Is compatibel voor alle modellen.
  • Reception: Is niet compatibel voor algemene sets modellen (er bestaat geen "kleinste" eindig representabel superset voor bepaalde oneindige ketens). Het is echter compatibel voor de klasse van eindige boomvormige gepunte interpretaties.
• $\mathcal{ALC}$:
  • Eviction & Reception: Zijn in het algemeen niet compatibel, zelfs niet voor boomvormige interpretaties, vanwege de complexiteit van negatie en de structuur van de modellen.
  • Positief Resultaat: Er is compatibiliteit voor $\mathcal{ALC}$ wanneer de modellen worden beperkt tot eindige sets van eindige boomvormige interpretaties over een eindig signature, en wanneer de sets gesloten zijn onder bisimulatie.

C. Relatie tussen Operatoren

De auteurs bewijzen dat revisie een overkoepelend concept is:

• Als een klasse van modellen "revisie-compatibel" is, impliceert dit automatisch dat de onderliggende klassen voor alleen toevoegen (reception) en alleen verwijderen (eviction) ook compatibel zijn.
• Revisie kan alleen worden uitgevoerd in klassen die compatibel zijn met zowel reception als eviction.

---

4. Resultaten en Bewijzen

De paper levert zowel positieve als negatieve stellingen (theoremas):

1. Niet-reductie: Revisie reduceert niet tot een seriële combinatie van eviction en reception. Er zijn gevallen waar een seriële aanpak faalt om een geldige, eindige oplossing te vinden, terwijl een directe revisie-operator wel een oplossing vindt (of vice versa, afhankelijk van de volgorde).
2. Onmogelijkheid in $\mathcal{ALC}$: Voor $\mathcal{ALC}$ is het vaak onmogelijk om een concept te herzien dat exact de gewenste modellen toevoegt en verwijdert zonder extra, ongewenste modellen te introduceren, tenzij de modellen aan strenge restricties voldoen (eindigheid, boomstructuur, bisimulatie-sluiting).
3. Constructie van Operators: De auteurs geven een constructie voor een naieve relationele revisie-operator en bewijzen dat deze voldoet aan de rationaliteitspostulaten (vooral circumspectie) als de inputklasse compatibel is.
4. Bisimulatie als Sleutel: Voor $\mathcal{ALC}$ is het cruciaal om te werken met sets die gesloten zijn onder bisimulatie. Omdat $\mathcal{ALC}$-concepten niet kunnen onderscheiden tussen bisimulaire modellen, moet een revisie die het ene model toevoegt, automatisch alle bisimulaire modellen toevoegen.

---

5. Significance en Toekomstperspectief

Wetenschappelijke Impact:

• Dit werk vult een gat in de literatuur over geloofsverandering (belief change) binnen Description Logics. Waar eerdere werken zich vaak richtten op ontologie-expansie of -contractie via formules, richt dit artikel zich op modelgebaseerde verandering, wat meer aansluit bij het proces van ontologie-leren en -validatie.
• Het introduceert een rigoureuze theoretische basis voor het begrijpen van de beperkingen van het aanpassen van concepten in expressieve logica's.

Praktische Relevantie:

• Voor het bouwen van ontologieën (bijv. in de biomedische sector of semantisch web) is het vaak nodig om een concept te corrigeren op basis van nieuwe data (modellen). Deze paper laat zien dat dit niet altijd "minimaal" mogelijk is zonder de expressiviteit van de logica te beperken of extra aannames te doen.
• De resultaten geven aanwijzingen voor ontwikkelaars van ontologie-leer-systemen: als men $\mathcal{ALC}$ gebruikt, moet men rekening houden met de noodzaak van bisimulatie-sluiting bij het verwerken van positieve en negatieve voorbeelden.

Toekomstig Werk:
De auteurs suggereren verdere onderzoeken naar:

• Praktische implementaties van deze operatoren.
• Uitbreiding naar nog expressievere DL's.
• Het toepassen van deze theorie in real-world scenario's voor het leren van ontologieën uit data.

Samenvattend biedt dit artikel een fundamentele analyse van hoe kennis in de vorm van DL-concepten dynamisch kan worden aangepast aan nieuwe waarnemingen, met een scherp inzicht in de theoretische grenzen van minimaliteit en eindigheid.