Inductive equivalence in clausal logic and nonmonotonic logic programming

Chiaki Sakama, Katsumi InoueMachine Learning 2011 · DOI

In the field of Inductive Logic Programming (ILP), an agent uses a background theory ($B$) and an observation ($O$) to induce a hypothesis ($H$). While much research focuses on the algorithms used to find $H$, less attention has been paid to the background theory's representation. In their 2011 paper published in Machine Learning, Chiaki Sakama and Katsumi Inoue address a fundamental question: When can two different sets of background knowledge be considered "the same" for the purposes of induction?

By formalizing the concept of inductive equivalence, the authors provide a theoretical framework for optimizing background theories, verifying the correctness of learning algorithms, and comparing the inductive capabilities of different AI agents.

Defining Inductive Equivalence

The authors define two background theories, $B_1$ and $B_2$, as inductively equivalent if, for any given observation $O$, they lead to the identical set of hypotheses $H$. This property is critical because the same domain knowledge can often be written in multiple ways. If two theories are not inductively equivalent, an agent might learn different rules depending solely on how its background knowledge was phrased, rather than the underlying facts.

To test this definition, the researchers analyzed two major representation languages across four distinct induction frameworks:

  1. Cautious Induction: $O$ must be true in all possible models of $B \cup H$.
  2. Brave Induction: $O$ must be true in at least one model of $B \cup H$.
  3. Learning from Satisfiability (LFS): $B, H,$ and $O$ must be mutually consistent.
  4. Descriptive Induction: $H$ must describe regularities already present in $B$ and $O$.

Clausal Logic vs. Nonmonotonic Logic

The paper’s most significant contribution is the distinction between classical clausal logic and nonmonotonic logic programming (NLP).

Clausal Logic

In standard first-order clausal logic, the authors prove that logical equivalence is sufficient for inductive equivalence. If $B_1$ and $B_2$ have the same classical models, they will always produce the same hypotheses under the same observations. This aligns with traditional intuition in ILP.

Nonmonotonic Logic Programming

For NLP, which utilizes "negation as failure" (e.g., assuming $X$ is false if it cannot be proven true), the requirements are much stricter. The authors demonstrate that simple "weak equivalence" (having the same answer sets) is insufficient. Instead, theories require strong equivalence.

Two programs are strongly equivalent only if they remain equivalent even when an arbitrary set of new rules is added to both. Because the process of induction essentially "adds rules" (the hypothesis $H$) to the background theory, only strong equivalence ensures that the semantics of the program do not shift in unexpected ways during the learning process.

System-Specific Biases

The research also examines how specific ILP systems—such as FOIL, GOLEM, PROGOL, and CLAUDIEN—interact with these theoretical bounds.

  • Strict Systems: PROGOL and CLAUDIEN generally adhere to the strict requirements of logical equivalence.
  • Biased Systems: Systems like FOIL and GOLEM often operate under more restricted settings (e.g., using only ground facts or Datalog). The authors found that these systems can maintain inductive equivalence under "looser" conditions because their search biases prevent them from exploring the parts of the logic where the theories might diverge.

Practical Implications and Complexity

The paper warns that common program optimization techniques, such as "unfold/fold" transformations, may preserve deductive meaning (the ability to answer queries) while inadvertently breaking inductive equivalence. An optimized background theory might be faster to process but could lead a learner to entirely different conclusions than the original theory.

Computationally, deciding if two theories are inductively equivalent is generally coNP-complete. However, for simpler Horn logic programs—frequently used in database applications—the check can be performed in polynomial time.

Conclusion

The findings establish a definitive mapping between logic types and the conditions required for stable induction:

Representation Language Semantics Condition for Inductive Equivalence
Clausal Logic Classical / Minimal Model Logical Equivalence ($B_1 \equiv B_2$)
Nonmonotonic LP Answer Set Strong Equivalence ($B_1 \equiv_s B_2$)

This work serves as a cautionary tale for ILP practitioners: the way background knowledge is structured is not merely a matter of computational efficiency, but a factor that fundamentally defines what an agent is capable of learning.

Summary updated

BibTeX
@article{sakama2011inductive,
  author = {Chiaki Sakama and Katsumi Inoue},
  title = {{Inductive equivalence in clausal logic and nonmonotonic logic programming}},
  journal = {Machine Learning},
  year = {2011},
  doi = {10.1007/s10994-010-5189-4},
}
Figure