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

This paper introduces the IDP3 system, a finite model generator based on an extension of First-Order Logic ($FO(\cdot)$), as a powerful tool for solving complex search problems in machine learning (ML) and data mining (DM). By enriching standard logic with types, inductive definitions, aggregates, and partial functions, IDP3 allows researchers to replace thousands of lines of procedural code with concise, declarative models. We demonstrate the system's efficacy across three distinct domains: stemmatology, phylogenetic tree construction, and the learning of minimal deterministic finite automata (DFA). Our results show that IDP3-based models not only simplify the development process but also achieve performance levels competitive with state-of-the-art specialized solvers.

Introduction

In the fields of machine learning and data mining, researchers frequently encounter NP-hard search problems, such as finding the most likely evolutionary tree or the smallest automaton consistent with a dataset. Traditionally, these problems are solved using custom procedural algorithms written in languages like C++ or Perl. While effective, these "black-box" approaches are often difficult to implement, prone to bugs, and resistant to modification when problem constraints change.

This paper advocates for a declarative paradigm using the IDP3 system. Instead of specifying how to find a solution, the researcher describes what a valid solution looks like using a logic-based modeling language. We explore whether such a general-purpose system can handle the scale and complexity of real-world research tasks without sacrificing performance.

The IDP3 System and $FO(\cdot)$

IDP3 is a Knowledge Base System built on $FO(\cdot)$, an extension of First-Order Logic. To bridge the gap between pure logic and practical problem-solving, $FO(\cdot)$ incorporates several key features:

  • Types and Partial Functions: These improve model readability and significantly reduce the search space by constraining the domain of variables.
  • Inductive Definitions: This allows for the natural expression of recursive concepts, such as reachability in a graph, which are cumbersome in standard First-Order Logic.
  • Aggregates: These enable constraints on sets, such as counting or summing (e.g., limiting the number of incoming edges to a node).
  • Procedural Integration: IDP3 uses the Lua scripting language to manage complex workflows, such as iterating over multiple datasets or sequencing inference tasks.

Solving in IDP3 occurs via model expansion: the user provides a vocabulary (symbols), a theory (logical constraints), and a partial structure (the data). The solver then identifies a complete structure that satisfies all constraints.

Domain Applications

1. Stemmatology

Stemmatology studies the relationships between surviving variant versions of ancient texts. Using five datasets (including the 48-manuscript Heinrichi set), we modeled the search for a "stemma" (a directed acyclic graph representing manuscript descent). The IDP3 model processed the Heinrichi dataset in 12 seconds, outperforming a specialized 370-line Perl script that required 25 seconds.

2. Phylogenetic Trees

In biology, phylogenetic trees represent the evolution of species. We addressed the problem of finding a minimum common supergraph for a set of trees. By optimizing the logical definition of an "arc" to avoid redundant variables, we reduced the solving time from 144 seconds to just 8 seconds, demonstrating that high-level modeling choices have a profound impact on performance.

3. DFA Learning

Learning the smallest Deterministic Finite Automaton (DFA) consistent with a set of strings is a classic challenge. We tested IDP3 against 100 "tough" problems from the 2010 Stamina competition. IDP3 solved 59 out of 100 problems. While the specialized competition winner (DFASAT) solved 69, the IDP3 model was significantly shorter and easier to verify. Notably, during development, the clarity of the IDP3 model helped identify subtle bugs in a hand-tuned SAT encoding used by experts.

Key Insights: The Importance of Modeling

A central finding of this research is that the way a problem is modeled in logic drastically affects the "grounding" size—the process of translating logic into propositional clauses for the SAT solver.

For instance, defining reachability between all pairs of nodes ($n^2$ atoms) can lead to an $n^3$ grounding explosion. By switching to a unary reachable predicate (is node X reachable from the start?) or using functions to represent parent-child relationships, we achieved dramatic speedups. This suggests that while declarative modeling is powerful, users must still be mindful of how their logic translates to the underlying solver mechanics.

Conclusion and Future Work

IDP3 proves to be a viable and efficient alternative to custom procedural algorithms for ML and DM research. It offers a "clear box" approach where constraints are explicit and easily modified.

However, challenges remain. The "grounding bottleneck" can consume significant memory for very large instances. Future work will focus on "lazy grounding"—generating only the necessary parts of the search space on the fly—and automatic symmetry breaking to further enhance the solver's efficiency. Despite these hurdles, IDP3 stands as a robust tool for researchers who prioritize flexibility and correctness in complex search tasks.

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 a 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