Internal Guidance for Satallax

Michael Färber, Chad E. BrownarXiv 2016 · arXiv

TL;DR

Researchers have developed a new "internal guidance" system for the Satallax theorem prover that uses Naive Bayesian classification to prioritize promising proof steps. By generalizing the classifier using a mathematical structure called a commutative monoid, the system can learn from both successful proof steps (positive examples) and wasted efforts (negative examples), ultimately solving 26% more problems on the Flyspeck dataset.

What Problem Does This Paper Address?

Automated Theorem Provers (ATPs) are like digital mathematicians: they try to find a logical path from a set of axioms to a conclusion. Most ATPs use a "given-clause" algorithm, where they maintain a massive pile of "unprocessed" logical statements. The prover must constantly decide: Which statement should I pick next?

Traditionally, provers use simple heuristics—like picking the shortest statement or the oldest one. However, human mathematicians use experience to "feel" which path is most promising. The challenge is to give ATPs this same sense of intuition. While "premise selection" (choosing which axioms to start with) is a well-studied area of machine learning in ATPs, "internal guidance" (making better choices during the search) is much harder because it happens thousands of times per second and requires extreme efficiency.

Methods

The authors introduce a guidance method based on Naive Bayesian classification, but with a clever mathematical twist.

  1. The Monoid Generalization: Standard classifiers often just count how many times a feature appears in a successful proof. The authors generalize this by representing occurrences as elements of a commutative monoid. This allows them to track not just "this clause was useful" (positive), but also "this clause was processed but didn't help" (negative). By using a monoid of pairs $(p, n)$ for positive and negative counts, they can calculate a "confidence" score for every proposition.
  2. Integration with Satallax: Satallax is a higher-order logic prover that uses a priority queue to manage commands. The authors modified Satallax to inject a "relevance rank" into this queue. If the machine learning model thinks a proposition looks like one that helped in previous proofs, it gets bumped to the front of the line.
  3. Post-processing and Normalization: To help the prover recognize similar logic across different problems, they used techniques like Skolem filtering (removing specific constants) and Inference filtering (focusing only on the original axioms).
  4. Optimization: They used Particle Swarm Optimization (PSO)—an algorithm inspired by the movement of bird flocks—to fine-tune the weights and constants of their ranking formula.

Datasets

The researchers evaluated their method using the Flyspeck project dataset.

  • Content: A simply-typed higher-order logic version of the formal proof of the Kepler conjecture.
  • Scale: 14,185 problems spanning topology, geometry, and integration.
  • Context: On average, each problem includes about 84.3 premises.

Key Insights and Ideas

  • Negative Examples Matter: One of the biggest "aha" moments was finding that negative training examples are crucial. Knowing what not to do is just as important as knowing what to do when navigating a massive search space.
  • Simplicity Wins: Surprisingly, the authors found that using a complex set of "features" (like the symbols present in the current state) actually slowed the prover down too much. They achieved their best results using an empty feature set, meaning the system learned purely based on the "labels" (the normalized clauses themselves) rather than the context they appeared in.
  • Inference Filtering is Key: The most effective version of the system focused its learning on the initial axioms of the problem rather than every intermediate clause generated during the search. This kept the "noise" low and the guidance focused.

Key Results

The impact of internal guidance was significant across multiple testing scenarios:

  • Overall Performance: On the Flyspeck dataset, the guided version of Satallax solved 26% more problems than the standard version within the same time limit.
  • Efficiency: The guided prover could solve roughly the same number of problems in 1 second that the unguided prover could solve in 2 seconds.
  • Scaling: In a longer 30-second timeout experiment, the guided version solved 4,028 problems compared to the baseline's 3,097—a 30% improvement.
  • Post-processing: "Inference filtering" proved to be the most robust technique, yielding 786 "gained" problems (problems solved with guidance that were failed without it).

Limitations and Future Work

While the results are impressive, the authors noted a few areas for improvement:

  • Feature Engineering: The current "state-based" features were too computationally expensive. Finding "cheap" features that characterize the prover's current state without adding lag is a major goal.
  • Learning from Failure: Currently, the system only learns from successful proofs. The authors suggest that in the future, the system could benefit from analyzing failed proof attempts to better understand which paths lead to dead ends.
  • Integration: There is potential to integrate this internal guidance into "hammer" systems (tools that link interactive proof assistants like Isabelle/HOL to automated provers), potentially creating a virtuous cycle of learning and proving.

Summary updated

Abstract

We propose a new internal guidance method for automated theorem provers based on the given-clause algorithm. Our method influences the choice of unprocessed clauses using positive and negative examples from previous proofs. To this end, we present an efficient scheme for Naive Bayesian classification by generalising label occurrences to types with monoid structure. This makes it possible to extend existing fast classifiers, which consider only positive examples, with negative ones. We implement the method in the higher-order logic prover Satallax, where we modify the delay with which propositions are processed. We evaluated our method on a simply-typed higher-order logic version of the Flyspeck project, where it solves 26% more problems than Satallax without internal guidance.
BibTeX
@misc{farber2016internal,
  author = {Michael Färber and Chad E. Brown},
  title = {{Internal Guidance for Satallax}},
  year = {2016},
  eprint = {1605.09293},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.09293},
}

Loading related content...

Figure