Coq:为什么重写定理中的引理会产生两个子目标？ - 腾讯云开发者社区

虽然都以有类型λ演算为理论基础（Agda是UTT，Coq是归纳构造演算），但是表现在证明上，两者就有很大的不同了。在Agda中，命题的证明就是给出一个类型的一个项。...可以说，在Agda中证明一个命题能充分体现Curry-Horwad同构的实质。进一步的说，Agda根本没有强调“证明”，而你的每一次证明，其实都是C-H同构的体现。而Coq却完全相反。...而针对这个目标，Agda提供了比如Case和Refine之类的工具来根据类型生成目标代码，这一点是十分方便的。但是缺点也显而易见，就是证明过程并不按照一般的证明顺序进行的，毕竟只是项的构造。...另外，Agda的证明代码也需要一定理解才能获得大致的证明思路。相比之下，Coq的证明过程更加近似于人工证明。...Coq的证明中自然而然的带入的证明的“顺序”，所以在一定程度上，阅读Coq的代码更容易得到证明的大致思路。

1.4K1 0

谷歌等用LLM自动证明定理拿顶会杰出论文，上下文越全证得越好

例如CompCert，使用Coq交互式定理证明器验证的C编译器，是无处不在的GCC和LLVM等使用的唯一编译器。...比如Coq和Isabelle等证明助手，通过训练一个模型来一次预测一个证明步骤，并使用模型搜索可能的证明空间。...如上图所示，仅使用定理语句作为证明生成模型的输入，然后从模型中抽取证明尝试，并使用Isabelle执行证明检查。...当人工编写证明的时候，会区分两种情况：集合是有限的或者不是有限的：所以，对于模型来说，输入是定理陈述，而目标输出是这个人工编写的证明。...Isabelle返回以下错误消息：为了从这些字符串中派生出一个证明修复训练示例，这里将定理陈述、失败的证明尝试和错误消息连接起来作为输入，并使用正确的人工编写的证明作为目标。

1171 0

您找到你想要的搜索结果了吗？

是的

没有找到

数学证明和计算机程序等同的深层链接

简单地说，柯里-霍华德对应假设计算机科学中的两个概念（类型和程序）分别等价于逻辑概念：命题和证明。这种对应的一个后果是，编程——通常被视为个人的手艺——被提升到数学的理想化水平。...编写一个程序不仅仅是“编码”，它变成了证明一个定理的行为。这形式化了编程行为，并提供了从数学上推理程序正确性的方法。该对应以独立发现它的两位研究人员命名。...1934年，数学家和逻辑学家哈斯克尔·柯里（Haskell Curry）注意到数学中的函数（function）与逻辑中的蕴涵关系（implication relationship）之间的相似性，它采用两个命题之间的...当计算机程序运行时，每一行都经过“求值”以产生单个输出。...这些是有助于构建形式证明的软件工具，例如Coq和Lean。在Coq中，证明的每一步本质上都是一个程序，证明的有效性通过类型检查算法进行检查。

2021 0

2013年图灵奖得主Leslie Lamport：如何写出数学上完美的算法

两个观察者可能对事件的顺序有异议，但如果一个事件导致了另一个事件，这就消除了模糊性。而发送或接收一个信息可以在多个过程中建立因果关系。...这就是模型检查的作用吗？模型检查是一种详尽地测试系统的小模型的所有执行情况的方法。它只是显示模型的正确性，而不是算法的正确性。当模型检查测试正确性时，编码只是产生代码。它并不测试任何东西。...听起来，模型检查与另一种程序验证方法有关：使用Coq等工具进行交互式定理证明。它们有什么不同？ Coq的设计是为了做真正的数学，并且能够捕捉数学家所做的推理。...由Lamport在过去几十年中开发的规范语言TLA+，让工程人员可以以精确的数学方式描述程序要实现的目标程序员花在写代码上的时间比花在思考上的时间多，这是否是一种偏见？...是的，在编写代码之前思考和写作的重要性需要在本科计算机科学课程中教授，而现在却没有。而原因是，教编程的人和教程序验证的人之间没有沟通。从我所看到的情况来看，错误在于这个鸿沟的两边。

