Introduction
Automated Theorem Provers (ATPs) are powerful tools for logical deduction, yet they frequently encounter a "needle in a haystack" problem when applied to large-scale mathematical libraries. In repositories like the Mizar Mathematical Library (MML), which contains over 100,000 formulas, the sheer volume of available axioms can overwhelm an ATP's search space. This paper presents a method to enhance ATP performance by utilizing "semantic features" to filter relevant premises more effectively.
The Premise Selection Pipeline
To navigate vast libraries, researchers employ a "premise selection" pre-filter. This machine learning component identifies the most likely relevant axioms before the ATP begins its search. Traditionally, these filters relied on shallow symbolic features, such as shared sub-terms or symbols. However, these methods often miss deeper logical connections.
The authors propose a shift toward semantic features that capture how formulas relate within a logical space. This involves identifying whether a formula is a generalization or an instantiation of another, as well as determining if two formulas are unifiable.
Methods: Semantic Feature Extraction
The core innovation lies in the efficient extraction of these complex features using specialized data structures:
- Matching and Generalization: The system recognizes hierarchical relationships. For instance, a general rule like $X + Y = Y + X$ is identified as a match for a specific instance like $1 + 2 = 2 + 1$.
- Unification: By determining if two formulas can be made identical through variable substitution, the system identifies axioms likely to interact during a proof.
- Deductive Data Structures: To handle hundreds of thousands of formulas in real-time, the authors repurposed Discrimination Nets and Substitution Trees. These structures allow for millisecond-level retrieval of generalizations and unifiable terms across the entire library.
The Instantiation Lattice
Mathematical statements do not exist in isolation; they form a hierarchy. A statement regarding integers is often a specific case of a broader statement about groups. By mapping these "upward" (generalization) and "downward" (instantiation) links, the machine learning model gains a sophisticated "map" of the library.
Key Results
The implementation of these semantic features yielded significant improvements across standard benchmarks like MPTP2078 and the full Mizar library (MML1147):
- Ranking Accuracy: The average predicted rank of necessary premises improved by 22.1% over previous state-of-the-art symbolic methods.
- Proving Success: Using the 'E' prover, the system successfully proved 1,130 theorems—an 8% increase compared to the 1,050 theorems proven using traditional features.
- Scalability: The system processed the full MML1147 library (approx. 146,500 formulas) in under 100 seconds, proving that semantic analysis is practical for large-scale "Big Math" applications.
Conclusion and Future Work
While premise selection remains a high-level approximation of the proof search, this work demonstrates that logical depth can be captured efficiently. Future research aims to integrate these semantic features directly into the internal search processes of ATPs to provide real-time guidance during the exploration of proof trees, potentially moving beyond pre-filtering to internal heuristic guidance.
Summary updated