Predicate Invention in Inductive Logic Programming

Duangtida Athakravi, Krysia Broda, Alessandra Russo

TL;DR

This paper proposes a general framework for predicate invention in Inductive Logic Programming (ILP) by abstracting the problem to a meta-level. This approach aims to unify two key aspects of predicate invention: reformulation (restructuring knowledge) and bias shift (specializing hypotheses), offering a more flexible and powerful learning system.

What Problem Does This Paper Address?

Learning new concepts is fundamental to intelligence, and in the realm of logic programming, this often involves "predicate invention." This is the process of creating new predicates (like new verbs or concepts) that aren't explicitly defined in the existing knowledge base or examples. Current ILP systems often tackle predicate invention for either restructuring existing knowledge (reformulation) or for making a hypothesis more specific to fit the data (bias shift), but rarely both. This paper aims to bridge this gap by providing a unified framework that can handle both scenarios, making ILP systems more adept at learning and adapting.

Methods

The core of the proposed framework is to abstract the predicate invention problem to a "meta-level." This means reasoning about the process of learning and hypothesis formation itself, rather than just directly learning the predicates. They leverage a meta-level abductive approach, transforming inductive learning tasks into equivalent abductive tasks. This allows them to search for explanations that involve inventing new predicates.

Specifically, they build upon an existing ILP system called ASPAL (Answer Set Programming Abductive Learning), which uses meta-level abduction. ASPAL works by converting an ILP problem into an abductive one, using a "top theory" that encodes how hypotheses should be constructed based on mode declarations (which define the allowed structure of rules).

For predicate invention, they introduce the concept of "placeholders." These are essentially temporary, undefined predicates that can be added to the mode declarations. The system then tries to learn definitions for these placeholders. This approach is designed to be flexible enough to accommodate both reformulation and bias shift.

Datasets

Not discussed in the paper. The paper focuses on the theoretical framework and demonstrates its application with small, illustrative examples rather than large-scale datasets.

Key Insights and Ideas

  • Unified Framework: The most significant insight is the development of a general framework that can handle both predicate reformulation and bias shift within a single approach, moving beyond systems that specialize in only one.
  • Meta-Level Abduction: Abstracting the problem to a meta-level, where the system reasons about hypothesis construction, is key to achieving this generality. This allows for a more principled way to search for and define new predicates.
  • Placeholders for Flexibility: The use of "placeholders" in mode declarations provides a flexible mechanism to introduce potential new predicates without knowing their exact form beforehand. This allows the learning system to discover them.
  • ASP for Efficient Search: Leveraging Answer Set Programming (ASP) solvers like ASPAL offers an efficient way to handle the potentially complex search space involved in predicate invention, especially when dealing with many mode declarations.

Key Results

The paper presents a conceptual framework and demonstrates its potential through small examples.

  • Bias Shift Example: The framework successfully demonstrated bias shift by inventing a new predicate p to distinguish between positive and negative examples when the initial vocabulary was insufficient.
  • Reformulation Example: The framework also showed promise in theory reformulation by inventing a new predicate new to factor out common conditions in rules, leading to a more compact and structured knowledge base.
  • Efficiency: ASPAL's implementation, using ASP solvers, showed efficiency in handling a large number of mode declarations (up to 17 alternative ones) for predicate invention, solving the problem in under a second for small examples.

Limitations and Future Work

  • Scalability: While ASPAL is efficient for small examples, the authors acknowledge the need to test the framework on larger problems to ensure that a high number of mode declarations doesn't lead to an unmanageable increase in computational time or the number of solutions.
  • Controlling Search Space: For theory reformulation, determining when to reformulate and how to effectively control the search for revision operators remains an area for further development. Associating revision operators with measures of their impact on program size is suggested.
  • Hypothesis Refinement: The authors plan to complete work on hypothesis refinement within ASPAL. This is seen as crucial for determining when to invent new predicates for bias shift, aiming to invent them only when truly demanded, similar to existing systems like CHAMP and SIRIES.
  • Determining Reformulation Need: A key future direction is to develop methods for determining when theory reformulation is necessary, rather than just applying it.

Summary updated

Abstract

The ability to recognise new concepts and incorporate them into our knowledge is an essential part of learning. From new scientific concepts to the words that are used in everyday conversation, they all must have at some point in the past, been invented and their definition defined. In this position paper, we discuss how a general framework for predicate invention could be made, by reasoning about the problem at the meta-level using an appropriate notion of top theory in inductive logic programming.
BibTeX
@inproceedings{athakravi2012predicate,
  author = {Duangtida Athakravi and Krysia Broda and Alessandra Russo},
  title = {{Predicate Invention in Inductive Logic Programming}},
  booktitle = {Iccsw},
  year = {2012},
  doi = {10.4230/oasics.iccsw.2012.15},
}
Figure