8693 0

2013年图灵奖得主Leslie Lamport：如何写出数学上完美的算法

4792 0

2013年图灵奖得主 Leslie Lamport 专访：程序员需要更多的数学知识

Leslie Lamport 彻底改变了现代计算机之间的对话方式。2013年，他被授予图灵奖，以表彰他在分布式系统方面的工作。在分布式系统中，不同网络上的多个组件协调一致，以实现一个共同的目标。...两个观察者在事件顺序上可能存在分歧，但如果是一个事件导致另一个事件的发生，那么就能消除模糊性。发送或接收消息可以在多个进程之间建立因果关系。...为什么会这样？...但对于任何规模的系统和算法的使用，证明都可以验证其正确性。 Quanta：听起来，模型检测与另一种程序验证方法有关：使用Coq等工具进行交互式定理证明。它们有何不同？...Lamport：Coq的目的是解决真正的数学问题，它能够捕捉数学家所做的推理。例如， Georges Gonthier用它来证明了四色定理（four-color theorem）。

6872 0

2013年图灵奖得主 Leslie Lamport 专访：程序员需要更多的数学知识

6133 0

理论|来聊聊最近很火的WGAN

在实践中人们发现，当D训练得更精确，G的更新会变得越差，训练变得异常地不稳定。为什么会产生这些这样的问题？之前一直没有人给出解答。...横截相交和完美对齐的严谨定义将在下期推送中给出，在这里形象地说明一下：横截相交（intersect transversally）：对两个子流形，在任意一个交点处，两者的切平面能够生成整个空间，则称两个子流形横截相交...完美对齐（perfectly align）: 如果两个子流形有交集，并且在某个交点处，它们不是横截相交的。...定理3.1和推论3.1表明，ε的分布会影响我们对距离的选择。 Theorem3.2: 设Pr和Pg分别是支撑集落在M和P中的两个分布 ? 则G的梯度具有以下形式 ?...定理6证明了若D和G的学习能力足够强的话（因此目标函数能够被最大化），WGAN是有解的。WGAN的算法流程如下： ?

2.2K2 0

策略梯度入门（上）

强化学习是机器学习中的一个子领域，其目标是为「代理」（agent）找到一个最优的行为策略以获得最大的奖励。...1.3 策略梯度定理及证明实际上计算梯度并不简单。梯度不仅依赖于动作的选择（由直接决定），还依赖于由选择的动作而产生的状态的平稳分布（由间接决定）。...目标函数的梯度可以进一步表示为：由于其中指，对应的状态和动作分布均遵循策略生成，也就是所谓的「同轨策略」（on-policy）。策略梯度定理是各种策略梯度算法的理论基石。...一个常用的基准值是状态-值函数，那么在实际的梯度更新中我们使用的就是优势函数。关于为什么基准值能够减少方差的解释可以参考 CS229 学习笔记第十七章以及这篇博客[4]。...2.2 Actor-Critic 策略梯度和值函数是策略梯度中的两个主要组件。

1.2K4 2

机器学习包含哪些学习思想？

我们有两种假设: ? : 我们是从 ? 中抽取的，即从偶数中抽取 ? : 我们是从 ? 中抽取的根据上文给出的公式进行计算，我们发现 ? 远大于 ? ，即我们相信 ? 从 ?...中产生的可能更大，但是 ? 似乎也能解释我们的结果。这个时候我们就应选择概率更高的那个。从奥卡姆剃刀角度思考的话， ? 在0~99中只有5个满足要求的元素，而 ? 却有50个满足要求的元素。...相信敏锐的读者已经发现，集成学习似乎和前面提到的奥卡姆剃刀定理相违背。明明一个分类模型就够麻烦了，现在为什么要做更多？...代表算法：随机森林每个子学习器都是强分类器，融合过程中可能：思路2（强中取强）：选择最强的那一个。...如果我们的目标是参数估计，那么有一个无法回避的问题...参数到底存不存在？换句话说，茫茫宇宙中是否到处都是不确定性(Uncertainty)，而因此并不存在真实的参数，而一切都是处于运动当中的。

6883 0

陶哲轩上手Copilot：不可思议，它能从定理名字猜出我想要的方向

定理证明是代码生成的一种特殊形式，在评估上非常严格，没有让模型产生幻觉的空间。...陶哲轩表示，Github copilot 能够正确预测各种例行验证的多行代码，并从定理的名字等线索中推断出他想要的方向，这种能力是「不可思议」的。...Lean 的「重写」策略是不可或缺的，它可以通过有针对性的替换来修改冗长的假设或目标，无需完整地键入表达式就能对其进行操作。...「在用 LaTeX 撰写证明时，我经常粗略地模拟这种方法，将我要处理的冗长表达式从一行剪切粘贴到下一行，然后进行有针对性的编辑，但这有时会导致错字在文档中多行传播，因此能以自动和可验证的方式进行重写是件好事...陶哲轩表示后续的论证虽然会很耗时，但并不是特别困难。但目前的工具仍有一些局限性，例如，重写涉及绑定变量（如数列中的求和变量）的表达式并不总是很容易完成。

1742 0

redis为什么需要持久化？

为什么需要持久化？ redis的数据都是存放到内存中的，如果突然宕机，数据就会全部丢失，因此必须有一种机制来保证redis在内存中的数据不会丢失，这种机制就叫redis持久化机制。...持久化的方式 redis持久化分为两种，第一种是快照，第二种是AOF日志，快照是一次全量备份，AOF是连续的增量备份 ?...fork(多进程) redis在持久化的时候会调用glibc的函数fork产生一个子进程，快照持久化交给子进程来处理，不影响父进程继续处理客户端的请求，子进程持久化的时候，不会修改现有内存的数据结构，他只会对数据进行遍历读取...AOF重写 redis提供了bgrewriteaof指令用于对AOF日志进行瘦身，其原理就是开辟一个子进程对内存进行遍历，转换成一系列redis操作指令，序列化到一个新的aof日志中。...redis4.0引入了一个新的持久化选项——混合持久化，先读取快照进行恢复，然后读取增量的AOF日志，这里的AOF是继上一次产生快照后，产生的增量日志，不再是以前的全量日志。 ? ?

1.4K2 0

高等数学——微分中值定理

但是提出中值定理的几个数学家倒是如雷贯耳，前段时间抽空研究了一下，发现很有意思，完全没有想象中那么枯燥。...罗尔中值定理罗尔中值定理是在费马引理的基础上做了一点引申，我们还是看上图，在上图当中A和B两点的函数值相等。...拉格朗日中值定理罗尔定理简单易懂，但是有一个小问题就是限制条件太死，函数上不一定能找到两个点相等。针对这个问题，大佬拉格朗日对这个公式进行了拓展。...我们在证明罗尔定理的时候用到了费马引理，那么证明拉格朗日中值定理的时候能不能用上罗尔定理呢？如果能用上当然很好，但是直接用是不行的，我们不能保证函数在a和b两点处值相等。...如果我们整理一下上面几个中值定理，会发现这是一个俄罗斯套娃，层层嵌套，但是它们研究的都是同样一件事情。这些定理会在以后微积分的章节派上用场，现在我们先有个印象即可。

8631 0

DeepMind大神Silver联手Sutton论证无限猴子原理：用强化学习就能搞定通用人工智能！

