Model Change for Description Logic Concepts

This paper introduces a formal framework for "model change" in description logic concepts, distinguishing between eviction, reception, and revision, and demonstrates that revision is a distinct operation that cannot be simply reduced to a combination of the other two while analyzing their compatibility within EL and ALC logics.

The Gist

Imagine you are a Librarian in charge of a very special library. This library doesn't store books; it stores Concepts.

In this library, a "Concept" (like "Dog," "Mammal," or "Platypus") is defined by a list of stories (called models) that fit that description.

• If you say "A Platypus is a mammal that lays eggs," your library contains every possible story where a creature fits that description.
• If you see a real platypus eating an insect, you realize your current list of stories is slightly wrong. You need to update your Concept.

This paper is about how to update these Concepts when you get new information, using three specific tools. The authors call this process "Model Change."

Here is the breakdown of their ideas using simple analogies:

1. The Three Tools of Change

The authors identify three ways to fix your library's definitions:

A. Eviction (The "Bouncer")

• What it is: You realize a story in your library is false. You kick it out.
• The Analogy: Imagine you thought "All birds can fly." Then you see a penguin. You realize your definition is too broad. You must evict the penguin from your "Flying Bird" list.
• The Goal: Remove the bad stories while keeping as many good stories as possible. You don't want to throw away the eagles just because you kicked out the penguin.

B. Reception (The "Welcomer")

• What it is: You realize your definition is too narrow. You need to let new stories in.
• The Analogy: You thought "Marsupials are only Koalas and Kangaroos." Then you see a Tasmanian Devil and learn it's a marsupial too. You must receive the Tasmanian Devil into your list.
• The Goal: Add the new story without accidentally letting in things that aren't marsupials (like a cat).

C. Revision (The "Tightrope Walker")

• What it is: You have to do both at the same time. You must kick out a story and let a new one in, in a single move.
• The Analogy: Imagine you thought "Koalas are mammals that are not placental." Then you read a sign saying, "Actually, Koalas are placental."
  • You must evict the story where the Koala is non-placental.
  • You must receive the story where the Koala is placental.
  • The Catch: You can't just do Eviction first, then Reception. Why? Because kicking out the "non-placental" story might accidentally kick out the "placental" story too, or the logic might get tangled. You have to find a new definition that does both perfectly in one go.

2. The Big Surprise: Revision is NOT Just A + B

The authors discovered something counter-intuitive. You might think: "Revision is just Eviction followed by Reception."

They proved this is wrong.

• The Metaphor: Imagine you are trying to fix a leaky boat.
  • Eviction is plugging the hole.
  • Reception is adding a new seat.
  • Revision is trying to plug the hole and add the seat simultaneously without the boat sinking in the middle.
• Sometimes, if you plug the hole first, the boat shifts, and you can't add the seat. If you add the seat first, the boat tilts, and you can't plug the hole.
• The Result: Sometimes, it is impossible to simply combine the two steps. You need a completely new strategy (a new "Concept") that satisfies both conditions at once. In some complex logic systems (like ALC), this "Revision" is so tricky that it might be impossible to do perfectly without breaking other rules.

3. The "Finiteness" Problem

The authors also ran into a practical problem: The Library is Infinite.

• In the real world, there are infinite variations of stories.
• The Problem: Sometimes, when you try to kick out one bad story (Eviction) or let in one new story (Reception), the math forces you to kick out infinite other stories or let in infinite others just to keep the definition "finite" (manageable).
• The Solution: They found that for some types of logic (like EL), you can usually do this cleanly. But for more complex logic (like ALC), it's often impossible to find a "perfectly minimal" change. You might have to accept a "good enough" change that includes a few extra stories you didn't strictly need, just to keep the definition from becoming an infinite mess.

4. The "Tree" Analogy

To make sense of this, the authors look at the stories as Trees.

• Imagine every story is a tree growing from a root.
• If two trees look exactly the same from the outside (even if their internal roots are different), they are "bisimilar."
• The authors found that if you restrict your library to only "Tree-shaped" stories (which are simpler), you can often perform these updates successfully. But if you allow "weird" shapes or infinite loops, the update tools (Eviction, Reception, Revision) often break.

