按年被提到
20192019 · 2 次2026
数学、逻辑与理论›AI 数学与定理证明·arXiv:1907.07794 · cs.PL

Generating Correctness Proofs with Neural Networks

用神经网络生成正确性证明
Alex Sanchez-Stern, Yousef Alhessi, Lawrence Saul, Sorin Lerner · 2019

用机器学习的证明搜索系统 Proverbot9001,自动生成 Coq 里的软件正确性证明

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2019-07-19 · 最近 2023-10-27
3不同的人
3活跃月份
3讨论串
49被引(OpenAlex)

基础验证能为软件提供很高的可靠性,但产出基础验证软件需要高水平专家大量手工工作,成本居高不下。论文提出 Proverbot9001,一个使用机器学习在交互式定理证明器中生成软件正确性证明的证明搜索系统。作者在大型实际证明项目 CompCert 已验证 C 编译器的证明义务上进行了演示:结合基于求解器的工具,它能自动证明测试集中 27.5% 的定理陈述;不借助额外求解器时,其证明完成率是此前最先进的 Coq 证明机器学习模型的 4 倍。

HN 为什么提它

评论者引用它作为用神经网络为 Coq 生成证明已经可行的例子,并把它与 CoqGym/ASTactic、Diva 等同类系统并列提及。

方法难度 4 / 5约 45 分钟经得起时间
读之前最好知道
1Coq 与交互式定理证明
2形式化验证与 CompCert
3证明策略(tactic)
4深度学习序列预测

学习路径

读这篇之前,按顺序读书架上的 5 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

这条路径带你从前提选择和深度学习引导证明搜索,到用学习系统在 Coq 等交互式证明器里做证明,最后读 Proverbot9001。

  1. 1
    DeepMath - Deep Sequence Models for Premise SelectionDeepMath:用于前提选择的深度序列模型 · 2016

    最早用深度序列模型为自动定理证明选前提,是学习式证明系统的起点。

    读把前提选择当成分类问题的做法,以及神经网络如何打分;抓问题设定。

  2. 2
    Deep Network Guided Proof Search深度网络引导的证明搜索 · 2017

    把深度网络接进证明搜索,引导子句选择,是学习引导搜索的早期工作。

    读神经网络如何嵌入证明器的搜索循环、用什么特征和训练数据。

  3. 3

    为高阶逻辑做的神经自动定理证明器,展示搜索与策略预测结合的思路。

    读证明树搜索与神经网络策略和相关性预测的结合方式。

  4. 4

    在 Coq 里用学习系统与证明助手交互,与 Proverbot9001 的任务设定最接近。

    读数据集构造、策略预测方式,以及生成证明的评测指标。

  5. 5
    HOList: An Environment for Machine Learning of Higher-Order Theorem ProvingHOList:高阶定理证明的机器学习环境 · 2019

    给出学习式证明的环境与基准,帮助理解与目标论文的对比维度。

    读环境接口、基准和 DeepHOL 基线的设计,对照目标论文的评测方式。

  6. 6
    Generating Correctness Proofs with Neural Networks用神经网络生成正确性证明 · 2019 · 就是这篇

    目标论文:用机器学习证明搜索系统在 Coq 中生成软件正确性证明。

    读策略预测与搜索如何结合,以及在大型证明项目上的评测结果。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用xvilka · 2019-10

“Yes, it's already possible[1] with Coq. There are two strategies for that”

指出用 Coq 已能做到,并引用神经网络生成正确性证明的工作
Can Computers Prove Theorems?原评论 ↗
引用aSanchezStern · 2023-10

“CoqGym/ASTactic ([OTHER_PAPER]), Proverbot9001, and Diva ([LINK]), among others.”

列出 Coq 的神经证明搜索系统,Proverbot9001 是其中之一
Lean4 helped Terence Tao discover a small bug in his recent paper原评论 ↗
被提交为 story · 1 次