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:
- 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.
- 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.
- 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