Deep Network Guided Proof Search

By Sarah M. Loos, Geoffrey Irving, Christian Szegedy, Cezary Kaliszyk. 2017

169 citations recorded by the source corpus.

Deep learning techniques lie at the heart of several significant AI advances in recent years including object recognition and detection, image captioning, machine translation, speech recognition and synthesis, and playing the game of Go.Automated first-order theorem provers can aid in the formalization and verification of mathematical theorems and play a crucial role in program analysis, theory reasoning, security, interpolation, and system verification.Here we suggest deep learning based guidance in the proof search of the theorem prover E. We train and compare several deep neural network models on the traces of existing ATP proofs of Mizar statements and use them to select processed clauses during proof search. We give experimental evidence that with a hybrid, two-phase approach, deep learning based guidance can significantly reduce the average number of proof search steps while increasing the number of theorems proved.Using a few proof guidance strategies that leverage deep neural networks, we have found first-order proofs of 7.36% of the first-order logic translations of the Mizar Mathematical Library theorems that did not previously have ATP generated proofs. This increases the ratio of statements in the corpus with ATP generated proofs from 56% to 59%.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Natural Language Processing

Citations in the corpus

Generative Language Modeling for Automated Theorem Proving (2020, methodology): “Loos et al. [29] investigated the use of models similar to DeepMath’s for proof guidance and demonstrated a signiﬁcant uplift on the Mizar library.”
DeepCoder: Learning to Write Programs (2016, methodology): “A recent extension (Loos et al., 2017) is similar to our DFS enumeration strategy and uses a neural network to guide the proof search at intermediate steps.”
Deep Learning for Symbolic Mathematics (2019, background): “…investigated the capacity of neural network to deal with mathematical objects, and apart from a small number of exceptions (Zaremba et al., 2014; Loos et al., 2017; Allamanis et al., 2017; Arabshahi et al., 2018b), the majority of these works focus on arithmetic tasks like integer addition and…”
Learning Continuous Semantic Representations of Symbolic Expressions (2016, background): “However, apart from some notable exceptions (Alemi et al., 2016; Loos et al., 2017; Zaremba et al., 2014), this area has received relatively little attention in machine learning.”
Formal Mathematics Statement Curriculum Learning (2022, background): “…and lem-mas but very few exercises), we hypothesized that if the difﬁculty of this set of statements was made varied enough, expert iteration could potentially leverage it to effectively shift our models’ distribution closer to miniF2F ’s, and in turn, improve their eventual performance on it.”
Autoformalization with Large Language Models (2022, background): “The revolution of deep learning then kicked off a new wave of interest in the topic starting with DeepMath [1, 33].”
Improving Graph Neural Network Representations of Logical Formulae with Subgraph Pooling (2019, background): “Deep learning approaches to proof guidance include [12], where the authors explored a number of neural architectures in their implementation (including a structure-aware Tree LSTM that encoded the parse trees of logical formulae).”
HOList: An Environment for Machine Learning of Higher-Order Theorem Proving (extended version) (2019, background): “[23] proposed deep neural networks to augment theorem prover E [20] to rank given clauses during proof search.”
A Survey of Deep Learning for Mathematical Reasoning (2022, unknown): “, 2017) TP Classification CNN CNN - 7 A CNN-based theorem prover WaveNetTP (Loos et al., 2017) TP Classification WaveNet WaveNet - 7 A WaveNet-based theorem prover DeepHOL (Bansal et al.”
Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples (2018, methodology): “Work of Loos et al. (2017) represents the closest work with a similar technique but their work is applied to an automated theorem prover, and hence need not care about generalization.”
INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving (2020, background): “Their performances have been improved by machine learning [30, 3, 12, 21, 33, 24, 15].”
Reinforcement Learning of Theorem Proving (2018, methodology): “This has been done in the connection tableau setting [48, 20, 10], saturation style setting [16, 30], and also as direct automation inside interactive theorem provers [12, 14, 49].”
Premise Selection for Theorem Proving by Deep Graph Embedding (2017, background): “[25] were the first to apply deep networks to internal guidance of ATPs.”
GamePad: A Learning Environment for Theorem Proving (2018, methodology): “Recent work (Irving et al., 2016; Loos et al., 2017; Kaliszyk et al., 2017) has shown the promise of applying deep learning techniques in this domain, primarily on tasks useful for automated theorem provers (e.g., premise selection) which operate with little to no human supervision.”