Ordering Default Theories

Chiaki SakamaIJCAI 2003

Abstract

This paper presents a formal framework for comparing the "strength" of default theories using a novel nine-valued logic, $IX$. By distinguishing between definite facts and various types of default conclusions (skeptical vs. credulous), the proposed approach enables the ordering of theories based on their information content. This ordering is essential for tasks such as inductive learning and the merging of knowledge from disparate, potentially conflicting sources.

Introduction

In classical first-order logic, the relative strength of theories is well-defined: Theory A is stronger than Theory B if A entails everything that B proves. However, in Default Logic—where "rules of thumb" can be retracted in the face of new evidence—this comparison is more complex.

Two default theories might yield identical sets of conclusions (extensions), yet differ fundamentally in how those conclusions are derived. For instance, one theory might treat a conclusion as an immutable fact, while another treats it as a tentative default. Standard logic fails to capture this distinction in reliability and stability. This work introduces a formal ordering that accounts for the quality and justification of information within nonmonotonic systems.

Methodology: The IX Logic and Bilattices

The primary innovation is the introduction of the $IX$ logic, which utilizes nine truth values organized into a mathematical structure known as a bilattice. A bilattice supports two distinct partial orderings: a "truth" ordering ($\leq_t$) and a "knowledge" or "information" ordering ($\leq_k$).

The nine-valued bilattice structure of the IX logic, illustrating the knowledge and truth orderings.

The nine values in $IX$ are categorized as follows:

  • Definite: True ($t$), False ($f$), Contradictory ($\top$), and Undefined ($\perp$).
  • Skeptical Default: Skeptically true ($dts$) and skeptically false ($dfs$).
  • Credulous Default: Credulously true ($dtc$), credulously false ($dfc$), and contradictory by default ($*$).

A mapping function, $\phi_\Delta$, assigns one of these values to any formula based on its presence across the extensions of a default theory $\Delta$. A theory is considered "stronger" ($\leq_{DL}$) if its conclusions occupy higher positions in the $\leq_k$ ordering. This framework is also extended to Extended Logic Programs (ELPs) under answer set semantics.

Key Insights: Information Quality and Justification

A central tenet of this research is that how a conclusion is reached is as significant as the conclusion itself. A fact derived from a "hard" rule possesses greater information quality than one derived from a "soft" default. Traditional default logic, which focuses solely on extensions, obscures these underlying justifications.

Furthermore, the $IX$ logic explicitly distinguishes between skeptical conclusions (true in all extensions) and credulous ones (true in at least one extension). Previous bilattice models, such as Ginsberg’s seven-valued logic, failed to make this distinction, treating all defaults with the same weight.

A seven-valued bilattice structure that lacks the granularity to distinguish between skeptical and credulous default conclusions.

The ordering is inherently nonmonotonic; adding information to a theory does not guarantee an increase in "strength." New facts may block existing default rules, leading to the withdrawal of previously held conclusions—a hallmark of nonmonotonic reasoning.

Results and Applications

The paper establishes a formal pre-order ($\leq_{DL}$) for default theories that generalizes standard logical entailment. Key results include:

  1. Order-Equivalence: The author proves that "order-equivalence" is a more rigorous and informative metric than standard "extension-equivalence."
  2. Inductive Logic Programming (ILP): The framework provides a theoretical basis for "generalization" in nonmonotonic logic programs. It demonstrates that a program explicitly handling exceptions is a formal generalization of a simpler, less nuanced program.

Conclusion and Future Work

While the $IX$ logic provides a robust theoretical foundation, challenges remain regarding computational complexity, as determining the truth value of complex formulas is not always straightforward. Future research will focus on extending this framework to full first-order nonmonotonic logic and implementing these "generalization" operations in practical Inductive Learning systems to automate the refinement of default theories from data.

Summary updated

BibTeX
@inproceedings{sakama2003ordering,
  author = {Chiaki Sakama},
  title = {{Ordering Default Theories}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure