Lexicographic Entailment, Syntax Splitting and the Drowning Problem

Jesse Heyninck, Gabriele Kern-Isberner, Thomas Andreas MeyerIJCAI 2022 · DOI

TL;DR

This paper demonstrates that lexicographic entailment, a high-quality non-monotonic reasoning approach, satisfies "syntax splitting." This means reasoning can be restricted to relevant parts of the knowledge base, potentially improving efficiency. The authors also show that syntax splitting is independent of the "drowning problem," a phenomenon where irrelevant information can obscure valid inferences.

What Problem Does This Paper Address?

Non-monotonic reasoning deals with drawing conclusions that can be revised in light of new information. Lexicographic entailment is a powerful logic for this, known for its "high quality" – it extends rational closure and avoids the "drowning problem." However, it's computationally expensive. A desirable property for inference relations is "syntax splitting," which allows reasoning to focus only on the parts of the knowledge base relevant to a specific query. This can significantly reduce computational costs. While other inference relations satisfy syntax splitting, it was unknown if lexicographic entailment did. This paper aims to fill this gap by proving that lexicographic entailment does satisfy syntax splitting, and to explore its relationship with other key concepts like c-representations and the drowning problem.

Methods

The paper introduces and utilizes several key concepts:

  • Propositional Logic and Non-monotonic Conditionals: Standard definitions are provided for logical languages, interpretations (possible worlds), and conditionals of the form (B|A), representing "B is true given A."
  • Inductive Inference Operators: These are mappings that induce inference relations from conditional belief bases. Lexicographic entailment is presented as an inductive inference operator.
  • Syntax Splitting (SynSplit): This property requires an inference relation to satisfy both "Independence (Ind)" and "Relevance (Rel)." Ind means inferences from one part of a partitioned language are independent of other parts. Rel means inferences within a sublanguage can be made using only conditionals from that sublanguage.
  • Lexicographic Entailment: This is defined using lexicographic vectors, which count the number of violated conditionals in specific partitions of the belief base.
  • System Z: A well-known inference relation based on ordinal conditional functions (OCFs) and Z-partitions.
  • C-Representations: Another inductive inference relation that satisfies syntax splitting, based on OCFs and specific parameter constraints.
  • Drowning Problem: This occurs when irrelevant information in a belief base can prevent valid inferences from being made.

The core of the paper involves proving that lexicographic entailment satisfies Ind and Rel, thereby satisfying SynSplit. This is done through theoretical arguments and illustrated with examples. The authors also introduce "System Zind," a novel inference relation designed to show that syntax splitting is independent of the drowning problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical properties of inference relations and uses small, illustrative examples rather than large datasets.

Key Insights and Ideas

  • Lexicographic Entailment Satisfies Syntax Splitting: This is the paper's main contribution. It means that despite its high computational complexity in the worst case, practical reasoning with lexicographic entailment can be made more efficient by focusing on relevant parts of the knowledge base.
  • Syntax Splitting is Independent of the Drowning Problem: The authors construct "System Zind," an inference relation that satisfies syntax splitting and is RC-extending but still suffers from the drowning problem. This disproves a potential conjecture that these two desirable properties are intrinsically linked.
  • Lexicographic Entailment and C-Representations are Related but Distinct: While both satisfy syntax splitting and avoid the drowning problem, they are not identical. The paper explores their relationship, showing that lexicographic entailment is not always captured by a "convex" c-representation.
  • The "Qual" Property: The paper suggests a property called "Qual" (and its stronger version "Qual'") which might be key to avoiding the drowning problem. It states that if a world falsifies fewer conditionals than another, it should be ranked strictly higher.

Key Results

  • Theorem 1: Lexicographic entailment satisfies syntax splitting.
  • System Zind: Introduced as an inference relation that satisfies syntax splitting and is RC-extending but suffers from the drowning problem.
  • Proposition 4: System Zind is weaker than lexicographic entailment, and both are RC-extending.
  • Example 6: Demonstrates that System Zind differs from lexicographic entailment and can suffer from the drowning problem.
  • Example 7: Shows that there can be multiple RC-extending inference relations satisfying syntax splitting, and that lexicographic entailment is not the most refined among them.

Limitations and Future Work

  • Worst-Case Complexity: While syntax splitting offers practical efficiency gains, the paper acknowledges that it does not improve the worst-case computational complexity of lexicographic entailment.
  • Formalizing the Drowning Effect: The authors suggest that formalizing the drowning effect into a general property of inductive inference relations is an open question.
  • Axiomatic Characterization: Finding an axiomatic characterization for lexicographic entailment remains an open problem.
  • Generalization: The paper suggests future work in generalizing syntax splitting to first-order and probabilistic description logics, and richer preferential languages.
  • Relationship between Qual and Drowning: Further investigation into the connection between the "Qual" property and avoiding the drowning effect is proposed.

Summary updated

BibTeX
@inproceedings{heyninck2022lexicographic,
  author = {Jesse Heyninck and Gabriele Kern-Isberner and Thomas Andreas Meyer},
  title = {{Lexicographic Entailment, Syntax Splitting and the Drowning Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/369},
}
Figure