例如蝙蝠的回声定位或黑猩猩的工具使用等。这些能力的产生也都将服务于一个单一的目标，也就是在动物所处的环境中获得最大化的回报。...例如，一只想要「活着」的松鼠，那么饥饿最小化这个奖励机制就可以认为是「活着」的一个子目标。于是，这只松鼠就产生了感知和运动的技能，从而帮助它在有食物的时候找到并收集坚果。...在执行操作的过程中，代理会依据操作过程对于目标的影响程度来决定奖励或者惩罚，同时改变自己和环境状态。许多的强化学习产生的问题在于代理对于环境缺乏初始的认知，从而导致开始时的随机操作。...通用人工智能指的是通用人工智能是一些人工智能研究的主要目标，也是科幻小说和未来研究中的共同话题。...根据达尔文的自然选择理论，生物进化大概需要4亿年的时间，但是至今也没人能解释清楚6亿年前寒武纪地球上为什么会突然多了那么多新物种。或许在自然界中的进化，也远非我们想象中的那么简单。

2783 0

【剑指Offer】机器学习面试题（1）

准确率指的是：正样本被预测为正所占所有预测为正样本数的比例 - 预测正预测负真实正 TP FN 真实负 FP TN ? Q6: 什么是贝叶斯定理，它是如何使用在机器学习中的？...贝叶斯定理会根据一件事发生的先验知识告诉你它后验概率。数学上，它表示为：一个条件样本发生的真正率占真正率和假正率之和的比例，即： ?...某人检验结果为阳性，求此人患病的概率。 ? 贝叶斯定理使一些机器学习算法如：朴素贝叶斯等的理论基础。 Q7：为什么我们要称“朴素“贝叶斯？...深度学习是机器学习的一个子领域，它关心的是参照神经学科的理论构建神经网络，使用反向传播对大量未标注或半结构化的数据进行建模。...Q23的一个子问题。首先你需要知道LR的目标是什么？（分类或预测）然后通过举一些例子来说明。 Q25：什么是核技巧，有什么用处？

6092 0

GPT自动证明数学题，结果被专业数据库收录，数学家点赞

在大致了解 OpenAI 这项新研究之后，我们来看这个延续了 GPT 系列之名的方法到底是如何诞生的。为什么用自动定理证明？...为什么使用自动定理证明呢？自动定理证明适合探索常规的推理，尤其是语言模型的推理能力，原因如下：推理方式更广泛：定理证明可能需要通用和灵活推理，因此定理证明的进步也让推理有了更广泛的发展。...为此，研究者制定了如下数据格式：数据集中每个 JSON 行都有一个这样的目标。研究者在每段上下文（不分块）中仅训练一个句子，并通过设置损失权重 w_loss = 0 来遮蔽上下文的其余内容。...为了获得值函数，研究者只需要训练模型，来预测证明搜索过程中产生的目标能否通过生成以下形式的新数据集得到解决：实验该研究所用的基线方法如下表 5 所示：下表 6 展示了不同模型大小对性能的影响：...印第安纳大学数学博士 Junyan Xu 则对 tactic 的定义提出疑问：论文一作 Stanislas Polu 进行了回复：这确实不是真正的「策略」，而更像是一种内核重写规则。

5621 0

机器学习中的“哲学”

我们有两种假设: h1: 我们是从{0,2,4,6,8,...,98}中抽取的，即从偶数中抽取 h2: 我们是从{2n}中抽取的根据上文给出的公式进行计算，我们发现Pr(D|h1)远大于Pr(D|h2...)，即我们相信D={2,4,8,16,32}从h1:{2n}中产生的可能更大，但是h2:{0,2,4,6,8,...,98}似乎也能解释我们的结果。...集成学习的思想无处不在，比较著名的有随机森林等。从某种意义上说，神经网络也是一种集成学习，有兴趣小伙伴可以想想为什么… 相信敏锐的读者已经发现，集成学习似乎和前面提到的奥卡姆剃刀定理相违背。...明明一个分类模型就够麻烦了，现在为什么要做更多？这其实说到了一个很重要观点，就是奥卡姆剃刀定理并非不可辩驳的真理，而只是一种选择方法。从事科学研究，切勿相信有普遍真理。...如果我们的目标是参数估计，那么有一个无法回避的问题…参数到底存不存在？换句话说，茫茫宇宙中是否到处都是不确定性(Uncertainty)。频率学派相信参数是客观存在的，虽然未知，但不会改变。

1.1K9 0

详解 CAP 定理 Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性）

详解 CAP 定理 Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性） CAP原则又称CAP定理，指的是在一个分布式系统中，Consistency...这个结论就叫做 CAP 定理。 Partition tolerance 先看 Partition tolerance，中文叫做”分区容错”。大多数分布式系统都分布在多个子网络。...每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。...Consistency 和 Availability 的矛盾一致性和可用性，为什么不可能同时成立？答案很简单，因为可能通信失败（即出现分区容错）。...如果保证 G2 的可用性，那么势必不能锁定 G2，所以一致性不成立。综上所述，G2 无法同时做到一致性和可用性。系统设计时只能选择一个目标。

8323 0

详解 Diffusion (扩散) 模型

不幸的是，这是不可能的。但扩散模型试图拟合一个模型，其最终目标是逆转这一过程。其基本思想是通过迭代前向扩散过程系统地、缓慢地破坏数据分布中的结构。...通过贝叶斯定理重写KL散度，我们得到：所以我们的变分下界变成：我们现在的目标是将右侧转换为可分析计算的。...让我们首先将日志重写为产品：使用对数乘积法则，我们可以重写右侧：取出求和的第一项，得到以下结果：使用贝叶斯定理重写 q(xₜ|xₜ₋₁) 并在 t = 0 时对输入图像进行调节：替代...取 T 等于任何数字，您会发现大部分项都被抵消了，您将得到以下结果：替换使用商规则，我们可以重写最后两项：您可以看到第一项和最后一项相互抵消。...这就是为什么它被称为潜在扩散；我们不是在像素中而是在潜在空间中实现扩散过程。下图应该足以概括 LDM：总结扩散模型的工作原理是迭代地向图像添加噪声，然后训练神经网络来学习噪声并恢复图像。

9422 0

详解 CAP 定理 Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性）…

CAP原则又称CAP定理，指的是在一个分布式系统中，Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），三者不可得兼。...这个结论就叫做 CAP 定理。 Partition tolerance 先看 Partition tolerance，中文叫做”分区容错”。大多数分布式系统都分布在多个子网络。...每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。...Consistency 和 Availability 的矛盾一致性和可用性，为什么不可能同时成立？答案很简单，因为可能通信失败（即出现分区容错）。...如果保证 G2 的可用性，那么势必不能锁定 G2，所以一致性不成立。综上所述，G2 无法同时做到一致性和可用性。系统设计时只能选择一个目标。

3623 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

用了一段时间Agda的感想

谷歌等用LLM自动证明定理拿顶会杰出论文，上下文越全证得越好

数学证明和计算机程序等同的深层链接

2013年图灵奖得主Leslie Lamport：如何写出数学上完美的算法

2013年图灵奖得主Leslie Lamport：如何写出数学上完美的算法

2013年图灵奖得主 Leslie Lamport 专访：程序员需要更多的数学知识

2013年图灵奖得主 Leslie Lamport 专访：程序员需要更多的数学知识

理论|来聊聊最近很火的WGAN

策略梯度入门（上）

机器学习包含哪些学习思想？

陶哲轩上手Copilot：不可思议，它能从定理名字猜出我想要的方向

redis为什么需要持久化？

高等数学——微分中值定理

DeepMind大神Silver联手Sutton论证无限猴子原理：用强化学习就能搞定通用人工智能！

【剑指Offer】机器学习面试题（1）

GPT自动证明数学题，结果被专业数据库收录，数学家点赞

机器学习中的“哲学”

详解 CAP 定理 Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性）

详解 Diffusion (扩散) 模型

详解 CAP 定理 Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性）…

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