Learning Extended Logic Programs

Katsumi Inoue, Yoshimitsu KudohIJCAI 1997 · OpenReview

Abstract

This paper presents a method to generate nonmonotonic rules with exceptions from positive/negative examples and background knowledge in Inductive Logic Programming. We adopt extended logic programs as the form of programs to be learned, where two kinds of negation—negation as failure and classical negation—are effectively used in the presence of incomplete information. While default rules are generated as specialization of general rules that cover positive examples, exceptions to general rules are identified from negative examples and are then generalized to rules for cancellation of defaults. We implemented the learning system LELP based on the proposed method. In LELP, when the numbers of positive and negative examples are very close, either parallel default rules with positive and negative consequents or nondeterministic rules are learned. Moreover, hierarchical defaults can also be learned by recursively calling the exception identification algorithm.

Introduction: Beyond the Closed World Assumption

Most traditional Inductive Logic Programming (ILP) systems operate under the Closed World Assumption (CWA): if a fact isn't explicitly known to be true, it is assumed to be false. While efficient, this creates a paradox in machine learning: if we already assume we know everything that is false, the value of learning from negative examples is diminished.

In the real world, information is often incomplete. We might know some birds fly and some penguins don't, but for a newly discovered species, the answer should be "unknown" until we have evidence. Standard Normal Logic Programs (NLPs) cannot easily distinguish between "I know this is false" and "I don't know if this is true." This paper seeks to bridge that gap by learning Extended Logic Programs (ELPs), which can explicitly handle "unknown" states using a three-valued logic framework.

The LELP System and Methodology

The authors introduce LELP (Learning Extended Logic Programs), a system that learns non-monotonic rules—rules that allow for exceptions—from incomplete data. The core of the system is a multi-stage process:

  1. Candidate Generation: LELP uses standard ILP techniques to generate initial "monotonic" rules from positive examples.
  2. Open World Specialization (OWS): This is the paper's primary algorithmic contribution. Unlike previous "Closed World" specialization methods, OWS identifies exceptions specifically from the provided negative examples without assuming that everything else in the world is a negative instance.
  3. Default and Cancellation Rules: LELP introduces "abnormality" predicates (e.g., ab1(X)). It learns a general rule (e.g., "Birds fly") and qualifies it with a "Negation as Failure" (NAF) clause (e.g., "Birds fly unless they are abnormal"). It then generates "cancellation rules" to define what makes something abnormal (e.g., "Penguins are abnormal").
  4. Hierarchical Learning: The system can call itself recursively. If an exception itself has exceptions (e.g., "Birds fly, except penguins, but maybe genetically modified penguins can fly"), LELP can learn these nested layers.
Figure 1: A conceptual diagram of the 'Bird Example' showing the relationships between birds, penguins, and the ability to fly. This illustrates how LELP identifies exceptions (like penguins) within a general category (birds).

Key Insights: Two Kinds of Negation

The paper emphasizes the power of using both Classical Negation (explicitly stating something is false) and Negation as Failure (stating we have no evidence something is true). This allows the learner to distinguish between "I know it's not" and "I don't know."

By adopting three-valued semantics (yes, no, unknown), the learned programs are much more robust to incomplete data. An object not covered by the learned rules is simply "unknown" rather than "false" by default. Additionally, LELP uses Ratio-Based Defaults: if 90% of examples are negative, it learns a negative default with positive exceptions, ensuring the most efficient rule representation.

Evaluation and Results

The paper evaluates LELP using classic logic programming benchmarks and illustrative "commonsense reasoning" problems:

  • The Bird Example: As shown in Figure 1, LELP successfully demonstrated the ability to learn "exceptions to exceptions" by recursively applying the OWS algorithm to birds, penguins, and non-flying birds.
  • The Nixon Diamond: A famous problem in non-monotonic reasoning involving whether a person (Nixon) is a pacifist based on being both a Quaker (typically pacifist) and a Republican (typically not). LELP proved it could handle "nondeterministic" cases where two rules conflict, providing two different "answer sets."
  • Superiority over CWS: The authors show that their Open World Specialization is more appropriate for concept learning than older Closed World methods because it doesn't over-fit to the assumption that all unobserved data is negative.

Limitations and Future Work

While LELP is a significant step forward, the authors acknowledge that it currently treats every negative example as a potential exception. In real-world data, some of these might just be noise (errors). Distinguishing between a genuine exception and a data error remains a challenge. Furthermore, while the logic is sound for symbolic reasoning, how LELP scales to the massive, high-dimensional datasets common in modern machine learning is a subject for future exploration.

Summary updated

Abstract

This paper presents a method to generate nonmonotonic rules with exceptions from positive/ negative examples and background knowledge in Inductive Logic Programming. We adopt extended logic programs as the form of programs to be learned, where two kinds of negation--negation as failure and classical negation--are effectively used in the presence of incomplete information. While default rules axe generated as specialization of general rules that cover positive examples, exceptions to general rules are identified from negative examples and are then generalized to rules for cancellation of defaults. We implemented the learning system LELP based on the proposed method. In LELP, when the numbers of positive and negative examples are very close, either parallel default rules with positive and negative consequents or nondeterministic rules are learned. Moreover, hierarchical defaults can also be learned by recursively calling the exception identification algorithm.
BibTeX
@inproceedings{inoue1997learning,
  author = {Katsumi Inoue and Yoshimitsu Kudoh},
  title = {{Learning Extended Logic Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
  url = {https://openreview.net/forum?id=H1-Q4Qfubr},
}
Figure