Efficient Semantic Features for Automated Reasoning over Large Theories

Cezary Kaliszyk, Josef Urban, Jirí VyskocilIJCAI 2015

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.

Overview of the formal proof mining and premise selection workflow, illustrating the transition from corpus analysis to real-time querying.

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:

  1. 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$.
  2. Unification: By determining if two formulas can be made identical through variable substitution, the system identifies axioms likely to interact during a proof.
  3. 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.

A lattice representing the hierarchy of generalizations and instantiations for a given formula, used to map the logical space 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

BibTeX
@inproceedings{kaliszyk2015efficient,
  author = {Cezary Kaliszyk and Josef Urban and Jirí Vyskocil},
  title = {{Efficient Semantic Features for Automated Reasoning over Large Theories}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure