Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3

Maurice Bruynooghe, Hendrik Blockeel, Bart Bogaerts, Broes De Cat, Stef De Pooter, Joachim Jansen, Anthony Labarre, Jan Ramon, Marc Denecker, Sicco Verwer

Abstract

Declarative modeling offers a powerful alternative to procedural programming for solving complex search and optimization problems. This paper explores the utility of the IDP3 system—a knowledge base system based on an extension of first-order logic—as a modeling language for diverse tasks in machine learning and data mining. By evaluating IDP3 across domains such as stemmatology, phylogenetic tree analysis, and Deterministic Finite Automaton (DFA) learning, the authors demonstrate that high-level logical specifications can achieve performance comparable to specialized algorithms while offering superior flexibility and clarity.

Introduction

Solving NP-complete search and optimization problems typically requires one of two demanding paths: writing complex, error-prone procedural code or manually translating the problem into low-level formats like SAT (Boolean Satisfiability). While Answer Set Programming (ASP) and Constraint Programming (CP) provide alternatives, they often deviate from standard first-order logic (FO) or lack the flexibility to handle complex procedural workflows.

This research investigates whether FO(·)—an extension of first-order logic including types, inductive definitions, and aggregates—can serve as a practical, high-level modeling language. Using the IDP3 system, the authors demonstrate how researchers in fields as varied as biology and philology can model complex problems declaratively, focusing on the "what" rather than the "how."

The IDP3 System: A Knowledge Base Approach

IDP3 is designed as a "Knowledge Base System" (KBS) that strictly separates declarative logic from procedural execution. The system's architecture relies on several key components:

  • FO(·) Logic: This extends standard predicate logic with types, partial functions, and inductive definitions. Inductive definitions are particularly vital for representing recursive concepts like graph reachability.
  • Model Expansion: Rather than simply checking the truth of a formula, IDP3 performs model expansion, taking a partial interpretation of data and expanding it into a full solution that satisfies all defined constraints.
  • Grounding and Solving: The system automatically transforms high-level logic into Extended Conjunctive Normal Form (ECNF). This low-level format is then processed by an underlying SAT-based solver, MiniSAT(ID).
  • Procedural Integration: IDP3 utilizes Lua scripting to manage the high-level workflow. This allows for tasks such as iterative data loading, multiple solver calls, or the implementation of greedy approximation strategies for problems too large for exact solving.

Application Domains and Methodology

The efficacy of IDP3 was tested across three distinct research areas:

  1. Stemmatology (Philology): The study of manuscript traditions. The authors used five datasets (including Notre Besoin and Heinrichi) to reconstruct the "family trees" of historical texts based on shared variants.
  2. Phylogenetic Networks (Biology): The system was tasked with finding the "minimum common supergraph" for sets of phylogenetic trees, using both exact and greedy approaches on datasets with up to 75 nodes.
  3. DFA Learning (Computer Science): Using 100 problems from the 2010 Stamina competition, the authors modeled the search for the smallest automaton consistent with specific sets of accepted and rejected strings.

Key Results and Insights

Performance and Scalability

In the field of stemmatology, IDP3 processed the Heinrichi dataset—containing over 1,000 features—in just 12 seconds. This outperformed a specialized 370-line Perl script, which took 25 seconds and was later found to be incomplete. For DFA learning, the IDP3 model solved 59 out of 100 "tough" problems. While a hand-tuned competition winner (DFASAT) solved 69, the IDP3 model was significantly shorter, more readable, and easier to modify for different optimization criteria.

The "Modeling Matters" Effect

The research highlights that the way logic is written significantly impacts performance. For instance, optimizing a "reaches(x, y)" relation into a unary "reachable(x)" predicate drastically reduced the grounding size, leading to substantial speedups. This emphasizes that while the system is declarative, some intuition regarding logical efficiency remains beneficial.

Logic as a Debugging Tool

One of the most striking findings occurred during the DFA learning experiments. By comparing their high-level IDP3 model against a state-of-the-art, hand-crafted SAT encoding, the authors uncovered subtle bugs in the competition-winning code. The clarity of the FO(·) model made it easier to verify correctness compared to the "ingeniously tuned" but opaque procedural code.

Discussion and Limitations

Despite its successes, the IDP3 approach faces certain bottlenecks:

  • Grounding: For extremely large instances, the translation from high-level logic to SAT clauses can consume excessive memory. Future work on "lazy grounding" aims to mitigate this.
  • Symmetry Breaking: The solver can waste time exploring redundant permutations of the search space. While IDP3 includes some symmetry-breaking features, more automated detection is required.
  • Data Structures: Unlike logic programming languages like Prolog, IDP3 currently lacks native support for rich, nested data structures like lists.

Conclusion

The IDP3 system demonstrates that predicate logic is a viable and powerful modeling language for complex data mining and machine learning tasks. By providing a high-level interface that does not sacrifice significant performance, it allows researchers to focus on the conceptual rules of their domain. The ability to combine declarative constraints with procedural Lua scripts makes it a versatile tool for both exact solving and heuristic search in large-scale applications.

Summary updated

Abstract

This paper provides a gentle introduction to problem-solving with the IDP3 system. The core of IDP3 is a finite model generator that supports first-order logic enriched with types, inductive definitions, aggregates and partial functions. It offers its users a modeling language that is a slight extension of predicate logic and allows them to solve a wide range of search problems. Apart from a small introductory example, applications are selected from problems that arose within machine learning and data mining research. These research areas have recently shown a strong interest in declarative modeling and constraint-solving as opposed to algorithmic approaches. The paper illustrates that the IDP3 system can be a valuable tool for researchers with such an interest. The first problem is in the domain of stemmatology, a domain of philology concerned with the relationship between surviving variant versions of text. The second problem is about a somewhat related problem within biology where phylogenetic trees are used to represent the evolution of species. The third and final problem concerns the classical problem of learning a minimal automaton consistent with a given set of strings. For this last problem, we show that the performance of our solution comes very close to that of the state-of-the art solution. For each of these applications, we analyze the problem, illustrate the development of a logic-based model and explore how alternatives can affect the performance.
BibTeX
@article{bruynooghe2015predicate,
  author = {Maurice Bruynooghe and Hendrik Blockeel and Bart Bogaerts and Broes De Cat and Stef De Pooter and Joachim Jansen and Anthony Labarre and Jan Ramon and Marc Denecker and Sicco Verwer},
  title = {{Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3}},
  journal = {Theory Pract. Log. Program.},
  year = {2015},
  doi = {10.1017/s147106841400009x},
}
Figure