Belief Update in the Horn Fragment

Nadia Creignou, Adrian Haret, Odile Papini, Stefan WoltranIJCAI 2018 · DOI

TL;DR

This paper tackles the challenge of belief update for a restricted logical language called the Horn fragment. The authors adapt standard belief update postulates and introduce new ones to ensure that the updated beliefs remain representable within this fragment, leading to a formal characterization of Horn update operators using preorders on possible worlds.

What Problem Does This Paper Address?

Belief update, a core concept in artificial intelligence, deals with how an agent's beliefs should change when new information arrives about a dynamic environment. While well-studied for full propositional logic, applying these concepts to restricted logical languages (fragments) presents significant challenges. The Horn fragment, a subset of propositional logic, is particularly interesting due to its computational tractability and relevance in areas like logic programming and description logics. However, standard belief update operators and their formalizations don't directly translate to the Horn fragment because it's not closed under disjunction. This means that an update operation that works perfectly in propositional logic might produce a result that cannot be expressed as a Horn formula, rendering it unsuitable for Horn-based systems. This paper aims to bridge this gap by developing a formal framework for belief update specifically tailored to the Horn fragment.

Methods

The authors build upon the established KM postulates for belief update in propositional logic. They adapt these postulates to the Horn fragment, recognizing that some postulates (especially those involving disjunction) need to be weakened or modified. A key innovation is the introduction of a new condition called "Horn compliance" for assignments that map worlds to preorders. This ensures that the resulting set of minimal worlds is always representable by a Horn formula. They also introduce new postulates, denoted by $\mathbb{A}$ and $\mathbb{A}^*$, which are crucial for ruling out undesirable structures in the preorders that arise specifically in the Horn fragment. The paper then establishes representation theorems that connect these adapted postulates and Horn-compliant assignments to specific types of preorders (total and partial) on possible worlds, effectively characterizing Horn update operators.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Horn Fragment's Limitations: The Horn fragment's lack of closure under disjunction is the primary hurdle. This means standard update operations can produce results that are "outside" the Horn fragment, making them unusable in Horn-based systems.
  • "Horn Compliance" is Crucial: Simply using standard preorders isn't enough. The preorders used in the update process must be "Horn compliant" to guarantee that the output is always representable by a Horn formula.
  • New Postulates for Horn Logic: Standard postulates are insufficient. New postulates ($\mathbb{A}$ and $\mathbb{A}^*$) are needed to capture the specific structural properties required for rational belief update within the Horn fragment, particularly for ruling out problematic non-transitive cycles in preorders.
  • Bridging Update and Revision: The paper highlights the strong similarities between update and revision postulates in propositional logic and how these similarities extend to the Horn fragment, enabling the extension of results from update to revision.

Key Results

The paper presents two main representation theorems:

  1. A Horn update operator satisfies the adapted KM postulates plus the new postulate $\mathbb{A}$ if and only if it can be represented by a Horn-compliant assignment mapping each interpretation to a total preorder.
  2. A Horn update operator satisfies the adapted KM postulates (weakened version) plus the new postulate $\mathbb{A}^*$ if and only if it can be represented by a Horn-compliant assignment mapping each interpretation to a partial preorder.

The authors also provide concrete examples of Horn update operators, including a trivial one and one that prioritizes models of small cardinality, demonstrating the practical application of their theoretical framework.

Limitations and Future Work

The authors acknowledge that their work focuses on the Horn fragment and that generalizing these findings to other logical fragments might be possible by identifying shared structural properties. Future work includes:

  • Developing more concrete Horn update operators.
  • Investigating iterated belief update within the Horn fragment.
  • Extending the framework to other belief change operations like "erasure."
  • Exploring the applicability of their results to other logical fragments characterized by closure properties.

Summary updated

BibTeX
@inproceedings{creignou2018belief,
  author = {Nadia Creignou and Adrian Haret and Odile Papini and Stefan Woltran},
  title = {{Belief Update in the Horn Fragment}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/246},
}
Figure