Summary: What did they actually do?

1. Defined the Rules: They created a strict mathematical rulebook for how to Evict, Receive, and Revise concepts.
2. Found the Limits: They proved that for some complex logic systems, you cannot simply combine Eviction and Reception to get Revision. Revision is its own unique, difficult beast.
3. Mapped the Territory: They created a map showing exactly which types of logic (EL vs. ALC) and which types of stories (simple trees vs. complex webs) allow for these updates to work smoothly, and which ones cause the system to crash.

In a nutshell:
Updating your beliefs (or a computer's database) isn't just about deleting old facts and adding new ones. Sometimes, you have to rewrite the whole rulebook to fit the new reality, and depending on how complex your world is, you might not always be able to do it without breaking something else. The authors figured out exactly when you can do it and when you can't.

Technical Summary

Here is a detailed technical summary of the paper "Model Change for Description Logic Concepts" by Ana Ozaki and Jandson S. Ribeiro.

1. Problem Statement

The paper addresses the problem of model change in Description Logics (DL). Unlike traditional belief revision, which modifies a knowledge base using logical formulae, this work considers modifications based on pointed interpretations (models).

In many practical scenarios (e.g., ontology learning or debugging), an agent observes specific models of the world (positive and negative examples) and needs to update their conceptual beliefs (DL concepts) to accommodate these observations. The authors define three fundamental operations:

1. Eviction: Removing a set of models from the set of models satisfying a concept (retraction).
2. Reception: Incorporating a set of models into the set of models satisfying a concept (expansion).
3. Revision: A complex operation that simultaneously removes a set of models ($M^-$) and adds a set of models ($M^+$) in a single step.

The core challenge is to perform these operations while adhering to the principle of minimal change. This means the resulting concept must be finitely representable (a valid DL concept) and must change the original set of models as little as possible, only adding or removing models strictly necessary to achieve finiteness.

2. Methodology and Framework

Formal Setting

• Logic: The authors focus on $\mathcal{EL}^\bot$ (allowing the empty concept) and $\mathcal{ALC}$ (allowing negation and disjunction).
• Semantics: Concepts are interpreted over pointed interpretations $(I, d)$, where $I$ is an interpretation and $d$ is a designated element in the domain.
• Satisfaction Systems: The authors utilize a general framework of satisfaction systems $(L, \mathcal{M}, \models)$ to define logics, allowing for the analysis of finite representability.
• Rationality Postulates: The authors adapt and extend rationality postulates from belief change theory (e.g., Success, Inclusion, Persistence, Uniformity) to the context of model change.
  • Success: The new concept must satisfy the required models (for reception/revision) or exclude the forbidden models (for eviction).
  • Finite Temperance/Retainment: Extra models added or removed beyond the input set must be minimized to ensure the result is finitely representable.
  • Circumspection: A specific postulate for revision ensuring that any extra additions or removals are strictly necessary to achieve a finite representation.

Key Definitions

• Compatibility: A class of models is reception-compatible (or eviction-compatible) if, for any base and any set of models to add/remove, there exists a "closest" finitely representable set of models (a least finitely representable superset or greatest finitely representable subset).
• Revision-Realisability: A binary class of model pairs $(M^+, M^-)$ is revision-realisable if there exists a finitely representable set containing $M^+$ and disjoint from $M^-$.
• Revision-Compatibility: A class is revision-compatible if a revision operator exists that satisfies all rationality postulates (Success, Vacuous-Expansion, Vacuous-Removal, and Circumspection).

3. Key Contributions

A. Theoretical Study of Eviction and Reception

The authors provide a comprehensive analysis of when eviction and reception are possible for $\mathcal{EL}^\bot$ and $\mathcal{ALC}$ concepts under different constraints on the class of models (e.g., tree-shaped, finite, finite signature).

• $\mathcal{EL}^\bot$:
  • Eviction: Compatible for all models.
  • Reception: Not compatible for general models or even for tree-shaped models over infinite signatures. However, it is compatible if restricted to finite tree-shaped pointed interpretations.
• $\mathcal{ALC}$:
  • Eviction: Not compatible for general models.
  • Reception: Not compatible for general models or even for finite tree-shaped models over infinite signatures.
  • Positive Result: Both eviction and reception become compatible if restricted to finite sets of finite tree-shaped pointed interpretations over a finite signature.

B. Introduction of Model Revision

The paper introduces Model Revision as a distinct operation, arguing that it cannot be reduced to a simple sequential combination of eviction and reception.

• Non-Commutativity/Non-Decomposability: Performing eviction then reception (or vice versa) often fails to satisfy the minimal change principle because the intermediate step might force the inclusion/exclusion of models that should have been handled differently in a single step.
• Formalization: Revision is defined via a symmetric difference minimization strategy. The authors define a Symmetric-Differential Revision Operator that selects the finitely representable model set minimizing the symmetric difference with the original base, subject to the constraints of $M^+$ and $M^-$.
• Characterization: They prove that an operator satisfies the rationality postulates for revision if and only if it is a symmetric-differential revision operator.

C. Relationship Between Operations

The paper establishes a deep theoretical link between the three operations:

• Decomposability: If a binary class of models is decomposable (meaning it allows for pure reception $(M^+, \emptyset)$ and pure eviction $(\emptyset, M^-)$), then Revision-Compatibility implies both Reception-Compatibility and Eviction-Compatibility.
• Conversely, if a class is compatible with both reception and eviction, one can construct a revision operator. This allows the translation of negative results (incompatibility) from reception/eviction directly to revision.

4. Key Results

Logic	Operation	General Models	Finite Tree-Shaped	Finite Tree-Shaped + Finite Signature
$\mathcal{EL}^\bot$	Eviction	Compatible	Compatible	Compatible
	Reception	Incompatible	Incompatible	Compatible (if finite sets)
$\mathcal{ALC}$	Eviction	Incompatible	Incompatible	Compatible (if finite sets)
	Reception	Incompatible	Incompatible	Compatible (if finite sets)
Both	Revision	Incompatible	Incompatible	Compatible (for $\mathcal{ALC}$ under bisimulation closure)

• Negative Result for $\mathcal{ALC}$ Revision: Even with finite tree-shaped interpretations, $\mathcal{ALC}$ is not revision-compatible unless the class of models is restricted to be closed under bisimulation. This is because $\mathcal{ALC}$ cannot distinguish between bisimilar models; if one must be added and a bisimilar one removed, success is impossible.
• Positive Result for $\mathcal{ALC}$ Revision: Revision is compatible if the class of models consists of finite sets of finite tree-shaped pointed interpretations over a finite signature, closed under bisimulation, and the sets to be added and removed are bisimulation-disjoint.

5. Significance and Implications

1. Foundational for Ontology Learning: The work provides a rigorous logical foundation for learning DL concepts from data (positive/negative examples). It clarifies the limits of what can be learned (represented as model change) in different DL languages.
2. Clarification of Revision: It corrects the intuition that revision is merely "remove then add." The paper proves that a unified approach is necessary to satisfy minimal change postulates, especially in non-monotonic or expressive logics.
3. Limits of Expressivity: The results highlight the tension between the expressivity of a logic (e.g., $\mathcal{ALC}$'s ability to express complex constraints) and the ability to perform minimal model changes. $\mathcal{ALC}$'s sensitivity to bisimulation makes certain revision tasks impossible without restricting the model space.
4. Practical Constraints: The positive results rely on significant restrictions (finite signatures, finite models, tree-shapes). This suggests that practical ontology learning systems using these logics must operate within these constrained domains or accept that minimal change might not always be achievable.

In conclusion, the paper successfully formalizes model change for DLs, introduces a robust theory of revision, and delineates the precise boundaries of compatibility for these operations across different Description Logics and model classes.