A Sequential Reversible Belief Revision Method Based on Polynomials

AAAI 1999

TL;DR

This paper introduces a novel method for updating an agent's beliefs when new information arrives, focusing on "drastic" revisions that prioritize new observations. They achieve this by representing belief states as polynomials and using lexicographical ordering, allowing for efficient, reversible, and sequential belief updates.

What Problem Does This Paper Address?

Reasoning about how an agent's beliefs should change when presented with new information is a fundamental problem in artificial intelligence. The AGM (Alchourron, Gärdenfors, Makinson) school established foundational postulates for belief revision, but these struggled with iterated revision – how to handle a sequence of updates. Specifically, early AGM models didn't adequately capture how the plausibility of different interpretations of the world should evolve over time. While some approaches like Boutilier's "natural revision" minimally adjust plausibility, this paper tackles the opposite extreme: a "drastic" revision where new information is strongly prioritized, making worlds consistent with the new observation much more plausible than those that aren't. The challenge is to do this in a way that is reversible (allowing recovery of past states) and computationally tractable, especially for sequences of observations.

Methods

The core innovation is representing an agent's epistemic state (their beliefs and their relative plausibilities) using polynomials. Specifically, each possible interpretation (or "world") of the propositional calculus is assigned a polynomial weight. The lexicographical ordering of these polynomials then defines the plausibility ordering of worlds.

  • Polynomial Representation: Weights are polynomials in a variable x with coefficients in {0, 1}. The use of positive and negative indices for x allows for efficient "shifting" operations. A right shift (multiplying by x) corresponds to making worlds more plausible, while a left shift (multiplying by x⁻¹) corresponds to making them less plausible.
  • Drastic Revision Operator (o): When a new observation µ arrives, the revision operator o modifies the polynomial weights. Worlds that satisfy µ (models of µ) have their weights right-shifted (x * p(x)), making them more plausible. Worlds that don't satisfy µ (countermodels of µ) have their weights right-shifted and then incremented by 1 (x * p(x) + 1), making them significantly less plausible. This ensures that all models of µ become more plausible than all countermodels of µ.
  • Dual Revision Operator (o₄): The paper also introduces a dual operator that prioritizes older information. This uses left shifts (x⁻¹ * p(x)) for models of µ and left shifts plus an increment (x⁻¹ * p(x) + 1) for countermodels.
  • Syntactic Representation: To make these operations practical, the paper proposes a "weighted belief base" – a set of formulas paired with their polynomial weights. This allows for a syntactic counterpart to the semantic polynomial operations, enabling belief revision without explicitly enumerating all interpretations.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Polynomials as a History Tracker: The coefficients of the polynomials naturally encode the sequence of observations. A specific coefficient's position can indicate whether a world satisfies the first, second, or subsequent observation.
  • Reversibility is Key: A major advantage of the polynomial approach is its inherent reversibility. Unlike some other methods, it's possible to "undo" a revision and recover the previous epistemic state, which is crucial for realistic belief update scenarios.
  • Drastic vs. Minimal Revision: The paper clearly distinguishes its "drastic" revision (prioritizing new info) from "minimal" revision (like Boutilier's natural revision, which only boosts the best models of new info). This offers a spectrum of revision strategies.
  • Syntactic Elegance: The translation of semantic polynomial operations into operations on weighted belief bases provides a computationally efficient and conceptually clean way to perform belief revision.

Key Results

The paper demonstrates that the proposed polynomial-based revision operators (o and o₄) satisfy modified AGM postulates and Darwiche-Pearl postulates for iterated revision. They show that the drastic revision operator o ensures that all models of a new observation µ are strictly preferred to all its countermodels. The syntactic representation using weighted belief bases is shown to be equivalent to the semantic polynomial representation, allowing for practical implementation.

Limitations and Future Work

  • Computational Complexity: While polynomials offer efficiency, the paper doesn't delve deeply into the precise computational complexity of operations on these polynomials, especially as the number of observations grows.
  • "Drastic" Nature: The drastic revision rule, while principled, might be too strong for some real-world scenarios where gradual belief adjustment is more appropriate. The paper acknowledges this by introducing the dual operator and suggesting that other "milder" rules could also be encoded.
  • Future Work: The authors suggest exploring other revision tools that can be efficiently encoded using polynomial operations and syntactic counterparts for Boutilier's natural belief revision. They also hint at the potential relevance of their approach for updating preferences beyond just beliefs.

Summary updated

BibTeX
@inproceedings{1999sequential,
  title = {{A Sequential Reversible Belief Revision Method Based on Polynomials}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure