Conditional Independence for Iterated Belief Revision

Gabriele Kern-Isberner, Jesse Heyninck, Christoph BeierleIJCAI 2022 · DOI

TL;DR

This paper introduces a novel semantic definition of conditional independence for "total preorders," which are the foundational structures for iterated belief revision in intelligent agents. By axiomatizing how this independence should behave during belief updates, the authors provide a framework for more efficient and localized reasoning in agents that learn and adapt over time.

What Problem Does This Paper Address?

Intelligent agents need to update their beliefs when new information arrives. While traditional belief change models (AGM theory) handle single belief updates well, they struggle with iterated belief revision – how to update beliefs that have already been revised. This requires a richer representation of an agent's knowledge than just propositional formulas, leading to the use of "epistemic states" like total preorders over possible worlds.

A crucial concept in probabilistic reasoning is conditional independence, which allows for efficient computation by exploiting redundancies. However, applying this concept to symbolic, qualitative reasoning in belief change has been challenging. This paper aims to bridge this gap by defining conditional independence semantically for total preorders and showing how it can be preserved during iterated belief revision, enabling more localized and efficient reasoning within an agent's evolving knowledge.

Methods

The core of the paper is the development of a semantic definition of conditional independence for total preorders (TPOs). This definition, denoted as $\Sigma_2 ||_< \Sigma_3|\Sigma_1$, captures the idea that information about $\Sigma_3$ is irrelevant for ordering worlds concerning $\Sigma_2$ when information from $\Sigma_1$ is already known.

The authors then:

  • Relate to Ordinal Conditional Functions (OCFs): They show how their TPO-based conditional independence is compatible with the established notion for OCFs (ranking functions), which are a more structured representation of plausibility.
  • Axiomatize for Iterated Revision: They propose axioms (CItpo and CIocf) that specify how conditional independence should be preserved under iterated belief revision. The key idea is that if independence holds before a revision, it should also hold after, provided the new information is compatible with this independence.
  • Propose c-revisions: They use "c-revisions," a specific type of revision operator for OCFs, as a proof of concept to demonstrate that these axioms can be satisfied. This allows for the practical implementation of iterated belief revision that respects conditional independence.
  • Constructive Methods: They provide methods for constructing TPOs and OCFs that satisfy conditional independence statements, drawing inspiration from probabilistic graphical models.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Probabilistic and Symbolic Reasoning: The paper successfully translates the powerful concept of conditional independence from probabilistic reasoning to the symbolic, qualitative realm of iterated belief revision, which is crucial for modeling intelligent agents.
  • Semantic Definition for TPOs: Defining conditional independence directly on the semantic structure of total preorders (TPOs) provides a more general foundation than relying solely on syntactic properties.
  • Axiomatic Preservation of Independence: The proposed axioms (CItpo, CIocf) offer a clear criterion for what constitutes a "good" iterated belief revision operator in terms of maintaining conditional independence. This is key for ensuring that agents can reason efficiently even as their knowledge base grows and changes.
  • c-revisions as a Practical Tool: Demonstrating that c-revisions can satisfy these axioms shows a concrete path towards implementing agents that can leverage conditional independence for more efficient reasoning during iterated belief change.
  • Local Reasoning in Agents: By preserving conditional independence, agents can perform more localized computations, avoiding the need to re-evaluate all possible worlds or all pieces of information after each update.

Key Results

  • A formal semantic definition of conditional independence for total preorders ($\Sigma_2 ||_< \Sigma_3|\Sigma_1$) is introduced.
  • This definition is shown to be compatible with conditional independence for ordinal conditional functions (OCFs).
  • Axioms for iterated belief revision operators are proposed to ensure the preservation of conditional independence (CItpo, CIocf).
  • c-revisions are shown to satisfy these axioms, providing a constructive method for iterated belief revision that respects conditional independence.
  • The paper demonstrates through examples how conditional independence can be maintained during belief revision, leading to more efficient reasoning.

Limitations and Future Work

  • Graphoid Properties: While some graphoid properties (like symmetry and weak union) are shown to hold for TPO conditional independence, the paper notes that full graphoid properties are not expected due to the limitations of TPOs compared to probabilities or OCFs.
  • Constructing TPOs: The paper mentions that constructing TPOs from local ones compatible with conditional independence statements is an open question.
  • Revisions by Conditionals: Extending the framework to handle revisions by conditionals (not just propositions) is suggested as future work.
  • Efficient Network Models: The authors plan to leverage conditional independence to design efficient network-based models for iterated revision, aiming to reduce the complexity of revision tasks.
  • Extraction Algorithms: Developing algorithms for extracting conditional independencies from data, inspired by Bayesian network structure learning, is also a future direction.

Summary updated

BibTeX
@inproceedings{kernisberner2022conditional,
  author = {Gabriele Kern-Isberner and Jesse Heyninck and Christoph Beierle},
  title = {{Conditional Independence for Iterated Belief Revision}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/373},
}
Figure