Solving olympiad geometry without human demonstrations

被引:88
作者
Trinh, Trieu H. [1 ,2 ]
Wu, Yuhuai [1 ]
Le, Quoc V. [1 ]
He, He [2 ]
Luong, Thang [1 ]
机构
[1] Google Deepmind, Mountain View, CA 94043 USA
[2] NYU, Comp Sci Dept, New York, NY 10012 USA
关键词
THEOREM; GENERATION;
D O I
10.1038/s41586-023-06747-5
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
Proving mathematical theorems at the olympiad level represents a notable milestone in human-level automated reasoning1-4, owing to their reputed difficulty among the world's best talents in pre-university mathematics. Current machine-learning approaches, however, are not applicable to most mathematical domains owing to the high cost of translating human proofs into machine-verifiable format. The problem is even worse for geometry because of its unique translation challenges1,5, resulting in severe scarcity of training data. We propose AlphaGeometry, a theorem prover for Euclidean plane geometry that sidesteps the need for human demonstrations by synthesizing millions of theorems and proofs across different levels of complexity. AlphaGeometry is a neuro-symbolic system that uses a neural language model, trained from scratch on our large-scale synthetic data, to guide a symbolic deduction engine through infinite branching points in challenging problems. On a test set of 30 latest olympiad-level problems, AlphaGeometry solves 25, outperforming the previous best method that only solves ten problems and approaching the performance of an average International Mathematical Olympiad (IMO) gold medallist. Notably, AlphaGeometry produces human-readable proofs, solves all geometry problems in the IMO 2000 and 2015 under human expert evaluation and discovers a generalized version of a translated IMO theorem in 2004. A new neuro-symbolic theorem prover for Euclidean plane geometry trained from scratch on millions of synthesized theorems and proofs outperforms the previous best method and reaches the performance of an olympiad gold medallist.
引用
收藏
页码:476 / 482
页数:21
相关论文
共 17 条
[1]  
Brown TB, 2020, ADV NEUR IN, V33
[2]   Automated generation of readable proofs with geometric invariants .2. Theorem proving with full-angles [J].
Chou, SC ;
Gao, XS ;
Zhang, JZ .
JOURNAL OF AUTOMATED REASONING, 1996, 17 (03) :349-370
[3]   A deductive database approach to automated geometry theorem proving and discovering [J].
Chou, SC ;
Gao, XS ;
Zhang, JZ .
JOURNAL OF AUTOMATED REASONING, 2000, 25 (03) :219-246
[4]  
Coelho H., 1986, Journal of Automated Reasoning, V2, P329, DOI 10.1007/BF00248249
[5]   A COMPUTING PROCEDURE FOR QUANTIFICATION THEORY [J].
DAVIS, M ;
PUTNAM, H .
JOURNAL OF THE ACM, 1960, 7 (03) :201-215
[7]  
Lample Guillaume, 2022, ADV NEURAL INFORM PR
[8]  
Lewkowycz A., 2022, Advances in Neural Information Processing Systems, V35, P3843
[9]   GRAMY: A geometry theorem prover capable of construction [J].
Matsuda, N ;
Vanlehn, K .
JOURNAL OF AUTOMATED REASONING, 2004, 32 (01) :3-33
[10]   PLANE GEOMETRY THEOREM PROVING USING FORWARD CHAINING [J].
NEVINS, AJ .
ARTIFICIAL INTELLIGENCE, 1975, 6 (01) :1-23