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