A Feature-Based Learning Method for Theorem Proving

AAAI 1998

TL;DR

This paper introduces a novel feature-based machine learning approach to improve automated theorem provers (ATPs). By learning "search-guiding heuristics" from solved problems using feature-value vectors, the system can significantly speed up proofs and even solve problems previously out of reach for conventional ATPs.

What Problem Does This Paper Address?

Automated theorem proving is fundamentally a search problem in vast, often infinite, search spaces. While ATPs have made significant progress, they still struggle with "challenging" theorems, largely because they lack the ability to learn from past successes. Unlike human mathematicians, ATPs typically treat each problem as a novice. Existing machine learning approaches for theorem proving, particularly those based on analogical proof transformation, face difficulties due to the extreme sensitivity of proofs to minor problem variations. This paper aims to bridge this gap by enabling ATPs to learn effective search strategies from solved problems.

Methods

The core of the proposed method is a feature-based learning approach to adapt existing search-guiding heuristics. When an ATP successfully proves a problem, the facts used in the proof (positive facts, P) and those that were not (negative facts, N) are identified. The learning algorithm, called "Compute Feature Coefficients" (CFC), then generates a new heuristic, HAS.

HAS is created by adding a "penalty weight" to the original heuristic's weight for each fact. This penalty is calculated based on a feature-value vector representation of each fact. Features capture syntactic properties of facts (e.g., number of variables). The penalty is designed such that facts that were crucial for the original proof (in P) receive no penalty, while other facts (in N) receive a penalty that increases with their deviation from the "ideal" feature values observed in P. This encourages the adapted heuristic to prioritize facts similar to those used in successful proofs. The CFC algorithm iteratively adjusts coefficients for these features to balance specialization (to the source problem) with flexibility (for future, similar problems).

Datasets

The experiments were conducted using the TPTP (Thousands of Problems for Theorem Provers) library, specifically version 1.2.1. The authors selected related problems from the LCL (logic calculi) domain for the CODE prover and the ROB (Robbins algebra) domain for the DISCOUNT prover. The TPTP is described as a large, publicly accessible collection of standardized problems, serving as a platform for evaluation and comparison.

Key Insights and Ideas

  • Feature-based abstraction is key: Representing facts by feature-value vectors allows for a level of abstraction that makes learning more robust to minor problem variations, a common pitfall in theorem proving.
  • "Uncoupled" features promote flexibility: The penalty calculation method treats features independently, preventing over-specialization to a single source proof and enhancing the adapted heuristic's applicability to a wider range of target problems.
  • Balancing specialization and generalization: The CFC algorithm's iterative adjustment of feature coefficients is crucial for finding a sweet spot between learning from a specific proof and retaining the ability to solve related, but not identical, problems.
  • Learning is more than just speed-up: The most significant contribution is not just faster proofs, but the ability to solve problems that were previously intractable for conventional heuristics.

Key Results

Experiments with the CODE and DISCOUNT ATPs demonstrated significant improvements:

  • Speed-ups: For CODE, run-times were reduced by factors of 3-7 on problems where the adapted heuristic (HAS) was successful. For DISCOUNT, similar speed-ups were observed.
  • Solving previously intractable problems: In several cases, HAS was able to find proofs within a reasonable time limit where conventional heuristics failed entirely (indicated by '-' in the tables, meaning failure to find a proof before a one-hour timeout).
  • Learning phase efficiency: The learning phase (running the CFC algorithm) was negligible, taking less than a second, making the approach practical.

Limitations and Future Work

  • Feature selection is critical: The effectiveness of the approach heavily relies on the quality and distinctiveness of the chosen features. The authors acknowledge that feature engineering is a general challenge in feature-based AI methods.
  • Instance-based learning and EBL connections: The authors note similarities to instance-based learning and explanation-based learning (EBL), suggesting these as interesting areas for further study.
  • Automating source problem selection: Currently, selecting appropriate source problems for learning is done manually. The authors mention that recent research has shown promising results in automating this selection process, which would further enhance the practicality of their approach.
  • Bootstrapping for more complex problems: The paper suggests that a "bootstrapping" approach, where learned heuristics are used to solve progressively more difficult problems, could be a fruitful direction.

Summary updated

BibTeX
@inproceedings{1998feature,
  title = {{A Feature-Based Learning Method for Theorem Proving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}

Loading related content...

Figure