What Is Believed Is What Is Explained (Sometimes)

AAAI 1996

TL;DR

This paper introduces a novel "possible causes approach" (PCA) for updating knowledge bases about actions and change. Instead of simply adding new information, PCA identifies and incorporates the underlying causes that explain the new observation, ensuring that the causal relationships within the knowledge base are maintained. This approach is particularly useful for domains where actions have clear cause-and-effect relationships.

What Problem Does This Paper Address?

Agents often need to update their knowledge bases when new information arrives. Traditional belief revision methods, like the AGM theory, can sometimes lead to unintuitive results by not fully preserving the causal structure of the domain. For instance, if an agent learns that a light is on, a simple update might just add "light is on" to its knowledge. However, this doesn't explain why the light is on (e.g., someone flipped the switch). This paper addresses the challenge of incorporating new knowledge in a way that respects and maintains the causal relationships inherent in domains of actions and change, ensuring that the agent's beliefs are not just consistent but also explanatory.

Methods

The authors propose a "possible causes approach" (PCA) for belief update. The core idea is that when new information (a fluent becoming true or false at a certain time) is observed, the agent should first identify all possible causes for this observation. These causes are defined as abduced occurrences of actions and initial state propositions that would explain the new fact.

The methodology involves:

  1. Action Description Language (A): Using Gelfond and Lifschitz's language A to formally describe domains of actions and their effects.
  2. Translation to Abductive Logic Programs: A new translation is presented that converts domain descriptions in A into abductive logic programs, crucially incorporating a time dimension. This allows for reasoning about sequences of actions and their effects over time.
  3. Knowledge Bases as Abductive Logic Programs: The knowledge bases are represented as these abductive logic programs.
  4. Possible Causes Approach (PCA): When a new fact N is observed, the system searches for subsets δ of possible causes (abduced actions and initial state propositions) such that KB(D, H) + δ entails N and is consistent.
  5. Incorporation: Instead of just adding N, the knowledge base is updated by adding δ (the possible cause) and all its effects. This ensures that the causal link between δ and N is explicitly represented.
  6. Computational Techniques: The paper outlines how to compute these possible causes using abductive logic programming and suggests techniques to improve search efficiency.

Datasets

Not discussed in the paper. The paper uses examples like the "Stolen Car Problem" and a "Tom and Mary" scenario to illustrate its approach, but these are not presented as formal datasets.

Key Insights and Ideas

  • Belief is Explained: The central slogan is "What is believed is what is explained." This shifts the focus from mere consistency to causal justification for new beliefs.
  • Causal Completeness: PCA aims to incorporate not just the observed fact but also its explanatory causes and all their consequences, preserving the causal chain.
  • Abduction for Explanation: Abduction is used as the core mechanism to infer the most plausible causes for observed events, which is a natural fit for explaining actions and their outcomes.
  • Time Dimension is Crucial: Explicitly incorporating time into the logic programs is essential for reasoning about sequences of actions and their temporal dependencies.
  • Comparison with Existing Approaches: The paper highlights how PCA differs from Ginsberg's Possible Worlds Approach (PWA) and Winslett's Possible Models Approach (PMA) by demonstrating that PCA can derive more comprehensive and causally grounded updates, especially in scenarios with multiple plausible explanations.

Key Results

The paper presents theoretical results on the soundness and completeness of their translation from domain descriptions to abductive logic programs. It also provides formal definitions for the "possible causes" and the PCA knowledge incorporation operator. Through examples, it demonstrates that PCA can derive a richer set of updated knowledge bases compared to PWA and PMA, capturing multiple plausible causal explanations for new observations. For instance, in the Tom-Mary example, PCA can derive explanations for Mary having a book that PWA and PMA cannot.

Limitations and Future Work

  • Concurrent Actions: The current formulation assumes no concurrent actions. The paper notes that this assumption can be relaxed, but it adds complexity.
  • Computational Cost: While techniques for improving search efficiency are discussed, computing all possible causes can still be computationally expensive, especially in large domains.
  • Minimality Definition: The definition of minimality for causes is based on set inclusion. The paper acknowledges that other definitions of minimality might be explored.
  • Future Work: The authors suggest that the PCA approach can be used to evaluate counterfactual queries (e.g., "if F1 were true, would F2 be true?"). They also mention that all examples have been experimented with the REVISE system, implying potential for practical implementation.

Summary updated

BibTeX
@inproceedings{1996what,
  title = {{What Is Believed Is What Is Explained (Sometimes)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure