TL;DR
This paper introduces a novel paradigm for belief change where an agent's knowledge is represented by finite sets of models, and incoming information is also given as sets of models. This approach addresses the limitations of traditional belief change models that struggle with infinite representations and offers a more general framework for rational belief updates.
What Problem Does This Paper Address?
Traditional belief change models, like the AGM framework, represent an agent's knowledge as a set of sentences (a theory) that is logically closed. However, for many expressive logics, these theories can be infinite. This poses a problem for agents with limited cognitive resources who can only store a finite amount of explicit beliefs. While "finite based" approaches exist, they often focus on finite sets of formulas. This paper tackles the challenge of representing an agent's epistemic state using finite sets of models, which is a more general input than formulas and aligns better with scenarios like learning from interpretations. The core problem is how to define rational belief change operations (expansion and contraction) that guarantee the resulting epistemic state is finitely representable in terms of models, and to characterize the logical properties that enable such operations.
Methods
The authors propose a new framework for belief change centered around model-oriented operations. Instead of operating on formulas, they define belief change as functions that take a finite belief base (a set of formulas) and a set of input models, and return a new finite belief base.
Key techniques include:
- Satisfaction Systems: A logic is viewed as a satisfaction system $(L, M, \models)$, where $L$ is the language, $M$ is the set of models, and $\models$ is the satisfaction relation.
- Finite Representability (FR): A set of models $M'$ is finitely representable if there exists a finite set of formulas $B$ such that $M' = \text{Mod}(B)$. The set of all finitely representable sets of models is denoted by $FR(\mathcal{A})$.
- Model Change Operations:
- Eviction: Removing models from the agent's epistemic state. This is achieved by finding the "closest" finitely representable subset of models that do not include the input models. This involves identifying maximal finitely representable subsets of the remaining models ($\text{MaxFRSubs}$).
- Reception: Incorporating new models into the agent's epistemic state. This is done by finding the "closest" finitely representable superset of models that do include the input models. This involves identifying minimal finitely representable supersets of the combined models ($\text{MinFRSups}$).
- Rationality Postulates: New postulates are defined to characterize these model change operations, focusing on success, inclusion, vacuity, finite temperance (minimality), and uniformity.
- Compatibility Analysis: The paper analyzes various logics (propositional logic, Horn logic, 3-valued logics, Gödel logic, LTL, Description Logics) to determine if they are "eviction-compatible" and "reception-compatible" – meaning that the required operations can always be performed while maintaining finite representability.
Datasets
Not discussed in the paper. The paper focuses on theoretical frameworks and logical systems rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Models as Input: Representing incoming information as sets of models is more general than formulas and better suited for certain learning and knowledge representation tasks.
- Finite Model Sets are Key: The core innovation is to shift the focus from finite formulas to finite sets of models as the representation of an agent's epistemic state. This is crucial for computational tractability and cognitive limitations.
- "Closest" Finitely Representable Sets: When the desired set of models is not finitely representable, the approach relies on finding the "closest" finitely representable subset or superset, guided by specific criteria (minimality/maximality).
- Logic-Dependent Compatibility: Not all logics are equally amenable to this model-based belief change. The paper identifies specific logical properties (like the Reverse Monotonic Bijection Property - RMBP) that determine whether a logic is "eviction-compatible" or "reception-compatible."
- New Postulates for Finite Representation: The standard AGM postulates are insufficient. New postulates like "finite temperance" are introduced to ensure that minimal changes are made to achieve finite representability.
Key Results
- Novel Belief Change Operations: The paper defines and characterizes "maxichoice" eviction and reception functions based on FR selection functions.
- Postulate Characterizations: Theorems 5 and 10 provide characterizations of these model change operations using the newly defined postulates.
- Compatibility Results: The paper systematically analyzes the eviction- and reception-compatibility of various logics, including propositional logic (compatible), Horn logic (compatible), 3-valued logics (mixed), Gödel logic (compatible), LTL-NeXt (reception-compatible, not eviction-compatible), and Description Logic ALC (neither compatible).
- Formal Conditions for Compatibility: Theorems 16 and its subsequent claims provide formal conditions for a satisfaction system to be eviction- or reception-compatible, often relating to the existence of immediate predecessors/successors in the poset of finitely representable sets.
Limitations and Future Work
- Uniqueness Issues: The paper acknowledges that in many cases, the "closest" finitely representable set might not be unique, requiring a "selection function" to make a choice. This introduces a degree of non-determinism or reliance on agent preferences.
- Model Revision: The authors suggest "model revision" (incorporating new information while ensuring consistency) as a future direction, noting that it would require selecting a "closest" finitely representable set to avoid inconsistent states.
- Pseudo-Contractions: The work relates to "pseudo-contractions" and suggests further research into partially constraining the structure of the resulting belief base.
- Specific Logics: While many logics are analyzed, the framework's applicability to other non-classical logics or more expressive fragments of first-order logic could be further explored.
Summary updated